分形的计算机生成

分形的计算机生成

分散理论是一门非线性的新兴学科。自从20世纪70年代,B.B.Mandelbrot首先提出分形以来,这门学科无论在其数学基础还是在其他学科的应用方面都得到了迅速发展。目前,分形理论在物理、化学、生物学、医学、材料科学、地质、地震、经济学等学科以及工程技术中都有着广泛的应用,特别是随着计算机技术的迅速发展和广泛应用,分形的思想和方法在模式识别、图象处理、自然景物的模拟、信息讯号的处理以及艺术制作等领域都取得了极大的成功。人们把分形与耗散结构及混沌理论称为70年代中期科学上的三大重要发现。在分形的诸多研究课题中,分形的计算机生成问题有明显的挑战性。采用分形生成方法,可以从少量的数据出发生成复杂的用传统数学方法无法表达的形态,如山脉、花草、科学实验中的生成物等,还能生成根本“不存在”的图形世界。这使人们在计算机仿真模拟方面前进了一大步。分形在“制造”以假乱真的景物方面的进展和潜在的前途,使得无论怎样估计它的影响也不过分。在分形的计算机生成中,自然景物的模拟是一个重要的研究内容。由于蕴含于自然景物中的图形具有无穷多的随机纹理细节,即使选择简要造型,也需要使用一个庞大的数据结构,而且随着对自然景物观察尺度的变化,在自然景物中又有无穷细节需要描述,因此已存贮在数据结构中的细节资源可能很快陷入枯竭,所以采用一般的图形生成方法中所使用的静态数据结构来表示一个自然景物是不可取的。考虑到自然景物中纹理的随机性和自相似性,许多研究者将目光转向随机过程理论,并提出了一系列有效的过程迭代模型来生成各种特定的自然景物。一般地,这类模型均采用递归方式,并通过引进随机变量来反映细节的千变万化,随着迭代的不断进行,算法生成的随机纹理细节也将越来越丰富。人们将这样的模型称为过程模型或算法模型(proceduremodel)。常用的过程模型有以下5类:1)基于分形迭代的算法模型,如L-系统;2)基于三维噪声和湍流函数的算法模型;3)基于Fourier合成原理的算法模型;4)基于语法规则的算法模型;5)基于动态随机生成原理的算法模型。在基于动态随机生长原理的算法中,Reeves的粒子系统(particlesystem)是具有代表性的一种算法。1粒子系统的模拟粒子系统是迄今为止被人们认为模拟不规则模糊物体最为成功的一种图形生成算法。由于自然景物的计算机模拟的其他算法模型往往是专门针对某一类自然景物而设计的,因而无法用统一的一种模式来生成诸如云、烟、火、结晶体的凝聚等具有变化形状的自然景物。而粒子系统采用一种完全不同于以往造型的绘制系统的方法来构造、绘制景物。景物被定义为由成千上万个不规则的随机分布的粒子所组成,而每个粒子均有一定的生命周期,它们不断改变形状,不断运动。在粒子系统中,最关键的是景物的总体形态和特征的动态变化,而不是各个粒子本身。粒子系统的这一特征,使得它充分体现了不规则模糊物体的动态性和随机性,能很好地模拟火、云、水、森林和原野等自然景观和材料科学、化学、生物等学科中粒子动态变化及形态。粒子系统并不是一个简单的静态系统,而是一个复杂的动态系统,随着时间的推移,系统中已有粒子不断改变形状、不断运动,而且不断有新的粒子加入,并有旧粒子的消失。为模拟生长和死亡过程,每个粒子被赋予一定的生命周期,它将经历出生、成长、衰老和死亡的过程。同时为了使粒子系统所表示的景物具有良好的随机性,与粒子有关的每一参数均受到一个随机过程的控制。粒子系统的上述构造方式使得用它来模拟动态自然景物,如流水、云彩飘移等成为可能。生成粒子系统某瞬间画面的基本步骤如下1)将产生的新粒子加入系统中;2)赋予每一粒子以一定的属性;3)删除那些已经超过其生命周期的粒子;4)根据粒子的动态属性对粒子进行移动和变换;5)绘制并显示由有生命的粒子组成的图形。上述步骤中每一步的操作均是过程计算模型,因而它可与任何描述物体运动和特征的模型结合起来。例如,粒子的运动、变换可用一偏微分方程来表达。为表达粒子系统的随机性,还可采用一些非常简化的随机过程来控制粒子在它所在系统中的形状、特征及运动。对每一粒子参数均确定其变化范围,然后在该范围内随机地确定它的值,而其变化范围则由给定的平均期望值和最大方差确定,其基本表达式为:par=mp+rand()×varpar,(1)式中par代表粒子系统中的任一需要确定的参数,rand()为区间[-1,1]上的均匀随机函数,mp为该参数的均值,varpar为其方差。粒子数目在很大程度上影响模糊物体的密度及其绘制色彩。这可以通过确定每一时刻进入系统的粒子来控制系统中的总粒子数目,而每一时刻进入系统的粒子数则可由给定粒子的平均数和方差按(1)式计算。为了有效控制粒子的层次细节及绘制效率,也可根据单位屏幕面积上所具有的平均粒子数mpt和方差varpt来确定进入系统的粒子数npt,此时(1)式可修改为:npt=(mpt+rand()×varpt)×screenp,(2)式中screenp为当前模拟景物在屏幕上的投影面积。式(2)有效地避免了用大量粒子来模拟在屏幕上投影面积很小的景物,大大提高了算法的绘制效率。另外,在粒子系统中还可以将上述进入系统的平均粒子数看作是时间的函数,从而使粒子系统在光强和颜色上有所变化。还可用(1)式确定粒子的初始位置、大小和方向、颜色、透明度、形状及生命周期等基本属性。同时考虑到被模拟的自然景物的复杂性和多变性,在模拟时也可根据需要用多个粒子系统,这时只要通过粒子系统的层次结构来加强对复杂物体的整体控制即可。2dla模型中的生成物上述的粒子系统的造型方法具有一般性,可根据个人爱好和不同的应用的需要,设计出独特的粒子系统,从而得到不同的模拟效果。自然界中的许多物体和现象明显地以分形的形状生长,分枝重复地分裂产生了更小的边分枝。当用适当的尺度观察一些树、一些根系、一些植物时,看起来均是分形。闪电和其他的放电现象的分叉状图样以及在水中加进粘性液体时所发生的“粘性指进”也都具有分枝分形的形式。在硫酸铜电解过程中,阴极上铜的沉积也是以分形形式生长的。为了解释和观察烟尘微粒的分形聚集,Witten和Sander1981年单独提出了Witten-Sander模型。这是一种特殊的有限扩散凝聚模型(Diffusion-LimitedAggregation)即DLA模型。它是一个特殊的粒子系统,习惯上人们把这种模型称为DLA模型。该模型的规则如下:先在平面的中心放一个被称为种子的粒子,然后在远离种子的地方释放出另一个粒子,该粒子可以随机地行走(称之为扩散)。当它运行到种子旁边时,停止行走,留在该处不动。接下来第二个粒子被释放出来,也是随机行走,当它靠近种子或第一个粒子时,也停留不动……。如此反复地进行下去,就可以获得一个称之为凝聚体的生成物。该凝聚体具有有限扩散条件下生成物的特征,即树枝状标度不变的复杂结构。如图1便是用VisualC++6.0编制的模拟DLA模型的程序所生成的图形。该图形是从长宽为300×300像素单位的矩形四边中点位置发射随机行走的具有一个种子的3500个粒子而形成的凝聚体。图2是从300×300像素单位矩形四边中点位置发射而具有两个种子的8000个随机行走的粒子而形成的凝聚体。按Hausdorff维数的意义,根据公式DH=limδ→0lnN(δ)ln(1/δ)DΗ=limδ→0lnΝ(δ)ln(1/δ)计算可得DH≈1.70。另外按盒维数(Boxdimension)(也叫Minkovski维数)的定义,根据公式DB=limδ→0lnNδ(F)ln(1/δ)DB=limδ→0lnΝδ(F)ln(1/δ)计算可得DB≈1.70。根据填充维数(Packingdimension)与Hausdorff维数、Minkovski维数的关系:DH(F)≤(D)P(F)≤DB(F)¯¯¯¯¯¯¯¯¯¯DΗ(F)≤(D)Ρ(F)≤DB(F)¯可知,对于这个凝聚体,DH=DP=DB≈1.7。如果对上述DLA模型中从矩形的四个边中点发射扩散粒子改为从矩形上下边中点发射粒子,可以得到如图3和图4所示的凝体。图3中的凝聚体是从300×300像素单位的矩形的上下边中点发射1800个随机扩散粒子所形成的凝聚体。图4中的凝聚体是从300×300像素单位的矩形的上下边中点发射3200个随机扩散粒子所形成的凝聚体。根据盒维数(Minkovski维数)计算公式,可计算出这种类型的DLA凝聚体的分形维数DB≈1.67。如果改变DLA凝聚模型的其他条件也可以得到与此形状不同的凝聚体。DLA模型计算机模拟中的参数设置主要有以下几个方面:运动粒子与不动粒子(聚集体)之间的距离为多大时,它停止运动并粘附在聚集体上,成为不动粒子。一般分为最邻近、次邻近、相接触3种类型;运动粒子粘附到聚集体上的几率;扩散步长;凝聚中心即种子的数目;粘附在聚集体上的粒子脱离凝聚体的几率;表面张力的影响、扩散粒子的反应几率、表面粗糙度以及各向异性的影响等等。大量的计算机模拟表明,即使让参加模拟的随机扩散粒子的总数从几千到几万变化,按DLA模型生长的分形凝聚体都满足标度不变性和自相似性,其分形维数都近似等于1.67。同时,按DLA模型模拟得到的凝聚体,只要尺度足够大,那么其分形维数与模拟时有无点阵以及点阵的类型(如三角形、正方形、六边形等)无关。上述DLA模型的计算机模拟过程是一个特殊的粒子系统,通过它可以模拟自然界中的