计算机图形学之 分形几何

◆分形和分维 ◆递归模型
8.1 8.2 8.5 8.6

分形和分维 递归模型 本章小结 习题
8.1分形和分维
真实的世界并不规则，闪电不是直线，海 岸线不是弧线，云团不是球体，山峦也不是锥 体。自然界的许多对象是如此不规则和支离破 碎，以致欧氏几何学不能真实有效地再现大自 然。 为了再现真实世界，必须选择新的工具， 分形几何学应运而生。分形几何是以非规则物 体为研究对象的几何学。由于闪电、海岸线、 云团、山峦、海浪、野草、森林、火光等非规 则物体在自然界里比比皆是，因此分形几何学 又被称为描述大自然的几何学。
先绘制第一段直线，然后改变夹角，分别绘制其余3段直线
8.2.3 Peano-Hilbert曲线
意大利数学家皮亚诺（Peano， 1858～1932），通过对一些古代装饰图 案的研究，于1890年构造出一种奇怪的 平面曲线，这条曲线蜿蜒向前，一笔绘 成，并能充满整个平面。接着德国数学 家希尔伯特(Hilbert，1862～1943)于 1891年也构造出一种类型相同但比较简 单的曲线。这种曲线被称为PeanoHilbert曲线。
n＝0 n ＝2 n ＝1
Peano-Hilbert曲线的出现，当时曾令当时的 数学界大吃一惊： 它是一条曲线，但又是一个平面； 皮亚诺曲线的方程只有一个参数，但它却能确定 了一个平面；而在欧氏几何学中，确定一条曲线需
要一个参数，确定一个平面需要两个参数。
8.2.4 Sierpinski垫片、地毯和海绵
分形山
8.1分形和分维
8.1.1 8.1.2 8.1.3 8.1.4

分形的诞生 分形的基本特征 分形的定义 分形维数的定义
8.1.1 分形的诞生
分形（Fractal）这个词，是由美籍法国 数学家曼德尔布罗特（Benoit B.Mandelbrot） 自己创造出来的，此词来源于拉丁文fractus， 意为不规则、支离破碎。1967年曼德尔布罗特 在美国《科学》杂志上发表了划时代的论文 《英国海岸线有多长？统计自相似与分数维》， 成为其分形思想萌芽的重要标志。1973年，在 法兰西学院讲学期间，曼德尔布罗特提出了分 形几何学的整体思想，并认为分数维是个可用 于研究许多物理现象的有力工具。1982年曼德 尔布罗特出版了《大自然的分形几何学》，引 起了学术界的广泛重视，曼德尔布罗特也因此 一举成名。
8.1.4 分形维数的定义



维数是几何对象的一个重要特征量，它是欧氏几 何学描述点的位置所需的独立坐标数目。为了定量地 刻画分形，引入了分数维数的概念。分数维数与欧氏 几何学中的整数维数相对应。 分形理论认为，维数中可以包含有小数。把分数维数 记为D，一般称为分数维或分维。 分维的计算公式为： ln N D ln S 其中D代表分维，N为和整体自相似的局部形体个数， S为相似比，等于整体和局部之比。 注：分维的计算结果是两个参数的对数值之比，所以 分维的计算结果不一定是整数。
3.谢尔宾斯基海绵 生成规则：将一个立方体沿其各个面等分为九 个小立方体，舍弃位于体心的一个小立方体，以及 位于立方体六个面心的六个小立方体。将二十个小 立方体继续按相同的方法分割并舍弃位于立方体体 心和面心处的更小的立方体。如此不断地分割与舍 弃，就能得到中间有大量空隙的Sierpinski海绵。
n＝ 1
n＝ 2
n＝ 3
n＝ 4
“病态”原因：总周长趋于无穷， 总面积趋于零。也就是说：当用一 维得尺度去测量时，其值趋于无穷 大，当用二维尺度去度量时，其值 趋于零。 分形维数：D=ln8/ln3=1.8927。
生成元：Sierpinski地毯是平面分形，具有自相似性。 其生成元是把正方形分成九个小正方形，舍弃中间一 个正方形，余下八个小正方形。正方形的左上角点和 右下角点是生成元的设计顶点。Sierpinski地毯的递 归调用是通过反复使用生成元来取代每一个小正方形 进行的。 大正方形的左上角点和右下角点为：（x1，y1），（x2， y2）。
2.无标度性
标度是计量单位的刻度。比如 长度的标度是米；重量的标度是公 斤；面积的标度是平方米等。对欧 氏几何学内的不同形体，可以选择 不同的标度去度量。例如，直线是 多长，面积是多大，体积是多少。 自然界中很多的物体具有特征长度， 如人有高度、山有海拔等等。
8.1.3 分形的定义

