计算机图形学07分形几何.ppt

分形几何fractal分形几何造型的基本概念n1904年Koch研究了“雪花”图形，欧氏几何无法解释n1960年代Mandelbrot重新研究了这问题，并将此“雪花”与自然界中的海岸线、山、树联系起来，提出了“Fractal”这个词n由于不规则现象在自然界是普遍存在的，因此分形几何又称为描述大自然的几何学分形几何造型的基本概念n Mandelbrot 1967年的论文：“英国海岸线的长度不确定”n海岸线的长度随测量尺度变化而变化n对自然几何形态的数学研究（1）具有无限嵌套层次的精细结构（2）在不同尺度下具有某种相似特性分形几何造型的基本概念n分数维（Fractal Dimension） D = 其中：N为每一步细分的数目，S为细分时的缩放倍数Koch雪花线的维数是 log Nlog(1/S)分形几何造型的基本概念n分行图形处处不规则（混沌chaos）n在不同尺度上，图形的规则性又是一致的自相似 self-similar）分形的应用领域n物理学——如湍流的研究n气象学——如云系的形状n地貌学——如山川、地形、地貌的形态n图象处理——如图象压缩n美术——如分形艺术典型的分形曲线集1. Von Koch曲线 典型的分形曲线集2. Sierpinski三角形 典型的分形曲线集n3. Mandelbrot 分形集n G(Z) = Z2 + Cn 其中 Z 和 C都是复数n迭代公式：nxn+1 = xn2-yn2 + Cxnyn+1 = 2*xn*yn + Cy典型的分形曲线集分形技术的常用模型n随机插值模型 本模型不是事先决定各种图素和尺度，而是用一个随机过程的采样路径作为构造模型的手段 。

n粒子系统模型 本模型是用大量的粒子图元（particle)来描述景物n正规文法模型（Graftal)    本模型是用正规文法生成结构性强的物体的拓扑结构，在通过进一步几何解释来形成逼真的画面n迭代函数系统模型    本模型以迭代函数系统理论作为数学基础随机插值模型 Xnew=1/2(Xi+Xi+1)     Ynew=1/2(Yi+Yi+1)+P(Xi+1-Xi)R(Xnew)随机插值模型一维中点变换算法:    以一条水平地平线段开始    重复足够多次{　　对场景中的每条线段做{　　　　找到线段的中点　　　　在 Y 方向上随机移动中点一段距离　　　　减小随机数取值范围　　}}    随机插值模型 每次循环减少的越多，所得山脊线就越平滑但如果减得太多，则会有明显的锯齿感 随机插值模型 随机值范围设为 -1.0 到 1.0 （可任意取） 随机值范围减为 -0.5 到 0.5 （可任意取） 随机值范围再减为 -0.25 到 0.25 （可任意取） 随机插值模型粗糙度常量 这个值决定每次循环随机数值域的减少量，也就是说，决定分形结果的粗糙程度。

使用一个 0.0 到 1.0 之间的浮点数并称之为 H 随机数范围在每次循环时乘上2(-h) 粒子系统模型 该模型是由粒子刻划的，粒子可以随时间推移发生位置和形态的变化每个粒子的位置、取向及动力学性质都有一组预先定义的随机过程来说明每个粒子运动时，其路径被绘制且以特殊颜色显示粒子系统模型生成粒子系统瞬间画面的基本步骤： （1）将产生的新粒子加入系统中； （2） 赋予每一粒子以一定的属性； （3） 删除那些已经超过其生命周期的粒子； （4）根据粒子的动态属性对粒子进行移动和变换；           （5）显示由有生命的粒子组成的图形粒子系统模型与粒子有关的每一参数均受到一个随机过程的控制确定粒子参数的基本表达式：par=mp+rand( )*varpar par :粒子系统中的任一需要确定的参数 rand():均匀随机函数 mp:参数的均值 varpar：方差粒子系统模型模拟火焰： 火焰可以用在一个球域内的随机生成微粒来显示，其允许它们向外快速移动。

