（计算机应用技术专业论文）基于改进l系统的植物形态可视化研究.pdf

浙江工业大学硕士学位论文 基于改进l 系统的植物形态可视化研究 摘要 随着虚拟现实技术和计算机图形学的发展，利用计算机对自然界中植 物的模拟，已经成为个热门课题。本文结合浙江省基金项目，探讨了植 物形态可视化建模中的问题。研究的内容和取得的成果如下： ( 1 ) 构造了基于子结构算法的新型l 一系统 l 一系统虽然应用广泛，但传统的迭代算法，运行效率低，原因是因 为传统算法存在着同一结构重复计算、重复构造的问题，为了解决这个问 题，本文提出一种新型的l 系统改进算法，沿用子结构算法，改善了l 一 系统的性能，并减少了存储空间。 ( 2 ) 建立了植物结构模型参数库 植物学家定义的二十三种植物结构模型能够比较精确描述植物形态 结构的连续变化特点。本文根据这些结构模型的拓扑结构以及p e t r i 网，构 造了相应的l 一系统文法，建立了描述植物拓扑结构的参数模型库，为用户 进行植物仿真提供了模板，从而实现快速构造植物模型。 ( 3 ) 提出了改进的枝条算法 本文通过对一般枝条算法的研究，提出了改进枝条算法，该算法不仅 能较好的模拟植物的枝条形状，也解决了一般枝条算法在模拟时出现缺口 的问题，与一般枝条算法相比，时间复杂度并没有增加。 ( 4 ) 开发了植物形态仿真系统原型 i 浙江工业大学硕士学位论文 本文将上述研究成果整合，使用o p e n g l 对模型进行三维化，建立了 基于改进l ，系统的植物仿真系统原型。在原型系统中，用户能方便的利用 提供的植物结构模型库以及植物器官库，构造个性化的植物结构。 关键字：虚拟植物，卜系统，子结构，植物结构模型 浙江工业大学硕士学位论文 r e s e a r c ho f v i s u a lp l a n tm o d e l l i n g b a s e do ni m p r o v e dl s y s t e m a b s t r a c t w i t ht h ed e v e l o p m e n to f v i r t u a lr e a l i t yt e c h n o l o g ya n dc o m p u t e r g r a p h i c s ， i m i t a t i n gt h ep l a n t si n n a t u r eb yc o m p u t e rh a sb e c o m eah e a t e di s s u eo f r e s e a r c h c o m b i n e dw i t hz h e j i a n gp r o v i n c e f u n d e dp r o g r a m ，t h i sp a p e r d i s c u s s e st h ep r o b l e m se x i s t e di nt h em o d e l i n go fv i s u a lp l a n tm o r p h o l o g y t h ec o n t e n t sa n dt h ea c h i e v e m e n t sa r ea sf o l l o w s ： ( 1 ) c o n s t r u c tan e wl s y s t e mb a s e do ns u b s t r u c t u r ea l g o r i t h m d e s p i t e t h ew i d e a p p l i c a t i o n o fl s y s t e m ，t h e m u l t i c o m p u t a t i o n ， m u l t i c o n s t r u c t i o no ft h es a m es t r u c t u r ei nt h et r a d i t i o n a li t e r a t i v ea l g o r i t h m r e s u l t si nl o we f f i c i e n c y i no r d e rt os o l v et h i sp r o b l e m ，t h i sp a p e rp r e s e n t sa n e wi m p r o v e dl - s y s t e mw h i c hm a k e su s eo ft h ea d v a n t a g e so fs u b s t r u c t u r e a l g o r i t h m i tn o to n l yi m p r o v e st h ep e r f o r m a n c eo fl s y s t e m ，b u ta l s or e d u c e s t h em e m o r y s p a c e ( 2 ) c o n s t r u c tt h ep a r a m e t e rd a t a b a s eo f p l a n t - s t r u c t u r em o d e l 2 3k i n d so fp l a n t - s t r u c t u r em o d e l sd e f i n e db yb o t a n i s t sc a nd e p i c tt h e c o n t i n u o u sd i v e r s i f i c a t i o nf e a t u r e so fp l a n t s t r u c t u r e a c c o r d i n g t ot h e t o p o l o g i e s o ft h e s es t r u c t u r em o d e l sa n dp e t r i n e t ，w ec o n s t r u c ta 浙江工业大学硕士学位论文 c o r r e s p o n d i n gl s y s t e ma n ds e tu pap a r a m e t e rm o d e ld a t a b a s ed e p i c t i n gt h e p l a n tt o p o l o g y t h ed a t a b a s ep r o v i d e st h em o d e l sf o rt h e i m i t a t i o no fp l a n t s ； c o n s e q u e n t l y ，i te s t a b l i s h e st h ef u n d a t i o nf o rf a s tc o n s t r u c t i o no fp l a n tm o d e l s a l s o ( 3 ) p u tf o r w a r da ni m p r o v e db r a n c ha l g o r i t h m b yd o i n gs o m er e s e a r c h e so ng e n e r i cb r a n c ha l g o r i t h m ，t h i sp a p e rg i v e sa l l i m p r o v e db r a n c ha l g o r i t h mw h i c h n o to n l yc a ni m i t a t et h eb r a n c hs h a p e so ft h e p l a n t ，b u ta l s os o l v et h eg a pp r o b l e m se x i s t e di ng e n e r i cb r a n c ha l g o r i t h m m o r e o v e r t h eb r a n c ha l g o r i t h md o e s n ti n c r e a s et h ec o s tt i m ec o m p a r i n gw i t h t h eg e n e r i cb r a n c ha l g o r i t h m ( 4 ) d e v e l o pap l a n t - i m i t a t i o np r o t o t y p es y s t e m t h i sp a p e rc o n f o r m i t i e st h er e s e a r c ha c h i e v e m e n t sm e n t i o n e da b o v e ， b u i l d sap l a n t - i m i t a t i o np r o t o t y p es y s t e mb a s e do ni m p r o v e dl s y s t e m i nt h e p r o t y p es y s t e m ，t h eu s e r sc a nm a k eu s eo ft h ep l a n t s t r u c td a t a b a s ea n dt h e o r g a nd a t a b a s eo f f e r e db ys y s t e m ，a n db u i l d st h ei n d i v i d u a lp l a n t k e yw o r d s ：v i r t u a lp l a n t ，l s y s t e m ，p l a n ta r c h i t e c t u r a lm o d e l ，s u b s t r u c t 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江 工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的 法律责任。 作者签名：了氐缒铷日期：扣7 年告月方7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) 作者签名：k 导师签名：旁 雅鼬 日期：。j 。j 7 年 日期：知7 年 ， 于月乒日 ， ，月岛e t | 浙江工业大学硕士学位论文 第一章绪论 1 1 虚拟植物生长建模与可视化研究的目的和意义 虚拟植物生长的计算机建模与可视化仿真是计算机领域近几年来一个热门且极富 挑战性的课题。通过对植物结构进行形式化语言描述、设计相应的绘图算法，实现对 诸如树木、灌木、花卉等植物进行十分逼真的虚拟仿真。 虚拟植物生长的计算机建模与可视化仿真研究在农林业、景观设计或园林设计、 虚拟现实技术、计算机动画、计算机教学等领域有着广泛的应用前景【”。农林业信息化 是未来的发展趋势，也是二十一世纪的重要发展目标。以计算机为辅助工具对植物生 长进行建模与可视化仿真有很多好处，不仅可以节省资源，缩短研究周期，优化产出， 而且在探索植物生长过程规律及改善人类生存环境等方面都具有重要的意义。 一般，虚拟植物生长研究主要包括基于植物学、农林学知识的植物生理生态模型 的研究与基于视觉效果和计算机图形学知识的三维植物可视化研究1 2 1 。因此虚拟植物生 长研究主要应用在以下几个方面： ( 1 ) 农林业方面的应用：虚拟植物可以模拟整株植物及其胚芽或根系部分的生长 p 】。它可以代表一个真实的植物，其形态变化规则可通过己经测量的数据、几种真实植 物的平均值或某一假定植物得到。虚拟植物不只局限于模拟植物表象，也可以具体表 现任何受植物结构影响的实测或假设过程。例如，可以模拟植物代谢物的运动，病虫 害与植物形态变化之间的关系，并将其可视化为错误的颜色或信号。还可以模拟外部 环境与虚拟植物的交互过程，如光照、水肥、昆虫在植物表面的运动及其对植物体所 造成的影响。因此，应用虚拟植物可以在不破坏真实植物的情况下研究其生理、生态 行为以及与周围环境的相互作用，从而，培育和推广优良品种，通过调控周围环境状 况来促进作物生长，达到高产高效的目的。 ( 2 ) 图形图像方面的应用：虚拟植物的形态结构可以以植物不同部分的数据、位置、 大小、表面积、附着角度、年龄和相互间的拓扑连接关系等形式输出，也可以被概述 浙江工业大学硕士学位论文 为直观、真实的或示意性的图像或模拟时间序列摄影的动画。这些图形图像可以被应 用于计算机教学、商业、计算机辅助园林和景观设计、生态环境预测与可视化、计算 机动画、游戏、影视和虚拟现实等领域【4 】。 ( 3 ) 荒山改造、美化环境方面的应用：计算机模拟出的虚拟植物图像是对植物某一 特定时刻状态的描述，是植物生理生态模型的外在表现形式。我们可以将植物的形态 结构模型和生理生态模型结合起来，应用计算机图形学的知识将植物的生长过程等通 过计算机屏幕再现出来。因此，虚拟植物可以满足园林设计、遥感等应用领域的需求。 如在公园、住宅区内栽种花草树木前，可应用虚拟模型预测所栽植物数年后的生长状 况，从而确定所采用的栽种密度、品种搭配是否理想。近年来，由于人类对树木、森 林、植被的破坏，导致气候日益恶劣，沙漠化程度日益加剧。因此，我们可以通过遥 感图像分析、荒地土质分析、植物品种分析，将虚拟植物生长技术应用于荒山改造、 环境规划、建筑投标等领域垆】。 因此，虚拟植物生长的计算机建模与可视化仿真研究有着广泛的应用前景它对中 国这样的农业大国及林业弱国，有着十分重大的意义【2 】。 1 2 国外研究现状 对虚拟植物的研究可以追溯到上世纪六十年代。早在1 9 6 8 年，美国学者 l i n d e n m a y e r 就提出了l 一系统【6 】，初步建立了植物形态结构模拟典型的理论方法框架。 近三十年来，随着计算机科学、应用数学、植物学、农林学以及生态学等学科的众多 专家学者对植物生长建模、仿真、可视化及其应用越来越关注，越来越重视，他们进 行了多角度的研究。总的来说，虚拟植物主要的研究方向可以归纳为：( 1 ) 单纯的植物 外观形态模拟。这种外观形态模拟注重视觉效果的真实性，主要研究植物三维结构、 植物器官以及自然场景的模拟与可视化7 d 0 1 ；( 2 ) 真实植物生长过程的模拟。这种以强 调真实植物生长为主的模拟注重植物学理论的真实性，通常借助反映植物生理生态的 功能模型与反映植物结构的几何模型的相互作用来模拟植物的真实生长过程【1 1 ”1 。在 众多学者的发展和推动下，虚拟檀物研究取得了相当大的进展。 在植物形态建模方面，目前国外出现了多种形态发生模型，如各种改进的l _ 系统、 分形方法、函数迭代系统、分枝矩阵、粒子系统、参考轴技术、a 系统等等。 2 塑垩三些奎兰堡主堂垡堡奎 l 一系统定义简洁，描述具有严格分形结构的物体非常精炼，因此应用很广泛。 加拿大c a l g a r y 大学的p r u s i n k i e w i c z 教授综合基于生物学的计算机图形学、形式化语 言理论和数学等多方面知识，在利用l - 系统对植物虚拟仿真领域做出了杰出的贡献。 他不仅对l 一系统模拟植物做了深入研究，还在研究过程中对l 一系统理论进行了扩充， 并针对植物虚拟仿真的特点，开发出l + c 建模语言( l + cm o d e l i n gl a n g u a g e ) 【1 6 】。以 他为首的工作小组，在s g i 工作站上开发了基于u n i x 系统的虚拟植物实验室v i r t u a l l a b o r a t o r y ( v l a b ) 和植物与分形产生器c p f g ( p i a n ta n df r a e t a lg e n e r a t o rw i t hc o n t i n u o u s p a r a m e t e r s ) ，以及基于w i n d o w s 的l s t u d i o 系统。该系统通过编译植物对应的l 文法， 使用l + c 建模语言，实现对不同类型植物的模拟，并且能够用简单动画的形式表现出 植物生长的过程。由于他的研究，使得l 一系统被广泛应用在植物虚拟仿真领域，并且 取得了很好的效果。 德国k a r l s r u h e 大学开发的x f r o g 软件使用l 一系统实现树木的拓扑结构。该软件定 义了一些表示植物器官、植物结构、全局变量和功能函数的小图符，每个图符与描述 其具体属性的参数表对应。x f f o g 将这些图符作为构筑植物结构的部件，用户通过组合 这些图符，就能生成相应的植物。 虽然l 一系统应用很广泛，但是这种用字符串表达的形式语言在产生式中将植物的 几何结构信息和拓扑结构信息同时描述，理解和使用都比较困难。特别是模拟指定植 物形态的迭代公理和产生式多是手工构造，缺乏有效的设计方法【2 】f m 。为此，b i a nr 等人对如何从植物拓扑结构数据库中自动抽取l _ 系统公理和产生式规则进行了有益的 探索1 8 。1 9 】。但是他们仅仅研究了二维l 一系统规则的提取，另外，随着搜索空间的增大， 如何获得具有最佳适应度的个体没有涉及。 基于有限自动机模型i 冽建立的a m a p 系列软件在植物生长机理模型与可视化模型 结合方面取得了卓有成效的进展。a m a p m o d 系统依靠功能强大的田间数据采集与分 析模块，将测定的植物各类数据通过特有的编码方式记录，通过数据库系统管理这些 数据，然后应用a m a p 建模语言a m l ( a m a pm o d e l i n gl a n g u a g e ) 对数据库中的数据 进行提炼，得到植物生长规律叫。但在实现各种植物构造模型方面，分形方法能力有 限且缺少与生理生态模型的接口方式。 粒子系统方法由r e e v e s l 2 2 1 在1 9 8 3 年提出，最早用于模拟火焰、云彩等不确定物体 ( f u z z yo b j e c t ) 。后来，r e e v e s 等人通过使用结构化粒子系统( s t r u c t u r e dp a r t i c l e s y s t e m s ) ，比较成功地对森林场景进行了虚拟仿真田1 。该方法具有动态、随机的特征， 3 浙江工业大学硕士学位论文 适合于对大片的植物群从景观上进行有效地模拟，但是不适合用来表达单个植物的形 态结构以及发展过程，而且用粒子系统所绘制的树木看起来有比较明显的人造痕迹， 缺乏高度的真实感。 根据建模的方法和目的，上述模型可以分为三类：静态模型、动态模型和纯图形 学模型。 ( 1 ) 静态模型主要针对特定种类植物的形态模拟，先使用三维数字化方法测定植物 的形态结构，然后根据所测数据直接构造植物的形态结构 2 4 - 2 6 。这种方法能够有效地 模拟特定植物的形态结构，可用来研究与植物空间结构有关的定量和定性特征以及生 理生态过程等。但是，它需要测量大量的数据和人工干预处理，不适合反映植物形态 结构的动态变化规律 5 1 。 ( 2 ) 动态模型通过模拟组成植物体的各离散部分的活动来描述植物分枝结构的生 长【2 】，适合模拟大多数种类植物的形态结构，主要包括各种l 一系统和自动机模型等。 ( 3 ) 分枝矩阵模型、迭代函数系统及a 系统等纯图形学模型侧重于计算机图形学， 只注重视觉效果的真实性，主要研究如何用最少的植物学知识，方便快捷地生成单纯 外观上的植物图形。此类模型不需要复杂的植物生长机理模型，所以一般不适合模拟 植物生长发育过程，主要用于园林规划、景观设计等方面。 此外，植物体可视化的研究也一直是计算机图形学领域中的一个热点。其主要研 究集中在植物器官的模拟及细节表达、植物生长特性的表现及植物群落的模拟等方面。 器官的模拟可以归纳为三种方法：几何方法、基于过程的方法以及基于视觉、图 像处理技术的方法。早期植物器官的模拟多采用几何方法构造，这种方法比较简单， 但不适合模拟复杂的器官，也不能表现器官的动态生长；基于过程的方法虽然能够模 拟器官的动态生长，但是寻找合适的产生式规则及数学公式的常量因子比较困难；基 于视觉、图像处理技术的方法目前也不能实现完全的自动化，依然需要大量的人工干 预。随着计算机计算能力的不断增强，近几年来，研究者越来越重视植物器官细节的 表现口7 之9 】，目前已能非常逼真地模拟。植物群落的可视化方面，较早的研究多是从纯 图形学的角度，生成逼真的三维场景，常用的方法有植株依次绘制法、细节简化法、 纹理映射方法以及相似样本化方法 z l 。这些方法大都有其局限性，往往是顾此失彼。最 近几年，一些学者开始尝试利用复杂系统思想和人工生命技术探索植物群落动态演化 的可视化仿真 3 0 - 3 3 1 ，展现了很好的研究前景。 4 浙江工业大学硕士学位论文 1 3 国内研究现状 我国对虚拟植物的研究起源于上世纪九十年代末期。在国家自然科学基金、8 6 3 计划等的资助下，国内许多研究机构进行了卓有成效的研究。但同国外的研究相比， 还存在较大的差距。国内的研究主要集中在农作物生长可视化模拟与计算机图形学等 方面。 ( 1 ) 在农作物生长模型方面：赵星等联合提出了双尺度自动机模型【3 4 】。该模型在 参考轴技术的基础上发展而来，结合了植物的许多固有生长特点，适合模拟植物生长 过程中形态结构的变化。后来，他们又研究了多尺度自动机模型1 4 j 。 中科院自动化所胡包钢教授领导的中法联合实验室( l i m i a ) 同中国农业大学、 法国国际农业研究发展中心的c i r a d 及法国国家计算机科学与控制研究所i n r i a 合 作，在著名的虚拟植物模型a m a p 模型的基础上，联合开发出一种通用植物生长模 型c h e l l l a b 模型。该模型采用双尺度自动机模拟植物结构的形成，通过模拟植株 的生物量生产与基于植株拓扑结构的生物量分配，以及器官生物量积累与器官形态的 关系，并行模拟植物结构一功能过程，从而更精确地模拟植物的生长【i 引。 中国农业大学【3 5 】运用l 一系统方法，建立了不同土壤水分条件下小麦根系生长发育 三维可视化模型：与北方工业大学c a d 中心合作，实现了理想条件下冬小麦苗期生长 的三维动画模拟。 中国农业大学资源与环境学院的郭焱、李保国教授应用高精度的三维数字化仪， 对不同生育期玉米冠层的结构进行了精确的测量，在此基础上建立了虚拟玉米静态模 型1 3 6 1 。借助该模型，能够分析玉米冠层的三维结构特征。近几年来，他们在植物的“结 构一功能”模型、光线在作物冠层间的分布与传播特性等方面进行了深入的研究【3 ”。 ( 2 ) 在计算机图形学方面：潘云鹤等对美学理论在三维树木建模中的作用进行有 益的探索【3 8 】。通过对树枝的交互变形，提供了一种以美学理论为准则对树木整体形状 进行美学控制的方法。吴恩华等人提出基于图像的造型方法，从真实照片中抽取树的 骨架，并基于此重建树的三维模型 3 9 1 。陈彦云、严涛等采用基于分类及环境特征的方 法绘制虚拟场景。为减少复杂树结构占用的计算机资源，康孟珍、d er e f f y e 等通过 事先将自动机模型计算过程中重复出现的结构定义成子结构，提出一种从最简单的子 结构起，基于子结构的引用来形成复杂结构的方法【4 “。该方法有效地提高了复杂结构 的计算速度。在自然场景的真实感绘制方面，柳有权等针对过去研究的不足，提出一 浙江工业大学硕士学位论文 种模拟树在风中摇曳的新方法。该方法基于统计数据，采用高斯分布来近似逼近实际 风力，并对树的各个部分分别进行独立的变形计算，然后再根据它们的连接关系进行 组合，从而完整地获得树的变形【4 2 】。 1 4 研究的内容和目标 从以上的综述我们可以发现，由于植物形态千差万别，生长规律也不一样，目前 植物生长建模与可视化研究还不完善，现有的虚拟植物模型的可视化模型耗时大，对 计算机性能要求高，而作为植物形态发生模型中重要的一种方法l 一系统，由于其具有 定义相对简洁、结构化程度高、易于实现等优点，已经越来越多地得到了研究和应用。 但是，传统的l 一系统存在描述植物结构繁琐、执行效率低等缺点。本文提出一种 新型l 一系统性能改进算法，该算法在l 一系统字符串的后续迭代过程中重复利用以前的 迭代结果，而不是每次都重新用产生式对临时字符串进行替换，从而避免了字符串的 重复迭代，减少了临时字符串的长度；另外，在字符串的图形化解释过程中，利用图 形的分形特点，沿用子结构思想来提高算法的执行效率。 基于此算法，本文建立植物结构模型参数库。在进行植物仿真时，用户不用自己 构造l 系统文法，只要在拓扑结构参数库中选择一种感兴趣的植物结构模型作为模拟 的模板，就可直接重构出三维植物，并且可以在重构的模型上进行修改，从而实现植 物形态的快速模拟。 最后，开发了植物模拟生长的可视化仿真原型系统。仿真研究表明该算法能明显 改善传统l 一系统的性能，且算法简单有效。 本课题是浙江省基金项目的重要部分，本系统为项目的后续开发提供了平台，也 为快速重建植物三维结构奠定了基础，有一定的实际意义和学术意义。 1 5 论文的章节安排 第一章：绪论。主要介绍了基于植物形态模拟与可视化研究的目的及当前国内外 6 浙江工业大学硕士学位论文 的研究现状，提出本文的研究内容与目标。 第二章：基于卜系统的植物形态模拟方法。在介绍各种传统l - 系统的模拟方法的 基础上，提出了l - 系统性能改进算法，并用仿真实验对两者进行效率分析。 第三章：植物结构模型库的建立。介绍2 3 种植物结构模型，并用几种典型的结构 模型为例，详细介绍模型库的构造过程。 第四章：植物器官模拟。介绍植物器官枝干、花、叶、果实模拟方法，以及对这 些器官的渲染方法，包括光照，纹理，颜色渲染。 第五章：植物原型仿真系统。介绍仿真环境以及构成仿真系统的各个模块的功能。 第六章；工作总结与展望。对论文进行总结，展望未来。 7 浙江工业大学硕士学位论文 第二章基于l _ 系统的植物形态模拟方法 植物是自然界最常见的景物，其形状各异，千姿百态，且结构特征性很强。就当 前的虚拟现实技术而言，不规则形体建模也是一个难点。耐分形理论能较好地解决不 规则形态物体的仿真建模问题。 分形的模拟方法有多种，如迭代函数系统、l 一系统等。前者通过选定若干仿射变 换，将整体形态变换到局部，并将这一过程迭代进行下去，直到得到合适的造型，但 是前者在植物的生成中，采用大量的空间点表示植物的形状，对生成植物的处理带来一 定的难度，而后者是一种文法系统，由若干产生式和一个表示植物初始状态的简单字符 串组成，从初始字符串开始，通过产生式并行回写方法生成表示植物结构的字符串， 然后由字符串获得植物的模型，方便之处。 但是，虽然l 一系统应用已经很广泛，可是一般l 一系统算法效率低，建模速度慢。 针对这些缺点，华北工学院的张树兵【4 3 】等人提出了用递归算法来改进l 一系统。使用这 种算法可以有效地缩短l 一系统最终的字符串的长度，从而提高它的效率。但这种方法 还是没有解决好同一结构重复解释这一问题，使得此算法从整体上来讲并未改变l 一系 统计算复杂度上的指数增长特性。 本文基于这个问题提出了新型的l 一系统性能改进算法，用子结构思想改进l 一系统， 改进后的算法较之传统的l - 系统算法从空间复杂度及时间复杂度上都有了改善。 2 1l 一系统的定义 l _ 系统本质上是基于字符串重写的并行系统。通过对分形对象进行经验式地概括 和抽象，构造出公理与产生式集，然后按照字符串重写过程来生成字符发展序列，再 将各个字符解释成相应的图形元素，从而得到目标分形图形。l 一系统方法不仅能够用 来生成许多经典的分形图形，而且在模拟植物的分枝形态结构发展方面有着自己的独 浙江工业大学硕士学位论文 特之处。 l _ 系统的基本构图原理洲是，利用一个三元式来表达所需要构造的对象： l = 其中，v 是一个字符集，其中的元素用来组成表示图形命令的字符串；c a ) 是起始元， 用以确定字符串的起始状态，并且6 0 v ：p 是产生式的有限集合，产生式( a ，x ) p 写 作a 斗x ，字符t 2 和单词x 分别称为产生式的前驱和后继。如果对于给定的前驱a v 没有明确的重写产生式，则规定a 寸口，且产生式( 口，口) p 。通常也称v 为字母表， 为公理。 l _ 系统从一个字符串开始，通过将产生式规则多次迭代，最终得到一个表达分形 图的字符串。如何来解释重写后的字符串，可以借助l o g o s t y l et u r t l e 表示法，它由 t u r t l e s z i l a r d 和q u i u t i o n t 4 5 】最早提出。 2 1 1l - 系统的平面几何解释 l o g o s t y l et u r t l e 平面表示法的基本定义如下：设s 是一个字符串，( 而，y o ) 表示 龟的初始平面位置，表示龟的初始运动方向，d 表示龟的前进增量参数，万表示龟的 角增量参数，那么可用( x o ，y o ，a 0 ) 三个参数来决定龟的初始状态，再通过定义龟的移 动命令来对字符串进行图形化鳃释。命令定义如下： a ：龟向前移动一步，步长为d ，移动后龟的状态由( x ，y ，a ) 状态变为 ( x + c o s a ，y + s i n a ，口) ； + ：向左旋转万角，则龟的状态将由状态( 工，y ，口) 变为( x ，y ，口+ 艿) 状态，这里 规定正向角为逆时针方向，负向角为顺时针方向； 一：向右旋转占角，则龟的状态将由状态( z ，y ，口) 变为( x ，y ，口- 艿) ； ：将龟的当前状态( 包括龟所在的位置和方向) 压入堆栈； 】：从堆栈中弹出一个状态作为龟的当前状态。 l o g o - s t y l et u r t l e 平面表示法可以通过如下实例来表示。设有字符串： a + a a - a a 9 浙江工业大学硕士学位论文 令龟的初始方向角为= 9 0 。，旋转角增量为6 = 9 0 0 ，前进增量步长为d ( 等于方格的 单位长度) ，则龟的爬行路径如图2 - 1 所示： j l 7 j 图2 - 1l o g o s t y l et u r t l e 表示的简单分支结构 2 1 2l - 系统的三维立体几何解释 上述为二维图形，龟的移动命令也只涉及到向左向右两个方向，若要绘制三维树 形结构，需要将在l 一系统中将龟的而维动作方式扩展到三维空间上。从二维l - 系统转 换到三维l 一系统，需要考虑的是空间上前进的方向不只是向右旋转( 顺时针) 和向左 旋转( 逆时针) 两个方向，应从空间三维坐标来考虑。 首先给出描述龟运动当前方向的三个向量x 、y 、z ，分别表示龟沿着x 轴，y 轴， z 轴的运动方向，均是单位长度，如图2 2 所示。 图2 - 2 空间坐标与旋转方向关系 其关系满足满足x xy = z ，三者之间互相垂直，龟的旋转满足以下方程： 阻。y z 。i = i x y z i 盂 ( 2 - 1 ) 其中r 是3 x 3 旋转矩阵。关于向量旋转0 的矩阵表示如下： 1 0 浙江工业大学硕士学位论文 o c o s 口 一s i n 口 rc o s o r a e ) ：l s i n 口 l 0 。耋毋1 c 。s 口j i e o s os i n 80 li 也( d = i - s i n e c o s 80 i l 00 1 j 用下列带参数的符号控制龟形的空同方向： + ( 0 ) ：用旋转矩阵r x ( 0 ) 表示绕x 轴逆时针旋转0 角； 一( 0 ) ：用旋转矩阵r x ( 一o ) 表示绕x 轴顺时针旋转。角； 宰( 0 ) ：用旋转矩阵r y ( o ) 表示绕y 轴逆时针旋转8 角； ( e ) ：用旋转矩阵r y ( 一0 ) 表示绕y 轴顺时针旋转0 角； ( 0 ) ：用旋转矩阵r z ( e ) 表示绕z 轴逆时针旋转e 角； l ( b ) ：用旋转矩阵r z ( 一0 ) 表示绕z 轴顺时针旋转。角。 通过这种命令方式的扩展，就可以利用l 一系统在三维空间上绘制图形。 2 2l 系统的分类 ( 2 - 2 ) ( 2 3 ) 由于l 一系统的具体应用场合不同，先后形成了多种不同的形式，如d o l - 系统、 随机l 一系统、参数l 一系统、语义相关l 一系统等。下面简要介绍一下它们各自的基本特 点。 2 2 1d o l 一系统 d o l 一系统是最简单的一类l - 系统，它是确定的、语义无关的系统。在字符串的重 l o o _。l i i 、， 口 ，疋 叽副 9 口 璺| 宝o 浙江工业大学硕士学位论文 写过程中，字符的重写替换与它所处的语义环境无关，并且关于某个字符的重写产生 式是唯一确定的。一个d o l - 系统可以用一个有序的三元组l = 来表示【4 6 】，对 于每一个字母a v ，当且仅当有一个单词j ，使得口_ s 。 d o l 一系统作为最简单的一类l - 系统，用来模拟简单的植物结构非常方便。它的产 生式可以表示为： p r e d e c e s s o i - - s u c c e s s o r ( 2 - 5 ) p r e d e c e s s o r 表示前驱，s u c c e s s o r 表示后继。如以下的d o l 一系统文法为例： ：a b 】 ( 2 6 ) pi ：b 寸a - a b + a b ( 2 - 7 ) 其中： a ：沿着生长方向长出一段枝干； b ：用于表示侧枝； ：枝干当前状态压入堆栈； ；从堆栈中弹出一个状态作为枝干的当前状态； 其它符号含义与2 1 2 节介绍的一致，用于控制植物的生长方向。图2 3 是上式 迭代4 次的结果。 图2 - 3d o l - 系统仿真例子 从以上利用d o l 一系统来模拟植物结构的过程中可以看出，d o l - 系统使用简单， 产生式规则的构造相对简便。但是，d o l - 系统是确定的、语义无关的，它的产生式规 则不能体现具体的语义环境，而且是唯一确定的。这样，就使得d o l 一系统生成的图形 缺乏灵活性，在模拟植物生长等方面不够生动。但是，它的生成规则简单，易于构造， 在某些方面也得到了一定的应用。 1 2 浙江工业大学硕士学位论文 2 2 2 随机l 一系统 为了改善d o l - 系统不够灵活的缺陷，可以在字符串的重写替换过程中引入随机 性。随机性可以用在最终字符串中字符的解释上，例如长出的枝干长度a 是可以随机 变化的，还可以对一个字符给出多种产生式规则，将随机性用在产生式的选择上。显 然，前一种随机性能够保持基本拓扑结构不变，后者则能使基本结构发生变化，从而 生成更为灵活的结构。 对于通过对最终字符串中字符进行随机解释来实现随机o l 一系统的情况，可以在 d o l 一系统实现对字符串重写的基础上，对结果字符串中的相同字符给出不同的解释来 实现。例如，在前进时将前进的步长取不同的随机值，或者是在旋转时将旋转的角度 取不同的随机值，从而来实现最终生成有一定随机性的灵活的图形。 在2 2 1 节的示例中，对最终结果字符串进行解释时，将其中的a 取为不同的前进 步长，在进行旋转时每次旋转的角度也取为不同的随机值，从而就可以得到一组灵活 的图形，以迭代4 次为次。 图2 - 4 通过对字符随机解释获得的一组植物结构 对于通过对字符串中的字符随机选择产生式规则进行重写来实现随机o l 一系统的 情况，则要复杂一些。在这种情况下，一个随机o l 一系统是一个有序的四元组： b ，其中字符集v 、公理和产生式集p 的定义与d o l - 系统中的相同； 函数石：p 辛 0 ，1 称为概率分布，用来确定每个产生式被选择的概率1 4 7 。具体地说， 在字符串重写的过程中，以字符a 为前驱的产生式可能有好几个，每一个产生式以一 定的概率被选择用来对字符口进行重写，这些产生式被选择的概率之和应该为1 。随机 0 l _ 系统的产生式通常表示为： 13 浙江工业大学硕士学位论文 p r e d 专( p r o b ) s u c c ( 2 - 8 ) 其中p r e d 和s u c c 分别称为前驱和后继，p r o b 表示该产生式被选择的概率。 将随机性用在产生式选择上，对字符串中的某些字符给出多个产生式规则，能使 生成的基本结构发生变化，从而得到更为灵活的图形。如以下的一个简单例子： 0 7 ：彳【b 】爿【丑】( 2 - 9 ) p 1 ：b 寸( o 6 ) 4 卜a b + a b 】 ( 2 - 1 0 ) p 2 ：b 一( 0 3 ) 彳卜l a b 】( 2 - u ) p 3 ：b _ ( o 1 ) a + a b 】( 2 1 2 ) 对公理迭代一次后可能得到如下结果： a b a b 】 4 【4 卜彳8 】【+ 爿b 】4 【爿【一la s 】( 2 1 3 ) 其中，随机对第一个b 应用了产生式p 1 ，对第二个b 应用了产生式p 2 。根据概率 因子的随机选择，可以对模块应用不同的产生式，生成不同的字符串。 这样，在随机o 卜系统中，对于同样的生成规则，经过相同的迭代次数可以生成 不同的结构，从而实现各种灵活的分形结构。 2 2 3 参数o l _ 系统 随机o l 一系统可以在一定程度上实现灵活多变的植物结构图形。但是，由于它是 通过不可控制的随机过程来实现生成图形的多样性的，因此，随机o l - 系统产生的图形 的结构畸变就无法避免。此外，在刻画外界环境对植物结构的影响方面，随机o l 一系 统也无能为力。为了解决这些问题，引入了参数l 一系统。它将字符串的重写过程扩展 到了带有参数控制的单词扩展过程，从而实现了生成灵活图形过程的可控性。 参数o l _ 系统是一个四元组：l ： ，其中字符集v 、公理m 和产生式集 p 的定义与d o l 一系统中的相同，是系统的参数集。参数o l 一系统的产生式由前驱、 条件和后继三部分组成，其一般形式如下【4 8 】： p r e d ：c o n d i t i o n s c c ( 2 - 1 4 ) 其中：p m d ，c o n d i t i o n 和$ 1 1 c c 分别表示产生式的前驱、条件和后继。在参数o l 1 4 塑塾三些奎兰堡主兰垒堡奎 系统中。一个带参数的模块与某个产生式相匹配，它必须满足以下三个条件： 1 ) 模块的字符和产生式的前驱字符相同； 2 ) 模块的实参个数和产生式前驱模块的形参个数相等； 3 ) 用实参替换产生式前驱模块的形参以后，条件表达式的运算结果为真。 当某个匹配的产生式能用来对某个模块进行重写时，就用该产生式的后继来替换 这个模块，并且用模块中的实参来替换产生式后继中相应位嚣上的形参。如果某个模 块没有和它相匹配的显式产生式来对其进行重写，则在字符串重写的过程中就用它自 身来进行恒等置换。在参数l 一系统中，可以根据参数的不同取值来决定字符模块产生 式的选择，这样就可以通过给参数赋予不同的值来控制分形图的生成，既可以实现分 形图的灵活多样，又可以避免随机o l 一系统产生的结构畸变。下面给出一个利用参数 l 一系统来生成植物结构的实例： ：4 ( 墨y ) b ( ，r ，q ) 】彳( x ，y ) f b ( t ，口) 】( 2 1 5 ) p l ：b ( t ，r ，口) ：口2 0 斗a ( 1 ，r + w ) 【+ 4 ( 口) 爿( ，r + w ) b ( t ，+ w ，口) 】 卜( 口) 彳( ，+ 们b ( ，+ w ，口) 】( 2 1 6 ) p 2 ：b ( i ，口) ：口 q - -