计算机图形基础第九章分数维图形

1、2022/7/171计算机图形基础第九章 分数维图形2022/7/172 自然景物模拟是计算机图形学的一个重要研究内容。与规则几何体不同，自然景物的表面往往包含有丰富的细节或具有随机变化的形状，它们很难用传统的解析曲面来描述。尽管凹凸纹理映射技术可以模拟规则景物表面的几何纹理细节，但在表达诸如山脉、云彩、火焰、树木、浪花等自然景象时，凹凸纹理映射技术仍难以胜任。从欧氏几何来看，这些自然景物是极端无规则的，为了解决这一问题，分数维图形生成技术应运而生。分数维图形是利用分数维几何学的自相似性质，采用各种模拟真实图形的模型，使整个生成的景象呈现出细节的无穷回归性质。所生成的景物中，可以有结构性较强的

2、树，也可以是结构性较弱的火、云、烟，甚至可生成有动态特性的火焰、浪等。2022/7/173分数维几何方法分数维几何概念 对复杂现象的探索早在图形学产生以前就已经开始，可以回溯到1904年，当时von Koch研究了一种他称为雪花的图形，他将一个等边三角形的三边都三等分，在中间的那一段上再凸起一个小正三角形,如图1所示，这样一直下去，理论上可证明这种不断构造成的雪花周长是无穷，但其面积却是有穷的。这和正统的数学直观是不符的，周长和面积都无法刻划出这种雪花的特点，欧氏几何对这种雪花的描述无能为力。图12022/7/174 二十世纪六十年代开始，重新研究了这个问题，并将雪花与自然界的海岸线、山、树等

