分形在自然景观仿真研究中的进展与展望

刘 鹏（太原工业学院 太原 030008）

【摘要】分形几何学是自然景观仿真研究的一项重要技术，国内外学者在这方面做了大量的研究。自然景观仿真的基本要素是云、山和树等方面。本文给出了在分形云、分形山以及分形树方面的现有研究成果；同时在此研究基础上，提出了对自然景观综合模拟的算法建议。

【关键词】分形几何 视景仿真 算法

1 引言

自然景观一般由山、云和树等景物组成。分形几何学是描述大自然的几何学，对具有“自相似”的不规则和具有高度“复杂度”景物的描述，已收到了惊人的逼真效果。用分形理论模拟自然景观尚处于探索阶段，国内外学者对此做了大量的研究，但这些研究成果多数只是零碎的分形景物，而且各技术之间没有协调统一起来。为此本文集中给出了其研究成果，并在已有成果的基础上提出了笔者的见解。

尽管自然界的诸多事物形态各异，看似杂乱无章，但仔细观察后不难发现这些景物无不具有自相似的特点。只不过这种自相似是统计意义上的自相似^[1]。因此，采用相应的分形模型模拟自然景观，其图像质量将达到前所未有的逼真效果。递归算法是分形几何中的经典算法，常用来构造分形模型。

2 分形在自然景观仿真研究中的进展

研究表明^[2]，地形具有分形的性质，即满足 。其中N(r)为所研究范围内的物体数目，r为物体的线性大小，D为这个系统的分形维数。

一维地形的分形维数为 ，D的值在(1，2)之间，相应的β值在(1，3)之间，注意：这里的一维不同于一般所理解的概念，沿着某一固定方向还有高度的变化。

二维的分形维数为 ，其中D的数值范围是(2，3)。

2.1.1 随机中点位移法

随机中点位移法是描画分形景观常用的基本技术，其计算要点如下[3]。

⑴取当前区间并将它分成两半。

⑵利用公式 计算中间值，其中N(0,s)是Gauss随机变量，其均值为0，方差为s，N(0,1)是Gauss随机变量的一个样本。

⑶在新的区间重复上述过程，把新区间的标准偏差减至原值的1/2。

随机中点位移法的核心是迭代函数和高度随机函数的使用，大致可分为如下两类。

图1  三角形随机中点位移法原理图

a.初始图像为一个三角形，将初始三角形的各边采用垂直向上的随机中点位移法，各边的中点在高度方向上经随机偏移得到的新点与边的端点就构成了新的三角形，并对所得的新三角形选择明暗不同的颜色进行填充，完成一次递归调用。对新得的三角形继续应用随机中点位移法，通过递归并逐渐减小随机数的取值范围，最后得到分形山。加拿大卡尔加里大学的Przemyslaw Prusinkiewicz和Mark Hammel^[4]就用过这种算法来构造分形山，原理如图1，生成的分形山如图2。

图2 三角形随机中点位移法生成图

 b.首先给定一个矩形，然后联结各边的中点得到一田字型的四个子块区域，在田字型的四个顶点和中心，施行随机中点位移法，即将中心在高度方向上经随机偏移得到第一个凸峰，并将偏移所得的新点与原矩形的四个顶点联结，得到四个三角形。选择明暗不同的四种颜色对得到的四个三角形进行填充，完成一次调用。对四个子块，再重复上述操作，经过多次递归调用并逐渐减小随机数的取值范围最后可得到分形山。西安交通大学的李水根在其编著的《分形》一书中就用到了该算法^[3]。这种算法的生成效果见图3所示。

图3 矩形随机中点位移法生成图

需要说明的是，随机中点位移法还有网格法以及散点法，但这些方法生成的分形山由于存在网格与散点而不够逼真，如果将高分辨率的网格图或散点图应用到低分辨率分形山的景观模拟中，其效果还是相当可观的。网格法生成的分形山，其效果如图4所示。

图4 网格法分形山生成效果图

2.1.2 分形插值法

