（计算机应用技术专业论文）基于分形理论的植物模拟方法研究(1).pdf

大连理工大学硕士学位论文 摘要 分形理论是近二、三十年才发展起来的一门新的学科，主要描述自然界和非线性系 统中不光滑和不规则的几何形体。自然界中种类繁多的植物虽然形态千差万别，却大都 具有自我相似、自我繁殖的分形特征。近年来，随着分形理论的发展，分形植物模拟成 为计算机仿真领域的重要课题。本文器在从理论研究和应用软件两个方面对以分形理论 为基础的植物模拟方法进行一些探讨和实践。 当前，基于分形理论的植物模拟方法主要有i 广系统、迭代函数系统、受限扩散凝聚 模型和粒子系统等。本文将自然界中比较有代表性的树木和类似树木的植物作为主要研 究对象。在对四种主要分形植物模拟方法的模拟对象和算法特点进行分析对比后，选定 以l 系统为主要研究起点，作者对基本l - 系统作了三个方面的改进，在其三维可视化 方面也作了一些探索。为了对植物各个部分进行细节控制，增强植物模拟的立体效果， 作者针对基本l 系统模拟植物效果存在的一些缺点，在编程过程中引入了b s p 算法， 并将其与l 系统和分形递归算法相结合。通过对相关指标的实验对比，证明这是一种比 较好的模拟植物结构形态的编程思路。 为了在编程过程中灵活地描绘和控制植物的各个器官，作者着眼模拟更多种类植物 的形态，从真实植物生长机理和不同植物形态差异的角度考察，在为植物各部器官灵活 建模的基础上，提取控制参数，并大量使用随机函数。同时，在编程中灵活运用g d i + 中的各种绘图方法和画笔、画刷，使生成的植物模拟图形更加自然逼真。 作者采用v b n e t 和g d i + 编程，设计了基于s q l s e r v e r 2 0 0 0 参数数据库基础上的 “植物形态动态模拟系统”，不仅能生成多种自然逼真、立体感较强的植物静态模拟图 形，而且通过使用计时器技术，还实现了对植物的动态模拟控制。 论文最后，介绍了“植物形态动态模拟系统”的设计思路和主要功能模块。 关键词：分形理论；b s p 算法：g d l + ；植物模拟 武志峰：基于分形理论的植物模拟方法研究 r e s e a r c ho nt h em e t h o d sf o rs i m u l a t i n gp l a n t sb a s e do nf r a c t a lt h e o r y a b s t r a c t f r a c t a lt h e o r yi sas c i e n c en e w l yd e v e l o p e di nt h ep a s t2 0t o3 0y e a r s ，i tc a nd e s c r i b e r o u g h n e s sa n di r r e g u l a rg e o m e t r i cs h a p e si nt h en a t u r eo ri nn o n - l i n e a rs y s t e m a l t h o u g ht h e s h a p e s o fp l a n t sv a r i o u s s p e c i e s i s d i f f e r e n c e ，t h e yh a v et h e c o m m o nc h a r a c t e ro f s e l f - s i m i l a r i t ya n ds e l f - r e p r o d u c e w i t ht h ed e v e l o p m e n to ff r a c t a lt h e o r y , s i m u l a t ep l a n t s u s i n gf f a c t mb e c a m ea ni m p o r t a n tp r o b l e mo nc o m p u t e rs i m u l a t ef i e l d t h i st h e s i sp u r p o s e i n v e s t i g a t i n ga n dp r a c t i c i n gt h em e t h o do fs i m u l a t i n gp l a n t sb a s e do nf r a c t a lt h e o r yi nt h e o r y s t u d ya n da p p l i e ds o f t w a r e t h e r ea r ef o u rm e t h b d so ns i m u l a t i n gp l a n t sb a s e do nf r a c t a lt h e o r yc u r r e n t l y ：l - s y s t e m ， i t e r a t e df u n c t i o ns y s t e m ：d i f f u s i o nl i m i t e d a g g r e g a t i o nm o d e la n dp r a c t i c a ls y s t e m b e c a u s et h ee m p h a s i so fr e s e a r c hi st r e ea n dp l a n t so fs i m i l a rt r e ei n n a t u r e ，t h ea u t h o r c h o o s e st h el s y s t e ma st h ef o u n d a t i o no fr e s e a r c ha f t e rac o m p a r a t i v ea n a l y s i st os i m u l a t i n g o b j e c ta n dt h ec h a r a c t e ro fa l g o r i t h m t h e r ea r et h r e ei m p r o v e m e n t si nl s y s t e ma n ds o m e e x p l o r a t i o ni n3 d v i s u a l i z eo fl - s y s t e mi nt h i sp a p e r i no r d e rt oc o n t r o ld e t a i l a d dt h e3 d e f f e c to ft h ei m a g e s ，t h ea u t h o ru s e sb s pt e c h n i q u ei np r o g r a m ，c o m b i n i n gl - s y s t e ma n d f r a c t a lr e c u r s i v ea l g o r i t h m i th a sb e e np r o v e dt ob eao p t i m a la l g o r i t h ms i m u l a t i n gm o r e c l a s sp l a n t sb yc o n t r a s t i n gt h ee f f e c to fi m a g e sa n ds o m e p r o p e r t y i no r d e rt od e s c r i b ed e t a i le a s i l y ，t h ea l g o r i t h mc o n s i d e r st h ed i f f e r e n c eo fi n d i v i d u a l p l a n t ，c o n s t i t u t e st h ef l e x i b l em o d e lo fe v e r yp l a n t sp a r ta n dc h o o s ep a r a m e t e r so nt h eb a s e d o fa n a l y z i n gt h es t r u c t u r eg r o w t hc h a r a c t e r i s t i co fp l a n t a d d i n gr a n d o mf u n c t i o n s ，i tm a k e s t h ei m a g em o r el i f e l i k eb yu s i n gt h ed r a w i n gm e t h o da n d p e n ，b r u s hi ng d i + b yu s i n gt i m e r t o o l ，i tc a ns i m u l a t ea n dc o n t r o ld y n a m i cg r o w t ho fs o m ep l a n t s u s i n gv b n e ta n dg d i + ，t h ea u t h o rh a sd e s i g n e dt h ea p p l i c a t i o ns o f t w a r en a m e d “s y s t e mo fd y n a m i cs i m u l a t ep l a n t sm o r p h o l o g y ”i tc a nc r e a t el o t so fl i v e l ya n dl i f e l i k e i m a g e so fp l a n t s f u r t h e r m o r e ，r e a l i z e st h ed y n a m i cs i m u l a t ec o n t r o lo fp l a n t sg r o w t hb y u s i n gt i m e rc o n t r o lt e c h n o l o g y a ni n t r o d u c t i o nt ot h ed e s i g n i n gi d e a sa n dm a i nm o d u l e so ft h ea p p l i c a t i o ns o f t w a r ei si n t h ee n do ft h i st h e s i s k e yw o r d s ：f r a c t a lt h e o r y ：b s pa l g o r i t h m ；g d i + ；p l a n t ss i m u l a t i o n 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：丛遮e t l l ：趁：! ! ：丝 人近理工人学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论支版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名 赵堑生聋 王篓乞 边年三月上l 日 大连理工大学硕士学位论文 1 绪论 1 1 分形植物模拟的提出 种类繁多的植物是构成自然景物的基础。千百年来，无数的科学家被多姿多彩的自 然植物所吸引，数学家们更是对其显著的几何特性作了广泛的研究。结果表明，自然界 中的植物虽然形态千差万别，却大都蕴含着一个同样的、具有自相似性质的物质结构规 则：植物体中每一相对独立部分的形态构造模式是整体构造模式的缩影。正是基于植物 的这一几何特性，使得许多人致力于利用分形理论进行植物模拟的研究。 2 0 世纪7 0 年代，美国科学家m a n d e l b r o t 创立了分形几何学【1 2 1 ，用来描述那些不 规则、欧氏几何无法描述的几何现象和物体，被誉为“大自然本身的几何学”，开创了 2 0 世纪分形理论的发展。分形理论作为研究非线性问题的一门新兴学科，引起了许多科 学家的关注，因为传统的欧氏几何主要研究规则图形和光滑曲线，对自然植物的描述却 显得无能为力。分形理论研究的对象正是在非线性系统中产生的不光滑和不可微的几何 形体，对应的定量参数是维数，是刻划混沌运动的直观的几何语言，更是接近现实世界 的数学。因此，分形几何为自然植物的模拟提供了描述语言和理论基础。 因此j 正是分形理论的发展，使自然植物的描绘成为可能，这也是分形几何得到高 度重视的原因之一。近年来，基于分形的自然景物模拟已成为计算机图形学应用研究的 前沿课题，而对自然植物的模拟则是其中的难点和重点。 1 2 分形植物模拟的方法 分形植物模拟就是基于分形理论的植物形态模拟，其原理是利用植物自身结构的分 形性质( 结构自相似性) 生成植物图形或图像的方法。当前，分形植物模拟的方法主要 有i 厂系统、迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ，i f s ) 、受限扩散凝聚( d i f f u s i o n l i m i t e da g g r e g a t i o n ，d l a ) 模型和粒子系统。这四种方法的算法原理不同，模拟对象也 各有侧重。 1 2 ，1l 一系统 l 系统是美国理论生物学家l i n d e n m a y e r 在1 9 6 8 年提出的鸭它以形式化的语言描 述植物的结构和生长，用语言的终结符与植物结构相对应，由文法生成的句子代表植物， 而句子生成的中间过程是植物的生长发育过程1 4 】。其本质上是种形式语言，所以也称 之为文法构图方法。l 系统能简洁地描述植物的拓扑结构，例如枝条和花序的结构，但 武志峰：基于分形理论的植物模拟方法研究 较难模拟复杂的植物形态。后来，通过s m i t h 、p r u s i n k i e w i c z 的发展【5 _ 1 0 】，l - 系统成为植 物生长建模的主要方法之一。 1 2 2i f s i f s 最早来源于h u t c h i n s o n 于1 9 8 1 年对自相似集的研究1 1 1 】。1 9 8 5 年，美国科学家 b a r n s l e y 发展了这一分形构型系统，并命名为迭代函数系统【1 2 ，1 3 】。1 f s 可以定义为由一 组满足一定条件的映射函数鹏( 例如压缩的仿射变换) 及一组变换发生的概率只组成， 可表示为： i f s = ( 彬，层) ，f - 1 , 2 ，l ，n ) 。 利用i f s 生成植物图形的方法是对初始植物图形按照已知概率选择某个仿射变换而 实施的一种迭代变换。 1 2 3d l a 模型 d l a 模型是美国科学家w i t t e n 和s a n d e r 于1 9 8 1 年提出的【1 4 l ，其基本方法是：在 一个平面网格上选定一个静止的微粒作为种子，然后在距种子较远的格点上产生一个微 粒，令微粒沿网格上下左右的方向随机行走。如果该微粒在行走过程中与种子相碰，就 凝聚在种子上；如果微粒走到边界上，就被边界吸收而消失。如此重复上述步骤，就会 以种子为中心形成一个不断增长的凝聚集团。d l a 模型主要用于模拟各种分形生长和 凝聚现象。利用d l a 模型或其修改的模型可以对植物根系的生长过程和海藻类植物的 形态结构进行计算机模拟。 1 2 4 粒子系统 粒子系统( p a r t i c a ls y s t e m ) 是r e e c e s 于1 9 8 3 年提出来的1 1 5 ，基本思想是用大量的、 具有一定生命的粒子图元来描述自然界不规则的模糊景物。每个粒子在任一时刻都具有 随机的形状、大小、颜色、透明度、运动方向和运动速度等属性，并随时间推移发生位 置、形态的变化。每个粒子的属性及动力学性质均由一组预先定义的随机过程来说明。 粒子在系统内都要经过“产生”、“活动”和“死亡”这三个具有随机性的阶段，在 某一时刻所有存活粒子的集合就构成了粒子系统的模型。粒子系统适合用来模拟山、水、 树丛、草地等模糊和随机图形。 综上所述，虽然i f s 、d l a 模型、粒子系统和l 系统都能用来模拟一些自然植物， 但是它们的模拟对象各有侧重。d l a 模型适合模拟一些凝聚现象，因而模拟对象受限。 粒子系统在模拟森林、草地等方面具有其无可比拟的优点，而在对单株自然植物的模拟 中却无能为力。本文的研究对象将放在自然植物中最具代表性的树木或类似树木的植 大连理工大学硕士学位论文 物，因此，作者将主要研究l 系统和i f s 这两种分形植物模拟方法，而l 系统将是本 论文的研究重点，也是作者提出的植物形态模拟优化算法的基础。 1 3 理论研究及应用软件发展现状 1 3 1l 一系统的研究现状 加拿大学者p r u s i n k i e w i c z 提出的参数化( p a r a m e t r j c ) l - 系统使其能够模拟时延信 息 7 1 。m e c h 与p r u s i n k i e w i c z 发展的“开放式( o p e n ) l - 系统”在形式化公理与产生式 中引入了交流单元( c o m m u n i c a t i o nm o d u l e s ) i s l ，用于传送、调整“环境一植物”两方 的相互信息，以实现植物与环境并发过程的模拟研究，典型的应用实例之一是植物根系 的发展过程模拟。为了模拟植物的连续生长过程，p r u s i n k i e w i c z 还先后提出了时变l 系统和微分( d i f f e r e n t i a l ) l - 系统【9 ，1 叭，这两种系统能较好地模拟植物的叶序、花朵以及 植物生长、竞争、裁减等自然现象。 国内也有很多学者和分形爱好者致力于l - 系统的研究，主要内容集中在三个方面： 一是利用。系统的基本原理，在计算机上绘制例如雪花、c 型、地毯等艺术类图案和少 量的蕨类植物；二是在基本l 广系统的基础上进行一些改进和创新，丰富模拟植物的种类； 三是尝试将l 系统用于三维植物形态的模拟构造。王方石利用l 系统的理论，结合计 算机图形学，模拟了个别植物的造型 1 6 1 ，如树、叶、花等；高旭，姜楠在【广系统中引 入随机序列，使生成的图形更加逼真【1 7 ；张树兵，王建中针对l 系统编程繁琐的缺点， 尝试将字符序列转换成递归表达式【1 8 】；魏琼，蒋湘宁利用d o l 系统模拟了简单树木的 三维造型【1 9 1 ；孔小利利用l 系统给出了三维植物形态的简单描述，并建立了植物的拓 扑结构【2 0 】；王莉莉、赵沁平针对i 广系统的字符串规则灵活性不够的问题，提出建立一 种较为通用的基于。系统规则语言分析器的解决方法【2 l 】。但总的看，l 系统模拟生成的 植物种类比较单一、死板，更无法体现植物的动态生长过程，而且其产生式规则也没有 一致的确定方法 2 2 出】。因此，作者认为l 系统还有广阔的研究空间。 1 3 2l f s 的研究现状 b a r n s l e y 通过若干仿射变换，应用迭代函数系统生成了自相似性极强的蔗类植物叶 片，之后又发展了再现迭代函数系统( r e c u r r e n ti f s ) 【1 2 ，1 3 】，在自相似性生成方面更为 灵活地体现了植物体局部之间的不同自相似性。p r u s i n k i e w i c z 和h a m m e l 通过加入变换 顺序的约束条件，综合各类不同的i f s 方法发展了一种称为语言约束式迭代函数系统 ( l a n g u a g e r e s t r i c t e di f s ) 的方法瞄1 。i f s 将整体形态变换到局部，较好地模拟了迭代 性较强的各类植物。 武志峰：基于分形理论的植物模拟方法研究 近年来，i f s 理论有了较大的发展，它在一大类物体的建模问题中，特别是在自然 景物的计算机模拟生成中具有很大的优势。国内很多学者对i f s 也做了大量的研究和探 索：i f s 的研究范围在自相似分形图的基础上不断扩展，其范围已不再局限于仿射变换： 在用i f s 建模的研究中，实现了对原图形的几何变换，将i f s 中的线性变换推广到非线 性变换：对自然景物的建模研究也由二维推广到三维。例如：仲兰芬、王琰、李庆忠等 研究了基于i f s 的三维树木模拟方法f 拈冽：李光辉、李洪研究了基于i f s 的植物模拟 c a d 方法f 2 9 】和基于a c t i v e x 的i f s 植物模拟控件的实现【3 0 l ；万庆萱、方建安、张旭还 研究了i f s 模拟植物图像的颜色生成算法【3 1 , 3 2 1 。 1 3 3 应用软件的发展 在应用软件方面，随着计算机硬件的飞速发展和数据采集能力的提高，许多国家涌 现出一些优秀的植物建模软件。澳大利亚的研究机构c e n t r ef o rp l a n t a r c h i t e c t u r e i n f o r m a t i c s 基于l 系统建模方法开发了v i r t u a ip l a n t s 软件，能模拟棉花、大豆、玉米等 农作物根系的生长和病虫害对植物生长的影响。加拿大c a l g a r y 大学基于l 广系统建模方 法，应用植物学知识开发的c p e g 、l - s t u d i o 、v i r t u a ll a b o r a t o r y 能再现灭绝的树种，可 应用于计算机辅助景观设计和植物学教学。 总的看，这些工具软件专业性强，操作比较复杂，而国内基于分形理论的植物模拟 软件还没有成功的例子。因此，作者认为，无论是从自然景观设计还是从植物学研究等 角度，用于模拟自然植物方面的建模软件都有一定的应用需求。 1 4 分形植物模拟的现实意义 利用分形方法来模拟自然景观，特别是植物的形态结构，是一件很有意义的工作。 分形理论的创立为植物形态的定量模拟提供了有力的手段，为植物科学的进一步发展预 示出动人的前景。 简单地说，植物生长形态的模拟主要有以下三个应用方向：第一是单纯的植物外观 形态模拟。注重模拟效果的逼真性，其目的是再现自然景观，主要用于教育、娱乐、商 业、园林规划等领域；第二是真实植物生长过程的模拟。注重植物学理论的应用，其目 的在于对植物生长过程的研究，可用于农田试验、作物病虫害研究、资源环境分析、作 物栽培指导以及生长机理的研究等；第三是用在艺术图案和电脑宠物的设计中。偏重植 物各部分形态模拟和颜色搭配的艺术性。作者曾尝试将浇灌、温度、光照等外部条件与 植物各部分的生长比例系数相关联，在电脑屏幕上模拟出整株植物的生长过程。作为应 用，可设计成一种生长在电脑屏幕上的植物宠物，也可作为一种能体现人工培育的电脑 屏保。 大连理工大学硕士学位论文 1 5 论文结构安排 下面将本文各章节内容安排介绍如下： 第一章绪论。主要介绍分形植物模拟课题的提出背景、主要研究方法和对两种主 要分形植物模拟方法的研究现状，以及研究本课题的现实意义。 第二章l 系统的基础理论以及作者对l 广系统的改进和实现。主要包括l 系统的提 出及其二维、三维数学模型，i 广系统的不同分类及其在植物模拟中的应用，同时介绍了 作者对l 系统在三个方面的改进。 第三章i f s 的理论。包括仿射变换的数学表达和几何特征、随机i f s 的算法思想以 及拼贴方法与i f s 码的确定，最后列举了i f s 模拟部分植物形态的实例。 第四章将具有“剖分空间”功能的b s p 算法引入植物模拟的程序设计中，并在此 基础上提出一种结合l 广系统算法思想，将原始分形递归算法与b s p 相结合的编程思路。 通过对各自模拟植物效果和相关指标的对比分析，证明这种优化后的编程方法可作为一 种能模拟较多种类植物、更灵活高效的植物模拟算法。 第五章简要介绍作者开发的“植物形态动态模拟系统”的设计要点。包括系统开 发环境和用到的理论知识，重点介绍了植物各部器官的数学模型、系统各功能模块的设 计要点以及一些忠实于真实植物生长机理的编程技巧。 最后雾总结本文所作的主要工作，提出进一步研究的方向。 武志峰：基于分形理论的植物模拟方法研究 2l 一系统的实现和改进 在众多分形图形的生成算法中，l 广系统无疑是最灵活的，它能生成许多经典的分形 图形。特别是应用在模拟植物方面，工，系统能很好地表达植物的分枝特征，侧重于描述 植物的拓扑结构和生长过程，在模拟植物的种类上具有一定的通用性和可扩展性。因此， 作者将l 广系统作为主要研究起点，并且在基本l 系统的基础上，进行了一些探索和改进。 2 1l 一系统的提出 1 9 6 8 年，美国著名理论生物学家l i n d e n m a y e r 【3 4 i 在研究植物形态的进化和构造时， 提出了一种文法描述方法，即i ，系统。这是一种字符重写系统，后来发展为形式语言的 一个重要分枝。它通过对植物对象生长过程的经验式概括和抽象，构造公理、产生式集 和生成字符的发展序列，以表现植物的拓扑结构。其中的公理可理解为一个初始状态， 产生式集就是一个或多个描述规则。1 9 8 4 年，s m i t h 首次将。系统运用到计算机图形学 领域，形成一种自然植物模拟的有效方法1 5 。 2 2l 一系统的原理及数学模型 2 2 1l 一系统的原理 l 系统是一种基于符号的重写系统，即用一个重写规则逐次地置换初始对象的各个 部分来确定一个复杂的对象，其核心思想是“字符串替换”。字符串即按一定规律排列 的字符集合，它可以包含短语、字母、数字或标点符号，一般用大写字母书写。字符串 替换可以定义为根据一组改写规则或产生式( p r o d u c t i o n ) 依次替换一个简单初始物的 每一部分，即给出初始物( 一条字符串) ，然后根据产生式规定的替换规则去替换初始 字符串中的每一个字符。这种替换的次数是无穷的，可得到无限推导序列。替换中每一 次反复称之为字符串的深度，例如深度为3 就表明字符串替换进行了3 次。 设有两个字母组成的字符串，重写规则为： b a a - a b 则系统演变的过程为： b a a b a ba 大连理工大学硕士学位论文 a ba a b a ba a ba ba 这个字符串中字母个数的增长恰恰是f i b o n a c c in u m b e r ，即如下序列： 1 ，1 ，2 ，3 ，5 ，8 ，1 3 ， 记该序列的第n 项为f n ，则这个序列满足以下递推关系： f n = f n 一14 - f n _ 2 2 2 2l - 系统的数学模型 l 系统的数学模型可用“乌龟行走算法”解释【1 6 州，其思想是：将龟形状态定义成 一个三元素集合y ，a ) ，其中笛卡尔坐标o ，y ) 表示龟形的位置，方向角口表示龟头的 方向，给出步长d 和角增量6 ，龟形对应于下列命令( 如图2 1 ) ： 图2 1 字符“f 、+ 、一”的含义 f i g 2 1m e i n g so fc h a r a c t e r “f 、+ 、。 图2 2 字符串“f + f f 一f f ”的解释 f i g 2 2i n t e r p r e t a t i o no fs t r i n g “f 【+ f 】1 - f i e ” f 似) ：向前移动一步，步长为d ，龟形状态变为0 ，y ，口) ，其中工- z + d c o s a ， y = y + ds i n a ，在点 ，y ) 和 ，y ) 间画一直线段； + ( 6 ) ：向左转6 ，龟形的下一状态为0 ，y , a + 6 ) ，角的正向为逆时针方向； 一( 6 ) ：向右转6 ，龟形的下一状态为伍，y ，a - 一6 ) ； 如果用于模拟树木的分叉，需加入以下两个新的符号，用龟形解释如下： “f ”：将龟形的当前状态压入堆栈。存入堆栈的信息包括龟形的位置和方向以及 其它一些属性，如所画线段的颜色及宽度等； “1 ”：从堆栈中弹出一个状态作为当前状态，不画线。 例如，字符串“f 【+ f f 【f i f ”解释见图2 2 所示。 在构图时，还要给出循环次数或递归深度，起始符号元即字符串中的每个字符由生 成规则集给出的替代规则进行字符替代，产生一个新字符串，按照规定的循环次数重复 这一替换过程，产生最后的一个字符串，再在计算机屏幕上绘制出图形。 武志峰：基于分形理论的植物模拟方法研究 2 3l 一系统的算法设计 l 系统的核心思想是“字符串替换”，首先要根据起始符号元和替换规则产生一系 列字符串，然后读取字符，按照不同字符表示的意义来执行不同的动作。因此，其算法 实砀；上是分两个过程完成的。下面简单描述如下： 第一个过程：生成字符串 n ) 声明并设置公理、产生式规则； ( 2 ) 声明并设置起始点、初始角、迭代步长以及迭代上限等控制参数； ( 3 ) 循环用替换字符串替换种子，直到迭代次数大于迭代的上限。 第二个过程：读取字符并画图 ( ；4 ) 逐个读取字符串中的每个字符： ( 5 ) 根据读取到的字符采取不同的动作： 读取字符为f 时，丽线段； 读取字符为“+ ”时，逆时针旋转； 读取字符为“”时，顺时针旋转： 读取字符为“”时，进栈，记录当前状态； 读取字符为“1 ”时，出栈。 2 4l - 系统的分类 l 系统是一种形式语言，现在已发展成一种比较成熟的技术。主要有两种不同的分 类方法p 4 l ：如依据生成规则的数目可分为单一规则的l 系统和多规则的l 系统；依据 产生式的前驱和后继的对应关系，可分为确定性i ，系统和随机性i ，系统。作者在设计 “植物形态动态模拟系统”时使用的是后一种分类方法，并将确定性l 系统和随机性 l 系统分别做为一个模块来设计。下面分别举例说明这两种分类方法： 2 4 1 第一种分类 f 1 ) 单一规则的l 广系统 单一规则的l 系统，就是只有一条生成规则，以这一条规则进行反复替换而生成分 形图像。例如画一棵带有分枝的植物，我们用符号“f ”可以代表树的主干和侧枝；用 “+ ”和“一”可以代表树枝的生长方向；而分枝问的节点可以由“【”和“】”来控制， 用符号“f ”将当前的树枝状态保存起来，接下来执行向某一侧“前进”符号的动作， 这一侧画完后可以利用符号“1 ”将保存的分枝节点状态取出来，即返回到刚刚保存的 查垄坚奎堂堡主堂! ! 堡茎 节点处，开始画另外方向的分枝。如此反复。通过调整初始字符、生成规则及偏转角度， 就能得到类似某种自然植物的图像。 表2 1 列出了一组模拟植物的单一规则l - 系统，其对应的植物图形如图2 3 。 表2 1 一组单一规则的l - 系统 t a b 2 1a g r o u po fo n e - p r o d u c t i o nl - s y s t e m 对应图例 6 0 7 p 图2 5 ( a ) 图2 5 ( b ) 图2 5 图2 。5 图2 5 图2 5 2 5 。 2 5 。 f f ( c ) 2 5 。f ( d )2 5 。 f ( e ) 2 0 。f ( f ) 2 2 5 。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 幽2 5 ( g ) 2 2 5 f f f 一f f f f t f + i + f ：+ 阿一卜f 图2 5 ( h ) 2 2 5 。f f - - f f 一 + 卜f - f 一 一f 1 f 1 f 影 ( a )( b ) ( c ) ( d ) 礤辩 w 铡辩 嘲 葺 ( e )( f )( g ) ( h ) 图2 3 一组单一规则l 一系统生成的植物图形 f i g 2 3i m a g e so fs o m ep l a n t sg e n e r a t e db yo n e - p r o d u c t i o nl - s y s t e m 9 武志峰：基于分形理论的植物模拟方法研究 ( 2 ) 多规则的l 系统 多规则l 系统就是包括两条甚至多条生成规则，或者字母表中包括两个甚至多个字 母的情况。多规则的l 系统至少包括两种情况：一种是规则中的字符只作为被替换的字 符，而不作为绘图字符；另一种是规则中的字符既作为被替换的字符。又参与绘图操作。 表2 2 列出了一组多规则的l 系统实例，对应生成的植物图形如图2 4 所示： 表2 2 一组多规则l 一系统 t a b 2 2a g r o u po fm o r e - p r o d u c t i o nl - s y s t e m 锤 k 摹隆 鹫蘑 凝。k 喾 蝴酚 图2 4 一组多规则l - 系统生成的植物图形 f i g 2 4i m a g e so f $ o m cp l a n t sg e n e r a t e db ym o r c - p r o d u d i o nl s ”t e m 2 4 2 第二种分类 ( 1 ) 确定性l 系统 确定性i 广系统，也可称为简单l 系统，通常记为d o l 系统。下面给出d o l 系统 的正式定义： 大连理工大学硕士学位论文 令矿表示字母表，v 表示v 上所有单词的集合，一个确定性l 系统就是一个有序 的三元组：g = c v ，甜，p ，这里是一个非空单词，称为公理；p 是产生式的有限集合。 l 系统中的初始物( 亦称公理) 和产生式规则均是由字符串描述的。产生式写作a x 。 字母a 和单词x 分别称作产生式的前驱和后继，规定对任何字母d e v ，至少存在一个非 空的单词x ，使得a x 。对给定的前驱a e v ，若无明确解释的产生式，则规定口一a ， 这个特殊的产生式属于p ，对每个a e v ，当且仅当恰有一个非空单词x ，使口一x ，那 么就说这个系统是确定的l 系统。 附录c 是一组确定性l 系统生成的植物图形，对应的参数见表2 3 。 表2 3 一组确定性l - 系统 图c o6 墨最 ( 2 ) 随机性l 广系统 植物形态模拟中，最重要的一点就是要力求生动，避免呆板，但是用确定性l 系统 模拟的效果却不能满足这一点，所以我们必须在保留主要特征的前提下，体现细节的不 同变化，以求生动逼真。用随机性l 系统可以得到较好的效果。 武志峰：基于分形理论的植物模拟方法研究 随机性i ，系统是一个有序的四元组：g - c v ，p ，石，其中y 是字母表，为公理， p 为产生式的集合，万是函数：玎( 0 山称为概率分布，将产生式集合映射到产生式概 率集合上。设口为v 中任意字符，以它为前驱可以有多个不同的产生式，所有这些产生 式的概率之和为i 。 如下面就是一个随机性l 系统的例子： 6 2 5 0 甜：f 只：f 巫! i l + f 【+ f 】f 【一f f 己：f 巫旦l + f 【+ f 】f 【一f 【+ f 】 忍：f 至生f f + 【+ f + f 】- 【+ f 】 这里的石( 只) 表示不同规则出现的概率，且有靠) + z ( 只) + 丌( 只) = 1 。当我们给出3 种规则的不同概率时，便会得到恰如同一种( 科) 植物的不同标本的植物图像，如图2 5 。 ( b ) 标本二( c ) 标本三 图2 5 一个随机性l _ 系统生成的植物图形 f i g 2 5i m a g e so fp l a n t sg e n e r a t e db yr a n d o ml - s y s t e m 2 5l 一系统的三维可视化研究 利用l 系统对自然植物进行三维模拟，是当前该领域的主要研究方向之一，作者在 这方面也进行了一些尝试。 2 5 1 命令字符的扩展 若要绘制三维树的结构，需要将二维龟形命令扩展到三维空间上。首先给出描述龟 形当前方向的三个向量抒，三，f ，它们分别表示龟形的向前、向左和向上的方向，均是单 位长度，且满足方程： 大连理工大学硕士学位论文 叫吊薯s i n a 口卜，删习叫避0 + ( 6 ) ：用旋转矩阵r v p ) 表示向左转6 角： - ( 6 ) ：用旋转矩阵r v ( 一6 ) 表示向右转d 角； ( d ) ：用旋转矩阵吃p ) 表示向下转d 角； ( d ) ：用旋转矩阵r 。p ) 表示左滚动d 角； 将l 系统与计算机图形学中的三维几何造型技术结合，可以实现三维可视化模拟。 以简单的d o l 系统为例，将树木分枝角度和树干直径作为基本参数，用v c 和o p i e n g l 编程，树枝( 干) 的模型用圆台体( 基部截面积较大，顶端截面积较小) ，树叶用多边 形来造型1 1 9 。运用光照效果、阴影生成、混合雾化和纹理贴图等技术，可使生成的植物 形态更逼真。以单一规则的d o l 系统为例，基本字符串和生成规则如下： 口：a ( s o ，w o ) ， f ! ( w ) f 0 ) p 2 ：a ( s ，w ) + + ( 口1 ) ( 吼) 彳08 ，w 4 q e ) 】 ， i 【+ 2 ) ( 仍) 4 0 4 r 2 ，w + 0 - q ) ae ) 】 其中参数s 和w 指定节间的长度和宽度，s 。为初始节问长度，w o 为初始树木直径。角度 值a ，、a ：、妨、妒：决定各顶点的方向。常数r 1 和r 2 代表树木节间的长度从基部到顶部 的缩短系数，常数目和e 控制树木直径的变化系数。生成规则p l 中的符号! ( w ) 表示当前 线段的宽度减小为w ，耶) 表示从初始位置向前移动了s 长度，“f ”表示将当前状态压 栈，“】”表示将当前状态出栈，+ ) 表示绕u 轴逆时针旋转a 角度，( 妒) 表示绕h 轴 逆时针旋转妒角度。 1l_f_l-lj_j m ao幽i宝 _ c 武志峰：基于分形理论的植物模拟方法研究 图2 6 ( a ) 是当该d o l 系统的常数如下取值时生成的图形：s o = 8 0 ，w o = 2 0 ，r l = o 7 0 ， r 2 = o 8 5 ，a l - - - - 2 5 。，a 2 = - 3 0 。，吼= 1 3 7 。，伊2 = 1 3 7 。，q = 0 5 0 ，e = 0 5 0 。 图2 6 0 ) 是在使用了光照的基础上，加入投影矩阵后的效果图。 ( b ) 阴影效果 图2 6d o l 系统生成的三维树及其阴影效果 f i g 2 6t h r e e - d i m e n s i o n a lt r e ea n de f f e c to fc a s t i n gs h a d o wu s i n gd o l - s y s t e m 2 6 对基本l 一系统的扩展和改进 分形l 系统经过了近四十年的发展，已经成为分形科学中比较成熟的理论。然而， 笔者认为，这一理论若用在对自然植物的模拟中，特别是在实际编程中，仍有一些可以 改进的地方。在设计“植物形态动态模拟系统”中确定性l 系统模块的编程中，作者在 坚持其基本算法的基础上，进行了三方面的改进。 2 6 1 绘图字符的扩展 在基本l 系统中，参与绘图的字符只有个“f ”，其动作只是画直线。如果将其用 于模拟植物形态，就大大局限了模拟植物的种类，因此，可以根据需要，在初始字符集 中加入新的具有实际意义的绘图字符，并在编程过程中规定其相应的绘图动作，如绘制 根茎、花朵、果实等。在确定性l 系统的设计中，笔者在字母表中增加了以下两个字符， 相应在程序中编写了其绘图的执行动作： “h ”：绘制椭圆形的果实，果实的大小可以控制； “g ”：用直线或贝塞尔曲线绘制根茎，根的粗细和弯曲程度都可以控制。 例如下面【，系统：( 对应的图形如图2 7 ( a ) ) 6 = 2 0 0 大连理工大学硕士学位论文 ：f p ：f f f - 【- f + f + f 】+ 【+ f - f - 明 为给这种植物加上根茎，我们将生成规则修改为“g g - 【一f + f + 川+ 【+ f - f - 明，生成的 图像如图2 7 ( b ) 。同理，图2 7 ( c ) 是将生成规则改为“g g 十f + f + f 】+ h 【+ f f - 同”，即在 生成规则中加入“h ”后生成的图像，图中紫色部分就是由字符“h ”绘制的椭圆型的 果实。 ( a ) 原图( b ) 加入g ( c ) 再加入“h ” 图2 7 在生成规则中加入字符“g ”和“h ”的情况 f i g 2 7c h a n g e s o fi m a g ea d d e d “g ”a n d 1 - ii np r o d u c t i o n 2 6 2 随机数的运用 l 系统是一种较好的模拟自然植物的分形算法，通过设定不同的公理和产生式规 则，可以模拟种类繁多的植物形态，但是相对都显得比较“单调”、“死板”。在确定 性l 厂系统中，同样的初始条件，生成的植物形态基本一致。在随机性l 系统中，只是 按照概率分布选择了已经确定的产生式，每次生成的图像依靠产生式的确定。因此，为 了使植物形态更生动，在编程过程中，笔者在l 系统的绘图函数中加入了一些随机因子： 一是在读取绘图字符“f ”画线时，使其步长乘以一个随机数( 范围可选) 作为长度随 机因子，使其在迭代过程中的画线长度略有差异。二是在读取“十”和“一”字符时， 使旋转角度乘以一个随机数( 范围可选) 作为角度随机因子，使每次画线时旋转的角度 有一定的随机幅度。这样，每次所生成的图形就能显示出同一种类植物不同植株之间的 差异，使模拟的植物形态更加自然逼真。 图2 8 表现了图2