分形算法与程序设计PPT演示课件

参,1,第1章,初识分形,1.1Fractal的含义1.2分形的几何特征1.3分形的度量,1.4分形维数1.5分形是一种方法论1.6分形与计算机图形学,参,2,1.1,Fractal的含义,英文单词Fractal，在大陆被译为“分形”，在台湾被译为“碎形”。它是由美籍法国数学家曼德勃罗（BenoitMandelbrot）创造出来的。其含义是不规则的、破碎的、分数的。曼德勃罗是想用此词来描述自然界中传统欧几里得几何学所不能描述的一大类复杂无规的几何对象。,参,3,1.2,分形的几何特征,自相似性,自相似，便是局部与整体的相似。,自仿射性,自仿射性是自相似性的一种拓展。如果，将自相似性看成是局部到整体在各个方向上的等比例变换的结果的话，那么，自仿射性就是局部到整体在不同方向上的不等比例变换的结果。前者称为自相似变换，后者称为自仿射变换。,精细结构,任意小局部总是包含细致的结构。,参,4,1.3,分形的度量,（1）长度的测量Length(n=0)=1Length(n=1)=4/3Length(n=2)=16/9Length=lim(Length(n)=lim(4/3)=,n,n,n,参,5,1.3,分形的度量,（2）面积的测量Area(n0)=(13/6)/2=3/12Area(n1)=3/12(4/9)Area(n2)=3/12(4/9)2Area(n)=lim(3/12(4/9)n)=0,n,如上所述，koch曲线在一维欧氏空间中的度量为，在二维欧氏空间中的面积为0。如此看来，Koch曲线在传统欧氏空间中不可度量。,参,6,1.4,分形维数,分形维数是分形的很好的不变量，它一般是分数，用它可以把握住分形体的基本特征。,图a是边长为1的正方形，当边长变成原来的12时，原正方形中包含4个小正方形，如图b，而4=22；图c是边长为1的正立方体，当边长变成原来的12时，原正立方体中包含8个小正立方体，如图d，而8=23。,则有NkD,D=log(N)/log(k)这样Koch曲线的分形维数D=log(4)log(3)=1.2618,参,7,1.4,分形维数,对于实际的自然景物，我们可以用计盒维数的方法测量分维。,参,8,1.5,分形是一种方法论,沃尔夫奖（WolfPrize）在颁发给分形理论创始人曼德勃罗时的评语所说的，“分形几何改变了我们对世界的看法”。分形理论至少会在三个方面改变我们对世界的认识。首先，自然界中许多不规则的形态其背后都有规则，都可以用分形的方法建立模型并在计算机上构造出以假乱真的景象来，显然利用这套方法我们可以把世界压缩到几个分形规则中，便于携带和传播。其次，许多以前被认为是随机的现象，从分形理论的角度看并不是随机的，比如布朗运动、股票价格的波动、传染病的流行传播等，这为我们控制这些貌似随机的现象奠定了理论基础。最后，分形理论中的分数维概念，为我们认识世界中的复杂形态提供了一个新的尺度。复杂性科学是现代科学的前沿，在这门科学的研究过程中，发现了许多符合分形规则的复杂形态，而分数维是测量这些形态复杂程度的一种度量。也就是说，我们找到了对复杂性做定量分析的工具。,参,9,1.6,分形与计算机图形学,分形理论的发展离不开计算机图形学的支持，如果一个分形构造的表达，不用计算机的帮助是很难让人理解的。不仅如此，分形算法与现有计算机图形学的其他算法相结合，还会产生出非常美丽的图形，而且可以构造出复杂纹理和复杂形状，从而产生非常逼真的物质形态和视觉效果。分形作为一种方法，在图形学领域主要是利用迭代、递归等技术来实现某一具体的分形构造。分形几何学与计算机图形学相结合，将会产生一门新的学科分形图形学。它的主要任务是以分形几何学为数学基础，构造非规则的几何图素，从而实现分形体的可视化，以及对自然景物的逼真模拟。,参,10,第2章,分形图的递归算法,2.1Cantor三分集的递归算法2.2Koch曲线的递归算法2.3Sierpinski垫片的递归算法,2.4Hilbert-Peano曲线的算法2.5分支结构分形递归算法2.6分形树递归算法,参,11,递归算法,u直接递归调用的例子如下：voidRecur(n)Recur(m);过程Recur的内部又调用了自身Recur过程。,参,12,递归算法,u间接递归调用的例子如下：voidRecur_A(n)Recur_B(m);voidRecur_B(n)Recur_A(m);,参,13,2.1,Cantor三分集的递归算法,参,14,2.2,Koch曲线的递归算法,参,15,2.2,Koch曲线的递归算法,参,16,2.2,Koch曲线的递归算法,参,17,2.3,Sierpinski垫片的递归算法,参,18,2.3,Sierpinski垫片的递归算法,参,19,2.4,Hilbert-Peano曲线的算法,参,20,2.4,Hilbert-Peano曲线的算法,参,21,2.5,分支结构分形递归算法,参,22,2.5,分支结构分形递归算法,参,23,2.6,分形树递归算法,参,24,2.6,分形树递归算法,参,25,第3章,文法构图算法,3.1LS文法3.2单一规则的LS文法生成,3.3多规则的LS文法生成3.4随机LS文法,参,26,文法构图算法,字母表：L，R生成规则：LR，RLR初始字母：R则有：RLRRLRLRRLRRLRLRRLRLRRLRRLRLRRLR,参,27,3.1,LS文法,二维LS是字母表的绘图规则如下：F：以当前方向前进一步，并画线；f：以当前方向前进一步，不画线；：逆时针旋转角；：顺时针旋转角；：将海龟当前信息压栈；：将“”时刻的海龟信息出栈。,参,28,3.2,单一规则的LS文法生成,Koch曲线的LS文法如下：w：Fa：60oP：FFFFF,步骤0：F步骤1：FFFF步骤2：FFFFFFFFFFFFFFFF步骤3：FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF步骤4：,参,29,3.3,单一规则的LS算法实现,参,30,3.3,单一规则的LS算法实现,参,31,3.3,单一规则的LS算法实现,参,32,3.3,多规则的LS文法生成,为了生成更复杂的图形，可将字母表增加字母元素,Sierpinski垫片的LS文法如下：w：La：600P1：LRLRP2：RLRL相应的改造1：,参,33,3.3,多规则的LS文法生成,相应的改造2：,参,34,3.3,多规则的LS文法生成,相应的改造3：,参,35,3.4,随机LS文法,w:Fa:25P1：FFFFFFP2：FFFFFFP3：FFFFFFFFF,为了更好的模拟自然景物，需要随机使用多个变换规则。,p1,p2,p3,相应的改造1：,相应的改造2：,参,36,3.4,随机LS文法,参,37,第4章,迭代函数系统算法,4.1混沌游戏4.2迭代函数系统4.3相似变换与仿射变换4.4IFS码,4.5Sierpinski垫片的IFS生成4.6拼贴与IFS码的确定4.7IFS植物形态实例4.8复平面上的IFS算法,参,38,混沌游戏,4.1,给定平面上三点A,B,C。再任意给定初始点Z0,做下列迭代。,当掷出的硬币呈正面,当掷出的硬币呈反面,当掷出的硬币呈侧面,参,39,迭代函数系统,4.2,迭代函数系统（IteratedFunctionSystem，IFS）是分形理论的重要分支。它将待生成的图像看成是由许多与整体相似的（自相似）或经过一定变换与整体相似的（自仿射）小块拼贴而成。,参,40,相似变换与仿射变换,直观上看：相似变换是指在各个方向上变换的比率必须相同的一种比例变换，仿射变换是指在不同的方向上变化的比率可以不同的一种比例变换。,4.3,相似变换：如果对于任意两点A、B，以及对应点A、B，总有AB=kAB（k为正实数），那么，这个变换叫做相似变换，实数k叫做相似比。仿射变换：x=ax+by+ey=cx+dy+f其中a,b,c,d,e,f为仿射变换系数。,参,41,4.4,IFS码,用多个仿射变换式表达一个图象w1,w2,w3,，使用每一个仿射变换式的概率p可以不同，一般面积越大，p值越大。于是，只要获得a,b,c,d,e,f,p（IFS码）的值便可以得到要表达的图形。,参,42,4.5,Sierpinski垫片的IFS生成,由于生成的三个小三角形的面积相等，所以我们可以让w1、w2、w3出现的概率相同或相近。,x=0.5xy=0.5y,x=0.5x+0.5y=0.5y,x=0.5x+0.25y=0.5y-0.5,x=0.5x+0y+0y=0x+0.5y+0 x=0.5x+0y+0.5y=0x+0.5y+0 x=0.5x+0y+0.25y=0x+0.5y-0.5,w1,w2,w3,参,43,4.5,Sierpinski垫片的IFS生成,参,44,4.5,Sierpinski垫片的IFS生成,（源代码：书中程序4.1）,参,45,4.6,拼贴与IFS码的确定,此时四个子图分别是目标图的1/4、1/5、1/4、1/2大小的复制品。然后按顺序交互式地在屏幕上调节每一个子图的仿射变换参数ai、bi、ci、di、ei，使得平移、旋转后基本覆盖住目标图。,参,46,4.7,IFS植物形态实例,IFS码在书中表4.18,IFS码在书中表4.20,IFS码在书中表4.19,参,47,4.8,复平面上的IFS算法,参,48,4.8,复平面上的IFS算法,参,49,4.8,复平面上的IFS算法,参,50,第5章,逃逸时间算法,5.1基本思想5.2Julia集的逃逸时间算法,5.3Mandelbrot集的逃逸时间算法5.4基于牛顿迭代的Julia集的逃逸时间算法,参,51,逃逸时间算法的基本思想,F(z)=z2+c当c=0时，由于z是复数，即z=x+yi，则有z2=zz=(x+yi)(x+yi)=x2+y2i2+2xyi=(x2-y2)+(2xy)i设复数z=x+yi的绝对值，即|z|=SQR(x2+y2)|F(z0)|=|x02-y02+2x0y0i|=SQR(x02-y02)2+(2x0y0)2)=SQR(x04+y04-2x02y02+4x02y02)=SQR(x02+y02)2)=|z0|2若01,经过迭代z会趋向无穷，z向无穷逃逸。若|z0|1,z是平面上的单位圆。,5.1,参,52,逃逸时间算法的基本思想,当c0时，其吸引子不再是0，而是一个区域，称混沌区。如图，假设有一个充分大的整数N，当未逃逸区域M中的初始点a经过小于N次迭代就达到未逃逸区域M的边界，甚至超出了边界，我们就认为点a逃逸出去了；而如果经过N次迭代后a的轨迹仍未到达M的边界，我们就认为，a是A上的点。用这样的方法，描绘出A的边界图形，这便是逃逸时间算法的基本思想。,5.1,参,53,5.2,Julia集的逃逸时间算法,参,54,5.2,Julia集的逃逸时间算法,参,55,5.2,Julia集的逃逸时间算法,参,56,参,57,5.3,Mandelbrot集的逃逸时间算法,参,58,5.3,Mandelbrot集的逃逸时间算法,参,59,参,60,5.4,基于牛顿迭代的Julia集的逃逸时间算法,牛顿迭代法求根公式：zn+1=zn-f(zn)/f(zn)其中，f(zn)是f(zn)的导数。考虑f(z)=z3-1=0的情况,那么相应的牛顿变换是f(z)=(2z3+1)/3z2则z的三个根分别是w1=1,w2=ei2/3,w3=ei4/3，三个根的吸引域A(w1)，A(w2)，A(w3)的交界便是牛顿函数的Julia集。经过迭代，在A(wi)上的点都会被吸引到点wi上。设一个较大的迭代次数N，以及一个距离小量r，当迭代次数达到N，其与根点的距离小于r的被认为是收敛到某根上了，否则被认为是逃逸了。,参,61,5.4,基于牛顿迭代的Julia集的逃逸时间算法,参,62,5.4,基于牛顿迭代的Julia集的逃逸时间算法,参,63,第6章,分形显微镜,6.1逃逸时间算法的放缩原理6.2Mandelbrot集的局部放大6.3Julia集的局部放大,6.4牛顿迭代法的局部放大6.5作为Julia集字典的Mandelbrot集,参,64,逃逸时间算法的放缩原理,6.1,参,65,6.2,Mandelbrot集的局部放大,参,66,6.2,Mandelbrot集的局部放大,参,67,6.3,Julia集的局部放大,参,68,6.3,Julia集的局部放大,参,69,6.4,牛顿迭代法的局部放大,参,70,6.4,牛顿迭代法的局部放大,参,71,6.5,作为Julia集字典的Mandelbrot集,Julia集是一个固定的值的图形展现，而Mandelbrot集却要走遍所有的值，显然，每一个值都对应一个Julia集，所以我们说Mandelbrot集是Julia集微缩字典。,我们可以在Mandelbrot集的绘图空间中任意取一点，并将其还原成相应的值，再将此值作为Julia集程序中选定的值，来绘制Julia集的图形。,参,72,第7章,分形演化算法,7.1从逻辑运算谈起7.2一维元胞自动机7.3二维元胞自动机,7.4分形演化的DLA模型7.5用DLA模型模拟植物的生长7.6不同初始条件的DLA形态,参,73,参,74,从逻辑运算谈起,7.1,逻辑异或本行：00011011下一行：0110,参,75,7.2,一维元胞自动机,元胞按等间隔方式分布在一条向两侧无限延伸的直线中，称为一维元胞自动机。,本行：001100其他下一行：110,参,76,7.2,一维元胞自动机,参,77,7.3,二维元胞自动机,在一个二维网格中，如果抛下一粒种子（元胞着色），然后考察一下种子身边的格子中的元胞状态会发生什么事情。给一个规则，即每一个格子的状态，由其周围的八个格子的状态（0或1）来决定，如果它周围八个格子中的状态值相加为奇数时，则此格子下一个状态为1；如果它周围八个格子中的状态值相加为偶数时，则此格子下一个状态为0。就这样一步一步演化下去，会看到图案。,参,78,7.3,二维元胞自动机,参,79,7.4,分形演化的DLA模型,自然界中有很多种这样的生长集团,参,80,7.4,分形演化的DLA模型,参,81,7.4,分形演化的DLA模型,参,82,7.5,用DLA模型模拟植物的生长,如果初始不是一个原点，而是一条直线，且随机粒子从上面落到平面上，它将会产生一个什么样的图形呢？,参,83,7.6,不同初始条件的DLA形态,参,84,第8章,分形动画,8.1双缓存技术8.2摇曳的递归分形树8.3旋转万花筒,8.4变形的芦苇8.5收缩与伸展8.6连续变化的Julia集,参,85,在计算机上实现动画，一个关键技术就是：在绘制新图之前要删除旧图。当然可以在每次画新图之前清屏以实现删除旧图，但由于分形图一般画起来都比较慢，清屏之后不会及时画出新图，这样就会使动画产生闪烁。为了解决这一问题，可以在程序中使用了双缓存技术，即创建两个缓冲区，一个用来绘制图形，一个用来显示图形，当在显示图形缓冲区中删除旧图的同时，在绘制图形缓冲区中画新图，随后由显示图形缓冲区调出此图，从而提高了显示速度，避免了动画的闪烁。,8.1,双缓存技术,参,86,8.1,双缓存技术,参,87,摇曳的递归分形树,8.1,参,88,8.3,旋转万花筒,参,89,8.4,变形的芦苇,参,90,8.4,收缩与伸展,参,91,8.6,连续变化的Julia集,参,92,8.6,连续变化的Julia集,参,93,8.6,连续变化的Julia集,参,94,第9章,三维空间中的分形,9.1OpenGL简介9.2三维空间中的Sierpinski地毯,9.3Sierpinski金字塔9.4三维空间中Sierpinski海绵,参,95,OpenGL简介,9.1,OpenGL，即开放性图形库（OpenGraphicsLibrary），是一个三维的计算机图形和模型库。OpenGL包含120个图形函数，在微机环境下共有5种函数，即基本（或核心）函数、实用函数、辅助函数、Windows专用函数和Win32API函数。,参,96,OpenGL的基本功能,1绘制物体OpenGL提供了丰富的基本图元绘制命令，从而可以方便地绘制物体，包括规则的和不规则的。,参,97,OpenGL的基本功能,2变换OpenGL提供了一系列基本的变换，如取景变换、模型变换、投影变换及视口变换。,参,98,OpenGL的基本功能,3光照处理包括发射光、环境光、散射光和镜面反射光。,参,99,OpenGL的基本功能,4着色OpenGL提供了两种物体着色模式，一种是RGBA颜色模式，另一种是颜色索引（ColorIndex）模式。,参,100,OpenGL的基本功能,5反走样在OpenGL绘制图形过程中，由于使用的是位图，所以绘制出的图像的边缘会出现锯齿形状，称为走样。为了消除这种缺陷，OpenGL提供了点、线、多边形的反走样技术。,参,101,OpenGL的基本功能,6融合为了使三维图形更加具有真实感，经常需要处理半透明或透明的物体图像，这就需要用到融合技术。,参,102,OpenGL的基本功能,7雾化正如自然界中存在烟雾一样，OpenGL提供了“fog”的基本操作来达到对场景进行雾化的效果。,参,103,OpenGL的基本功能,8位图和图像在图形绘制过程中，位图和图像是非常重要的一个方面。OpenGL提供了系列函数来实现位图和图像的操作。,参,104,OpenGL的基本功能,9纹理映射在计算机图形学中，把包含颜色、alpha值、亮度等数据的矩形数组称为纹理。而纹理映射可以理解为将纹理粘贴在所绘制的三维模型表面，以使三维图形显得更生动。,参,105,OpenGL的运行环境,10动画出色的动画效果是OpenGL的一大特色，OpenGL提供了双缓存区技术来实现动画绘制。,参,106,OpenGL的基本函数,1顶点坐标OpenGL采用有序排列的顶点集合来构造几何图元，而不是将线段、多边形组合起来构造几何图元。如：glVertex2s(2,5);/整数定义的二维坐标glVertex3f(2,5,7);/浮点定义的三维坐标,参,107,OpenGL的基本函数,2顶点关系在OpenGL中，同一个几何图元的所有被定义的顶点一起放在glBegin()和glEnd()函数之间，同时定义这些顶点之间的关系。如：glBegin(GL_POLYGON);glVertex2s(0,0);glVertex2s(0,11);glVertex2s(11,14);glVertex2s(14,7);glVertex2s(7,0);glEnd();,参,108,OpenGL的基本函数,3显示列表OpenGL显示列表（DispplayList）是由一组预先存储起来的留待以后调用的OpenGL函数语句组成的，当调用这张显示列表时就一次执行表中所列出的函数语句。创建显示列表OpenGL用下面的函数组创建显示列表：voidglNewList(GLuintlist,GLenummode);voidglEndList(void);执行显示列表显示列表的执行函数形式如下：voidglCallList(GLuintlist);参数list指定被执行的显示列表。,参,109,OpenGL的基本函数,4颜色设置RGBA模式下的颜色定义在RGBA模式下，利用glColor*命令来定义当前颜色。glColor*命令有如下几种形式：voidglColor3bsifdubusui(TYPEr,TYPEg,TYPEb);voidglColor4bsifdubusui(TYPEr,TYPEg,TYPEb,TYPEa);voidglColor3bsifdubusuiv(TYPE*v);voidglColor4bsifdubusuiv(TYPE*v);在颜色索引模式下的颜色定义通过调用函数glIndex*()从颜色索引表中选取当前颜色。voidglIndex(sfdi)(c:TYPE);voidglIndex(sfdi)v(c:PTYPE);,参,110,OpenGL的基本函数,5光照设置创建光源(LightSource)光源有许多特性，如颜色、位置、方向等。可以使用下面的函数定义光源：voidglLightifv(GLenumlight,GLenumpname,TYPEparam)启动光照在OpenGL中，必须明确指出光照是否有效或无效。如果光照无效，则只是简单地将当前颜色映射到当前顶点上去，不进行法向、光源、材质等复杂计算，那么显示的图形就没有真实感。启动和取消光源的函数如下:glEnable(GL_LIGHTING);/启动光照gDisable(GL_LIGHTING);/取消光照,参,111,OpenGL的基本函数,6明暗处理在OpenGL中，用单一颜色处理的称为平面明暗处理(FlatShading)，用许多不同颜色处理的称为光滑明暗处理(SmoothShading)。设置明暗处理模式的函数为：voidglShadeModel(GLenummode);,参,112,OpenGL的基本函数,7材质设置材质定义材质的定义与光源的定义类似。其函数为：voidglMaterialifv(GLenumface,GLenumpname,TYPEparam);改变材质在OpenGL中提供了两种方式来改变场景中的材质。第一种方法是利用函数glMaterial*()来改变材质，但是调用函数glMaterial*()需要同时保存当前矩阵，也就是调用函数glPushMatrix()和glPopMatrix()。第二种方法是使用函数glColorMaterial()，其形式为：voidglColorMaterial(GLenumface,GLenummode);,参,113,OpenGL的基本函数,8纹理映射纹理定义在程序中可以用以下函数定义二维纹理映射：voidglTexImage2D(GLenumtarget,GLintlevel,GLintcomponents,GLsizeiwidth,Glsizeiheight,GLintborder,GLenumformat,GLenumtype,constGLvoid*pixels);纹理控制OpenGL中控制纹理的函数是：voidglTexParameterifv(GLenumtarget,GLenumpname,TYPEparam);定义纹理坐标OpenGL坐标定义的函数是：voidgltexCoord1234sifdv(TYPEcoords);,参,114,OpenGL的基本函数,9选择与反馈在OpenGL中，提供了选择和反馈两种方式，以实现对屏幕上的某个物体的信息提供，达到交互的目的。进行模式选择的函数原型如下：LintglRenderMode(GLenumMode);在进入选择模式之前，必须调用函数glSelectBuffer()来制定选择数组。在进入反馈模式之前，必须调用函数glFeedbackBuffer()来制定反馈数组。,参,115,OpenGL的基本函数,10帧缓存与动画帧缓存的组成OpenGL帧缓存由以下四种缓存组成：颜色缓存（ColorBuffer）、深度缓存(DepthBuffer)、模板缓存(StencilBuffer)、累积缓存(AccumulationBuffer)。缓存清除OpenGL清除缓存操作过程是：先给出要写入每个缓存的清除值，然后用单个函数命令执行操作，传入所有要清除的缓存表。动画OpenGL提供了双缓存，可以用来制作动画。也就是说，在显示前台缓存内容中的一帧画面时，后台缓存正在绘制下一帧画面，当绘制完毕，则后台缓存内容便在屏幕上显示出来，而前台正好相反，又在绘制下一帧画面内容。这样循环反复，屏幕上显示的总是已经画好的图形，于是看起来所有的画面都是连续的。,参,116,9.2,三维空间中的Sierpinski地毯,参,117,9.2,三维空间中的Sierpinski地毯,参,118,9.2,三维空间中的Sierpinski地毯,参,119,9.3,Sierpinski金字塔,参,120,9.3,Sierpinski金字塔,参,121,9.3,Sierpinski金字塔,参,122,9.4,Sierpinski海绵,参,123,9.4,Sierpinski海绵,参,124,9.4,Sierpinski海绵,参,125,9.4,Sierpinski海绵,参,126,9.4,Sierpinski海绵,参,127,9.4,Sierpinski海绵,参,128,9.4,Sierpinski海绵,参,129,9.4,Sierpinski海绵,参,130,第10章,分形自然景物模拟算法,9.1随机中点位移法生成山,9.2分形插值算法生成云和山,参,131,随机中点位移法生成山,10.1,1.一维中点位移法以一条水平地平线段开始重复足够多次对场景中的每条线段做找到线段的中点在Y方向上随机移动中点一段距离减小随机数取值范围,参,132,随机中点位移法生成山,10.1,1.一维中点位移法粗糙度常量。这个值决定每次循环随机数值域的减少量，也就是说，决定分形结果的粗糙程度。例如使用一个0.0到1.0之间的浮点数并称之为H。因此(a-h)是1.0(对于小H)到0.5（对大H）范围内的数。随机数范围在每次循环时乘上这个值。如果H设为1.0，则随机数范围将每次循环减半，从而得到一个非常平滑的分形。将H设为0.0，则范围根本不减小，结果有明显的锯齿感。,参,133,随机中点位移法生成山,10.1,2.二维中点位移法上面是将索引（x值）映射为高度值（y值）。如果需要一个两维高度值数组，它将索引(x,z)映射为高度(y)。数组只需保存高度值(y)。水平面值(x和z)可以在分析数组时即时生成。通过对每个高度指定一个颜色，可以将一幅高度图显示为一幅图像。如下，高点为白色，低处为黑色。绘制高度图的方法对于生成云彩纹理图是很有用的。,参,