计算机图形学基础教程课件

Computer Graphics第八章分形几何Computer第八章分形几何8.1

分形和分维8.2

递归模型8.3

L系统模型8.4

IFS迭代函数系统模型本章内容8.1分形和分维本章内容8.1分形和分维真实的世界却并不规则，闪电不是直线，海岸线不是弧线，云团不是球体，山峦也不是锥体。自然界的许多对象是如此不规则和支离破碎，以致欧氏几何学不能真实有效地再现大自然。为了再现真实世界，必须选择新的工具，分形几何学应运而生。分形几何是以非规则物体为研究对象的几何学。由于闪电、海岸线、云团、山峦、海浪、野草、森林、火光等非规则物体在自然界里比比皆是，因此分形几何学又被称为描述大自然的几何学。8.1分形和分维真实的世界却并不规则，闪电不是直线，海岸线不分形山

分形山8.1.1分形的诞生8.1.2分形的基本特征8.1.3分形的定义8.1.4分形维数的定义

8.1.1分形的诞生8.1.1分形的诞生

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

英国的海岸线蕨类植物叶的自相似性8.1.2分形的基本特征

1.自相似性自相似性是指局部与整体相似的性质。图8-3所示的是蕨类植物叶子上的细叶和整体叶子的相似性。

分形图形都具有细节的无穷回归性，随着尺度的缩短都会得到更多的细节。分形理论发展到今天，如果一个对象的部分和整体具有自仿射变换的关系，也可以称之为分形。8.1.2分形的基本特征1.自相似性2.无标度性

标度是计量单位的刻度。比如长度的标度是米；重量的标度是公斤；面积的标度是平方米等。对欧氏几何学内的不同形体，可以选择不同的标度去度量。

分形却不然，由于分形具有无穷嵌套的精细结构，自相似性使得其内部结构不存在特征长度。分形没有特征标度，也就是不能用标度去度量，成为无标度性。2.无标度性8.1.3分形的定义

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

维数是几何对象的一个重要特征量，它是欧氏几何对学描述点的位置所需的独立坐标数目。为了定量地刻画分形，引入了分数维数的概念。分数维数与欧氏几何学中的整数维数相对应。分形理论认为，维数中可以包含有小数。把分数维数记为D，一般称为分数维或分维。分维的定义有很多，有相似维数、容量维数、豪斯道夫维数等。本章只介绍相似维数。8.1.4分形维数的定义维数是几何对象的一个重要特征量，分维的计算公式为：代表分维为和整体自相似的局部形体个数为相似比分维的计算公式为：代表分维⑴对于直线：将一直线段二等分，则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⑷对于典型的分形曲线，例如Koch曲线，构成方法如下：从图中n＝5的递归图形中可以看出koch曲线点点连续，但点点不可导，属于病态曲线；koch曲线局部和整体相似，具有自相似性。因此可以使用koch曲线来模拟海岸线。根据曼德布罗特的计算，英国海岸线的分形维数为D=1.25。

从图中n＝5的递归图形中可以看出koch曲线点点连续，但点点8.2递归模型

分形图形的传统实现模型是递归模型。在调用一个函数的过程中，直接或间接地调用函数自身，称为递归调用。例如n！可以采用递归模型实现。即5！＝5×4！，而4！＝4×3！，……，1！＝1，递归公式表示如下：longfac(intn){longf;if(n==0||n==1)f=1;elsef=fac(n-1)*n;returnf;}8.2递归模型分形图形的传统实现模型是递归模型。在调用一个8.2.1Cantor集8.2.2Koch曲线8.2.3Peano-Hilbert曲线8.2.4Sierpinski垫片、地毯和海绵8.2.5C字曲线8.2.6Caley树8.2.1Cantor集8.2.1Cantor集