微粒路径可以用红色到黄色来着色，可以模拟爆炸粒子的温度粒子系统模型粒子系统模型模拟草丛： 草丛的真实感显示可以用“轨道”微粒来模拟，这些微粒从地面上射出，并在重力的作用下回落到地面微粒路径可用一卷柱体模拟，并可以使用从绿到黄的颜色粒子系统模型模拟瀑布： 水粒从一个高度落下，被一障碍物偏移，然后散开到地面不同的颜色用来区分每步的微粒路径粒子系统模型模拟物体分解： 左边物体分解成右边物体的微粒状况正规文法模型 该模型的工具是并行重写系统 它与形式语言理论中的一般重写系统有两点主要区别：一是该系统中产生式的匹配对一个输入字符串的所有字符是同时进行的；二是该系统没有终结符和非终结符之分 它可分为两大类：一类是象von Koch曲线这样“比较规则”的曲线 ；另一类是象植物枝一样的比较复杂的树状分形    正规文法模型产生规则：   AAA   BA[B]AA(B)   A：树枝   B：树叶   [ ]：左分枝   ( )：右分枝正规文法模型产生规则： A:沿逆时针方向角度 ;    B:沿顺时针方向转角度;    C:当前状态栈记录当前点的坐标,及角度)    D:出(取最近的一次 压入骱的信息 , 同时修改指针);    从当前点开始沿当前方向 画一线段E,G,H,I,J这些字符 在下次迭代中将分别被E $.G $.H $,I$,及J$所替代.其中    E$="EI"    G$="BHCAGDI"    H$="AGCBHDI"    I$="CAFFFDCBFFFDF"    J$="CBBBGDCAAAGDEJ"  正规文法模型正规文法模型4种不同种类树木的分形图形正规文法模型von Koch曲线曲线的构造是： 迭代初始把单位线段去掉中间的三分之一，代之以底边在被除去线段上的等边三角形的另外两边，重复进行迭代。

这些曲线的生成元是“_/\_”，曲线由把每一折线段反复迭代成缩小比例为1/3的生成元而成相似维数：    DS正规文法模型产生规则： A：沿逆时针方向转一角度δ；    B：沿顺时针方向转一角度δ；    C：从当前点开始沿当前方向画一长度L的线段   “CACBBCAC”中的C这一“操作”用复合“操作”C$=“CACBBCAC”来替代：    C$+“A”+C$+“BB”+C$+“A”+C$    正规文法模型正规文法模型正规文法模型布料设计作品 迭代函数系统模型一个n维空间的迭代函数系统由两部分组成： 一是一个n维空间到自身的线性映射的有穷集合M，二是一个概率集合P工作方式： 取空间中任意一点Z0，以Pi概率选取变换Mi，做变换Zi=Mi（Z0），同样地再对Zi做变换Zi+1=Mi（Zi），以此下去得到一个无数点集，该模型的方法就是要选取合适的映射集合，概率集合及初始点使得生成的无数点集能模拟某种景物迭代函数系统模型Sierpinski集集nSierpinski缕垫nSierpinski地毯迭代函数系统模型Sierpinski集集nSierpinski海绵Sierpinski集Sierpinski集Sierpinski集的共同特征：       （1）都是经典几何无法描述的图形，它是一种“只有皮没有肉”的几何集合。

       （2）都具有无穷多个自相似的内部结构，任何一个分割后的图形经适当放大后都是原来图形的翻版                     Sierpinski集Sierpinski缕垫    产生方式：    首先将一个等边三角形四等分，得到四个小等边三角形，去掉中间的一个，保留它的三条边，将剩下的三个小等边三角形再分别进行四等分，并分别去掉中间的一个，保留它们的边，重复操作直至无穷Sierpinski集Sierpinski缕垫相似维数：DS=logN/log(1/S)         N为每一步细分的数目，S为细分时的放大（缩小）的倍数Sierpinski集地毯设计作品 迭代函数系统模型Julia集集产生方式：    在复平面C上，由一个带有常数c的复变函数     f（z）的迭代生成Julia集 在复平面上，水平的轴线代表实数，垂直的轴线代表虚数每个Julia集合（有无限多个点）都决定一个常数C，它是一个复数在复平面上任意取一个点，其值是复数Z将其代入下面方程中进行反复迭代运算：  Zn+1=Zn2+c 就是说，用旧的Z自乘再加上C后的结果作为新的Z。