3、自然景象联系起来，找出了其中的共性，并提出了分数维(Fractal)的概念。 Mandelbrot曾举了一个海洋线的例子来说明这一理论。假设我们要测量不列颠的海岸线长度，我们可以用一个1000米的尺子，一尺一尺地向前量，同时数出有多少个1000米。这样得到一个长度为L(1000米）。然而这样测量会漏掉许多小于1000米的小湾，因而结果不准确。如果尺子缩到l米，那么我们会得到一个新的结果L(l米)，显然L(1米)L(1000米）。一般来说,如果用长度为r的尺子来量，将会得到一个与r有关的数值L(r)。与Koch的雪花一样r0，L(r)。也就是说，不列颠的海岸线长度是不确定的，它与测量用的尺子长度

4、有关。2022/7/175 Mandelbrot注意到von Koch雪花与海岸线的共同特点：它们都有细节的无穷回归，测量尺度的减小都会得到更多的细节。换句话说，就是将其一部分放大会得到与原来部分基本一样的形态，这就是Mandelbrot发现的轰动整个自然界的复杂现象的自相似性(Self Similarity）。为了定量地刻划这种自相似性，他引入了分数维概念，这是与欧氏几何中整数维相对应的,所以也称为分数维几何。分数维的引入，为研究复杂性提供了全新的角度，使人们从无序中重新发现了有序，许多学科象物理、经济、气象等都将分数维几何学作为解决难题的新工具。计算机图形学也从中受到启发，并形成了以模拟自

5、然界复杂景象、物体为目标的分数维图形学，由此方法生成的图形称为分数维图形或分形。2022/7/176统计自相似 对象被细分后的部分相互之间或与整体相似或相同的特性称之为自相似。von Koch曲线是严格自相似的。但海岸线不同，细分放大后，海岸线的每一小部分看起来像，但不完全像一个大些部分，所以，海岸线不是严格自相似，而是统计自相似。然而，分形维数的概念也可用于这样的统计自相似对象。统计自相似是自然界中分形的主要特征，象山、云、火、浪等都具有统计自相似的特性。分形的维数 分数维图形的细节变化可以用数字D来描述，D称为分形维数，它是图形粗细性的度量，同图形每一步细分数目和缩放倍数有关。2022/7

6、/177 设N为图形每一步细分的数目，S为细分时缩放因子，分形维数D定义为： 分形维数不像我们所熟悉的欧氏几何的维数是一整数，它可以是分数，这也是其名称的由来。如图.2是两个示例。图.22022/7/178 通常一维的对象（例如线段）可被分成N个相同部分。每一部分从整体上缩小S=1/N的比例。类似地，诸如平面上方形区域的二维对象可被分成N个自相似部分，每部分缩小S=1/N1/2的比例。像固体立方体这样的三维对象可被分成N个小立方体，每个立方体缩小S=1/N1/3的比例。按这样的S与N的关系细分得到的是欧氏几何的结果，维数是整数。如图2(b)所示，若我们按欧氏几何的方法，将一线段四等分，则N=4

7、，S=1/4，则D=1。得到的是同欧氏几何相一致的整数维。将一正方形16等分，此时N=16，线段的放大倍数S=1/4，则D=2。 利用自相似，对分形大小的推广是直观的。一个D维自相似对象可被分成N个更小的部分。每一部分缩小S因子。其中或者当D不取整数时，细分的结果是一个分数维图形。2022/7/179 仍以von Koch曲线为例，D非整维数(大于1而小于2)反映了曲线的特征。它从某种程度上更多填充了空间而非简单直线(D=1),但是又小于一个欧氏平面区域(D=2)。当D从1增加到2时，结果曲线从“线形”逐渐填充大部分平面，实际上，极限D=2产生一个称为Peano曲线或空间填充曲线，如图3所示。

8、这样，分形维数就提供了一个曲线摆动的度量。尽管这些von Koch曲线具有1到2的分形维数，但它们均是保持具有拓朴维数1的“曲线”，即去掉一个点即可将曲线分为两部分。2022/7/1710图32022/7/1711 一般地说，二维空间中的一个分数维曲线维数介于1和2之间，三维空间中的一个分数维曲线维数在1和3之间，而三维空间中的一个分数维曲面维数在2和3之间。9.2.1 分形生成过程 分形有二个基本特征：每点处无限的细节以及整体和局部特性之间的自相似性。自相似性质可有不同形式，这取决于分形表示的选择。可以用一个过程来描述分形，该过程为产生分形局部细节指定一重复操作。理论上自然景物用重复无限次的

9、过程来表示。实际中，自然景物的图形仅用有限步生成。如果给定一过程变换函数，一个分形可以通过在一空间区域里对初始图形重复使用变换函数来生成。 2022/7/1712若P0是选定的初始图形，每次重复变换函数的计算： P1=F(P0），P2=F(P1），P3=F(P2）可得细分的图形。增加变换次数可以产生更多细节，也更靠近一“真正”分形。 一般地，变换函数可以应用于给定的点集，或者应用于基本元素的初始集上，如直线、曲线、颜色区、表面和实体。每次重复时，我们既可用固定的也可用随机的生成过程。变换函数也可定义成几何变换，或者用非线性变换和决策参数来建立。 有许多种构造变换函数的方法，它们形成不同的分数维

10、图形构造模型。2022/7/17139.2.2 随机插值模型 为了克服传统模型技术中模型依赖于观察距离的局限性，本模型不是事先决定各种图素和尺度，而是用一个随机过程的采样路径作为构造模型的手段。例如构造二维海岸线的模型可以选择控制大致形状的若干初始点。再在相邻两点构成的线段上取其中点，并沿垂直连线方向随机偏移一个距离，再将偏移后的点与该线段两端点分别连成两个新线段。这样下去可得到一条曲折的有无穷细节回归的海岸线，其曲折程度由随机偏移量控制，它也决定了分数维的大小。在三维情况下可通过类似过程构造山的模型，一般通过多边形，简单的如三角形，细分的方法。2022/7/1714 可以在一个三角形的三条边

11、上，随机各取一点，沿垂直方向随机偏移一距离后得到新的三个点，再连接成四个三角形,如图5所示，如此继续，即可形成褶皱的山峰。山的褶皱程度由分数维控制。该模型能有效地模拟海岸线和山等自然景象图52022/7/1715 随机中点位移方法是一种简便快速逼近地面和其它自然现象的随机插值方法。从一直线段开始，设线段的起点P0，终点Pn。线段中点位移值通过起点和终点的平均值加上一随机偏移值r来获得： PmP0Pnrr值为从O到正比于| Pn-P0|2H的均方差之间的高斯分布，其中H=2-D，D1是分形维数。对中点位移后产生的两部分线段继续进行随机中点位移，递归进行可以得到模拟的自然现象。实际图形生成演示20

12、22/7/1716选代函数系统模型 该模型以迭代函数系统理论作为其数学基础。一个n维空间的迭代函数系统由两部分组成，一是一个n维空间到自身的映射变换的有穷集合M=M1,M2,.,Mn；二是一个概率集合P=P1,P2,Pn。每个Pi与Mi相联系，Pi=1。迭代函数系统是以下述方式工作的：取空间中任一点Z0，以Pi概率选取变换Mi，作变换Z1=Mi(Z0)，再以Pi的概率选取变换Mi，对Z1作变换Z2=Mi(Z1)，以此下去，得到一个无数点集，该模型方法就是要选取合适的映射集合、概率集合及初始点，使得生成的无数点集能模拟某种景物。如果选取的映射变换特征值的模小于1，则该系统有唯一的有界闭集，称为迭

13、代函数系统的吸引子。直观地说，吸引子就是迭代生成点的聚集处。点逼近吸引子的速度取决于特征值大小。2022/7/1717选代函数一般使用复平面，一种常用的选代函数是多项式变换函数： f(z)=z2+c 这一复映射变换的有界闭集称为Julia集合。迭代过程写成： zn+1=zn2+c 适当选取c,可以生成类似于云的分数维图形。图7所示是c分别取c1和c2时,生成的图形。图72022/7/17189.2.4 正规文法模型 该模型是1983年为模拟植物而引入的。正规文法模型能够生成结构性强的拓朴结构，如植物，再通过进一步几何解释来形成逼真的画面。该模型的工具是并行重写系统，它与形式语言理论中的一般重写

14、系统有两点主要区别：一是该系统中产生式的匹配对一个输入字符串的所有字符是同时进行的；二是该系统没有终结符和非终结符之分。并行重写系统的一个子集是L系统。L系统最简单的类型称作OL系统，它是上下文无关的。先以一个例子叙述主要思想。考虑由两个符号a和b组成的字符串， a、b可在同一字符串中出现多次。每个符号与一个改写规则有关。例如，如果写aab，那么这表示符号a用ab替换。ba表示符号b用a替换，这便是一个改写规则。改写过程从一个称作公理的符号开始，2022/7/1719 例如这个单词仅包括一个符号b，那么，第一步，由规则ba 可知公理b被a替换；第二步由规则aab得到字符串ab。下一步将对ab中

15、的a与b分别施行相应的替换，得到新的字符串aba，接着由aba生成abaab，由abaab又生成abaababa，继而生成abaababaabaab。过程如下列所示： b a ab aba abaab abaababa abaababaabaab这个例子说明怎样从一个符号出发，依据两条规则，递归地产生新的字符串。这种作法可以用来表示生长过程。2022/7/1720令V表示符号集合，OL系统是一个有序的3元素集合： G=（V,P,S）这里S是一个非空起始符，称作公理；P是产生式或重写规则集合，产生式的前驱和后继用“”相连，如aab。 要模拟具体的景物，除拓扑结构外，还需要加上几何形状，诸如线段的

16、长度和线段的转角。设想一只乌龟在平面上爬行，其状态用三个值来描述，记以(x,y,),其中x,y为龟所在位置的直角坐标，表示爬行的朝向，另外给出爬行步长d及扭转方向的角度增量。为了产生几何形状。定义下面符号的含义： F：向前移动一步，步长为d。龟的新状态为(x,y,),其中2022/7/1721从(x,y)向(x,y)画一直线段；+：向左转角，龟的下一状态为(x,y,+)，规定正向角是逆时针方向，负向角是顺时针方向；-：向右转角，龟的下一状态为(x,y,+)。 现在给出一个字符串的例子： FFFFFFFFFFFFFF =90则生成的图形如图8所示。图82022/7/1722令步长d在相邻两级子图

17、之间缩短4倍，规定后继多边形线(折线)端点之间的距离等于前驱线段的长度，起始符S和重写规则P及转角分别为： S：FFFF P：FFFFFFFFF =90其中，S表示一个封闭的正方形边界曲线。经过三次改写，我们得到n=1,n=2,n=3的von Koch曲线，也称为“Koch岛”。如图9所示。图92022/7/1723 为了形式化地描述许多植物的分支结构，引入两个新的字符，其含义为： : 将当前乌龟爬行的状态压入堆栈。信息包括乌龟所在的位置与方向等； : 从堆栈中弹出一个状态作为乌龟的当前状态，但不画线。 新字符的引入，使得分支结构能以简单的方式进行描述，例如，从图10(a)开始，字符串 FFF

18、F,=45产生图10(b) 所示的树，而FFFFFFFFF, =45产生图10(c)所示的树。图102022/7/1724 图11(a)(b)(c)中的三个图是采用这种带括号的产生式生成的分支结构，其中 （a） n=5，=30 S：F P：FFFFFF (b) n=5，=20 S: F P：FFFFFF （c） n=4，=20.5 S: F P：FFFFFFFFF 图112022/7/17259.2.5 粒子系统模型 粒子系统模型是W.T.Reeves 在1983年提出的又一个随机模型，用于模拟诸如云、烟、火等具有变化形状的自然景物。粒子系统采用粒子图元(Particle）来描述景物。粒子可以

19、随时间推移发生位置和形态变化。每个粒子的位置、取向及动力学性质都是由一组预先定义的随机过程来说明的。每个粒子均有一定的生命周期，它们不断改变形状、不断运动。粒子系统的这一特征，使得它充分体现了不规则模糊物体的动态性和随机性，很好地模拟了火、云、水、森林和原野等自然景观。 粒子系统最初引入时是为了模拟火焰。火焰被看成是一个喷出许多粒子的火山，粒子运动的轨迹构造了火焰的模型，每个粒子都有一组随机取值的属性，如起始位置、初速度、颜色及大小。后来又用该模型来模拟丛草、森林等全景要求高的景象。2022/7/1726粒子形状可以是小球、椭球、立方体或其它形状，粒子的大小和形状随时间变化。其它性质如粒子透明度、颜色和移动等都随机地变化。为模拟生长和衰亡过程，每个粒子均被赋予一定的生命周期，它将经历出生、成长、衰老和死亡的过程，不断有旧的粒子消失，新的粒子加入。粒子系统生成一娴幕静街枋牵 （1）生成新的粒子，并赋予每一新粒子以一定的