集合论的创始人康托（G.Cantor，1845～1918）在1883年曾构造了一种三等分Cantor集，其几何表示如下：生成规则：取一段长度为L0的直线段，将其三等分，保留两端的线段，将中间一段抛弃，如图8-9的n＝1的操作；再将剩下的两段直线分别三等分，然后将其中间一段抛弃，如图8-9的n＝2的操作；依此类推，便形成了无数个尘埃似的散点，所以cantor三分集也称为cantor灰尘。“病态”原因：数目无穷多，但长度趋近于零。分形维数：D＝ln2/ln3=0.6309。8.2.1Cantor集集合论的创始人康托（G.Cant计算机图形学基础教程课件8.2.2Koch曲线

1904年，瑞典数学家科和（Koch，1870～1924）发现一种曲线，其几何表示如下：生成规则：取一段长度为L0的直线段，如图8-7n＝0所示，将其三等分，保留两端的线段，将中间一段改换成夹角为60°的两个L0/3等长直线段，如图8-7n＝1所示；将长度为L0/3的4个直线段分别三等分，并将它们中间的一段改换成夹角为60°的两个L0/9等长直线段，如图8-7n＝2所示。依此类推，便得到具有自相似结构的折线。如果在等边三角形上按上述规则在每边的中间各凸起一个小三角形，这样一直进行下去，则曲线形状近似为似一朵雪花，称为Koch雪花，如图8-11所示。8.2.2Koch曲线1904年，瑞典数学家科和（Koc理论上可以证明这种不断构造的雪花周长是无穷的，但其面积却是有限的，这和传统的数学观念是不相符的，采用周长和面积都无法刻划出这种雪花的特点，欧氏几何学对描述这种雪花无能为力。

“病态”原因：处处连续，处处不可导。

分形维数：D=ln4/ln3=1.26186。理论上可以证明这种不断构造的雪花周长是无穷的，但其面积却是有计算机图形学基础教程课件生成元：koch曲线是著名的分形曲线，具有自相似性。其中生成元是图8-12所示的图形。生成元的第一段直线段和第二段直线段之间的夹角可以为任意角度（0°<θ<90°），不同的角度值生成的Koch曲线有很大差异。最常用的角度是θ＝60°和θ＝85°。生成元的起点和终点坐标分别为（ax，ay）和（bx，by），Koch曲线共由四条直线段构成。Koch曲线的递归调用是通过反复使用生成元来取代每一段直线而进行的。生成元：koch曲线是著名的分形曲线，具有自相似8.2.3Peano-Hilbert曲线

意大利数学家皮亚诺（Peano，1858～1932），通过对一些古代装饰图案的研究，于1890年构造出一种奇怪的平面曲线，这条曲线蜿蜒向前，一笔绘成，并能充满整个平面。接着德国数学家希尔伯特(Hilbert，1862～1943)于1891年也构造出一种类型相同但比较简单的曲线。这种曲线被称为Peano-Hilbert曲线。8.2.3Peano-Hilbert曲线意大Peano-Hilbert曲线的出现，当时曾令当时的数学界大吃一惊：

它是一条曲线，但又是一个平面；皮亚诺曲线的方程只有一个参数，但它却能确定了一个平面；而在欧氏几何学中，确定一条曲线需要一个参数，确定一个平面需要两个参数。Peano-Hilbert曲线的出现，当时曾令当生成规则：首先，将一正方形四等分为四个小正方形，求出各个小正方形的中心并用三条直线连接起来，如图8-13n＝0所示，可以使用两种连接方式：开口向上和开口向左。其次，将各个小正方形再细分为四个小正方形，用三条直线连接各个小正方形的中心，也会有两种连接方式，如图8-13n＝1所示。依此类推，便形成Peano-Hilbert曲线。“病态”原因：一维曲线却能充满整个平面。分形维数：D=ln4/ln2=2。生成规则：首先，将一正方形四等分为四个小正方形，求出各个小正n＝0n＝1n＝2n＝0n＝1n＝28.2.4Sierpinski垫片、地毯和海绵

