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

,ComputerGraphics,第八章分形几何,2,.,8.1分形和分维8.2递归模型8.3L系统模型8.4IFS迭代函数系统模型,本章内容,3,.,8.1分形和分维,真实的世界却并不规则，闪电不是直线，海岸线不是弧线，云团不是球体，山峦也不是锥体。自然界的许多对象是如此不规则和支离破碎，以致欧氏几何学不能真实有效地再现大自然。为了再现真实世界，必须选择新的工具，分形几何学应运而生。分形几何是以非规则物体为研究对象的几何学。由于闪电、海岸线、云团、山峦、海浪、野草、森林、火光等非规则物体在自然界里比比皆是，因此分形几何学又被称为描述大自然的几何学。,4,.,分形山,5,.,8.1.1分形的诞生8.1.2分形的基本特征8.1.3分形的定义8.1.4分形维数的定义,6,.,8.1.1分形的诞生,分形（Fractal）这个词，是由美籍法国数学家曼德尔布罗特（BenoitB.Mandelbrot）自己创造出来的，此词来源于拉丁文fractus，意为不规则、支离破碎。1967年曼德尔布罗特在美国科学杂志上发表了划时代的论文英国海岸线有多长？统计自相似与分数维，成为其分形思想萌芽的重要标志。1973年，在法兰西学院讲学期间，曼德尔布罗特提出了分形几何学的整体思想，并认为分数维是个可用于研究许多物理现象的有力工具。1982年曼德尔布罗特出版了大自然的分形几何学，引起了学术界的广泛重视，曼德尔布罗特也因此一举成名。,7,.,英国的海岸线,蕨类植物叶的自相似性,8,.,8.1.2分形的基本特征,1.自相似性自相似性是指局部与整体相似的性质。图8-3所示的是蕨类植物叶子上的细叶和整体叶子的相似性。分形图形都具有细节的无穷回归性，随着尺度的缩短都会得到更多的细节。分形理论发展到今天，如果一个对象的部分和整体具有自仿射变换的关系，也可以称之为分形。,9,.,2.无标度性标度是计量单位的刻度。比如长度的标度是米；重量的标度是公斤；面积的标度是平方米等。对欧氏几何学内的不同形体，可以选择不同的标度去度量。分形却不然，由于分形具有无穷嵌套的精细结构，自相似性使得其内部结构不存在特征长度。分形没有特征标度，也就是不能用标度去度量，成为无标度性。,10,.,8.1.3分形的定义,一般认为，满足下列条件的图形称为分形集：分形集具有任意尺度下的比例细节，或者说具有精细结构；分形集是不规则的，以致于不能用传统的几何语言来描述。分形集通常具有某种自相似性，或许是近似的或许是统计意义下的自相似。分形集在某种方式下定义的“分维数”一般大于它的拓扑维数。分形集的定义常常是非常简单的，或许是递归的。,11,.,8.1.4分形维数的定义,维数是几何对象的一个重要特征量，它是欧氏几何对学描述点的位置所需的独立坐标数目。为了定量地刻画分形，引入了分数维数的概念。分数维数与欧氏几何学中的整数维数相对应。分形理论认为，维数中可以包含有小数。把分数维数记为D，一般称为分数维或分维。分维的定义有很多，有相似维数、容量维数、豪斯道夫维数等。本章只介绍相似维数。,12,.,分维的计算公式为：,代表分维为和整体自相似的局部形体个数为相似比,13,.,对于直线：将一直线段二等分，则N=2，S=2，即2=21，所以，分维D=1,14,.,对于平面：将正方形四等分，则N=4，S=2，即4=22，所以，分维D=2,15,.,对于立体：将立方体八等分，N=8，S=2，即8=23，所以，分维D=3,16,.,对于典型的分形曲线，例如Koch曲线，构成方法如下：取一直线段，将其三等分，保留两端的两段，将中间一段拉起为等边三角形的两条边。N=4，S=3分维D=ln4/ln3=1.26186,17,.,从图中n5的递归图形中可以看出koch曲线点点连续，但点点不可导，属于病态曲线；koch曲线局部和整体相似，具有自相似性。因此可以使用koch曲线来模拟海岸线。根据曼德布罗特的计算，英国海岸线的分形维数为D=1.25。,18,.,8.2递归模型,分形图形的传统实现模型是递归模型。在调用一个函数的过程中，直接或间接地调用函数自身，称为递归调用。例如n！可以采用递归模型实现。即5！54！，而4！43！，1！1，递归公式表示如下：,longfac(intn)longf;if(n=0|n=1)f=1;elsef=fac(n-1)*n;returnf;,19,.,8.2.1Cantor集8.2.2Koch曲线8.2.3Peano-Hilbert曲线8.2.4Sierpinski垫片、地毯和海绵8.2.5C字曲线8.2.6Caley树,20,.,8.2.1Cantor集,集合论的创始人康托（G.Cantor，18451918）在1883年曾构造了一种三等分Cantor集，其几何表示如下：生成规则：取一段长度为L0的直线段，将其三等分，保留两端的线段，将中间一段抛弃，如图8-9的n1的操作；再将剩下的两段直线分别三等分，然后将其中间一段抛弃，如图8-9的n2的操作；依此类推，便形成了无数个尘埃似的散点，所以cantor三分集也称为cantor灰尘。“病态”原因：数目无穷多，但长度趋近于零。分形维数：Dln2/ln3=0.6309。,21,.,22,.,8.2.2Koch曲线,1904年，瑞典数学家科和（Koch，18701924）发现一种曲线，其几何表示如下：生成规则：取一段长度为L0的直线段，如图8-7n0所示，将其三等分，保留两端的线段，将中间一段改换成夹角为60的两个L0/3等长直线段，如图8-7n1所示；将长度为L0/3的4个直线段分别三等分，并将它们中间的一段改换成夹角为60的两个L0/9等长直线段，如图8-7n2所示。依此类推，便得到具有自相似结构的折线。如果在等边三角形上按上述规则在每边的中间各凸起一个小三角形，这样一直进行下去，则曲线形状近似为似一朵雪花，称为Koch雪花，如图8-11所示。,23,.,理论上可以证明这种不断构造的雪花周长是无穷的，但其面积却是有限的，这和传统的数学观念是不相符的，采用周长和面积都无法刻划出这种雪花的特点，欧氏几何学对描述这种雪花无能为力。“病态”原因：处处连续，处处不可导。分形维数：D=ln4/ln3=1.26186。,24,.,25,.,生成元：koch曲线是著名的分形曲线，具有自相似性。其中生成元是图8-12所示的图形。生成元的第一段直线段和第二段直线段之间的夹角可以为任意角度（090），不同的角度值生成的Koch曲线有很大差异。最常用的角度是60和85。生成元的起点和终点坐标分别为（ax，ay）和（bx，by），Koch曲线共由四条直线段构成。Koch曲线的递归调用是通过反复使用生成元来取代每一段直线而进行的。,26,.,8.2.3Peano-Hilbert曲线,意大利数学家皮亚诺（Peano，18581932），通过对一些古代装饰图案的研究，于1890年构造出一种奇怪的平面曲线，这条曲线蜿蜒向前，一笔绘成，并能充满整个平面。接着德国数学家希尔伯特(Hilbert，18621943)于1891年也构造出一种类型相同但比较简单的曲线。这种曲线被称为Peano-Hilbert曲线。,27,.,Peano-Hilbert曲线的出现，当时曾令当时的数学界大吃一惊：它是一条曲线，但又是一个平面；皮亚诺曲线的方程只有一个参数，但它却能确定了一个平面；而在欧氏几何学中，确定一条曲线需要一个参数，确定一个平面需要两个参数。,28,.,生成规则：首先，将一正方形四等分为四个小正方形，求出各个小正方形的中心并用三条直线连接起来，如图8-13n0所示，可以使用两种连接方式：开口向上和开口向左。其次，将各个小正方形再细分为四个小正方形，用三条直线连接各个小正方形的中心，也会有两种连接方式，如图8-13n1所示。依此类推，便形成Peano-Hilbert曲线。“病态”原因：一维曲线却能充满整个平面。分形维数：D=ln4/ln2=2。,29,.,n0,n1,n2,30,.,8.2.4Sierpinski垫片、地毯和海绵,1915-1916年，波兰数学家谢尔宾斯基(Sierpinski，1882-1969)将三分康托尔集的构造思想推广到二维平面和三维立体，构造出千疮百孔的谢尔宾斯基垫片、地毯和海绵。,31,.,1.谢尔宾斯基垫片生成规则：取一等边三角形，连接各边中点将原三角形分成四个小三角形，然后舍弃位于中间的一个小三角形，如图8-16n1所示。将剩下的其余三个小三角形按同样方法继续分割，并舍弃位于中间的那个三角形，如图8-16n2所示。如此不断地分割与舍弃，就能得到中间有大量孔隙的Sierpinski垫片。,32,.,“病态”原因：总周长趋于无穷，总面积趋于零。也就是说：当用一维得尺度去测量时，其值趋于无穷大，当用二维尺度去度量时，其值趋于零。分形维数：D=ln3/ln2=1.5849。,33,.,34,.,Sierpinski垫片生成元,35,.,2.谢尔宾斯基地毯生成规则：取一正方形，将其每条边三等分，正方形被等分为九个面积相等的小正方形，舍弃位于中央的一个小正方形，如图8-18n1所示。将剩下的八个小正方形按上面同样的方法继续分割，并舍弃位于中间的那个小正方形，如图8-18n2所示。如此不断地分割与舍弃，就能得中间有大量空隙的Sierpinski地毯。,36,.,“病态”原因：总周长趋于无穷，总面积趋于零。也就是说：当用一维得尺度去测量时，其值趋于无穷大，当用二维尺度去度量时，其值趋于零。分形维数：D=ln8/ln3=1.8927。,37,.,n1,n2,n3,n4,38,.,生成元：Sierpinski地毯是平面分形，具有自相似性。其生成元是把正方形分成九个小正方形，舍弃中间一个正方形，余下八个小正方形，如图8-19所示。正方形的左上角点和右下角点是生成元的设计顶点。Sierpinski地毯的递归调用是通过反复使用生成元来取代每一个小正方形进行的。大正方形的左上角点和右下角点为：（x1，y1），（x2，y2）。,39,.,40,.,3.谢尔宾斯基海绵生成规则：将一个立方体沿其各个面等分为九个小立方体，舍弃位于体心的一个小立方体，以及位于立方体六个面心的六个小立方体，如图8-20n1所示。将二十个小立方体继续按相同的方法分割并舍弃位于立方体体心和面心处的更小的立方体，如图8-19n2所示。如此不断地分割与舍弃，就能得到中间有大量空隙的Sierpinski海绵。,41,.,“病态”原因：有限体积具有无限表面积，也就是说：当用二维得尺度去测量时，其值趋于无穷大，当用三维尺度去度量时，其值趋于零。分形维数：D=ln20/ln3=2.7288。,42,.,n1,n2,n3,n4,43,.,生成元：Sierpinski海绵是分形立体，具有自相似性。其生成元是把立方体分成二十七个小立方体，挖去立方体六个面心的小立方体以及位于体心的一个小立方体，共挖去七个小立方体，见图8-21。Sierpinski海绵的递归调用是通过反复使用生成元来取代每一个小正方体进行的。,44,.,每个立方体在图形显示上是由前面、顶面和右面三个面构成的。设正方形的左上角点为（x，y），边长为d。对于顶面和右面，由于其为平行四边形，其夹角为45的斜边的水平投影DXdcos(/4)，垂直投影DYdsin(/4)。因为DXDY，所以全部以DX代替。,45,.,Sierpinski海绵生成元,46,.,生成元结构,47,.,8.2.5C字曲线,生成规则：以一条直线段为斜边，拉出一个等腰直角三角形，如图8-25n1所示。以该三角形的两条直角边分别为斜边，再拉出两个等腰直角三角形，如图8-25n2所示。依此类推，便形成了类似字母C的图形，如图8-25n10所示，称为C字曲线。,48,.,C字曲线,49,.,生成元：C字曲线具有很强的自相似性，是分形图形。生成元是等腰直角等边三角形。如图8-26所示。C字曲线的递归是通过反复以生成元的直角边作为斜边拉出等腰直角三角形而建立起来的。,C字曲线生成元,50,.,8.2.6Caley树,生成规则：以如图8-27n2所示二叉树为基础，以每个分支为主树干，按照比例递归出另一个二叉树，如图8-27n3所示。依此类推，便形成了疏密有致的分形树，称为Caley树。,51,.,Caley树,生成元：Caley树是完全自相似的分形结构。生成元是二叉树,52,.,8.3L系统模型,L系统是美国生物学家AristidLindenmayer提出的研究植物形态与生长的描述方法，起初只用于描述植物的拓扑结构，即植物的主干与旁支之间的相邻关系，后来把几何解释加进描述过程，形成所谓的L系统。1984年，A.R.Smith首次将L系统与计算机图形学结合起来，为计算机模拟植物生长提供了一个有力的工具。,53,.,1文法模型L系统是一种形式语言，包括：（1）字母表：使用到的字母（2）公理：初识字母（3）生成规则：字母的变换形式,8.3.1L系统文法,54,.,2绘图规则设想一只乌龟在海滩爬行，其状态用3个参数描述。(1)F：向前爬行一步(2)+：逆时针旋转(3)-：顺时针旋转(4)：将当前状态压入堆栈，但不画线(5)：从堆栈中弹出一个状态作为当前状态，但不画线,55,.,8.3.2Koch曲线,56,.,8.3.3分形草,57,.,58,.,8.3.4Peano-Hilbert曲线,8.3.5分形灌木丛,59,.,8.4IFS迭代函数系统模型,1985年美国佐治亚大学的M.F.Barnsley首先应用一组仿射变换族模拟自然景物，并将仿射变换集称为迭代函数系统。IFS的基本思想是，分形具有局部与整体的自相似性，也就是说局部是整体的一个小复制品，只是在大小、位置和方向上有所不同而已；而数学中的仿射变换是一种线性变换，正好具有把图形放大、缩小旋转和平移的性质。因此，产生一个复制品的过程就相当于对图形进行一次压缩仿射变换。,60,.,8.4.1仿射变换,61,.,仿射变换最主要的性质是保留了直线的“平直性”和“平行性”。平直性：仿射变换是线性变换，直线段经仿射变换后仍为直线段，并且保持直线上点的定比关系不变。平行性：两条平行直线经仿射变换后，仍然保持平行。,62,.,8.4.2IFS,1.压缩仿射变换2.IFS码的计算3.初始值问题,63,.,压缩映射定理,64,.,8.4.3Koch曲线,65,.,66,.,67,.,68,.,8.4.4Sierpinski垫片,69,.,Koch曲线算法,给定不同的递归深度，绘制Koch曲线：算法设计(1)输入递归深度n和夹角theta。(2)计算生成元递归n次后的最小线元长度(3)确定Koch曲线的起点。(4)先绘制第一段直线，然后改变夹角alpha,分别绘制其余3段直线。(5)执行递归子程序，对生成元的各部分进行递归并绘制曲线。,