分形算法与程序设计

null第 1 章第 1 章初识分形1.1 Fractal 的含义 1.2 分形的几何特征 1.3 分形的度量 1.4 分形维数 1.5 分形是一种方法论 1.6 分形与计算机图形学 Fractal 的含义1.1Fractal 的含义 英文单词Fractal，在大陆被译为“分形”，在台湾被译为“碎形”。它是由美籍法国数学家曼德勃罗（Benoit Mandelbrot）创造出来的。其含义是不规则的、破碎的、分数的。曼德勃罗是想用此词来描述自然界中传统欧几里得几何学所不能描述的一大类复杂无规的几何对象。 分形的几何特征1.2分形的几何特征自相似性 自相似，便是局部与整体的相似。自仿射性 自仿射性是自相似性的一种拓展。如果，将自相似性看成是局部到整体在各个方向上的等比例变换的结果的话，那么，自仿射性就是局部到整体在不同方向上的不等比例变换的结果。前者称为自相似变换，后者称为自仿射变换。 精细结构 任意小局部总是包含细致的结构。分形的度量1.3分形的度量（1）长度的测量 Length(n=0)=1 Length(n=1)=4/3 Length(n=2)=16/9 ………… Length=lim(Length(n)) =lim(4/3) = ∞ n→∞n→∞n分形的度量1.3分形的度量（2）面积的测量 Area(n0)=(1╳√3/6)/2= √3/12 Area(n1)=√3/12 ╳(4/9) Area(n2)=√3/12 ╳(4/9)2 ………… Area(n)=lim(√3/12 ╳(4/9)n)=0 n→∞ 如上所述，koch曲线在一维欧氏空间中的度量为∞，在二维欧氏空间中的面积为0。如此看来，Koch曲线在传统欧氏空间中不可度量。分形维数1.4分形维数 分形维数是分形的很好的不变量，它一般是分数，用它可以把握住分形体的基本特征。 图a是边长为1的正方形，当边长变成原来的1∕2时，原正方形中包含4个小正方形，如图b，而4=22； 图c是边长为1的正立方体，当边长变成原来的1∕2时，原正立方体中包含8个小正立方体，如图d，而8=23。则有N＝kD , D=log(N)/log(k) 这样Koch曲线的分形维数D=log(4)log(3)=1.2618分形维数1.4分形维数 对于实际的自然景物，我们可以用计盒维数的方法测量分维。分形是一种方法论1.5分形是一种方法论 沃尔夫奖（Wolf Prize）在颁发给分形理论创始人曼德勃罗时的评语所说的，“分形几何改变了我们对世界的看法”。 分形理论至少会在三个方面改变我们对世界的认识。首先，自然界中许多不规则的形态其背后都有规则，都可以用分形的方法建立模型并在计算机上构造出以假乱真的景象来，显然利用这套方法我们可以把世界压缩到几个分形规则中，便于携带和传播。其次，许多以前被认为是随机的现象，从分形理论的角度看并不是随机的，比如布朗运动、股票价格的波动、传染病的流行传播等，这为我们控制这些貌似随机的现象奠定了理论基础。最后，分形理论中的分数维概念，为我们认识世界中的复杂形态提供了一个新的尺度。复杂性科学是现代科学的前沿，在这门科学的研究过程中，发现了许多符合分形规则的复杂形态，而分数维是测量这些形态复杂程度的一种度量。也就是说，我们找到了对复杂性做定量分析的工具。 分形与计算机图形学1.6分形与计算机图形学 分形理论的发展离不开计算机图形学的支持，如果一个分形构造的表达，不用计算机的帮助是很难让人理解的。不仅如此，分形算法与现有计算机图形学的其他算法相结合，还会产生出非常美丽的图形，而且可以构造出复杂纹理和复杂形状，从而产生非常逼真的物质形态和视觉效果。 分形作为一种方法，在图形学领域主要是利用迭代、递归等技术来实现某一具体的分形构造。 分形几何学与计算机图形学相结合，将会产生一门新的学科——分形图形学。它的主要任务是以分形几何学为数学基础，构造非规则的几何图素，从而实现分形体的可视化，以及对自然景物的逼真模拟。第 2 章第 2 章分形图的递归算法2.1 Cantor三分集的递归算法 2.2 Koch曲线的递归算法 2.3 Sierpinski垫片的递归算法2.4 Hilbert-Peano曲线的算法 2.5 分支结构分形递归算法 2.6 分形树递归算法递归算法递归算法u       直接递归调用的例子如下： void Recur(n) { …… Recur(m); …… } 过程Recur的内部又调用了自身——Recur过程。 递归算法递归算法u       间接递归调用的例子如下： void Recur_A(n) { …… Recur_B(m); …… } void Recur_B(n) { …… Recur_A(m); …… } Cantor三分集的递归算法2.1Cantor三分集的递归算法Koch曲线的递归算法2.2Koch曲线的递归算法Koch曲线的递归算法2.2Koch曲线的递归算法Koch曲线的递归算法2.2Koch曲线的递归算法Sierpinski垫片的递归算法2.3Sierpinski垫片的递归算法Sierpinski垫片的递归算法2.3Sierpinski垫片的递归算法Hilbert-Peano曲线的算法2.4Hilbert-Peano曲线的算法Hilbert-Peano曲线的算法2.4Hilbert-Peano曲线的算法分支结构分形递归算法2.5分支结构分形递归算法 分支结构分形递归算法2.5分支结构分形递归算法分形树递归算法2.6分形树递归算法分形树递归算法2.6分形树递归算法第 3 章第 3 章文法构图算法3.1 LS文法 3.2 单一规则的LS文法生成 3.3 多规则的LS文法生成 3.4 随机LS文法文法构图算法文法构图算法字母表：L，R 生成规则：L→R，R→L R 初始字母：R 则有：R→L R→R L R→L R R L R→R L R L R R L R→L R R L R R L R L R R L R→…… LS文法3.1LS文法二维LS是字母表的绘图规则如下： F：以当前方向前进一步，并画线； f：以当前方向前进一步，不画线； ＋：逆时针旋转角； －：顺时针旋转角； [：将海龟当前信息压栈； ]：将“[”时刻的海龟信息出栈。 单一规则的LS文法生成3.2单一规则的LS文法生成Koch曲线的LS文法如下： w：F a ：60o P：F → F ＋ F － － F ＋ F 步骤0：F 步骤1：F ＋ F － － F ＋ F 步骤2：F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F － － F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F 步骤3：F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F － － F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F － － F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F － － F ＋F － － F ＋F ＋ F ＋ F － － F ＋ F － － F＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F － － F＋ F － － F ＋F ＋ F ＋ F － － F ＋ F 步骤4：…… 单一规则的LS算法实现3.3单一规则的LS算法实现单一规则的LS算法实现3.3单一规则的LS算法实现单一规则的LS算法实现3.3单一规则的LS算法实现多规则的LS文法生成3.3多规则的LS文法生成为了生成更复杂的图形，可将字母表增加字母元素Sierpinski垫片的LS文法如下： w：L a ：600 P1：L → ＋ R － L － R ＋ P2：R → － L ＋ R ＋ L － 相应的改造1：多规则的LS文法生成3.3多规则的LS文法生成相应的改造2：多规则的LS文法生成3.3多规则的LS文法生成相应的改造3：随机LS文法3.4随机LS文法w:F a:25 P1：F————→F[＋F]F[－F]F P2：F————→F[＋F]F[－F[＋F]] P3：F————→FF[－F＋F＋F]＋[＋F－F－F] 为了更好的模拟自然景物，需要随机使用多个变换规则。p1p2p3相应的改造1：相应的改造2：随机LS文法3.4随机LS文法第 4 章第 4 章迭代函数系统算法4.1 混沌游戏 4.2 迭代函数系统 4.3 相似变换与仿射变换 4.4 IFS码4.5 Sierpinski垫片的IFS生成 4.6 拼贴与IFS码的确定 4.7 IFS植物形态实例 4.8 复平面上的IFS算法混沌游戏混沌游戏4.1给定平面上三点A, B, C。再任意给定初始点Z0 , 做下列迭代。当掷出的硬币呈正面当掷出的硬币呈反面当掷出的硬币呈侧面迭代函数系统迭代函数系统4.2迭代函数系统（Iterated Function System，IFS）是分形理论的重要分支 。它将待生成的图像看成是由许多与整体相似的（自相似）或经过一定变换与整体相似的（自仿射）小块拼贴而成。相似变换与仿射变换相似变换与仿射变换直观上看：相似变换是指在各个方向上变换的比率必须相同的一种比例变换，仿射变换是指在不同的方向上变化的比率可以不同的一种比例变换。 4.3相似变换：如果对于任意两点A、B，以及对应点A’、B’，总有A’B’=k·AB（k为正实数），那么，这个变换叫做相似变换，实数k叫做相似比。 仿射变换：x’=ax+by+e y’=cx+dy+f 其中a,b,c,d,e,f为仿射变换系数。IFS码4.4IFS码用多个仿射变换式表达一个图象w1,w2,w3,……，使用每一个仿射变换式的概率p可以不同，一般面积越大，p值越大。于是，只要获得a,b,c, d,e,f,p（ IFS码）的值便可以得到要表达的图形。Sierpinski垫片的IFS生成 4.5Sierpinski垫片的IFS生成 由于生成的三个小三角形的面积相等，所以我们可以让w1、w2、w3出现的概率相同或相近。 x’=0.5x y’=0.5y x’=0.5x+0.5 y’=0.5y x’=0.5x+0.25 y’=0.5y-0.5 x’=0.5·x+0·y+0 y’=0·x+0.5·y+0 x’=0.5·x+0·y+0.5 y’=0·x+0.5·y+0 x’=0.5·x+0·y+0.25 y’=0·x+0.5·y-0.5w1w2w3Sierpinski垫片的IFS生成 4.5Sierpinski垫片的IFS生成 Sierpinski垫片的IFS生成 4.5Sierpinski垫片的IFS生成 （源代码：书中程序4.1）拼贴与IFS码的确定 4.6拼贴与IFS码的确定 此时四个子图分别是目标图的1/4、1/5、1/4、1/2大小的复制品。然后按顺序交互式地在屏幕上调节每一个子图的仿射变换参数ai、bi、ci、di、ei，使得平移、旋转后基本覆盖住目标图。 IFS植物形态实例 4.7IFS植物形态实例 IFS码在书中表4.18IFS码在书中表4.20IFS码在书中表4.19复平面上的IFS算法 4.8复平面上的IFS算法 复平面上的IFS算法 4.8复平面上的IFS算法 复平面上的IFS算法 4.8复平面上的IFS算法 第 5 章第 5 章逃逸时间算法5.1 基本思想 5.2 Julia集的逃逸时间算法 5.3 Mandelbrot集的逃逸时间算法 5.4 基于牛顿迭代的Julia集的逃逸时间算法 逃逸时间算法的基本思想 逃逸时间算法的基本思想 F(z)=z2+c 当c=0时，由于z是复数，即z=x+yi，则有 z2=z×z=(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 若0<|z0|<1, |F(z0)|<|z0|，对于每一次迭代z趋向0，即z向0收敛。 若|z0|>1, 经过迭代z会趋向无穷， z向无穷逃逸。 若|z0|>1, z是平面上的单位圆。5.1逃逸时间算法的基本思想 逃逸时间算法的基本思想 当c≠0时，其吸引子不再是0，而是一个区域，称混沌区。如图，假设有一个充分大的整数N，当未逃逸区域M中的初始点a经过小于N次迭代就达到未逃逸区域M的边界，甚至超出了边界，我们就认为点a逃逸出去了；而如果经过N次迭代后a的轨迹仍未到达M的边界，我们就认为，a是A上的点。用这样的方法，描绘出A的边界图形，这便是逃逸时间算法的基本思想。 5.1Julia集的逃逸时间算法 5.2Julia集的逃逸时间算法 Julia集的逃逸时间算法 5.2Julia集的逃逸时间算法 Julia集的逃逸时间算法 5.2Julia集的逃逸时间算法 nullMandelbrot集的逃逸时间算法 5.3Mandelbrot集的逃逸时间算法 Mandelbrot集的逃逸时间算法 5.3Mandelbrot集的逃逸时间算法 null基于牛顿迭代的Julia集的逃逸时间算法 5.4基于牛顿迭代的Julia集的逃逸时间算法 牛顿迭代法求根 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 ： 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的被认为是收敛到某根上了，否则被认为是逃逸了。基于牛顿迭代的Julia集的逃逸时间算法 5.4基于牛顿迭代的Julia集的逃逸时间算法 基于牛顿迭代的Julia集的逃逸时间算法 5.4基于牛顿迭代的Julia集的逃逸时间算法 第 6 章第 6 章分形显微镜6.1 逃逸时间算法的放缩原理 6.2 Mandelbrot集的局部放大 6.3 Julia集的局部放大 6.4 牛顿迭代法的局部放大 6.5 作为Julia集字典的Mandelbrot集逃逸时间算法的放缩原理 逃逸时间算法的放缩原理 6.1Mandelbrot集的局部放大 6.2Mandelbrot集的局部放大 Mandelbrot集的局部放大 6.2Mandelbrot集的局部放大 Julia集的局部放大 6.3Julia集的局部放大 Julia集的局部放大 6.3Julia集的局部放大 牛顿迭代法的局部放大 6.4牛顿迭代法的局部放大 牛顿迭代法的局部放大 6.4牛顿迭代法的局部放大 作为Julia集字典的Mandelbrot集 6.5作为Julia集字典的Mandelbrot集 Julia集是一个固定的值的图形展现，而Mandelbrot集却要走遍所有的值，显然，每一个值都对应一个Julia集，所以我们说Mandelbrot集是Julia集微缩字典。 我们可以在Mandelbrot集的绘图空间中任意取一点，并将其还原成相应的值，再将此值作为Julia集程序中选定的值，来绘制Julia集的图形。 第 7 章第 7 章分形演化算法 7.1 从逻辑运算谈起 7.2 一维元胞自动机 7.3 二维元胞自动机 7.4 分形演化的DLA模型 7.5 用DLA模型模拟植物的生长 7.6 不同初始条件的DLA形态 null从逻辑运算谈起从逻辑运算谈起7.1逻辑异或 本 行：0 0 0 1 1 0 1 1 下一行： 0 1 1 0 一维元胞自动机7.2一维元胞自动机元胞按等间隔方式分布在一条向两侧无限延伸的直线中，称为一维元胞自动机。 本 行：001 100 其他 下一行： 1 1 0一维元胞自动机7.2一维元胞自动机二维元胞自动机7.3二维元胞自动机在一个二维网格中，如果抛下一粒种子（元胞着色），然后考察一下种子身边的格子中的元胞状态会发生什么事情。给一个规则，即每一个格子的状态，由其周围的八个格子的状态（0或1）来决定，如果它周围八个格子中的状态值相加为奇数时，则此格子下一个状态为1；如果它周围八个格子中的状态值相加为偶数时，则此格子下一个状态为0。就这样一步一步演化下去，会看到图案。二维元胞自动机7.3二维元胞自动机分形演化的DLA模型 7.4分形演化的DLA模型 自然界中有很多种这样的生长集团分形演化的DLA模型 7.4分形演化的DLA模型 分形演化的DLA模型 7.4分形演化的DLA模型 用DLA模型模拟植物的生长 7.5用DLA模型模拟植物的生长 如果初始不是一个原点，而是一条直线，且随机粒子从上面落到平面上，它将会产生一个什么样的图形呢？ 不同初始条件的DLA形态7.6不同初始条件的DLA形态第 8 章第 8 章分形动画 8.1 双缓存技术 8.2 摇曳的递归分形树 8.3 旋转万花筒 8.4 变形的芦苇 8.5 收缩与伸展 8.6 连续变化的Julia集 双缓存技术 在计算机上实现动画，一个关键技术就是：在绘制新图之前要删除旧图。当然可以在每次画新图之前清屏以实现删除旧图，但由于分形图一般画起来都比较慢，清屏之后不会及时画出新图，这样就会使动画产生闪烁。 为了解决这一问题，可以在程序中使用了双缓存技术，即创建两个缓冲区，一个用来绘制图形，一个用来显示图形，当在显示图形缓冲区中删除旧图的同时，在绘制图形缓冲区中画新图，随后由显示图形缓冲区调出此图，从而提高了显示速度，避免了动画的闪烁。 8.1双缓存技术双缓存技术8.1双缓存技术摇曳的递归分形树摇曳的递归分形树8.1旋转万花筒8.3旋转万花筒变形的芦苇8.4变形的芦苇收缩与伸展8.4收缩与伸展连续变化的Julia集8.6连续变化的Julia集连续变化的Julia集8.6连续变化的Julia集连续变化的Julia集8.6连续变化的Julia集第 9 章第 9 章三维空间中的分形 9.1 OpenGL简介 9.2三维空间中的Sierpinski地毯 9.3 Sierpinski金字塔 9.4三维空间中Sierpinski海绵 OpenGL简介OpenGL简介9.1OpenGL，即开放性图形库（Open Graphics Library），是一个三维的计算机图形和模型库。OpenGL包含120个图形函数，在微机环境下共有5种函数，即基本（或核心）函数、实用函数、辅助函数、Windows专用函数和Win32 API函数。 nullOpenGL的基本功能1． 绘制物体 OpenGL提供了丰富的基本图元绘制命令，从而可以方便地绘制物体，包括规则的和不规则的。 nullOpenGL的基本功能2． 变换 OpenGL提供了一系列基本的变换，如取景变换、模型变换、投影变换及视口变换。nullOpenGL的基本功能3． 光照处理 包括发射光、环境光、散射光和镜面反射光。nullOpenGL的基本功能4． 着色 OpenGL提供了两种物体着色模式，一种是RGBA颜色模式，另一种是颜色索引（Color Index）模式。 nullOpenGL的基本功能5． 反走样 在OpenGL绘制图形过程中，由于使用的是位图，所以绘制出的图像的边缘会出现锯齿形状，称为走样。为了消除这种缺陷，OpenGL提供了点、线、多边形的反走样技术。 nullOpenGL的基本功能6． 融合 为了使三维图形更加具有真实感，经常需要处理半透明或透明的物体图像，这就需要用到融合技术。 nullOpenGL的基本功能7． 雾化 正如自然界中存在烟雾一样，OpenGL提供了“fog”的基本操作来达到对场景进行雾化的效果。 nullOpenGL的基本功能8． 位图和图像 在图形绘制过程中，位图和图像是非常重要的一个方面。OpenGL提供了系列函数来实现位图和图像的操作。 nullOpenGL的基本功能9． 纹理映射 在计算机图形学中，把包含颜色、alpha值、亮度等数据的矩形数组称为纹理。而纹理映射可以理解为将纹理粘贴在所绘制的三维模型表面，以使三维图形显得更生动。 nullOpenGL的运行环境10．动画 出色的动画效果是OpenGL的一大特色，OpenGL提供了双缓存区技术来实现动画绘制。 nullOpenGL的基本函数1．顶点坐标 OpenGL采用有序排列的顶点集合来构造几何图元，而不是将线段、多边形组合起来构造几何图元。 如： glVertex2s(2,5); //整数定义的二维坐标 glVertex3f(2,5,7); //浮点定义的三维坐标 nullOpenGL的基本函数2．顶点关系 在OpenGL中，同一个几何图元的所有被定义的顶点一起放在glBegin()和glEnd()函数之间，同时定义这些顶点之间的关系。如： glBegin(GL_POLYGON); glVertex2s(0,0); glVertex2s(0,11); glVertex2s(11,14); glVertex2s(14,7); glVertex2s(7,0); glEnd(); nullOpenGL的基本函数3．显示列表 OpenGL显示列表（Dispplay List）是由一组预先存储起来的留待以后调用的OpenGL函数语句组成的，当调用这张显示列表时就一次执行表中所列出的函数语句。 创建显示列表 OpenGL用下面的函数组创建显示列表： void glNewList(GLuint list,GLenum mode); …… void glEndList(void); 执行显示列表 显示列表的执行函数形式如下： void glCallList(GLuint list); 参数list指定被执行的显示列表。 nullOpenGL的基本函数4．颜色设置 ⑴ RGBA模式下的颜色定义 在RGBA模式下，利用glColor*命令来定义当前颜色。glColor*命令有如下几种形式： void glColor3{b s i f d ub us ui}(TYPE r,TYPE g,TYPE b); void glColor4{b s i f d ub us ui}(TYPE r,TYPE g,TYPE b,TYPE a); void glColor3{b s i f d ub us ui}v(TYPE *v); void glColor4{b s i f d ub us ui}v(TYPE *v); ⑵ 在颜色索引模式下的颜色定义 通过调用函数glIndex*()从颜色索引表中选取当前颜色。 void glIndex(s f d i)(c:TYPE); void glIndex(s f d i)v(c:PTYPE); nullOpenGL的基本函数5．光照设置 ⑴ 创建光源(Light Source) 光源有许多特性，如颜色、位置、方向等。可以使用下面的函数定义光源： void glLight{if}[v](GLenum light , GLenum pname, TYPE param) ⑵ 启动光照 在OpenGL中，必须明确指出光照是否有效或无效。如果光照无效，则只是简单地将当前颜色映射到当前顶点上去，不进行法向、光源、材质等复杂计算，那么显示的图形就没有真实感。启动和取消光源的函数如下: glEnable(GL_LIGHTING);//启动光照 gDisable(GL_LIGHTING);//取消光照nullOpenGL的基本函数6．明暗处理 在OpenGL中，用单一颜色处理的称为平面明暗处理(Flat Shading)，用许多不同颜色处理的称为光滑明暗处理(Smooth Shading) 。 设置明暗处理模式的函数为： void glShadeModel(GLenum mode); nullOpenGL的基本函数7．材质设置 ⑴ 材质定义 材质的定义与光源的定义类似。其函数为： void glMaterial{if}[v](GLenum face,GLenum pname,TYPE param); ⑵ 改变材质 在OpenGL中提供了两种方式来改变场景中的材质。 第一种方法是利用函数glMaterial*()来改变材质，但是调用函数glMaterial*()需要同时保存当前矩阵，也就是调用函数glPushMatrix()和glPopMatrix()。 第二种方法是使用函数glColorMaterial()，其形式为： void glColorMaterial(GLenum face,GLenum mode); nullOpenGL的基本函数8．纹理映射 ⑴ 纹理定义 在程序中可以用以下函数定义二维纹理映射： void glTexImage2D(GLenum target,GLint level,GLint components, GLsizei width,Glsizei height,GLint border,GLenum format,GLenum type,const GLvoid *pixels); ⑵ 纹理控制 OpenGL中控制纹理的函数是： void glTexParameter{if}[v](GLenum target,GLenum pname,TYPE param); ⑶ 定义纹理坐标 OpenGL坐标定义的函数是： void gltexCoord{1 2 3 4}{s i f d}[v](TYPE coords); nullOpenGL的基本函数9．选择与反馈 在OpenGL中，提供了选择和反馈两种方式，以实现对屏幕上的某个物体的信息提供，达到交互的目的。 进行模式选择的函数原型如下： Lint glRenderMode(GLenum Mode); 在进入选择模式之前，必须调用函数glSelectBuffer()来制定选择数组。 在进入反馈模式之前，必须调用函数glFeedbackBuffer()来制定反馈数组。 nullOpenGL的基本函数10．帧缓存与动画 ⑴ 帧缓存的组成 OpenGL帧缓存由以下四种缓存组成：颜色缓存（Color Buffer） 、深度缓存(Depth Buffer) 、模板缓存(Stencil Buffer) 、累积缓存(Accumulation Buffer) 。 ⑵ 缓存清除 OpenGL清除缓存操作过程是：先给出要写入每个缓存的清除值，然后用单个函数命令执行操作，传入所有要清除的缓存表。 ⑶ 动画 OpenGL提供了双缓存，可以用来制作动画。也就是说，在显示前台缓存内容中的一帧画面时，后台缓存正在绘制下一帧画面，当绘制完毕，则后台缓存内容便在屏幕上显示出来，而前台正好相反，又在绘制下一帧画面内容。这样循环反复，屏幕上显示的总是已经画好的图形，于是看起来所有的画面都是连续的。 三维空间中的Sierpinski地毯 9.2三维空间中的Sierpinski地毯 三维空间中的Sierpinski地毯 9.2三维空间中的Sierpinski地毯 三维空间中的Sierpinski地毯 9.2三维空间中的Sierpinski地毯 Sierpinski金字塔 9.3Sierpinski金字塔 Sierpinski金字塔 9.3Sierpinski金字塔 Sierpinski金字塔 9.3Sierpinski金字塔 Sierpinski海绵9.4Sierpinski海绵Sierpinski海绵9.4Sierpinski海绵Sierpinski海绵9.4Sierpinski海绵Sierpinski海绵9.4Sierpinski海绵Sierpinski海绵9.4Sierpinski海绵Sierpinski海绵9.4Sierpinski海绵Sierpinski海绵9.4Sierpinski海绵Sierpinski海绵9.4Sierpinski海绵第 10 章第 10 章分形自然景物模拟算法 9.1 随机中点位移法生成山 9.2 分形插值算法生成云和山 随机中点位移法生成山 随机中点位移法生成山 10.1 1. 一维中点位移法 以一条水平地平线段开始     重复足够多次{ 　　对场景中的每条线段做{ 　　　　找到线段的中点 　　　　在 Y 方向上随机移动中点一段距离 　　　　减小随机数取值范围 　　} }随机中点位移法生成山 随机中点位移法生成山 10.1 1. 一维中点位移法 粗糙度常量。这个值决定每次循环随机数值域的减少量，也就是说，决定分形结果的粗糙程度。例如使用一个 0.0 到 1.0 之间的浮点数并称之为 H 。因此 (a-h) 是1.0( 对于小 H) 到 0.5（对大 H ）范围内的数。随机数范围在每次循环时乘上这个值。如果 H 设为 1.0 ，则随机数范围将每次循环减半，从而得到一个非常平滑的分形。将 H 设为 0.0 ，则范围根本不减小，结果有明显的锯齿感。 随机中点位移法生成山 随机中点位移法生成山 10.1 2. 二维中点位移法 上面是将索引（ x 值）映射为高度值（ y 值）。      如果需要一个两维高度值数组，它将索引 (x,z) 映射为高度 (y) 。数组只需保存高度值 (y) 。水平面值 (x 和 z) 可以在分析数组时即时生成。      通过对每个高度指定一个颜色，可以将一幅高度图显示为一幅图像。如下，高点为白色，低处为黑色。      绘制高度图的方法对于生成云彩纹理图是很有用的。随机中点位移法生成山 随机中点位移法生成山 10.13. 三维中点位移法 选择AB、AC、BC线段中点，并沿y方向分别加一个随机量h1、h2、h3，得到E、F、G点，其中，h1、h2、h3的取值范围相同。 连接AE、BE、AF、CF、BG、CG，从而构成△AEG、△BEF、△CFG、△EFG等4个小三角形，并将原来的三角形△ABC抹去。选择明暗不同的4种颜色，分别填充这4个三角形。 分别基于上述形成的4个小三角形，重复执行上面的操作。随机中点位移法生成山 随机中点位移法生成山 10.13. 三维中点位移法 在实现此算法时应避免出现山体裂痕。当每一级中点位移时，都是基于每一个独立的小三角形进行的，但由于各三角形之间有共用边，所以会出现共用被移位两次的情况，而且两次位移的高度会有所不同（因为移位中有随机量），这样便会出现裂痕。解决办法是，先移位三边都是共用的三角形，然后其他三角形在移位时，只移位非共用边即可。分形插值算法生成云和山 10.2分形插值算法生成云和山 在平面上划分正方形网络n×n，随机给A、B、C、D四个角点的颜色； 根据四个角点的颜色值的平均值，产生中点M的颜色； 根据A、B、M点和网格外一虚拟点（颜色值为0）求平均，得到边中点E的颜色，根据B、C、M点和网格外一虚拟点（颜色值为0）求平均，得到边中点F的颜色，根据C、D、M点和网格外一虚拟点（颜色值为0）求平均，得到边中点G的颜色，根据A、D、M点和网格外一虚拟点（颜色值为0）求平均，得到边中点H的颜色； 根据小正方形EBFM，四角点颜色的平均值，求出小正方形中点以及小正方形的边中点的颜色；然后再沿用上述规则计算小正方形MFCG的中点及边中点的颜色，以此类推，计算小正方形HMGD、AEMH的中点和边中点的颜色。分形插值算法生成云和山 10.2分形插值算法生成云和山 在X-Y平面上绘制一个n×n的正方形网格，并对4个角点在Z方向上分别设置初始高度ha、hb、hc、hd，得到A、B、C、D四点； 根据式hm=(ha+hb+hc+hd)/4+△，计算正方形网格中点的高度hm，其中△为一随机量，从而得到M点； 根据角点和中点以及虚拟点，计算边中点的高度，即 he=(ha+hb+hm+0)/4+△ hf=(hb+hc+hm+0)/4+△ hg=(hc+hd+hm+0)/4+△ hh=(hd+ha+hm+0)/4+△ 其中△为一随机量，从而得到E、F、G、H四点；分形插值算法生成云和山 10.2分形插值算法生成云和山 再根据E、B、F、M四点的高度计算小正方形EBFM中点的高度，类似地计算小正方形MFCG、HMGD、AEMH中点的高度，即 he’=(ha+hb+hm+he)/4+△1 hf’=(hb+hc+hm+hf)/4+△1 hg’=(hc+hd+hm+hg)/4+△1 hh’=(hd+ha+hm+hh)/4+△1 以及这些正方形边中点的高度； 递归上面的步骤使正方形网格逐步细化，直至达到预期递归深度，然后连接每个正方形网格点。