1915-1916年，波兰数学家谢尔宾斯基(Sierpinski，1882-1969)将三分康托尔集的构造思想推广到二维平面和三维立体，构造出千疮百孔的谢尔宾斯基垫片、地毯和海绵。8.2.4Sierpinski垫片、地毯和海绵1.谢尔宾斯基垫片生成规则：取一等边三角形，连接各边中点将原三角形分成四个小三角形，然后舍弃位于中间的一个小三角形，如图8-16n＝1所示。将剩下的其余三个小三角形按同样方法继续分割，并舍弃位于中间的那个三角形，如图8-16n＝2所示。如此不断地分割与舍弃，就能得到中间有大量孔隙的Sierpinski垫片。1.谢尔宾斯基垫片“病态”原因：总周长趋于无穷，总面积趋于零。也就是说：当用一维得尺度去测量时，其值趋于无穷大，当用二维尺度去度量时，其值趋于零。分形维数：D=ln3/ln2=1.5849。“病态”原因：总周长趋于无穷，总面积趋于零。也就是说：当用一计算机图形学基础教程课件Sierpinski垫片生成元Sierpinski垫片生成元2.谢尔宾斯基地毯生成规则：取一正方形，将其每条边三等分，正方形被等分为九个面积相等的小正方形，舍弃位于中央的一个小正方形，如图8-18n＝1所示。将剩下的八个小正方形按上面同样的方法继续分割，并舍弃位于中间的那个小正方形，如图8-18n＝2所示。如此不断地分割与舍弃，就能得中间有大量空隙的Sierpinski地毯。2.谢尔宾斯基地毯

“病态”原因：总周长趋于无穷，总面积趋于零。也就是说：当用一维得尺度去测量时，其值趋于无穷大，当用二维尺度去度量时，其值趋于零。分形维数：D=ln8/ln3=1.8927。“病态”原因：总周长趋于无穷，总面积趋于零。也就是说：n＝1n＝2n＝3n＝4n＝2n＝4生成元：Sierpinski地毯是平面分形，具有自相似性。其生成元是把正方形分成九个小正方形，舍弃中间一个正方形，余下八个小正方形，如图8-19所示。正方形的左上角点和右下角点是生成元的设计顶点。Sierpinski地毯的递归调用是通过反复使用生成元来取代每一个小正方形进行的。大正方形的左上角点和右下角点为：（x1，y1），（x2，y2）。生成元：Sierpinski地毯是平面分形，具有自相似性。计算机图形学基础教程课件

3.谢尔宾斯基海绵生成规则：将一个立方体沿其各个面等分为九个小立方体，舍弃位于体心的一个小立方体，以及位于立方体六个面心的六个小立方体，如图8-20n＝1所示。将二十个小立方体继续按相同的方法分割并舍弃位于立方体体心和面心处的更小的立方体，如图8-19n＝2所示。如此不断地分割与舍弃，就能得到中间有大量空隙的Sierpinski海绵。3.谢尔宾斯基海绵“病态”原因：有限体积具有无限表面积，也就是说：当用二维得尺度去测量时，其值趋于无穷大，当用三维尺度去度量时，其值趋于零。分形维数：D=ln20/ln3=2.7288。“病态”原因：有限体积具有无限表面积，也就是说：当用二维得尺n＝1n＝2n＝3n＝4n＝1n＝2n＝3n＝4生成元：Sierpinski海绵是分形立体，具有自相似性。其生成元是把立方体分成二十七个小立方体，挖去立方体六个面心的小立方体以及位于体心的一个小立方体，共挖去七个小立方体，见图8-21。Sierpinski海绵的递归调用是通过反复使用生成元来取代每一个小正方体进行的。生成元：Sierpinski海绵是分形立体，具有每个立方体在图形显示上是由前面、顶面和右面三个面构成的。设正方形的左上角点为（x，y），边长为d。对于顶面和右面，由于其为平行四边形，其夹角为45°的斜边的水平投影DX＝d×cos(π/4)，垂直投影DY＝d×sin(π/4)。因为DX＝DY，所以全部以DX代替。每个立方体在图形显示上是由前面、顶面和右面三个面构Sierpinski海绵生成元

Sierpinski海绵生成元生成元结构

生成元结构8.2.5C字曲线