一般认为，满足下列条件的图形称为分形集： 分形集具有任意尺度下的比例细节，或者说 具有精细结构； 分形集是不规则的，以致于不能用传统的几 何语言来描述。 分形集通常具有某种自相似性，或许是近似 的或许是统计意义下的自相似。 分形集在某种方式下定义的“分维数”一般 大于它的拓扑维数。 分形集的定义常常是非常简单的，或许是递 归的。



⑴对于直线：

将一直线段二等分， 则N=2，S=2， 即2=21，所以，分维D=1


⑵对于平面：
将正方形四等分，则N=4，S=2，即 4=22，所以，分维D=2


⑶对于立体：
将立方体八等分， N=8，S=2，即 8=23，所以，分维D=3


⑷对于典型的分形曲线，例如Koch曲线，构成方法如下： 取一直线段，将其三等分，保留两端的两段，将中间 一段拉起为等边三角形的两条边。N=4，S=3，分维 D=ln4/ln3=1.26186。从图8-7中n＝5的递归图形中可以看 出koch曲线点点连续，但点点不可导，属于病态曲线； koch曲线局部和整体相似，具有自相似性。因此可以使用 koch曲线来模拟海岸线。
8.2.2 Koch曲线


1904年，瑞典数学家科和（Koch，1870～1924）发现一种 曲线，其几何表示如下： 生成规则：取一段长度为L0的直线段，将其三等分，保留 两端的线段，将中间一段改换成夹角为60°的两个L0/3等 长直线段；将长度为L0/3的4个直线段分别三等分，并将 它们中间的一段改换成夹角为60°的两个L0/9等长直线段。 依此类推，便得到具有自相似结构的折线。如果在等边三 角形上按上述规则在每边的中间各凸起一个小三角形，这 样一直进行下去，则曲线形状近似为似一朵雪花，称为 Koch雪花。
集合论的创始人康托（G.Cantor，1845～1918）在1883年曾构造了 一种三等分Cantor集，其几何表示如下： 生成规则：取一段长度为L0的直线段，将其三等分，保留两端的线 段，将中间一段抛弃，如图8-9的n＝1的操作；再将剩下的两段直 线分别三等分，然后将其中间一段抛弃，如图8-9的n＝2的操作； 依此类推，便形成了无数个尘埃似的散点，所以cantor三分集也称 为cantor灰尘。 “病态”原因：数目无穷多，但长度趋近于零。 分形维数：D＝ln2/ln3=0.6309。
8.2递归模型
分形图形的传统实现模型是递归模型。在调用一个函 数的过程中，直接或间接地调用函数自身，称为递归调用。 例如n！可以采用递归模型实现。即5！＝5×4！，而4！＝ 4×3！，……，1！＝1，递归公式表示如下：
1 n! n (n 1)!
阶乘递归子函数如下： Long fac(int n) { long f; If (n==0 || 1） f=1; Else f=fac(n-1)*n; Return f; }
1915-1916年，波兰数学家谢 尔宾斯基(Sierpinski，1882-1969) 将三分康托尔集的构造思想推广到 二维平面和三维立体，构造出千疮 百孔的谢尔宾斯基垫片、地毯和海 绵。
1.谢尔宾斯基垫片 生成规则：取一等边三角形，连接各边中点将原三 角形分成四个小三角形，然后舍弃位于中间的一个小 三角形，如图8-16 n＝1所示。将剩下的其余三个小三 角形按同样方法继续分割，并舍弃位于中间的那个三 角形，如图8-16 n＝2所示。如此不断地分割与舍弃， 就能得到中间有大量孔隙的Sierpinski垫片。
英国的海岸线
蕨类植物叶的自相似性
8.1.2 分形的基本特征
1.自相似性
自相似性是指局部与整体相似的性 质。在自然界中，具有自相似性的物体 比比皆是，起伏的山峦中一座座山峰和 整体山脉，弯曲的河流中一个个支流和 整体河川，茂密的树木上的一条条树杈 和整体树木等，均具有自相似性，如图 8-3所示的是蕨类植物叶子上的细叶和整 体叶子的相似性。
“病态”原因：总周长趋于无穷， 总面积趋于零。也就是说：当用 一维的尺度去测量时，其值趋于 无穷大，当用二维尺度去度量时， 其值趋于零。
分形维数：D=ln3/ln2=1.5849。
Sierpinski垫片生成元
2.谢尔宾斯基地毯 生成规则：取一正方形，将其每条边三等分， 正方形被等分为九个面积相等的小正方形，舍弃 位于中央的一个小正方形，如图8-18 n＝1所示。 将剩下的八个小正方形按上面同样的方法继续分 割，并舍弃位于中间的那个小正方形，如图8-18 n＝2所示。如此不断地分割与舍弃，就能得中间 有大量空隙的Sierpinski地毯。
n＝1
n＝2
n＝3
n＝4
“病态”原因：有限体积具有无限表 面积，也就是说：当用二维得尺度 去测量时，其值趋于无穷大，当用 三维尺度去度量时，其值趋于零。
分形维数：D=ln20/ln3=2.7288。
生成元：Sierpinski海绵是分形立体，具有自 相似性。其生成元是把立方体分成二十七个小立方体， 挖去立方体六个面心的小立方体以及位于体心的一个 小立方体，共挖去七个小立方体，Sierpinski海绵的 递归调用是通过反复使用生成元来取代每一个小正方 体进行的。 每个立方体在图形显示上 是由前面、顶面和右面三个面 构成的。设正方形的左上角点 为（x，y），边长为d。对于 顶面和右面，由于其为平行四 边形，其夹角为45°的斜边的 水平投影 DX＝ d×cos(π/4)， 垂直投影DY＝d×sin(π/4)。 因为DX＝DY，所以全部以DX代 替。
生成元结构
8.2.5 C字曲线

生成规则：以一条直线段为斜边，拉出一个等腰直 角三角形，如图8-25 n＝1所示。以该三角形的两 条直角边分别为斜边，再拉出两个等腰直角三角形， 如图8-25 n＝2所示。依此类推，便形成了类似字 母C的图形，如图8-25 n＝10所示，称为C字曲线。
理论上可以证明这种不断构造的雪 花周长是无穷的，但其面积却是有限的， 这和传统的数学观念是不相符的，采用 周长和面积都无法刻划出这种雪花的特 点，欧氏几何学对描述这种雪花无能为 力。 “病态”原因：处处连续，处处不可导。 分形维数：D=ln4/ln3=1.26186。
பைடு நூலகம்
生成元：koch曲线是著名的分形曲线，具有自相似性。其 中生成元是图8-12所示的图形。生成元的第一段直线段和第二 段直线段之间的夹角可以为任意角度（0°<θ<90°），不同的 角度值生成的Koch曲线有很大差异。最常用的角度是θ＝60° 和θ＝85°。生成元的起点和终点坐标分别为（ax，ay）和 （bx，by），Koch曲线共由四条直线段构成。Koch曲线的递归 调用是通过反复使用生成元来取代每一段直线而进行的。
(n 0,1) (n 1)
8.2递归模型


8.2.1 8.2.2 8.2.3 8.2.4 海绵 8.2.5 8.2.6
Cantor集 Koch曲线 Peano-Hilbert曲线 Sierpinski垫片、地毯和
C字曲线 Caley树
8.2.1 Cantor集




Cantor的生成元：
(a x , a y ) (c x , c y )
(d x , d y )
(b x , b y )
Cantor生成元

这些点之间的几何关系为
cx a x bx a x 2(bx a x ) ,cy a y ,d x a x ,d y a y 3 3


生成规则：首先，将一正方形四等分为四个小正方形， 求出各个小正方形的中心并用三条直线连接起来，如 图8-13 n＝0所示，可以使用两种连接方式：开口向 上和开口向左。其次，将各个小正方形再细分为四个 小正方形，用三条直线连接各个小正方形的中心，也 会有两种连接方式，如图8-13 n＝1所示。依此类推， 便形成Peano-Hilbert曲线。 “病态”原因：一维曲线却能充满整个平面。 分形维数：D=ln4/ln2=2。