（二）
苏 小 红
哈尔滨工业大学计算机科学与技术学院
2
欧氏几何
? 使用 方程 描述有平滑的表面和 规则 形状的物体
分形几何
? 使用 过程 对具有 不规则 几何形态的物体（如自然景物）建模
分形几何
4
1906年，瑞典数学家 H.Von Koch在研究构造
连续而不可微函数时，提出 Koch曲线。
周长无穷，但面积为定值 （ 0）
分形的由来（ 1/4）
构造方法
5构造方法
周长无穷，但面积为定值
分形的由来（ 2/4）
,3)34(,334,3 2 aaa ?? ??......
,43 2aS? 22 5 32,.,,,,,)94(439443,9443 aSSSSS ???????
Von koch snowflake
D=log4/log3=1.2618
……
6
分形的由来（ 3/4）
60年代,现代分形理论的奠基人 B.B.Mandelbrot
将雪花与海岸线、山水、树木等自然景物联系起来
67年，英国, 科学, 杂志,,英国的海岸线有多长？
统计自相似性与分数维数,
什么是分形？
指具有多重自相似的对象
它可以是自然存在的，也可以是人造的。
7
分形的由来（ 4/4）
fractal概念的由来
75年，法文专著, 分形对象,形、机遇与维数
77年，英译本, 分形：形,机遇与维数, (Fractals,Form,
Chance,and Dimension)
82年，增补本，改名为, 大自然的分形几何学,
根据拉丁语 fractus造的词
词根含义：
? 细片的、破碎的、分裂的、分数的
8
分形几何（ 1/8）
分形物体的细节变化用 分形维数（分数维）
来描述，它是物体粗糙性或细碎性的度量。
什么是 分数维？
9
分形几何（ 2/8）
整数维数
? 拓扑维数
? 只能取整数
表示描述一个对象所需的独立变量的个数
10
分形几何（ 3/8）
分数维数
? 度量维数
是从测量的角度定义的
? 从测量的角度看,维数是可变的 。
例如：看一个 毛线团
从测量的角度 重新理解维数概念
11
分形几何（ 4/8）
一根一维线段 L，单位长度 A，将其边长扩大到原来的 3倍，看看能得到几个
原始对象 (单位长度为 A的线段 )。
3个：
L→3L=3^1*L
平面上的一个正方形 P，边长为 A，将其边长扩大到原来的 3倍，则得到 9个正
方形：
P→9P=3^2*P
对于三维空间上的正方体 V，边长为 A，将其边长扩大到原来的 3倍，则得到
27个立方体：
V→27V=3^3*V
得到的总个数可表达为：
M=B^d
其中 B指放大倍数,M是总个数,d相当于对象的维数。
换一种写 法有：
d=logM/logB
其中指数 d相当于维数。
12
分形几何（ 5/8）
从 放大 的反面去理解
从,铺砌,的角度看
对给定对象,用很小的单元块 ε充填它，最后数一数所使用
的小单元数目 N
数学表达：
d=lim(ε→0)log N(ε)/log(1/ε) = -lim(ε→0)log N(ε)/logε
13
分形几何（ 6/8）
以 Koch曲线为例
? 细分线段数为 N=4，细分单元长度为 ε =1/3
? Koch曲线的分数维为：
d=ln4/ln3=1.2619
而按照欧氏几何方法
? 将一条线段 4等分
? 则 N=4,ε =1/4,d=1。
14
分形几何（ 7/8）
什么是分形？
Mandelbrot开始时
? 把那些 Hausdorff维数不是整数的集合 称为分形
但定义将某些显然为分形的集合排除在外
? 例如,Peano曲线的 Hausdorff维数为 2，是整数
定义修改为
? 强调 具有自相似性的集合 为分形
15
分形几何（ 8/8）
至今无统一定义，比较合理、普遍被人接受的定义
定义具有如下性质的集合 F为分形
? F具有 精细的结构,有任意小比例的细节
? F是如此地 不规则,以至于它的整体与局部都不能用传统
的几何语言来描述
? F通常有某种 自相似的性质,这种自相似性可以是近似的
或者是统计意义下的
? 一般地,F的某种定义之下的 分形维数大于它的拓扑维数
? 在大多数令人感兴趣的情形下,F通常能以非常简单的方
法定义，由 迭代过程产生
分形理论是 非线性科学 的生长点之一
16
随机插值模型（ 1/3）
1982年由
? Alain Fournier
? Don Fussell
? Loren Carpenter
提出
? 能有效地模拟海岸线和山等自然景象
? 不是事先决定各种图素和尺度
? 而是用一个随机过程的采样路径作为构造模型
的手段
17
随机插值模型（ 2/3）
构造 二维海岸线 的模型：
? 选择控制大致形状的若干初始点
? 在相邻两点构成的线段上取其中点
? 沿垂直连线方向随机偏移一个距离
? 将偏移后的点与该线段两端点分别连成两个新线段
如此继续可得到一条曲折的有无穷细节回归的海岸
线
18
随机插值模型（ 3/3）
在三维情况下用类似过程构造 山模型,
? 多边形（如三角形）细分
? 在三角形三边上随机各取一点
? 沿垂直方向随机偏移一段距离得到三个新点
? 连接成四个三角形
? 如此继续，可形成皱褶的山峰。
25
迭代函数系统（ 7/10）
收缩影射不动点原理
? 每个迭代函数系统都定义了一个唯一的分形图形，
称为该迭代函数系统的吸引子
怎样确定 仿射变换？
? 确定 a,b,c,d,e,f
IFS方法之所以能产生逐渐逼近吸引子的图像
? 是以 拼贴定理 为依据的
怎样确定 概率向量？
? 掷骰子操作
26
迭代函数系统（ 8/10）
D=log3/log2=1.585
Sierpinski三角形
f a b c d e f p
1 0.5 0 0 0.5 25 1 0.33
2 0.5 0 0 0.5 1 50 0.33
3 0.5 0 0 0.5 50 50 0.33
27
迭代函数系统（ 9/10）
Barnsley蕨的参数表
f a b c d e f p
1 0 0 0 0.16 0 0 0.01
2 0.85 0.04 － 0.04 0.85 0 1.6 0.85
3 0.2 － 0.26 0.23 0.22 0 1.6 0.07
4 － 0.15 0.28 0.26 0.24 0 0.44 0.07
32
L系统（ 4/10）
设计 D0L系统的步骤：
? 定义字符表 V
? 给出公理，即初始图 ω
? 定义产生式 P
33
L系统（ 5/10）
13世纪数学家 Fibonacci（ 1170-1250）
兔子的理想化繁衍问题
baby(b),adult(a)
? V,{a,b}
? W,b
? P,a->ab
b->a
b
a ab aba abaab abaababa
abaababaabaab
abaababaabaababaababa
35
L系统（ 7/10）
四方内生树
四方内生树
? V,{F,+,-}
? w,F+F+F+F
? P,F->FF+F++F+F
? δ= 90o
生成元初始图
37
L系统（ 9/10）
设计 L系统 的过程
? 是根据自相似结构形成 信息压缩 的一个过程
利用设计好的 L系统进行 绘制的过程
? 是信息压缩的逆过程，或者说是 信息复原 的过程。
38
L系统（ 10/10）
L系统能有效给出植物的 拓扑结构
但绘制 真实感 的二、三维植物形态还必须结合
几何造型技术
39
粒子系统（ 1/5）
Particle System
W.T.Reeves1983年提出
描述对象
? 不规则,结构随时间而变化 的 Fuzzy Object
? 尤其擅长模拟不规则物体的随机动态特性
如跳动的火焰, 烟雾, 下雨, 行云, 远处随风摇曳的
树林和草丛等
40
粒子系统（ 2/5）
基本思想
? 造型和动画是一个有机的整体
? 单个随时间变化的 粒子 (Particle)作为景物造型的基本元素
由粒子刻划的模型
? 每个粒子有一个 生命周期
包括 出生、成长、死亡 等几个阶段
? 粒子在不同的阶段具有不同的形态
? 粒子的运动由一定的 规则 控制
41
粒子系统（ 3/5）
本质是 随机模型
? 采用 随机过程 的方法来实现粒子在, 出生,,
,生长,,, 死亡, 三个阶段的不确定性
? 在生长过程中, 粒子的属性被随机地改变
42
粒子系统（ 4/5）
1985年, Reeves和 Blau
? 进一步发展了粒子系统
? 并维妙维肖的模拟了 小草随风摇曳 的景象
模拟动态模糊自然景物
电视电影的特技制作
最初引入是为了模拟 火焰
? 跳动的 火焰被看作是一个喷出许多粒子的火山 。
? 每个粒子都有一组 随机取值的属性
45
复平面上的迭代（ 2/11）
绘制 M集
? 以横轴 x记录实部
? 以纵轴 y记录虚部
? 迭代从 (x,y)=(0,0)开始迭
代
? 不同迭代次数和模值的点
涂上不同的颜色
M集合实际上是 常数 c=(p,q)构成的图象
qyxy
pyxx
qipc
iyxz
zcz
kkk
kkk
kk
??
???
??
???
??
?
?
?
21
1
1
22
2
46
复平面上的迭代（ 3/11）
M集特征：
? 一个主要的心形图与一系列圆盘形的“芽苞”突起连
在一起
? 每个芽苞又被更细小的芽苞所环绕
? 还有精细的“发丝状”分枝从芽苞向外长出
48
复平面上的迭代（ 5/11）
(a) c=0.1-0.1i，
f有吸引不动点, J为拟圆
(b) c=0.5-0.5i，
f有吸引不动点, J为拟圆
(c) c=1.0-0.05i，
f有周期为 2的吸引轨道
(d) c=0.2-0.75i，
f有周期为 3的吸引轨道
(e) c=-0.25-0.52i，
f有周期为 4的吸引轨道
(f) c=0.5-0.55i，
f有周期 5的吸引轨道
(g) c=-0.66i,f没有吸引轨道,
且 J为全部连通
(h) c=-i,f为无圈曲线
改变常数 c的取值，可以得到各式各样的 J集
49
复平面上的迭代（ 6/11）
二维复平面上二次映射
广义的 M集和 J集
? 任意多项式映射
? 三角函数
? 指数函数
? 对数函数
50
复平面上的迭代（ 7/11）
高维 M集与 J集
? 通过“四元数” (quaternions) 推广到高维空间中
在四维空间中研究迭代 x→x ^2+c下的超 Julia集
选一个截面，将超 Julia集投影到三维空间中，可以
得到立体的 J集图象
51
复平面上的迭代（ 8/11）
复平面域的牛顿法求根
? 本质是,以直代曲”
? 首先猜测一个值 x1，用它近似方程的根 c
? 用过 (x1,f(x1))点的切线
y=f(x1)+f’(x1)(x-x1)
近似代替曲线 f(x)
? 然后用切线方程
y=f(x1)+f’(x1)(x-x1)=0
的根
x=x2=x1-f(x1)/f’(x1)
近似代替曲线方程的根 c
? 这样就得到 c的第二个近似值
? 依此类推可得到迭代公式
x(n+1)=xn-f(xn)/f’(xn)
52
复平面上的迭代（ 9/11）
f(x)=x^p-1,其中 p是大于 2的正整数
x^3-1=0有三个根：
? x1=1
? x2=[-1+SQRT(3)i]/2
? x3=[-1-SQRT(3)i]/2
三个根均匀地分布在单位圆上,这三个根周围
构成三个,吸引盆,
53
复平面上的迭代（ 10/11）
改进方法
? 分式线性映射 w=1/z
在扩充的复平面上是一一对应的
且为具有保圆性和保对称性的保角映射
? 将牛顿函数取倒数，并在迭代过程中嵌入控制参数
用牛顿法求 z^4-1=0的根得到的分形图
)()(
)(
)(
1)(
zpzpz
zp
zfzF ??
???
2))()((
)()()(
zpzpz
zpzpzF
??
????
分子部分完全相同
超吸引不动点相同
iFIFR
iFIFR
zF
zFzF
bmbe
amae
b
a )()( )()()( )()( ????
iFIFR
iFIFRzF
bmbe
amae )()( )()()( ?? ??? ??
54
苏晓红等．用改进的 Newton-Raphson方法生成对
称的分形艺术图形，计算机学报,1999,22(11),
1147-1152
苏 小 红
哈尔滨工业大学计算机科学与技术学院
2
欧氏几何
? 使用 方程 描述有平滑的表面和 规则 形状的物体
分形几何
? 使用 过程 对具有 不规则 几何形态的物体（如自然景物）建模
分形几何
4
1906年，瑞典数学家 H.Von Koch在研究构造
连续而不可微函数时，提出 Koch曲线。
周长无穷，但面积为定值 （ 0）
分形的由来（ 1/4）
构造方法
5构造方法
周长无穷，但面积为定值
分形的由来（ 2/4）
,3)34(,334,3 2 aaa ?? ??......
,43 2aS? 22 5 32,.,,,,,)94(439443,9443 aSSSSS ???????
Von koch snowflake
D=log4/log3=1.2618
……
6
分形的由来（ 3/4）
60年代,现代分形理论的奠基人 B.B.Mandelbrot
将雪花与海岸线、山水、树木等自然景物联系起来
67年，英国, 科学, 杂志,,英国的海岸线有多长？
统计自相似性与分数维数,
什么是分形？
指具有多重自相似的对象
它可以是自然存在的，也可以是人造的。
7
分形的由来（ 4/4）
fractal概念的由来
75年，法文专著, 分形对象,形、机遇与维数
77年，英译本, 分形：形,机遇与维数, (Fractals,Form,
Chance,and Dimension)
82年，增补本，改名为, 大自然的分形几何学,
根据拉丁语 fractus造的词
词根含义：
? 细片的、破碎的、分裂的、分数的
8
分形几何（ 1/8）
分形物体的细节变化用 分形维数（分数维）
来描述，它是物体粗糙性或细碎性的度量。
什么是 分数维？
9
分形几何（ 2/8）
整数维数
? 拓扑维数
? 只能取整数
表示描述一个对象所需的独立变量的个数
10
分形几何（ 3/8）
分数维数
? 度量维数
是从测量的角度定义的
? 从测量的角度看,维数是可变的 。
例如：看一个 毛线团
从测量的角度 重新理解维数概念
11
分形几何（ 4/8）
一根一维线段 L，单位长度 A，将其边长扩大到原来的 3倍，看看能得到几个
原始对象 (单位长度为 A的线段 )。
3个：
L→3L=3^1*L
平面上的一个正方形 P，边长为 A，将其边长扩大到原来的 3倍，则得到 9个正
方形：
P→9P=3^2*P
对于三维空间上的正方体 V，边长为 A，将其边长扩大到原来的 3倍，则得到
27个立方体：
V→27V=3^3*V
得到的总个数可表达为：
M=B^d
其中 B指放大倍数,M是总个数,d相当于对象的维数。
换一种写 法有：
d=logM/logB
其中指数 d相当于维数。
12
分形几何（ 5/8）
从 放大 的反面去理解
从,铺砌,的角度看
对给定对象,用很小的单元块 ε充填它，最后数一数所使用
的小单元数目 N
数学表达：
d=lim(ε→0)log N(ε)/log(1/ε) = -lim(ε→0)log N(ε)/logε
13
分形几何（ 6/8）
以 Koch曲线为例
? 细分线段数为 N=4，细分单元长度为 ε =1/3
? Koch曲线的分数维为：
d=ln4/ln3=1.2619
而按照欧氏几何方法
? 将一条线段 4等分
? 则 N=4,ε =1/4,d=1。
14
分形几何（ 7/8）
什么是分形？
Mandelbrot开始时
? 把那些 Hausdorff维数不是整数的集合 称为分形
但定义将某些显然为分形的集合排除在外
? 例如,Peano曲线的 Hausdorff维数为 2，是整数
定义修改为
? 强调 具有自相似性的集合 为分形
15
分形几何（ 8/8）
至今无统一定义，比较合理、普遍被人接受的定义
定义具有如下性质的集合 F为分形
? F具有 精细的结构,有任意小比例的细节
? F是如此地 不规则,以至于它的整体与局部都不能用传统
的几何语言来描述
? F通常有某种 自相似的性质,这种自相似性可以是近似的
或者是统计意义下的
? 一般地,F的某种定义之下的 分形维数大于它的拓扑维数
? 在大多数令人感兴趣的情形下,F通常能以非常简单的方
法定义，由 迭代过程产生
分形理论是 非线性科学 的生长点之一
16
随机插值模型（ 1/3）
1982年由
? Alain Fournier
? Don Fussell
? Loren Carpenter
提出
? 能有效地模拟海岸线和山等自然景象
? 不是事先决定各种图素和尺度
? 而是用一个随机过程的采样路径作为构造模型
的手段
17
随机插值模型（ 2/3）
构造 二维海岸线 的模型：
? 选择控制大致形状的若干初始点
? 在相邻两点构成的线段上取其中点
? 沿垂直连线方向随机偏移一个距离
? 将偏移后的点与该线段两端点分别连成两个新线段
如此继续可得到一条曲折的有无穷细节回归的海岸
线
18
随机插值模型（ 3/3）
在三维情况下用类似过程构造 山模型,
? 多边形（如三角形）细分
? 在三角形三边上随机各取一点
? 沿垂直方向随机偏移一段距离得到三个新点
? 连接成四个三角形
? 如此继续，可形成皱褶的山峰。
25
迭代函数系统（ 7/10）
收缩影射不动点原理
? 每个迭代函数系统都定义了一个唯一的分形图形，
称为该迭代函数系统的吸引子
怎样确定 仿射变换？
? 确定 a,b,c,d,e,f
IFS方法之所以能产生逐渐逼近吸引子的图像
? 是以 拼贴定理 为依据的
怎样确定 概率向量？
? 掷骰子操作
26
迭代函数系统（ 8/10）
D=log3/log2=1.585
Sierpinski三角形
f a b c d e f p
1 0.5 0 0 0.5 25 1 0.33
2 0.5 0 0 0.5 1 50 0.33
3 0.5 0 0 0.5 50 50 0.33
27
迭代函数系统（ 9/10）
Barnsley蕨的参数表
f a b c d e f p
1 0 0 0 0.16 0 0 0.01
2 0.85 0.04 － 0.04 0.85 0 1.6 0.85
3 0.2 － 0.26 0.23 0.22 0 1.6 0.07
4 － 0.15 0.28 0.26 0.24 0 0.44 0.07
32
L系统（ 4/10）
设计 D0L系统的步骤：
? 定义字符表 V
? 给出公理，即初始图 ω
? 定义产生式 P
33
L系统（ 5/10）
13世纪数学家 Fibonacci（ 1170-1250）
兔子的理想化繁衍问题
baby(b),adult(a)
? V,{a,b}
? W,b
? P,a->ab
b->a
b
a ab aba abaab abaababa
abaababaabaab
abaababaabaababaababa
35
L系统（ 7/10）
四方内生树
四方内生树
? V,{F,+,-}
? w,F+F+F+F
? P,F->FF+F++F+F
? δ= 90o
生成元初始图
37
L系统（ 9/10）
设计 L系统 的过程
? 是根据自相似结构形成 信息压缩 的一个过程
利用设计好的 L系统进行 绘制的过程
? 是信息压缩的逆过程，或者说是 信息复原 的过程。
38
L系统（ 10/10）
L系统能有效给出植物的 拓扑结构
但绘制 真实感 的二、三维植物形态还必须结合
几何造型技术
39
粒子系统（ 1/5）
Particle System
W.T.Reeves1983年提出
描述对象
? 不规则,结构随时间而变化 的 Fuzzy Object
? 尤其擅长模拟不规则物体的随机动态特性
如跳动的火焰, 烟雾, 下雨, 行云, 远处随风摇曳的
树林和草丛等
40
粒子系统（ 2/5）
基本思想
? 造型和动画是一个有机的整体
? 单个随时间变化的 粒子 (Particle)作为景物造型的基本元素
由粒子刻划的模型
? 每个粒子有一个 生命周期
包括 出生、成长、死亡 等几个阶段
? 粒子在不同的阶段具有不同的形态
? 粒子的运动由一定的 规则 控制
41
粒子系统（ 3/5）
本质是 随机模型
? 采用 随机过程 的方法来实现粒子在, 出生,,
,生长,,, 死亡, 三个阶段的不确定性
? 在生长过程中, 粒子的属性被随机地改变
42
粒子系统（ 4/5）
1985年, Reeves和 Blau
? 进一步发展了粒子系统
? 并维妙维肖的模拟了 小草随风摇曳 的景象
模拟动态模糊自然景物
电视电影的特技制作
最初引入是为了模拟 火焰
? 跳动的 火焰被看作是一个喷出许多粒子的火山 。
? 每个粒子都有一组 随机取值的属性
45
复平面上的迭代（ 2/11）
绘制 M集
? 以横轴 x记录实部
? 以纵轴 y记录虚部
? 迭代从 (x,y)=(0,0)开始迭
代
? 不同迭代次数和模值的点
涂上不同的颜色
M集合实际上是 常数 c=(p,q)构成的图象
qyxy
pyxx
qipc
iyxz
zcz
kkk
kkk
kk
??
???
??
???
??
?
?
?
21
1
1
22
2
46
复平面上的迭代（ 3/11）
M集特征：
? 一个主要的心形图与一系列圆盘形的“芽苞”突起连
在一起
? 每个芽苞又被更细小的芽苞所环绕
? 还有精细的“发丝状”分枝从芽苞向外长出
48
复平面上的迭代（ 5/11）
(a) c=0.1-0.1i，
f有吸引不动点, J为拟圆
(b) c=0.5-0.5i，
f有吸引不动点, J为拟圆
(c) c=1.0-0.05i，
f有周期为 2的吸引轨道
(d) c=0.2-0.75i，
f有周期为 3的吸引轨道
(e) c=-0.25-0.52i，
f有周期为 4的吸引轨道
(f) c=0.5-0.55i，
f有周期 5的吸引轨道
(g) c=-0.66i,f没有吸引轨道,
且 J为全部连通
(h) c=-i,f为无圈曲线
改变常数 c的取值，可以得到各式各样的 J集
49
复平面上的迭代（ 6/11）
二维复平面上二次映射
广义的 M集和 J集
? 任意多项式映射
? 三角函数
? 指数函数
? 对数函数
50
复平面上的迭代（ 7/11）
高维 M集与 J集
? 通过“四元数” (quaternions) 推广到高维空间中
在四维空间中研究迭代 x→x ^2+c下的超 Julia集
选一个截面，将超 Julia集投影到三维空间中，可以
得到立体的 J集图象
51
复平面上的迭代（ 8/11）
复平面域的牛顿法求根
? 本质是,以直代曲”
? 首先猜测一个值 x1，用它近似方程的根 c
? 用过 (x1,f(x1))点的切线
y=f(x1)+f’(x1)(x-x1)
近似代替曲线 f(x)
? 然后用切线方程
y=f(x1)+f’(x1)(x-x1)=0
的根
x=x2=x1-f(x1)/f’(x1)
近似代替曲线方程的根 c
? 这样就得到 c的第二个近似值
? 依此类推可得到迭代公式
x(n+1)=xn-f(xn)/f’(xn)
52
复平面上的迭代（ 9/11）
f(x)=x^p-1,其中 p是大于 2的正整数
x^3-1=0有三个根：
? x1=1
? x2=[-1+SQRT(3)i]/2
? x3=[-1-SQRT(3)i]/2
三个根均匀地分布在单位圆上,这三个根周围
构成三个,吸引盆,
53
复平面上的迭代（ 10/11）
改进方法
? 分式线性映射 w=1/z
在扩充的复平面上是一一对应的
且为具有保圆性和保对称性的保角映射
? 将牛顿函数取倒数，并在迭代过程中嵌入控制参数
用牛顿法求 z^4-1=0的根得到的分形图
)()(
)(
)(
1)(
zpzpz
zp
zfzF ??
???
2))()((
)()()(
zpzpz
zpzpzF
??
????
分子部分完全相同
超吸引不动点相同
iFIFR
iFIFR
zF
zFzF
bmbe
amae
b
a )()( )()()( )()( ????
iFIFR
iFIFRzF
bmbe
amae )()( )()()( ?? ??? ??
54
苏晓红等．用改进的 Newton-Raphson方法生成对
称的分形艺术图形，计算机学报,1999,22(11),
1147-1152