生成规则：以一条直线段为斜边，拉出一个等腰直角三角形，如图8-25n＝1所示。以该三角形的两条直角边分别为斜边，再拉出两个等腰直角三角形，如图8-25n＝2所示。依此类推，便形成了类似字母C的图形，如图8-25n＝10所示，称为C字曲线。8.2.5C字曲线生成规则：以一条直线段为斜边，拉出一个

C字曲线

C字曲线生成元：C字曲线具有很强的自相似性，是分形图形。生成元是等腰直角等边三角形。如图8-26所示。C字曲线的递归是通过反复以生成元的直角边作为斜边拉出等腰直角三角形而建立起来的。C字曲线生成元

生成元：C字曲线具有很强的自相似性，是分形图形。生成元是等腰8.2.6Caley树

生成规则：以如图8-27n＝2所示二叉树为基础，以每个分支为主树干，按照比例递归出另一个二叉树，如图8-27n＝3所示。依此类推，便形成了疏密有致的分形树，称为Caley树。8.2.6Caley树Caley树

生成元：Caley树是完全自相似的分形结构。生成元是二叉树Caley树生成元：Caley树是完全自相似的分形结构。生8.3L系统模型L系统是美国生物学家AristidLindenmayer提出的研究植物形态与生长的描述方法，起初只用于描述植物的拓扑结构，即植物的主干与旁支之间的相邻关系，后来把几何解释加进描述过程，形成所谓的L系统。1984年，A.R.Smith首次将L系统与计算机图形学结合起来，为计算机模拟植物生长提供了一个有力的工具。8.3L系统模型1文法模型L系统是一种形式语言，包括：（1）字母表：使用到的字母（2）公理：初识字母（3）生成规则：字母的变换形式8.3.1L系统文法1文法模型8.3.1L系统文法2绘图规则设想一只乌龟在海滩爬行，其状态用3个参数描述。(1)F：向前爬行一步(2)+：逆时针旋转(3)-：顺时针旋转(4)[：将当前状态压入堆栈，但不画线(5)]：从堆栈中弹出一个状态作为当前状态，但不画线2绘图规则8.3.2Koch曲线8.3.2Koch曲线8.3.3分形草8.3.3分形草计算机图形学基础教程课件8.3.4Peano-Hilbert曲线8.3.5分形灌木丛8.3.4Peano-Hilbert曲线8.3.5分形灌8.4IFS迭代函数系统模型1985年美国佐治亚大学的M.F.Barnsley首先应用一组仿射变换族模拟自然景物，并将仿射变换集称为迭代函数系统。IFS的基本思想是，分形具有局部与整体的自相似性，也就是说局部是整体的一个小复制品，只是在大小、位置和方向上有所不同而已；而数学中的仿射变换是一种线性变换，正好具有把图形放大、缩小旋转和平移的性质。因此，产生一个复制品的过程就相当于对图形进行一次压缩仿射变换。8.4IFS迭代函数系统模型1985年美国佐治亚大学的M.8.4.1仿射变换8.4.1仿射变换仿射变换最主要的性质是保留了直线的“平直性”和“平行性”。平直性：仿射变换是线性变换，直线段经仿射变换后仍为直线段，并且保持直线上点的定比关系不变。平行性：两条平行直线经仿射变换后，仍然保持平行。仿射变换最主要的性质是保留了直线的“平直性”和“平行性”。8.4.2IFS1.压缩仿射变换

2.IFS码的计算

3.初始值问题8.4.2IFS1.压缩仿射变换

2.IFS码的计算