分形插值法是美国佐治亚理工学院的M. F. Barnsley于1986年首次提出的，他利用了一组仿射变换产生的迭代函数系统(Iterated Function System, IFS)，该函数对平面上一组节点进行插值。IFS是分形图形绘制的一种重要方法。Paul Martz^[5]详细介绍了二维分形插值算法。本算法的核心在于随机数与递归算法的应用。这种算法生成的山逼真程度高，峰谷过渡自然。这主要得益于递归过程中所加的随机数的取值范围逐渐减小。分形插值法适宜创作连绵的山峦景观。采用相应的着色算法可以使色调过渡自然，完全符合自然界的实际情况，具体的着色方法可参见后文用分形插值算法生成分形云。经过人工着色，山峰为白色，山谷为绿色，两者之间用灰色过渡。其生成的效果可参见图5。

图5 分形插值法生成的效果图

王梦与金文标^[6]对原有的插值算法进行了改进，完成了三维分形插值算法的设计，取得了较好的效果。

2.2云的分形研究

研究证实^[2] ，云的形状也具有分形特性，并有 。其中 为云在地球上投影的周长， 为投影的面积，D是云的分形维数。

孙博文^[5]介绍了使用Paul Martz随机插值算法生成分形云的方法，算法原理如图6所示。

图6 随机插值算法原理图

给定一个网格，随机指定网格顶点A、B、C、D的颜色，然后求四点颜色的平均值得中点M的颜色，并得到四个子网格。根据A，B，M点和网格外任一虚拟点（颜色值为0）求平均，得到边中点E的颜色，并用相同方法得到F、G、H点的颜色。在子网格上继续上述操作，通过递归生成分形云。为了效果逼真，通常还要使用粗糙度常量，以决定每次循环随机数值域的减少量，也就是说，决定分形结果的粗糙程度。这种算法符合自然界中阳光通过天空散射后所得的真实效果，色彩过渡自然，因而逼真度极高。如图7所示。

图7 分形云效果图

2.3 树（草）的分形研究

自然界生物系统的发育与生长过程具有分形的性质^[2]，它们的分形维D小于生物体所依存的空间的维数d。其质量M同某种特征长度L的关系为 ，其中D为分形维数，且有D<d。构建分形树（草）模型的方法有多种，笔者整理分析后，大致归为以下三类。

2.3.1递归算法生成分形树

基本思想是先画树干，接着在树干顶端按照已设定好的夹角画出树枝，有时夹角是一个设定了范围的随机角度，并且树枝的长度应为树干的K(0<K<1)倍，经过多次递归调用最终生成分形树（草），如图8所示。

图8 递归算法生成的分形树效果图

此种算法设计思路易于理解，但缺点在于可重用性不强，若要在一幅图画中产生多个姿态差异较大的树（草），则需重复编制多个独立算法，工作量较大。在营造大规模分形树林景观时需结合其它算法，以减少繁重的设计工作。

图9 简单L-系统生成的分形树效果图

2.3.2利用L-系统生成分形树

L-系统[7]是一种典型的分形生成算法，它以自动机理论为基础，用符号空间的一个符号序列来表示状态，通过符号序列的变化来描述形态生长的过程。算法核心是从根节点开始，按照一系列既定的规则确定子节点的位置直至叶节点，在达到规定的迭代次数后，便可以从根节点向叶节点解释命令绘制出相应的图形。

图10 随机L-系统生成的分形树效果图

通常用L-系统生成的分形树（草）是由一个或多个基本生成元经过多次迭代生成的。例如给定如下信息：δ=25o，W:F，P:F→F[+F]F[-F] [F]。按照L-系统算法可生成如图9所示的分形树。近年来，学者们对L-系统进行了改进。通过将多个生成元按照随机概率结合起来，就构成了随机L-系统，如图10所示。将描述景物分枝的字母增加为两个甚至多个，同时字母的替换表达式有多种选择，就形成了多规则的L-系统，如图11所示。大连理工大学的王兴元和孙天凯^[8]提出了上下文相关的L-系统的动态模型。这种改进后的算法引入了控制参数，在执行字符串重写时兼顾了上下文即考虑到受附近分枝的影响，其产生式的一般形式描述为 ；即pre被替换为X当且仅当其左边含有字符 ，右边含有字符 。其生成的分形效果如图12所示。

