1、ComputerGraphics第八章 分形几何8.18.1 分形和分维分形和分维 8.28.2 递归模型递归模型8.3 8.3 L L系统模型系统模型8.48.4 IFSIFS迭代函数系统模型迭代函数系统模型本章内容本章内容8.18.1分形和分维分形和分维真实的世界却并不规则，闪电不是直线，海岸真实的世界却并不规则，闪电不是直线，海岸线不是弧线，云团不是球体，山峦也不是锥体。自线不是弧线，云团不是球体，山峦也不是锥体。自然界的许多对象是如此不规则和支离破碎，以致欧然界的许多对象是如此不规则和支离破碎，以致欧氏几何学不能真实有效地再现大自然。氏几何学不能真实有效地再现大自然。 为了再现真实世界
2、，必须选择新的工具，分形为了再现真实世界，必须选择新的工具，分形几何学应运而生。分形几何是以非规则物体为研究几何学应运而生。分形几何是以非规则物体为研究对象的几何学。由于闪电、海岸线、云团、山峦、对象的几何学。由于闪电、海岸线、云团、山峦、海浪、野草、森林、火光等非规则物体在自然界里海浪、野草、森林、火光等非规则物体在自然界里比比皆是，因此分形几何学又被称为描述大自然的比比皆是，因此分形几何学又被称为描述大自然的几何学。几何学。 分形山8.1.1 8.1.1 分形的诞生分形的诞生 8.1.2 8.1.2 分形的基本特征分形的基本特征8.1.3 8.1.3 分形的定义分形的定义 8.1.4 8.
3、1.4 分形维数的定义分形维数的定义 8.1.1 8.1.1 分形的诞生分形的诞生 分形（分形（FractalFractal）这个词，是由美籍法国数学家）这个词，是由美籍法国数学家曼德尔布罗特（曼德尔布罗特（Benoit B.MandelbrotBenoit B.Mandelbrot）自己创造出）自己创造出来的，此词来源于拉丁文来的，此词来源于拉丁文fractusfractus，意为不规则、支，意为不规则、支离破碎。离破碎。19671967年曼德尔布罗特在美国年曼德尔布罗特在美国科学科学杂志杂志上发表了划时代的论文上发表了划时代的论文英国海岸线有多长？统计英国海岸线有多长？统计自相似与分数维自
4、相似与分数维，成为其分形思想萌芽的重要标，成为其分形思想萌芽的重要标志。志。19731973年，在法兰西学院讲学期间，曼德尔布罗年，在法兰西学院讲学期间，曼德尔布罗特提出了分形几何学的整体思想，并认为分数维是特提出了分形几何学的整体思想，并认为分数维是个可用于研究许多物理现象的有力工具。个可用于研究许多物理现象的有力工具。19821982年曼年曼德尔布罗特出版了德尔布罗特出版了大自然的分形几何学大自然的分形几何学，引起，引起了学术界的广泛重视，曼德尔布罗特也因此一举成了学术界的广泛重视，曼德尔布罗特也因此一举成名。名。 英国的海岸线 蕨类植物叶的自相似性8.1.2 8.1.2 分形的基本特征分
5、形的基本特征 1.1.自相似性自相似性 自相似性是指局部与整体相似的性质。图自相似性是指局部与整体相似的性质。图8-38-3所示的是蕨类植物叶子上的细叶和整体叶所示的是蕨类植物叶子上的细叶和整体叶子的相似性。子的相似性。 分形图形都具有细节的无穷回归性，随着分形图形都具有细节的无穷回归性，随着尺度的缩短都会得到更多的细节。分形理论发尺度的缩短都会得到更多的细节。分形理论发展到今天，如果一个对象的部分和整体具有自展到今天，如果一个对象的部分和整体具有自仿射变换的关系，也可以称之为分形。仿射变换的关系，也可以称之为分形。 2.2.无标度性无标度性 标度是计量单位的刻度。比如长度的标度是计量单位的刻
6、度。比如长度的标度是米；重量的标度是公斤；面积的标度标度是米；重量的标度是公斤；面积的标度是平方米等。对欧氏几何学内的不同形体，是平方米等。对欧氏几何学内的不同形体，可以选择不同的标度去度量。可以选择不同的标度去度量。 分形却不然，由于分形具有无穷嵌套的分形却不然，由于分形具有无穷嵌套的精细结构，自相似性使得其内部结构不存在精细结构，自相似性使得其内部结构不存在特征长度。分形没有特征标度，也就是不能特征长度。分形没有特征标度，也就是不能用标度去度量，成为无标度性。用标度去度量，成为无标度性。8.1.3 8.1.3 分形的定义分形的定义 一般认为，满足下列条件的图形称为分形集：一般认为，满足下列
7、条件的图形称为分形集： 分形集具有任意尺度下的比例细节，或者说分形集具有任意尺度下的比例细节，或者说具有精细结构；具有精细结构； 分形集是不规则的，以致于不能用传统的几分形集是不规则的，以致于不能用传统的几何语言来描述。何语言来描述。 分形集通常具有某种自相似性，或许是近似分形集通常具有某种自相似性，或许是近似的或许是统计意义下的自相似。的或许是统计意义下的自相似。 分形集在某种方式下定义的分形集在某种方式下定义的“分维数分维数”一般一般大于它的拓扑维数。大于它的拓扑维数。 分形集的定义常常是非常简单的，或许是递分形集的定义常常是非常简单的，或许是递归的。归的。 8.1.4 8.1.4 分形维
8、数的定义分形维数的定义 维数是几何对象的一个重要特征量，它是欧氏几维数是几何对象的一个重要特征量，它是欧氏几何对学描述点的位置所需的独立坐标数目。为了何对学描述点的位置所需的独立坐标数目。为了定量地刻画分形，引入了分数维数的概念。分数定量地刻画分形，引入了分数维数的概念。分数维数与欧氏几何学中的整数维数相对应。维数与欧氏几何学中的整数维数相对应。 分形理论认为，维数中可以包含有小数。把分数分形理论认为，维数中可以包含有小数。把分数维数记为维数记为D D，一般称为分数维或分维。，一般称为分数维或分维。分维的定义有很多，有相似维数、容量维数、豪分维的定义有很多，有相似维数、容量维数、豪斯道夫维数等
9、。本章只介绍相似维数。斯道夫维数等。本章只介绍相似维数。分维的计算公式为：分维的计算公式为： SNDlnlnDNS代表分维代表分维为和整体自相似的局部形体个数为和整体自相似的局部形体个数为相似比为相似比对于直线：对于直线： 将一直线段二等分，将一直线段二等分， 则则N=2N=2，S=2S=2，即，即2=22=21 1，所以，分维所以，分维D=1 D=1 SNDlnln对于平面：对于平面： 将正方形四等分，则将正方形四等分，则N=4N=4，S=2S=2，即，即4=24=22 2，所，所以，分维以，分维D=2 D=2 SNDlnln对于立体：对于立体： 将立方体八等分，将立方体八等分， N=8N=
10、8，S=2S=2，即，即8=28=23 3，所以，分维所以，分维D=3 D=3 SNDlnln对于典型的分形曲线，对于典型的分形曲线，例如例如KochKoch曲线，构成方法曲线，构成方法如下：如下： 取一直线段，将其三等取一直线段，将其三等分，保留两端的两段，将分，保留两端的两段，将中间一段拉起为等边三角中间一段拉起为等边三角形的两条边。形的两条边。 N=4 N=4，S=3S=3 分维分维D=ln4/ln3=1.26186D=ln4/ln3=1.26186从图中从图中n5的递归图形中可以看出的递归图形中可以看出koch曲线点曲线点点连续，但点点不可导，属于病态曲线；点连续，但点点不可导，属于病
11、态曲线；koch曲线局部和整体相似，具有自相似性。因此可以曲线局部和整体相似，具有自相似性。因此可以使用使用koch曲线来模拟海岸线。根据曼德布罗特曲线来模拟海岸线。根据曼德布罗特的计算，英国海岸线的分形维数为的计算，英国海岸线的分形维数为D=1.25。 8.28.2递归模型递归模型 分形图形的传统实现模分形图形的传统实现模型是递归模型。在调用一个型是递归模型。在调用一个函数的过程中，直接或间接函数的过程中，直接或间接地调用函数自身，称为递归地调用函数自身，称为递归调用。例如调用。例如n n！可以采用递归！可以采用递归模型实现。即模型实现。即5 5！5 54 4！，！，而而4 4！4 43 3
12、！，！，1 1！1 1，递归公式表示如下：，递归公式表示如下： ) 1()!1() 1 , 0(1!nnnnnlong fac(int n) long f; if(n=0|n=1) f=1; else f=fac(n-1)*n; return f;8.2.1 Cantor8.2.1 Cantor集集8.2.2 Koch8.2.2 Koch曲线曲线 8.2.3 Peano-Hilbert8.2.3 Peano-Hilbert曲线曲线 8.2.4 Sierpinski8.2.4 Sierpinski垫片、地毯垫片、地毯和海绵和海绵8.2.5 C8.2.5 C字曲线字曲线8.2.6 Caley8.2
13、.6 Caley树树8.2.1 C8.2.1 CANTORANTOR集集 集合论的创始人康托（集合论的创始人康托（G.Cantor，18451918）在在1883年曾构造了一种三等分年曾构造了一种三等分Cantor集，其几何表集，其几何表示如下：示如下：生成规则：取一段长度为生成规则：取一段长度为L0的直线段，将其三等分，的直线段，将其三等分，保留两端的线段，将中间一段抛弃，如图保留两端的线段，将中间一段抛弃，如图8-9的的n1的操作；再将剩下的两段直线分别三等分，然后将其的操作；再将剩下的两段直线分别三等分，然后将其中间一段抛弃，如图中间一段抛弃，如图8-9的的n2的操作；依此类推，的操作；
14、依此类推，便形成了无数个尘埃似的散点，所以便形成了无数个尘埃似的散点，所以cantor三分集也三分集也称为称为cantor灰尘。灰尘。“病态病态”原因：数目无穷多，但长度趋近于零。原因：数目无穷多，但长度趋近于零。分形维数：分形维数：Dln2/ln3=0.6309。 (,)xyaa(,)xyb b(,)xydd(,)xycc2(),;,33xxxxxxyyxxyybabacacadada8.2.2 K8.2.2 KOCHOCH曲线曲线 1904年，瑞典数学家科和（年，瑞典数学家科和（Koch，18701924）发现一种曲线，其几何表示如下：发现一种曲线，其几何表示如下：生成规则：取一段长度为生
15、成规则：取一段长度为L0的直线段，如图的直线段，如图8-7 n0所示，将其三等分，保留两端的线段，将中间一段改所示，将其三等分，保留两端的线段，将中间一段改换成夹角为换成夹角为60的两个的两个L0/3等长直线段，如图等长直线段，如图8-7 n1所示；将长度为所示；将长度为L0/3的的4个直线段分别三等分，个直线段分别三等分，并将它们中间的一段改换成夹角为并将它们中间的一段改换成夹角为60的两个的两个L0/9等长直线段，如图等长直线段，如图8-7 n2所示。依此类推，便得到所示。依此类推，便得到具有自相似结构的折线。如果在等边三角形上按上述具有自相似结构的折线。如果在等边三角形上按上述规则在每边
16、的中间各凸起一个小三角形，这样一直进规则在每边的中间各凸起一个小三角形，这样一直进行下去，则曲线形状近似为似一朵雪花，称为行下去，则曲线形状近似为似一朵雪花，称为Koch雪花，如图雪花，如图8-11所示。所示。理论上可以证明这种不断构造的雪花周长是理论上可以证明这种不断构造的雪花周长是无穷的，但其面积却是有限的，这和传统的数学无穷的，但其面积却是有限的，这和传统的数学观念是不相符的观念是不相符的，采用周长和面积都无法刻划出，采用周长和面积都无法刻划出这种雪花的特点，欧氏几何学对描述这种雪花无这种雪花的特点，欧氏几何学对描述这种雪花无能为力。能为力。 “病态病态”原因：处处连续，处处不可导。原因
17、：处处连续，处处不可导。 分形维数：分形维数：D=ln4/ln3=1.26186D=ln4/ln3=1.26186。 / (2(1cos )ndL 生成元：生成元：kochkoch曲线是著名的分形曲线，具曲线是著名的分形曲线，具有自相似性。其中生成元是图有自相似性。其中生成元是图8-128-12所示的图形。所示的图形。生成元的生成元的第一第一段直线段和第二段直线段之间的夹段直线段和第二段直线段之间的夹角可以为任意角度（角可以为任意角度（0 09090），不同的角），不同的角度值生成的度值生成的KochKoch曲线有很大差异。最常用的角度曲线有很大差异。最常用的角度是是6060和和8585。生成
18、元的起点和终点坐。生成元的起点和终点坐标分别为（标分别为（axax，ayay）和（）和（bxbx，byby），），KochKoch曲线共曲线共由四条直线段构成。由四条直线段构成。KochKoch曲线的递归调用是通过曲线的递归调用是通过反复使用生成元来取代每一段直线而进行的。反复使用生成元来取代每一段直线而进行的。 8.2.3 P8.2.3 PEANOEANO-H-HILBERTILBERT曲线曲线 意大利数学家皮亚诺（意大利数学家皮亚诺（PeanoPeano，1858185819321932），通过对一些古代装饰图案的研究，于，通过对一些古代装饰图案的研究，于18901890年构年构造出一种奇
19、怪的平面曲线，这条曲线蜿蜒向前，造出一种奇怪的平面曲线，这条曲线蜿蜒向前，一笔绘成，并能充满整个平面。接着德国数学家一笔绘成，并能充满整个平面。接着德国数学家希尔伯特希尔伯特(Hilbert(Hilbert，186218621943)1943)于于18911891年也构造年也构造出一种类型相同但比较简单的曲线。这种曲线被出一种类型相同但比较简单的曲线。这种曲线被称为称为Peano-HilbertPeano-Hilbert曲线。曲线。 Peano-Hilbert Peano-Hilbert曲线的出现，当时曾令当曲线的出现，当时曾令当时的数学界大吃一惊：时的数学界大吃一惊： 它是一条曲线，但又是一
20、个平面；它是一条曲线，但又是一个平面； 皮亚诺曲线的方程只有一个参数，但它皮亚诺曲线的方程只有一个参数，但它却能确定了一个平面；而在欧氏几何学中，确却能确定了一个平面；而在欧氏几何学中，确定一条曲线需要一个参数，确定一个平面需要定一条曲线需要一个参数，确定一个平面需要两个参数。两个参数。 生成规则：首先，将一正方形四等分为四个小正生成规则：首先，将一正方形四等分为四个小正方形，求出各个小正方形的中心并用三条直线连方形，求出各个小正方形的中心并用三条直线连接起来，如图接起来，如图8-13 n8-13 n0 0所示，可以使用两种连所示，可以使用两种连接方式：开口向上和开口向左。其次，将各个小接方式
21、：开口向上和开口向左。其次，将各个小正方形再细分为四个小正方形，用三条直线连接正方形再细分为四个小正方形，用三条直线连接各个小正方形的中心，也会有两种连接方式，如各个小正方形的中心，也会有两种连接方式，如图图8-13 n8-13 n1 1所示。依此类推，便形成所示。依此类推，便形成Peano-Peano-HilbertHilbert曲线。曲线。“病态病态”原因：一维曲线却能充满整个平面。原因：一维曲线却能充满整个平面。分形维数：分形维数：D=ln4/ln2=2D=ln4/ln2=2。 n0n1n28.2.4 S8.2.4 SIERPINSKIIERPINSKI垫片、地毯和海绵垫片、地毯和海绵
22、1915-1916 1915-1916年，波兰数学家谢尔宾年，波兰数学家谢尔宾斯基斯基(Sierpinski(Sierpinski，1882-1969)1882-1969)将三分将三分康托尔集的构造思想推广到二维平面和康托尔集的构造思想推广到二维平面和三维立体，构造出千疮百孔的谢尔宾斯三维立体，构造出千疮百孔的谢尔宾斯基垫片、地毯和海绵。基垫片、地毯和海绵。 1. 1.谢尔宾斯基垫片谢尔宾斯基垫片 生成规则：取一等边三角形，连接各边生成规则：取一等边三角形，连接各边中点将原三角形分成四个小三角形，然后舍中点将原三角形分成四个小三角形，然后舍弃位于中间的一个小三角形，如图弃位于中间的一个小三角形
23、，如图8-16 n8-16 n1 1所示。将剩下的其余三个小三角形按同样所示。将剩下的其余三个小三角形按同样方法继续分割，并舍弃位于中间的那个三角方法继续分割，并舍弃位于中间的那个三角形，如图形，如图8-16 n8-16 n2 2所示。如此不断地分割所示。如此不断地分割与舍弃，就能得到中间有大量孔隙的与舍弃，就能得到中间有大量孔隙的SierpinskiSierpinski垫片。垫片。“病态病态”原因：总周长趋于无穷，总面原因：总周长趋于无穷，总面积趋于零。也就是说：当用一维得尺积趋于零。也就是说：当用一维得尺度去测量时，其值趋于无穷大，当用度去测量时，其值趋于无穷大，当用二维尺度去度量时，其值
24、趋于零。二维尺度去度量时，其值趋于零。分形维数：分形维数：D=ln3/ln2=1.5849D=ln3/ln2=1.5849。 Sierpinski Sierpinski垫片生成元垫片生成元 2. 2.谢尔宾斯基地毯谢尔宾斯基地毯 生成规则：取一正方形，将其每条边三生成规则：取一正方形，将其每条边三等分，正方形被等分为九个面积相等的小等分，正方形被等分为九个面积相等的小正方形，舍弃位于中央的一个小正方形，正方形，舍弃位于中央的一个小正方形，如图如图8-18 n8-18 n1 1所示。将剩下的八个小正方所示。将剩下的八个小正方形按上面同样的方法继续分割，并舍弃位形按上面同样的方法继续分割，并舍弃位
25、于中间的那个小正方形，如图于中间的那个小正方形，如图8-18 n8-18 n2 2所所示。如此不断地分割与舍弃，就能得中间示。如此不断地分割与舍弃，就能得中间有大量空隙的有大量空隙的SierpinskiSierpinski地毯。地毯。 “病态病态”原因：总周长趋于无穷，总面原因：总周长趋于无穷，总面积趋于零。也就是说：当用一维得尺度积趋于零。也就是说：当用一维得尺度去测量时，其值趋于无穷大，当用二维去测量时，其值趋于无穷大，当用二维尺度去度量时，其值趋于零。尺度去度量时，其值趋于零。 分形维数：分形维数：D=ln8/ln3=1.8927D=ln8/ln3=1.8927。 n1n2n3n4 生成
26、元：生成元：SierpinskiSierpinski地毯是平面分形，具有自相似地毯是平面分形，具有自相似性。其生成元是把正方形分成九个小正方形，舍性。其生成元是把正方形分成九个小正方形，舍弃中间一个正方形，余下八个小正方形，如图弃中间一个正方形，余下八个小正方形，如图8-8-1919所示。正方形的左上角点和右下角点是生成元所示。正方形的左上角点和右下角点是生成元的设计顶点。的设计顶点。SierpinskiSierpinski地毯的递归调用是通过地毯的递归调用是通过反复使用生成元来取代每一个小正方形进行的。反复使用生成元来取代每一个小正方形进行的。 大正方形的左上角点和右下角点为：（大正方形的左
27、上角点和右下角点为：（x1x1，y1y1），），（x2x2，y2y2）。）。 3.3.谢尔宾斯基海绵谢尔宾斯基海绵 生成规则：将一个立方体沿其各个面等生成规则：将一个立方体沿其各个面等分为九个小立方体，舍弃位于体心的一个小分为九个小立方体，舍弃位于体心的一个小立方体，以及位于立方体六个面心的六个小立方体，以及位于立方体六个面心的六个小立方体，如图立方体，如图8-20 n8-20 n1 1所示。将二十个小所示。将二十个小立方体继续按相同的方法分割并舍弃位于立立方体继续按相同的方法分割并舍弃位于立方体体心和面心处的更小的立方体，如图方体体心和面心处的更小的立方体，如图8-8-19 n19 n2 2
28、所示。如此不断地分割与舍弃，就所示。如此不断地分割与舍弃，就能得到中间有大量空隙的能得到中间有大量空隙的SierpinskiSierpinski海绵。海绵。 “病态病态”原因：有限体积具有无限表面积，原因：有限体积具有无限表面积，也就是说：当用二维得尺度去测量时，其值也就是说：当用二维得尺度去测量时，其值趋于无穷大，当用三维尺度去度量时，其值趋于无穷大，当用三维尺度去度量时，其值趋于零。趋于零。分形维数：分形维数：D=ln20/ln3=2.7288D=ln20/ln3=2.7288。 n1n2n3n4 生成元：生成元：SierpinskiSierpinski海绵是分形立体，具海绵是分形立体，具
29、有自相似性。其生成元是把立方体分成二十七有自相似性。其生成元是把立方体分成二十七个小立方体，挖去立方体六个面心的小立方体个小立方体，挖去立方体六个面心的小立方体以及位于体心的一个小立方体，共挖去七个小以及位于体心的一个小立方体，共挖去七个小立方体，见图立方体，见图8-218-21。SierpinskiSierpinski海绵的递归调海绵的递归调用是通过反复使用生成元来取代每一个小正方用是通过反复使用生成元来取代每一个小正方体进行的。体进行的。 每个立方体在图形显示上是由前面、顶面每个立方体在图形显示上是由前面、顶面和右面三个面构成的。设正方形的左上角点为和右面三个面构成的。设正方形的左上角点为
30、（x x，y y），边长为），边长为d d。对于顶面和右面，由于。对于顶面和右面，由于其为平行四边形，其夹角为其为平行四边形，其夹角为4545的斜边的水平的斜边的水平投影投影 DXDXd dcos(/4)cos(/4)， 垂直投影垂直投影DYDYd dsin(/4)sin(/4)。因为。因为DXDXDYDY，所，所以全部以以全部以DXDX代替。代替。 SierpinskiSierpinski海绵生成元海绵生成元生成元结构生成元结构8.2.5 C8.2.5 C字曲线字曲线 生成规则：以一条直线段为斜边，拉出一个等腰直角生成规则：以一条直线段为斜边，拉出一个等腰直角三角形，如图三角形，如图8-25
31、 n8-25 n1 1所示。以该三角形的两条直所示。以该三角形的两条直角边分别为斜边，再拉出两个等腰直角三角形，如图角边分别为斜边，再拉出两个等腰直角三角形，如图8-25 n8-25 n2 2所示。依此类推，便形成了类似字母所示。依此类推，便形成了类似字母C C的图的图形，如图形，如图8-25 n8-25 n1010所示，称为所示，称为C C字曲线。字曲线。 C C字曲线字曲线生成元：生成元：C C字曲线具有很强的自相似性，是字曲线具有很强的自相似性，是分形图形。生成元是等腰直角等边三角形。分形图形。生成元是等腰直角等边三角形。如图如图8-268-26所示。所示。C C字曲线的递归是通过反复字
32、曲线的递归是通过反复以生成元的直角边作为斜边拉出等腰直角三以生成元的直角边作为斜边拉出等腰直角三角形而建立起来的。角形而建立起来的。 C C字曲线生成元字曲线生成元8.2.6 C8.2.6 CALEYALEY树树 生成规则：以如图生成规则：以如图8-27n8-27n2 2所示二叉树为所示二叉树为基础，以每个分支为主树干，按照比例递归出另基础，以每个分支为主树干，按照比例递归出另一个二叉树，如图一个二叉树，如图8-27n8-27n3 3所示。依此类推，便所示。依此类推，便形成了疏密有致的分形树，称为形成了疏密有致的分形树，称为CaleyCaley树。树。 CaleyCaley树树生成元：生成元：
33、CaleyCaley树是完全自相似的分形结构。树是完全自相似的分形结构。生成元是二叉树生成元是二叉树 8.3 L8.3 L系统模型系统模型L L系统是美国生物学家系统是美国生物学家AristidAristid LindenmayerLindenmayer提出的提出的研究植物形态与生长的描述方法，起初只用于描述研究植物形态与生长的描述方法，起初只用于描述植物的拓扑结构，即植物的主干与旁支之间的相邻植物的拓扑结构，即植物的主干与旁支之间的相邻关系，后来把几何解释加进描述过程，形成所谓的关系，后来把几何解释加进描述过程，形成所谓的L L系统。系统。19841984年，年，A.R.SmithA.R.S
34、mith首次将首次将L L系统与计算机图系统与计算机图形学结合起来，为计算机模拟植物生长提供了一个形学结合起来，为计算机模拟植物生长提供了一个有力的工具。有力的工具。1 1 文法模型文法模型L L系统是一种形式语言，包括：系统是一种形式语言，包括：（1 1）字母表：使用到的字母）字母表：使用到的字母（2 2）公理：初识字母）公理：初识字母（3 3）生成规则：字母的变换形式）生成规则：字母的变换形式8.3.1 L8.3.1 L系统文法系统文法2 2 绘图规则绘图规则设想一只乌龟在海滩爬行，其状态用设想一只乌龟在海滩爬行，其状态用3 3个参数个参数描述描述 。(1)F(1)F：向前爬行一步：向前爬
35、行一步(2)+(2)+：逆时针旋转：逆时针旋转(3)-(3)-：顺时针旋转：顺时针旋转(4)(4)：将当前状态压入堆栈，但不画线：将当前状态压入堆栈，但不画线(5)(5)：从堆栈中弹出一个状态作为当前状态，但不：从堆栈中弹出一个状态作为当前状态，但不画线画线, ,x y8.3.2 Koch8.3.2 Koch曲线曲线 =+,1,2,;Koch由于曲线没有分支，所以不需要保存中间断点，也就是说不需要绘图规则中的和,这里取75 。替换规则如下：字母表为：F， -初始字母为：F生成规则为：FF+F-F+F替换结果如下步骤0,F;步骤F+F-F+F;步骤F +F-F+F + F+F-F+F -F+F-
36、F+F + F+F-F+F8.3.3 8.3.3 分形草分形草 =1 F2345在L系统文法模型中，记录分枝点需要使用和绘图规则,取20绘图规则：代表主干和旁支，步长为Len：树枝生长方向，逆时针方向 为正：树枝生长方向，顺时针方向 为负：存储分枝点：释放分枝点 +,1,2,替换规则如下：字母表为：F，-,.初始字母为：F生成规则为：FFF+F-F-F-F+F+F替换结果如下步骤0,F;步骤FF+F-F-F-F+F+F;步骤FF+F-F-F-F+F+F FF+F-F-F-F+F+F+ FF+F-F-F-F+F+F - FF+F-F-F-F+F+F- FF+F-F-F-F+F+F - F F+F
37、-F-F-F+F+F+ FF+F-F-F-F+F+F + FF+F-F-F-F+F+F 8.3.4 Peano-Hilbert8.3.4 Peano-Hilbert曲线曲线8.3.5 8.3.5 分形灌木丛分形灌木丛8.4 IFS8.4 IFS迭代函数系统模型迭代函数系统模型19851985年美国佐治亚大学的年美国佐治亚大学的M.F.BarnsleyM.F.Barnsley首先应用一首先应用一组仿射变换族模拟自然景物，并将仿射变换集称为组仿射变换族模拟自然景物，并将仿射变换集称为迭代函数系统。迭代函数系统。IFSIFS的基本思想是，分形具有局部与的基本思想是，分形具有局部与整体的自相似性，也就
38、是说局部是整体的一个小复整体的自相似性，也就是说局部是整体的一个小复制品，只是在大小、位置和方向上有所不同而已；制品，只是在大小、位置和方向上有所不同而已；而数学中的仿射变换是一种线性变换，正好具有把而数学中的仿射变换是一种线性变换，正好具有把图形放大、缩小旋转和平移的性质。因此，产生一图形放大、缩小旋转和平移的性质。因此，产生一个复制品的过程就相当于对图形进行一次压缩仿射个复制品的过程就相当于对图形进行一次压缩仿射变换。变换。8.4.1 8.4.1 仿射变换仿射变换10011xaxbyeycxdyfxabexycdfy 仿射变换的公式表示为仿射变换的齐次坐标矩阵表示为仿射变换最主要的性质是保
39、留了直线的仿射变换最主要的性质是保留了直线的“平平直性直性”和和“平行性平行性”。平直性：仿射变换是线性变换，直线段经仿平直性：仿射变换是线性变换，直线段经仿射变换后仍为直线段，并且保持直线上点的射变换后仍为直线段，并且保持直线上点的定比关系不变。定比关系不变。平行性：两条平行直线经仿射变换后，仍然平行性：两条平行直线经仿射变换后，仍然保持平行。保持平行。8.4.2 IFS8.4.2 IFS1.压缩仿射变换2.IFS码的计算3.初始值问题压缩映射定理压缩映射定理(, )( ),0,1,2lim( )fnfnfnfXXX dfxXxXfx nxfxxf设 ：是完备距离空间上的一个压缩映射，则 具
40、有唯一的不动点，而且对任一个，序列收敛于 ，即压缩映射定理给出了 不动点的存在性和唯一性，也是用迭代函数系统绘图的理论依据。8.4.3 Koch8.4.3 Koch曲线曲线11/300101/3010011xxyy xy第 段直线，只进行比例变换S =S =1/32101/300cossin00101/30sincos0001001001101/31/300cos60sin60001001/30sin60cos6000010010011/63 /61/33 /61/60001eTf 第 段直线，平移、比例、旋转221/63 /61/33 /61/6010011xxyy 故第 段直线31/63
41、/61/ 23 /61/63 /610011xxyy 第3段直线41/302/301/3010011xxyy 第4段直线 向右平移2/3，长度缩小1/312341/3001/3001/ 41/63 /63 /61/61/301/ 41/63 /63 /61/61/ 23 /61/ 41/3001/32/301/ 4iiiiiiiiKochabcdefP曲线的IFS码8.4.4 Sierpinski8.4.4 Sierpinski垫片垫片1231/ 2001/ 2001/ 41/ 2001/ 21/ 201/ 41/ 2001/ 21/ 41/ 21/ 4iiiiiiiiabcdefPKOCH曲
42、线算法给定不同的递归深度，绘制给定不同的递归深度，绘制KochKoch曲线：曲线：算法设计算法设计(1)(1)输入递归深度输入递归深度n n和夹角和夹角thetatheta。(2)(2)计算生成元递归计算生成元递归n n次后的最小线元长度次后的最小线元长度(3)(3)确定确定KochKoch曲线的起点。曲线的起点。(4)(4)先绘制第一段直线，然后改变夹角先绘制第一段直线，然后改变夹角alpha,alpha,分别绘制其分别绘制其余余3 3段直线。段直线。(5)(5)执行递归子程序，对生成元的各部分进行递归并绘制执行递归子程序，对生成元的各部分进行递归并绘制曲线。曲线。KOCH曲线文法模型算法给
43、定不同的递归深度，使用给定不同的递归深度，使用L L系统模型绘制系统模型绘制KochKoch曲线：曲线：算法设计算法设计(1)(1)定义包含结点位置和角度的结点类定义包含结点位置和角度的结点类代表结点的状态（代表结点的状态（x,y,alphax,y,alpha）(2)(2)输入递归深度输入递归深度n n和夹角和夹角thetatheta。(3)(3)计算生成元递归计算生成元递归n n次后的最小线元长度次后的最小线元长度(4)(4)根据根据n n生成规则字符串的替换。生成规则字符串的替换。(5)(5)访问最终公理的每一个字母，根据绘图规则绘制图形。访问最终公理的每一个字母，根据绘图规则绘制图形。K
44、OCH曲线的IFS图形算法算法设计算法设计(1)(1)定义二维数组定义二维数组Code47,Code47,读入读入4 4个仿射变换的个仿射变换的IFSIFS码码(2)(2)设定循环次数为设定循环次数为100000100000(3)(3)生成随机数生成随机数R R，在，在0101之间之间(4)(4)分配仿射变换的概率空间。分配仿射变换的概率空间。(5)(5)判断随机数判断随机数R R落在哪一个概率空间，并调用相应的仿射落在哪一个概率空间，并调用相应的仿射变换所具有的变换所具有的IFSIFS码，赋给相应的仿射变换系数码，赋给相应的仿射变换系数(6)(6)进行仿射变换。进行仿射变换。(7)(7)根据
45、概率调整根据概率调整RGBRGB函数的分量，绘制点。函数的分量，绘制点。(8)(8)循环（循环（2 2）- -（7 7）(9)(9)完成循环次数结束完成循环次数结束8.5 8.5 本章小结本章小结 分形几何是科学与艺术相融合的一门新学科，分形几何是科学与艺术相融合的一门新学科，是计算机图形学的一个崭新的应用领域。计算机图是计算机图形学的一个崭新的应用领域。计算机图形学搭建起了科学和艺术的桥梁，将枯燥的数学公形学搭建起了科学和艺术的桥梁，将枯燥的数学公式表现为具体的视觉感受。本章在介绍分形的基本式表现为具体的视觉感受。本章在介绍分形的基本原理、分维的计算方法等概念的基础上，主要讲解原理、分维的计
46、算方法等概念的基础上，主要讲解了了CantorCantor集、集、KochKoch曲线、曲线、Peano-HilbertPeano-Hilbert曲线、曲线、SierpinskiSierpinski垫片、垫片、SierpinskiSierpinski地毯、地毯、SierpinskiSierpinski海海绵等曲线的递归模型。在绵等曲线的递归模型。在L-L-系统模型中给出了文法系统模型中给出了文法生成规则，绘制了分形植物，生成规则，绘制了分形植物，L-L-系统的关键是确定系统的关键是确定生成规则。生成规则。IFSIFS方法是分形的最有特色的领域，确定方法是分形的最有特色的领域，确定了了IFSIFS码就可以绘制图形。同时码就可以绘制图形。同时IFSIFS算法也是分形图算法也是分形图形压缩的基础，有兴趣的读者可以参考相关书籍学形压缩的基础，有兴趣的读者可以参考相关书籍学习习。