压缩映射定理压缩映射定理8.4.3Koch曲线8.4.3Koch曲线计算机图形学基础教程课件计算机图形学基础教程课件计算机图形学基础教程课件8.4.4Sierpinski垫片8.4.4Sierpinski垫片Koch曲线算法给定不同的递归深度，绘制Koch曲线：算法设计(1)输入递归深度n和夹角theta。(2)计算生成元递归n次后的最小线元长度(3)确定Koch曲线的起点。(4)先绘制第一段直线，然后改变夹角alpha,分别绘制其余3段直线。(5)执行递归子程序，对生成元的各部分进行递归并绘制曲线。Koch曲线算法给定不同的递归深度，绘制Koch曲线：Koch曲线文法模型算法给定不同的递归深度，使用L系统模型绘制Koch曲线：算法设计(1)定义包含结点位置和角度的结点类代表结点的状态（x,y,alpha）(2)输入递归深度n和夹角theta。(3)计算生成元递归n次后的最小线元长度(4)根据n生成规则字符串的替换。(5)访问最终公理的每一个字母，根据绘图规则绘制图形。Koch曲线文法模型算法给定不同的递归深度，使用L系统模型绘Koch曲线的IFS图形算法算法设计(1)定义二维数组Code[4][7],读入4个仿射变换的IFS码(2)设定循环次数为100000(3)生成随机数R，在0~1之间(4)分配仿射变换的概率空间。(5)判断随机数R落在哪一个概率空间，并调用相应的仿射变换所具有的IFS码，赋给相应的仿射变换系数(6)进行仿射变换。(7)根据概率调整RGB函数的分量，绘制点。(8)循环（2）-（7）(9)完成循环次数结束Koch曲线的IFS图形算法算法设计8.5本章小结

分形几何是科学与艺术相融合的一门新学科，是计算机图形学的一个崭新的应用领域。计算机图形学搭建起了科学和艺术的桥梁，将枯燥的数学公式表现为具体的视觉感受。本章在介绍分形的基本原理、分维的计算方法等概念的基础上，主要讲解了Cantor集、Koch曲线、Peano-Hilbert曲线、Sierpinski垫片、Sierpinski地毯、Sierpinski海绵等曲线的递归模型。在L-系统模型中给出了文法生成规则，绘制了分形植物，L-系统的关键是确定生成规则。IFS方法是分形的最有特色的领域，确定了IFS码就可以绘制图形。同时IFS算法也是分形图形压缩的基础，有兴趣的读者可以参考相关书籍学习。8.5本章小结分形几何是科学与艺术相融合的一门新学科，是Computer Graphics第八章分形几何Computer第八章分形几何8.1

分形和分维8.2

递归模型8.3

L系统模型8.4

IFS迭代函数系统模型本章内容8.1分形和分维本章内容8.1分形和分维真实的世界却并不规则，闪电不是直线，海岸线不是弧线，云团不是球体，山峦也不是锥体。自然界的许多对象是如此不规则和支离破碎，以致欧氏几何学不能真实有效地再现大自然。为了再现真实世界，必须选择新的工具，分形几何学应运而生。分形几何是以非规则物体为研究对象的几何学。由于闪电、海岸线、云团、山峦、海浪、野草、森林、火光等非规则物体在自然界里比比皆是，因此分形几何学又被称为描述大自然的几何学。8.1分形和分维真实的世界却并不规则，闪电不是直线，海岸线不分形山

分形山8.1.1分形的诞生8.1.2分形的基本特征8.1.3分形的定义8.1.4分形维数的定义

8.1.1分形的诞生8.1.1分形的诞生

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

英国的海岸线蕨类植物叶的自相似性8.1.2分形的基本特征

1.自相似性自相似性是指局部与整体相似的性质。图8-3所示的是蕨类植物叶子上的细叶和整体叶子的相似性。

分形图形都具有细节的无穷回归性，随着尺度的缩短都会得到更多的细节。分形理论发展到今天，如果一个对象的部分和整体具有自仿射变换的关系，也可以称之为分形。8.1.2分形的基本特征1.自相似性2.无标度性

标度是计量单位的刻度。比如长度的标度是米；重量的标度是公斤；面积的标度是平方米等。对欧氏几何学内的不同形体，可以选择不同的标度去度量。

分形却不然，由于分形具有无穷嵌套的精细结构，自相似性使得其内部结构不存在特征长度。分形没有特征标度，也就是不能用标度去度量，成为无标度性。2.无标度性8.1.3分形的定义

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