这些改进后的L-系统算法的优点大致有：①将随机性与多态性融入其中，并且充分考虑到了植物在生长过程中分枝结构会受其邻近分枝影响的实际情况，使产生的分形植物更加接近实际。使用L-系统的最大好处在于其可重用性强，只需对基本生成元进行简单修改即可产生形态完全不同的分形景象，而无需更改算法的具体内容，适宜创作大规模的多姿多态的分形森林景观。②人们可以通过基本生成元来将植物的形态加以归类整理，极大方便了分形树（草）模型的使用。③把控制参数引入其中之后，可以使图像按照既定的构想发生变化，增强了动态的可操作性。

图13 简单IFS生成的分形树效果图

IFS 生成树木的方法是根据拼贴定理^[9]，对已有的某一树木图像尽可能精确地用有限个该图形的压缩仿射变换子图去覆盖它，并允许部分重叠，进而完成制图，其生成效果如图13所示。这种算法加之必要的着色技术即可得到彩色的分形植物，如图14所示。迭代函数系统的优点在于：①任意图形或自然景物形态，都可以通过计算机把它们转化成IFS代码，进而利用迭代函数系统设计具体的绘图算法，生成逼真的分形图像^[1]。因此，这种算法的通用性强，可以作为分形模型的基本生成方法。②由于其核心是用有限个初始图形的压缩仿射变换子图去覆盖它，并允许部分重叠，因而其生成的分形植物层次感强。

图14 采用着色技术的IFS生成的分形树效果图

3 自然景观研究总结与展望

分形之父曼德尔布洛特曾说过：“分形是大自然的几何学”。将自然景观仿真中传统的数学模型用分形模型来取代，无疑是仿真建模划时代的进步。在实际构造仿真景观时，建议使用分形插值法生成山和云，使用L-系统生成分形树，并通过OpenGL技术对分形景物进行着色处理，以产生真实感极强的自然景观图像。但自然界的事物不是孤立的，任何事物的发展运动都会受到其它事物的影响。比如，山上的树在生长过程中由于受到地势影响，形态将发生一定程度的变化。再如，河边的树，靠近河的一面比远离河的一面茂密得多。因此，当多个分形模型共同存在时，不仅要利用消影算法将多个景物展现在一幅画卷中，也应考虑到其间的相互影响。可以通过使用一些控制参数，将各分形模型的生成算法协调起来，以实现分形景物间的相互制约，产生更加符合实际情况的仿真效果。

（收稿日期：2007－06－14；Email：en_001@126.com）

参考文献

[1]林夏水．分形的哲学漫步[M]．北京：首都师范大学出版社，1999

[2]张志三．漫谈分形[M]．长沙：湖南教育出版社，1993

[3]李水根．分形[M]．北京：高等教育出版社，2004

[4]Przemyslaw Prusinkiewicz and Mark Hammel. A Fractal Model of Mountains with Rivers.Proceeding of Graphics Interface ’93 pages 174–180. May 1993

[5]孙博文．分形算法与程序设计—Visual C++实现[M]．北京：科学出版社，2004

[6]王梦,金文标.基于函数迭代系统的3-D分形插值算法[J]．计算机应用, 2006年第26卷第11期

[7]陆汝铃，张文妍．广义L系统[J]．中国科学(E辑)第32卷，2002年8月第4期

[8]王兴元，孙天凯.扩展的分形L-系统与自然景观的动态模拟[J]．中国科技论文在线

[9]曾锋，璩柏青，张黎明.基于迭代函数系统的彩色植物模拟[J]．《电子科技》，2005 年第10 期  

The Development and prospect of Fractal in imitation of nature Sight

Liu Peng(Taiyuan Institute of Technology)

Abstract: Fractal is an important technique of nature sight. Researchers of home and abroad have down a lot of work. Nature sight includes mountains, clouds and tree etc. This paper summarizes the fruit of Fractal Mountains, Fractal Clouds and Fractal Tree.

Based on this, this paper put forward improvement arithmetic.

Keywords: Fractal；imitation in View；Arithmetic