再把新的Z作为旧的Z，重复运算 Julia集Julia集    F(z)=z2+c C的取值不同，产生的图形也不同Julia集Sin(z)的 Julia集Julia集人体中的分形 人体中存在着大量类似分形的组织结构，例如肺中的支气管树结构，神经元的增长可以用分形分叉模式建立大脑连接和神经元增长的模型      树分行模拟树突结构                 f(z)=z2+iJulia集自然景物中的分形分形动物               f(z)=z2+0.122+0.745i         f(z)=z2+0.360284+0.100376i  Julia集分形植物 由f(z)=z2产生的4花瓣花Julia集分形岩石Julia集自然纹理模拟图像: 采用分形超纹理基元模型生成的，这些纹理图像既有分形统计自相似特性，又具有纹理的结构特征 迭代函数：Zn+1=Z2n-0.5×Z+c Mandelbrot集Mandelbrot集M     为使fc的Julia集连通的参数c的集，     M={c：J（fc）是连通的}     也就是使fc的轨道不发生逃离的c的点集。

特征：    一个主要的心型与一系列圆盘形的“芽苞”突起连接在一起，每一个芽苞又被更细小的芽苞所环绕，以此类推Mandelbrot集Mandelbrot集产生方式：    在复平面内对映射f（Z）=Z2+Ci进行迭代就可以得到Mandelbrot集Mandelbrot集特点：n Mandelbrot集是二维复数平面上的大量点的堆积，它的形状不是由一次求解一个方程来定义的，而是在复平面上通过反馈环进行迭代来定义的此时迭代的方程就变成了过程而不是描述，是动态而不是静态Mandelbrot集的产生就是无穷次的迭代和精细化的结果，迭代产生大量的点并不满足一定的方程，而是产生一种行为n跨越尺度极其深渊，具有无穷复杂的边界它的内部不是连通的，而是由众多的块片组成，它们或是大心形线、圆周(一个心脏形的曲线)，或更小的和变形的心形线和圆周所界住的区域，其数无穷Mandelbrot集的延伸指数指数αα的取值对的取值对C C平面分形的影响平面分形的影响由复迭代变换Z=Zα+C得到的分形图是与指数α的取值有关的 Mandelbrot集与Julia集nJulia集合中的C是一个常量，Z作为原始点进行迭代；而Mandelbrot集合是用不同的C值反复进行迭代。

nMandelbrot集概括了所有可能的Julia集，它是无穷数量的Julia集的直观的图解目录表 Mandelbrot集和Julia集 它们都是由方程不断进行迭代产生一系列的点组成的在通过计算机绘图时，为屏幕上的像素指定不同的颜色，就可以绘制出复杂的图形Newton分形    把Julia集的迭代函数f(z)中的常值C加入变换，并改变一下算法，同时用同样的方法去估算Z，逼近答案，产生奇特的并称之为"Nova"的分形图形螺旋分形产生方式： 首先在范围框架的中心做一个点，接着，从五个框架中随机挑选一个（不包括范围框架）图中，随机选择的结果是蓝色框架，所以就在蓝色框架的中间同样作一个点，这样，范围框架的上半部分就有了一个点再随机选择另外的一个框架，这次选中了绿色框架那么，就在绿色框架的上半部分作一个点，这个过程被一遍又一遍地重复，就得到了一幅完美的分形图螺旋分形 在迭代函数系统中，框架其实给整个系统传递了信息框架的方向以及框架的大小决定怎么缩放整个图，这其实是定义了一个仿射变换，仿射变换可以由一个函数来表示，这也正是命名“迭代函数系统”的原因简单地说，迭代函数系统就是指把仿射变换函数系统经过多次迭代形成的分形。

分形技术n分形技术的不同模型可以模拟自然界的景物和其他不规则形状物体不同的景物具有不同的特点，应选用合适的模型n分形技术不仅在图形学上得到了广泛的运用，在生物学、地理物理学、天文学、经济学等其它领域也得到广泛的应用。