维数是几何对象的一个重要特征量，它是欧氏几何对学描述点的位置所需的独立坐标数目。为了定量地刻画分形，引入了分数维数的概念。分数维数与欧氏几何学中的整数维数相对应。分形理论认为，维数中可以包含有小数。把分数维数记为D，一般称为分数维或分维。分维的定义有很多，有相似维数、容量维数、豪斯道夫维数等。本章只介绍相似维数。8.1.4分形维数的定义维数是几何对象的一个重要特征量，分维的计算公式为：代表分维为和整体自相似的局部形体个数为相似比分维的计算公式为：代表分维⑴对于直线：将一直线段二等分，则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⑷对于典型的分形曲线，例如Koch曲线，构成方法如下：从图中n＝5的递归图形中可以看出koch曲线点点连续，但点点不可导，属于病态曲线；koch曲线局部和整体相似，具有自相似性。因此可以使用koch曲线来模拟海岸线。根据曼德布罗特的计算，英国海岸线的分形维数为D=1.25。

从图中n＝5的递归图形中可以看出koch曲线点点连续，但点点8.2递归模型

分形图形的传统实现模型是递归模型。在调用一个函数的过程中，直接或间接地调用函数自身，称为递归调用。例如n！可以采用递归模型实现。即5！＝5×4！，而4！＝4×3！，……，1！＝1，递归公式表示如下：longfac(intn){longf;if(n==0||n==1)f=1;elsef=fac(n-1)*n;returnf;}8.2递归模型分形图形的传统实现模型是递归模型。在调用一个8.2.1Cantor集8.2.2Koch曲线8.2.3Peano-Hilbert曲线8.2.4Sierpinski垫片、地毯和海绵8.2.5C字曲线8.2.6Caley树8.2.1Cantor集8.2.1Cantor集

集合论的创始人康托（G.Cantor，1845～1918）在1883年曾构造了一种三等分Cantor集，其几何表示如下：生成规则：取一段长度为L0的直线段，将其三等分，保留两端的线段，将中间一段抛弃，如图8-9的n＝1的操作；再将剩下的两段直线分别三等分，然后将其中间一段抛弃，如图8-9的n＝2的操作；依此类推，便形成了无数个尘埃似的散点，所以cantor三分集也称为cantor灰尘。“病态”原因：数目无穷多，但长度趋近于零。分形维数：D＝ln2/ln3=0.6309。8.2.1Cantor集集合论的创始人康托（G.Cant计算机图形学基础教程课件8.2.2Koch曲线

1904年，瑞典数学家科和（Koch，1870～1924）发现一种曲线，其几何表示如下：生成规则：取一段长度为L0的直线段，如图8-7n＝0所示，将其三等分，保留两端的线段，将中间一段改换成夹角为60°的两个L0/3等长直线段，如图8-7n＝1所示；将长度为L0/3的4个直线段分别三等分，并将它们中间的一段改换成夹角为60°的两个L0/9等长直线段，如图8-7n＝2所示。依此类推，便得到具有自相似结构的折线。如果在等边三角形上按上述规则在每边的中间各凸起一个小三角形，这样一直进行下去，则曲线形状近似为似一朵雪花，称为Koch雪花，如图8-11所示。8.2.2Koch曲线1904年，瑞典数学家科和（Koc理论上可以证明这种不断构造的雪花周长是无穷的，但其面积却是有限的，这和传统的数学观念是不相符的，采用周长和面积都无法刻划出这种雪花的特点，欧氏几何学对描述这种雪花无能为力。

“病态”原因：处处连续，处处不可导。

分形维数：D=ln4/ln3=1.26186。理论上可以证明这种不断构造的雪花周长是无穷的，但其面积却是有计算机图形学基础教程课件生成元：koch曲线是著名的分形曲线，具有自相似性。其中生成元是图8-12所示的图形。生成元的第一段直线段和第二段直线段之间的夹角可以为任意角度（0°<θ<90°），不同的角度值生成的Koch曲线有很大差异。最常用的角度是θ＝60°和θ＝85°。生成元的起点和终点坐标分别为（ax，ay）和（bx，by），Koch曲线共由四条直线段构成。Koch曲线的递归调用是通过反复使用生成元来取代每一段直线而进行的。生成元：koch曲线是著名的分形曲线，具有自相似8.2.3Peano-Hilbert曲线

意大利数学家皮亚诺（Peano，1858～1932），通过对一些古代装饰图案的研究，于1890年构造出一种奇怪的平面曲线，这条曲线蜿蜒向前，一笔绘成，并能充满整个平面。接着德国数学家希尔伯特(Hilbert，1862～1943)于1891年也构造出一种类型相同但比较简单的曲线。这种曲线被称为Peano-Hilbert曲线。8.2.3Peano-Hilbert曲线意大Peano-Hilbert曲线的出现，当时曾令当时的数学界大吃一惊：

它是一条曲线，但又是一个平面；皮亚诺曲线的方程只有一个参数，但它却能确定了一个平面；而在欧氏几何学中，确定一条曲线需要一个参数，确定一个平面需要两个参数。Peano-Hilbert曲线的出现，当时曾令当生成规则：首先，将一正方形四等分为四个小正方形，求出各个小正方形的中心并用三条直线连接起来，如图8-13n＝0所示，可以使用两种连接方式：开口向上和开口向左。其次，将各个小正方形再细分为四个小正方形，用三条直线连接各个小正方形的中心，也会有两种连接方式，如图8-13n＝1所示。依此类推，便形成Peano-Hilbert曲线。“病态”原因：一维曲线却能充满整个平面。分形维数：D=ln4/ln2=2。生成规则：首先，将一正方形四等分为四个小正方形，求出各个小正n＝0n＝1n＝2n＝0n＝1n＝28.2.4Sierpinski垫片、地毯和海绵

1915-1916年，波兰数学家谢尔宾斯基(Sierpinski，1882-1969)将三分康托尔集的构造思想推广到二维平面和三维立体，构造出千疮百孔的谢尔宾斯基垫片、地毯和海绵。8.2.4Sierpinski垫片、地毯和海绵1.谢尔宾斯基垫片生成规则：取一等边三角形，连接各边中点将原三角形分成四个小三角形，然后舍弃位于中间的一个小三角形，如图8-16n＝1所示。将剩下的其余三个小三角形按同样方法继续分割，并舍弃位于中间的那个三角形，如图8-16n＝2所示。如此不断地分割与舍弃，就能得到中间有大量孔隙的Sierpinski垫片。1.谢尔宾斯基垫片“病态”原因：总周长趋于无穷，总面积趋于零。也就是说：当用一维得尺度去测量时，其值趋于无穷大，当用二维尺度去度量时，其值趋于零。分形维数：D=ln3/ln2=1.5849。“病态”原因：总周长趋于无穷，总面积趋于零。也就是说：当用一计算机图形学基础教程课件Sierpinski垫片生成元Sierpinski垫片生成元2.谢尔宾斯基地毯生成规则：取一正方形，将其每条边三等分，正方形被等分为九个面积相等的小正方形，舍弃位于中央的一个小正方形，如图8-18n＝1所示。将剩下的八个小正方形按上面同样的方法继续分割，并舍弃位于中间的那个小正方形，如图8-18n＝2所示。如此不断地分割与舍弃，就能得中间有大量空隙的Sierpinski地毯。2.谢尔宾斯基地毯

“病态”原因：总周长趋于无穷，总面积趋于零。也就是说：当用一维得尺度去测量时，其值趋于无穷大，当用二维尺度去度量时，其值趋于零。分形维数：D=ln8/ln3=1.8927。“病态”原因：总周长趋于无穷，总面积趋于零。也就是说：n＝1n＝2n＝3n＝4n＝2n＝4生成元：Sierpinski地毯是平面分形，具有自相似性。其生成元是把正方形分成九个小正方形，舍弃中间一个正方形，余下八个小正方形，如图8-19所示。正方形的左上角点和右下角点是生成元的设计顶点。Sierpinski地毯的递归调用是通过反复使用生成元来取代每一个小正方形进行的。大正方形的左上角点和右下角点为：（x1，y1），（x2，y2）。生成元：Sierpinski地毯是平面分形，具有自相似性。计算机图形学基础教程课件

3.谢尔宾斯基海绵生成规则：将一个立方体沿其各个面等分为九个小立方体，舍弃位于体心的一个小立方体，以及位于立方体六个面心的六个小立方体，如图8-20n＝1所示。将二十个小立方体继续按相同的方法分割并舍弃位于立方体体心和面心处的更小的立方体，如图8-19n＝2所示。如此不断地分割与舍弃，就能得到中间有大量空隙的Sierpinski海绵。3.谢尔宾斯基海绵“病态”原因：有限体积具有无限表面积，也就是说：当用二维得尺度去测量时，其值趋于无穷大，当用三维尺度去度量时，其值趋于零。分形维数：D=ln20/ln3=2.7288。“病态”原因：有限体积具有无限表面积，也就是说：当用二维得尺n＝1n＝2n＝3n＝4n＝1n＝2n＝3n＝4生成元：Sierpinski海绵是分形立体，具有自相似性。其生成元是把立方体分成二十七个小立方体，挖去立方体六个面心的小立方体以及位于体心的一个小立方体，共挖去七个小立方体，见图8-21。Sierpinski海绵的递归调用是通过反复使用生成元来取代每一个小正方体进行的。生成元：Sierpinski海绵是分形立体，具有每个立方体在图形显示上是由前面、顶面和右面三个面构成的。设正方形的左上角点为（x，y），边长为d。对于顶面和右面，由于其为平行四边形，其夹角为45°的斜边的水平投影DX＝d×cos(π/4)，垂直投影DY＝d×sin(π/4)。因为DX＝DY，所以全部以DX代替。每个立方体在图形显示上是由前面、顶面和右面三个面构Sierpinski海绵生成元

Sierpinski海绵生成元生成元结构

生成元结构8.2.5C字曲线

生成规则：以一条直线段为斜边，拉出一个等腰直角三角形，如图8-25n＝1所示。以该三角形的两条直角边分别为斜边，再拉出两个等腰直角三角形，如图8-25n＝2所示。依此类推，便形成了类似字母C的图形，如图8-25n＝10所示，称为C字曲线。8.2.5C字曲线生成规则：以一条直线段为斜边，拉出一个

C字曲线

C字曲线生成元：C字曲线具有很强的自相似性，是分形图形。生成元是等腰直角等边三角形。如图8-26所示。C字曲线的递归是通过反复以生成元的直角边作为斜边拉出等腰直角三角形而建立起来的。C字曲线生成元

生成元：C字曲线具有很强的自相似性，是分形图形。生成元是等腰8.2.6Caley树

生成规则：以如图8-27n＝2所示二叉树为基础，以每个分支为主树干，按照比例递归出另一个二叉树，如图8-27n＝3所示。依此类推，便形成了疏密有致的分形树，称为Caley树。8.2.6Caley树Caley树

生成元：Caley树是完全自相似的分形结构。生成元是二叉树Caley树生成元：Caley树是完全自相似的分形结构。生8.3L系统模型L系统是美国生物学家AristidLindenmayer提出的研究植物形态与生长的描述方法，起初只用于描述植物的拓扑结构，即植物的主干与旁支之间的相邻关系，后来把几何解释加进描述过程，形成所谓的L系统。1984年，A.R.Smith首次将L系统与计算机图形学结合起来，为计算机模拟植物生长提供了一个有力的工具。8.3L系统模型1文法模型L系统是一种形式语言，包括：（1）字母表：使用到的字母（2）公理：初识字母（3）生成规则：字母的变换形式8.3.1L系统文法1文法模型8.3.1L系统文法2绘图规则设想一只乌龟在海滩爬行，其状态用3个参数描述。(1)F：向前爬行一步(2)+：逆时针旋转(3)-：顺时针旋转(4)[：将当前状态压入堆栈，但不画线(5)]：从