（计算机软件与理论专业论文）基于L系统的虚拟柑橘生长模型的构建方法研究.pdf

摘要 虚拟植物( v i r t u a lp l a n t ) 就是虚拟现实技术在农业领域的应用，虚拟现实技术为 许多领域的可视化研究提供了新的方法，例如在农业，教学方面和电视电影娱乐业都有 很多应用。虚拟现实技术应用计算机模拟植物在三维空间中的生长发育，利用可视化的 形式体现植物的形态结构规律，随着信息技术进步而迅速发展起来，它已成为计算机领 域的研究热点之一。虚拟植物生长是对植物在三维空间中的结构发育与生长过程的计算 机仿真模拟，是当今计算机研究领域的一个较新的研究方面。近年来，虚拟植物的建模 方法有了很大的突破和发展，现在较为流行的是利用l - s y s t e m 模拟植物生长。利用 l - s y s t e m 已经取得了长足的发展，例如在模拟植物建模方法、实现效率、空间复杂度、 现实可行性等方面取得了很大的突破，但l - s y s t e m 也存在一些缺陷，模拟植物生长效 率不高。特此本文提出引入子结构方法改进l - s y s t e m 的建模方法，在一定程度上优化 了虚拟植物的建模方法。 本文在总结虚拟现实技术的研究现状的基础上，提出了现存的问题以及本文的研究 意义与价值。接着给出了虚拟植物的基本方法和概念，如子结构和l 系统的基本原理。 论文主体部分对虚拟柑橘器官和柑橘树建模方法进行了详细的阐述，并将子结构和l 系 统突破性地共同运用到柑橘树生长模拟过程中。在此基础上，采用标准图形软件接口 o p e n g l 和支持可视化编程的集成丌发环境v c + + 6 0 ，完成了技术在柑橘生长模拟过程 中的应用创新，望能给同仁带来抛砖引玉的作用。 关键字：l - s y s t e m ；子结构；虚拟柑橘 ab s t r a c t v i r t u a lp l a n ti sa nv i r t u a lr e a l i t ya p p l i c a t i o n si nt h ef i e l do fa g r i c u l t u r e ，v i r t u a lr e a l i t y t e c h n o l o g yp r o v i d e san e wm e t h o df o rm a n ya r e a so fv i s u a l i z a t i o nr e s e a r c h ，s u c h a s a g r i c u l t u r e ，t e a c h i n g ，a n ds oo n i tc a ns i m u l a t et h eg r o w t ha n dd e v e l o p m e n to fp l a n tb y v i r t u a lr e a l i t yt e c h n o l o g yi nt h et h r e e d i m e n s i o n a l a n d u s i n gv i s u a l i z e df o r mc a np e r f o r mt h el a w so fp l a n tm o r p h o l o g y w i t ht h er a p i dp r o g r e s s o fi n f o r m a t i o nt e c h n o l o g yd e v e l o p e d ，i th a sb e c o m eah o tc o m p u t e rr e s e a r c hi nt h ef i e l do f o n e v i r t u a l p l a n tg r o w t ho fp l a n t sa r ea t t h r e e d i m e n s i o n a ls t r u c t u r eo ft h ep r o c e s so f d e v e l o p m e n ta n dg r o w t ho ft h ec o m p u t e rs i m u l a t i o n ，a n di ti sm o r en e wa r e ac o m p a r i s o n w i t h o t h e r s r e c e n t l y ，t h e m e a l lo fv i r t u a l p l a n t h a sa g r e a tb r e a k t h r o u g h a n d d e v e l o p m e n t ，a n dn o wt h em o s tp o p u l a ro n ei st h ew a yb yl s y s t e m a n di th a sad e a lo f b r e a k t h r o u g h i nt h ea r e a so ft h em e a n so fm o d e l i n g 、a c h i e v ee f f i c i e n c y 、s p a c ec o m p l e x i t y a n dp r a c t i c a lf e a s i b i l i t y a tt h es a m et i m e ，i ta l s oh a ss o m ed i s a d v a n t a g e ，t h ew a yo fv i r t u a l p l a n ti si n e f f i c i e n c y ，f o re x a m p l e s ot h ea u t h o ri n t r o d u c et h ec o n c e p to fs u b s t r u c t i o n ，a n d m a k ei tc o m b i n ew i t hl s y s t e mi n t ot h ep r o c e s so fv i r t u a lp l a n t i to p t i m i z et h em e a n so f v i r t u a lp l a n tm o d e l i n g t h ea u t h o rp u tf o r w a r dt h ee x i s t i n gp r o b l e m sa sw e l la st h es i g n i f i c a n c ea n dt h ev a l u e o fr e s e a r c hi nt h i sp a p e ro nt h eb a s i so fs t a t u sq u oo fv i r t u a lr e a l i t yt e c h n o l o g y t h e nt h ep a p e r i n t r o d u c e st h eb a s i cm e t h o d sa n dc o n c e p t so fv i r t u a lp l a n t s ，s u c ha ss u b s t r u c t u r ea n dl s y s t e mo ft h eb a s i ca n dp r i n c i p l e s t h em a i np a r to fp a p e rd e s c r i b e so nv i r t u a lo r g a no fc i t r u s a n dc i t r u st r e e m o d e l i n gm e t h o di nd e t a i l ，a n dm a k e ss u b s t r u c t u r e a n dls y s t e m c o m m o n l yi n t ot h ep r o c e s so fg r o w t ho fs i m u l a t ec i t r u st r e e o nt h i sb a s i s ，t h ep a p e ra d o p t s t a n d a r do p e n g lg r a p h i c ss o f t w a r ei n t e r f a c ea n ds u p p o r tf o rv i s u a lp r o g r a m m i n go ft h e i n t e g r a t e dd e v e l o p m e n te n v i r o n m e n tv c + + 6 0 a n da c h i e v e sag r o w t ho fs i m u l a t i o n t e c h n o l o g yi nt h ec i t r u si nt h ep r o c e s so f t h ea p p l i c a t i o no fi n n o v a t i o n ih o p et h a tt h i sa r t i c l e c a nb r i n gs o m ei n s p i r a t i o nt oo t h e rs c h o l a r s k e yw o r d s ：l s y s t e m ；s u b s t r u c t i o n ； v i r t u a lo r a n g e 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取得 的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文中作了 明确的说明。本声明的法律结果由本人承担。 学位论文作者签名：进丞生自 日期： 学位论文使用授权书 本学位论文作者完全了解东：i l n 范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许 论文被查阅和借阅。本人授权东：i i ：n 范大学可以将学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编本学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：畦么描 e l 期：。丝生：z 学位论文作者毕业后去向： 指导教师签名：圣鱼习= 日 期：2 翌呈：生! l 工作单位：勉鱼型鲨继纽让 通讯地址：型丝壅受鲥臣逸垃兹：2 丝丝 电话： 癌阁邮编： 东北师范大学硕士学位论文 第一章引言 1 1 问题的提出及研究意义 1 1 1 问题的提出 虚拟柑橘生长技术一直以来都是很多虚拟现实研究者主要研究的对象之一，也取得 了较为成熟的进展。例如，学者们在l 系统模拟虚拟生长的基础上又发展了参数l 系统、 微分l 系统、随机l 系统、语义相关l 系统等，对于虚拟柑橘生长的逼真程度有了很大 的改进。同时还有人提出了子结构的概念，对于提高虚拟柑橘生长的时间复杂度和空间 复杂度都有了长足的进展。可是，现在还没有人将二者结合起来共同应用于虚拟柑橘生 长过程中，在这里作者提出将柑橘的生长的过程中将二者有机的结合起来，使虚拟柑橘 的效果很为逼真、有效。 1 1 2 研究的理论价值 虚拟现实技术在现实生活中有着非常重要的应用，例如在三d 电影、奥运会开幕式 等场合都得到很好的发挥，取得了令人意料不到的效果。虚拟现实技术的出现标志着人 类的生活有了更高层次的提升。而虚拟植物生长可视化技术研究对虚拟现实、计算机仿 真等学科具有重要的意义。科学家们对人化世界在计算机上模拟算法已经研究得非常彻 底，并在很多方面得到了具体的应用。然而，长期以来，利用计算机来模拟自然界生物 的生长变化一直困扰着很多的虚拟仿真学方面的专家学者，他们也从没有停止过对其探 讨和研究。近年来，随着计算机图形学的发展和计算机处理能力的提高，人们创造了各 种模型来描述植物的发芽、生长、死亡等全部过程。然而，直至今r ，由于植物的生长 发育过程受到来自内部、外部的多种因素影响，它们的生长过程十分复杂，还没有一种 可靠的算法来实现植物生长过程在计算机上真实模拟。因而对虚拟植物的生长可视化技 术进行研究是非常必要，它是虚拟现实和计算机仿真等学科的核心技术，是计算机图形 学研究的热点，其具有很高的研究价值。 1 1 3 研究的应用价值 长期以来，人们在研究植物生长可视化的过程中，许多计算机科学家、植物学家以 及数学家等也被加入到该领域中来，为虚拟现实方法的研究提出了很多新的思路，丌拓 了更多的新的视野。现今，虚拟现实技术已经在各行各业都有了十分广泛的应用，举例 来说主要有以下几个方面： 第一是在教育教学中的应用用于制作教学软件、教育类电影软件。现在的中小学、 乃至大学都逐渐得将虚拟现实技术引入到教学当中，让大众形象的认识和了解他们赖以 生存的植物。并具有深远影响： 东北师范大学硕士学位论文 1 、激发学生对学习的热情。 这是虚拟现实技术在教育教学中最突出明显的作用。以往的教学模式是“老师教、 学生听“的单向教学模式，学生在遇到生涩难懂的抽象问题时只能靠自身的悟性来理解， 知识主要是“从耳朵”进入大脑，然后进行理解，这样的教学模式有其自身一定的局限 性和晦涩性。而引入了虚拟现实技术后，由于虚拟现实技术本身的沉浸性、交互性、构 想性，学生不仅是一个观察者，还是一个参与者。学生不仅可以接受教师的口头授教， 还可以通过眼睛看，动手参与到实验当中。这样就大大激发了学生的学习热情，改变学 生的学习态度，从“为了学习而学习转变为“喜欢学习而学习 。 2 、克服对一些自然条件的苛求 一些实验对象仅存在于一定的时间和空间之内，作为观察者在不同时期对同一事物 的感受也是不同的，就有可能对研究结果造成偏差；有些实验则需要漫长的时间，作为 一个研究者如果在真实世界中完成实验则需要消耗大量时间和精力，类似于这样的实验 现在的学习者就可以在利用虚拟技术在虚拟环境中进行。 3 、使学生尝试的范围更为宽泛。 有很多实验如果全部采取真实实验，可能会带来很多不利的影响，如研究者及其实 验场所附近的人的人身安全、实验场所附近建筑设施、环境等都会带来一定程度的毁坏。 而虚拟现实责可以使实验在虚拟状态下尽量临摹真实现场的状态。这样可以避免很多不 必要的麻烦。这些实验经常在航空航天、军事训练、抢球险情等带有一定危险性的试验 中得到应用。 4 、节省教学资源 在以往的教学实验过程中，由于大部分学校学生是分批、分组进行实验，一种教学 资源被多次重复使用，这样无形中造成很大的资源浪费。而采用虚拟现实技术进行的实 验对同一种实验研究只需构建一次，然后多次放映即可，这样就大大减少了教学资源的 浪费。相信随着虚拟技术在教学中的地位逐渐提高和虚拟实验设备成本的逐渐降低，虚 拟现实技术会在教学中得到普遍使用。从长远的角度来看，虚拟现实技术也必将会为教 育教学实验节省相当一部分的开支。 第二是在农业方面的应用虚拟植物生长建模可视化技术的研究，是虚拟农业研 究的重要组成部分，对农业的优质发展有非常重要的意义，具有多方面的实用意义： 1 、由于有些实验在现实世界中难以进行或费时、费力、昂贵的试验。而应用虚拟植 物生长的技术进行虚拟农田试验可以减少一些困扰。如种子多少、光照强度对作物生长 的影响、作物种植的搭配，为作物栽培提供信息，有利于资源的利用效率的提高。 2 、通过虚拟害虫的生活规律，例如藏匿、取食等特点，确定最佳的喷药时间和方式， 一方面可以降低成本，同时还可以减少环境污染，取得生态效益，并为培育降低病虫害 的作物形态提供依据。 3 、虚拟土地的养分和水分的变化会给植物带来怎样的变化，可以为植物更好的生长 提供参考依据，从而选择出该地区的生长作物和它们的最优水肥条件，推动灌溉和施肥 措施的升级，提高化肥和水资源的利用效率。 2 东北师范大学硕士学位论文 4 、建立虚拟农场，和一些智能化农业软件系统相配合使用，种植者可以利用网络直 接操作在计算机上种植虚拟作物，进行虚拟农田管理，观察作物生长状况和动态过程， 还可以实验在各种环境条件和栽培措施的情况下，观察作物生长状况的改变和最终结 果，从而探索出更多更宽阔的道路来。 总而言之，虚拟植物生长在精神与物质领域都可以给我们带来很多便利之处，在已 有的植物生长模拟模型的基础上，由于现在科学技术研究水平的不断提升，特别是计算 机方面突飞猛进的发展，植物生长模拟研究领域也发生着革命性的变化，将推动世界向 着更灿烂的文明前进，植物生长模拟涉及的学科相当繁多，其中包括植物生理学、农业 气象学、微气象学、土壤学、计算机科学、生物学、数学等众多学科。相信在不久的将 来虚拟现实技术会给人类带来更大更优质的便利。 1 2 国内外研究现状 1 2 1 国外研究现状 自从仿真学科诞生以来就有很多的国外知名学者致力于其的研究与发展，并取得了 丰硕的成果。1 9 6 8 年，美国生物学家l i n d e n m a y e r ( 1 9 2 5 - 1 9 8 9 ) 在生物杂志上发表了一 篇论文，突破性地提出了形式化的表达植物分枝状况的系统“字符串重写系统”， 这便是著名的、也是一直延用至今的l 系统( l - s y s t e m ) 。该系统对植物的形态与生长 进行了形式化的描述，在刚开始时大家只把焦点定在植物的拓扑结构上，人们只知道关 注植物的各个器官( 主干，枝条，叶，果等) 之间的相邻关系，随着技术的不断发展，人 们通过几何图形来表示字符串系统的各个符号，形成了现今的人们广为重视的l 系统。 继l i n d e n m a y e r 提出l 系统后，加拿大学者p r u s i n k i e w i c z 等人为了改进l 系统的 性能，对其了扩展，提出了开放l 系统和随机l 系统，前者的提出能够与周围环境交 互，后者则侧重于植物生长的随机性。 为了建立完整有效的植物模型，l 系统不断扩展其功能。一开始大多研究学者们都 认为l 系统只是一个孤立的系统，既不能模拟植物模型之问的交互，也不能够模拟植物 与周围环境的交互。加拿大学者m e s h 和p r u s i n k i e w i c z 在经历了一系列的讨论与研究 后对l 系统进行了进一步的扩充，提出了能与周围环境交互的“开放式l 系统”。该l 系统引入了一个特定的“交流符号”，该符号可以完成l 系统与周围环境的交互。开放 式l 系统概念的提出对于l 系统的发展有重要的意义，利用它可以模拟养分、阳光、天 气、风、病虫害等环境对作物生长的影响，对农业科学的研究也具有很重要的意义。之 后，p r u s i n k i e w i c z 等又提出了时变l 系统。后来，为了能够进一步描述植物生长连续 的过程，p r u s i n k i e w i c z 又将高等数学中的微分方程引入到了l 系统，从而提出了微分 l 系统。该系统能够模拟植物的叶序、各类植物的花朵、弯曲的枝条等，以及植物在生 长过程中相互影响等情况，到现在为止是较为完美的模拟植物的方法。 随后，美国的另一位著名学者r e e v e s 于1 9 8 3 年提出了著名的“粒子系统 ( p a r t i c l e ss y s t e m ) ”的建模方法。粒子系统是一种针对“模糊 对象( 比如火焰、云、 3 东北师范大学硕士学位论文 水等) 而提出的建模方法。粒子系统定义为是由很多的粒子构成，在一定时间内，每个 粒子都会经历产生、移动、变化和死亡这四个过程。用粒子系统来对物体进行建模的过 程在r e e v e s 之前有一个酝酿过程。爱玩电脑游戏的玩家大都知道电脑游戏中就是用许 多很小的发光点来表示飞船的爆炸过程，r o g e rw i l s o n 曾经在试验中用粒子系统来表 示烟雾的产生，j i mb 1 i n n 则曾用粒子来进行模拟光线的传送，然而这种模拟效果是无 法用经典的基于表面的建模方法来描述。粒子系统在电影“s t a rt r e k ”中就得到了淋 漓尽致的应用，其中大家看到的“s t a rt r e k ”中的“火墙”就是用粒子系统生成的， 模拟效果非常的形象逼真，带来的视觉冲击前所未有。 在此以后，r e e v e s 又对粒子系统进行了扩充，提出了结构化的粒子系统。他利用 这种方法成功的描述了树木、草地、森林、花朵等较为复杂的景物。粒子系统的粒子至 此不再是独立的，系统更加结构化，整体化。在生成模拟对象的时候，模型不但要绘制 粒子本身，而且还要描绘粒子运动的轨迹，所以可以利用其描述树木、花朵、草地等模 型。 美国学者j a s o nw e b e r 于1 9 9 5 年在计算机图形年会上提出了另外一种几何建模， 这种建模方法的主要特点是只重视树木外观的几何形状，但其并不是严格遵循树木的生 理结构。这个模型较为适合一般的用户采用，技术质量要求并不是很高，除了需要掌握 一定的基本几何知识外，不需要太多数学和生物学的基础知识。依据这个特点该模型定 义了很多相关的影响参数，w e b e r 利用这些影响参数构造出与样本非常类似的几何图 形。同时，人们还研究出了一种关于多利度模拟的简化算法，这样便可以实时的绘制大 片森林背景。 g r e e n e 提出了一种在微观世界里基于体素空间( v o x e ls p a c e ) 的方法。体素空间的 意思是将一块较为庞大的三维空间区域细分为若干较小立方体( c u b e ) ，而我们所说的一 个体元素指的就是一个小立方体。模型根据它们在元素空间中相交、相邻、碰撞等关系 在体素空间中“生长 ，空间中植物和周围环境可以利用体元素来表示。体元素的编号 则是至关重要的，利用它可以检测植物与周围的环境是否占用了相同的空间，我们就可 以适时宜地确定是否使植物与障碍物之间进行碰撞。实验证明，植物在体素空间中生长 比传统的几何空间中生长在速度上快很多，而且生长模型也非常简单。这样虚拟现实的 研究者们就可以利用体素空间元素划分的，控制植物的生长速度体素空间越大，植 物的生长过程越快，反之越慢。 d e r e f f y e 等人提出了“参考轴技术”的植物建模方法，该模型主要是运用有限自 动机来描述植物的形态，用随机过程的马尔可夫链理论以及“状态转换图 方式来描述 植物的生长模型。这种模型的特点主要体现在以下两个方面，第一个特点是利用该模型 模拟出的虚拟植物更为形象逼真，符合了虚拟现实的逼真性要素，并且这个模型方法较 为本色的遵循了植物生长的生理特点。该模型包含了植株架构的一些基本的生理知识： 比如树是如何生长的，如何向空中延伸，叶、花朵和果实如何分布等。第二个特点是该 模型能够可视化植物生长的各个阶段( 可以得到不同生长阶段的不同图片，可以准确模 拟植物的死亡和分支现象) 。另外，该模型它很容易将环境的一些参数集成于自身中， 4 东北师范大学硕士学位论文 比如风、养分、病虫害、化肥农药、温度、同光照射等，是一种非常有效的工具来研究 农学和生物学研究，模拟出的植物更为“真实“、客观、形象，是迄今为止最早能够真 正符合植物生长规律的模型。 1 2 2 国内研究现状 中国科学与技术大学的赵星博士在其博士论文研究期间，深入分析了当今世界上现 有的各种植物建模的方法，但仅l 系统和“参考轴技术 适合模拟植物生长过程，可 是这两种模型都不是特别便利的被别人使用，实施起来很困难。为了协调真实性与可行 性之间的平衡，他提出了一个既忠实于植物学，又简明易用、面向过程的植物形态发展 模型。其研究的成果包括：提出了“双尺度自动机模型”；概率模型；研究了虚 拟农作物生长的方法和过程；基于双尺度自动机模型的植物枝条弯曲算法。 中国农业大学信息与电气工程学院的杨娟等利用n u r b s 和o p e n g l 对棉花主要器 官进行建模，得到了逼真的效果，省去了大量精确数据的测量，提高了虚拟棉花方法的 时间复杂度和逼真程度。 国家农业信息化工程技术研究中心的雷蕾利用双尺度自动机对黄瓜进行了建模，提 出了黄瓜各个植物器官的几何构造算法，进行黄瓜果实、花的动态生长过程的模拟。 1 3 本文章节安排 本文在第一章引言里先提出了所研究的问题、分析了虚拟植物生长的可视化技术研 究的意义和应用价值，然后重点介绍了国内外的研究现状。 第二章罩详细介绍了基于l 系统和子结构的植物建模方法，首先介绍了植物的基 本结构；然后重点分析了现阶段的各种l 系统；接着对子结构作了详细的介绍，最后 介绍了b e z i e r 曲线、b 6 z i e r 曲面的基本理论。 第三章重点了论述了采用参数l 系统、b 6 z i e r 曲线、b 6 z i e r 曲面和参数方程对 柑橘器官的建模方法，分别介绍了柑橘的叶片( 轮廓和叶脉) 、花朵( 花瓣和萼片) 和 果实的建模方法。 第四章提出了采用子结构和l 系统相结合的方式建立柑橘树生长模型的方法。首 先介绍了柑橘树的生理形态；其次对子结构和l 系统进行了性能分析；接着介绍了子结 构和l 系统相结合的知识点；再次将二者共同运用到柑橘树的生长过程中；最后介绍了 虚拟柑橘生长约束方法设定。 第五章是虚拟柑橘生长模型有效性验证及编码实现，给出了模拟柑橘生长过程的实 验结果，并对实验结果进行了分析。 最后，对本论文的研究进行了总结，并对以后的工作进行了展望 5 东北师范大学硕士学位论文 第二章植物学基本概念及重要建模方法 在本章中，作者着重介绍了虚拟植物建模所需的基础知识，首先介绍了柑橘的基本 结构和生理特点，然后又分别介绍了虚拟柑橘生长建模的基础理论：l 系统和子结构的 基本概念，b 6 z i e r 曲线和b 6 z i e r 曲面的基本理论，为后面的柑橘生长建模打下基础。 2 1 植物基本结构 2 1 1 植物的轴结构 植物分枝结构是由轴构成的，植物的茎称为主轴；分枝用不同级的轴命名，例如在 主干上生长出的枝条被称为l 级侧轴，1 级侧轴上的分枝称为2 级侧轴，依次类推。 轴上生叶的部位称为节，节与节之间的那段轴称为节间。轴顶端的芽称为顶芽，叶腋处 的芽称为腋芽，侧枝由腋芽发育形成。节和节间，以及节上的侧生器官的集合植物学上 称为植物分生单位，本文称为叶元。一个叶元生长成熟的整个过程叫做为节周期，如图 2 1 所示川。 叶 腋芽 节 图2 1 轴的形态特征 侧枝的顶芽 间 2 1 2 植物的叶序模式与分枝模式 植物之所以呈现出千姿百态，是与其内部某种形态机制相对应的，也体现了植物组 织的基本规律。利用植物的分枝模式与叶序模式可以将这种生理规律体现出来。分枝模 式描述了植物顶端的发展趋势，是植物茎的形成方式。分枝模式种类繁多，这主要是与 顶芽、腋芽的生长势强弱、生长时间及寿命有关，而这些特性又取决于植物的遗传性， 有时还受阳光、温度、湿度等外界条件影响。植物的分枝主要有以下两种类型： 1 、单轴分枝。顶芽的不断生长，最后长成主干。与此同时，侧芽法杖成为侧枝， 6 东北师范大学硕士学位论文 侧枝又以同样的方式形成次级侧枝。这种分枝方式主轴明确，称为单轴分枝。单轴分枝 上的主干不断生长，长生各级分枝，而且主干的伸长和加粗比侧枝强得多。因此这种分 枝方式，主干显著。 2 、合轴分枝。顶芽发育经历了一段快速生长期后继而死亡或生长缓慢，而位于顶 芽下面的侧芽就取而代之，侧芽继续发育，形成强壮的侧枝，生长在原来的主干上。类 似的情况继续下去：这种侧枝上的顶芽停止发育，又由它下面的侧芽来代替，这样就形 成了弯曲的主轴。这类植物有个共同的特性就是整个地上部分呈开张状。 2 2l 系统基本原理 1 9 6 8 年，美国著名学者a r i s t i dl i n d e n m a y e r 首次提出了l i n d e n m a y e r 系统，这 便是著名的l 系统的雏身。它的主要作用是用形式语言的方法来描述植物形态的生长 过程。1 9 8 4 年s m i t h 等人首次将l 系统运用于计算机图形学当中，取得了十分好的 效果，至此带领着计算机虚仿真学进入了又一个新的阶段，为计算机模拟植物的真实感 图形提供了有力的工具。 2 2 1 简单l 系统 l 系统的本质是一个重写系统，通过对植物对象生长过程的经验式概括和抽象，初 始状态与描述规则，进行有限次迭代，生成字符发展序列以表现植物的拓扑结构，并对 产生的字符串进行几何解释，就能生成非常复杂的分形图形。 下面我们举一个例子来对l 系统的定义加以解释。由字母x 和y 组成一个字符串， 我们把它称为单词。x 、y 允许在同一单词中出现多次，每个字母又分别与一个改写规 则相关。改写过程从一个单词开始，我们把这个单词称为公理，例如这个单词仅包括 一个字母x ，那么第一步由规则y x 可知公理y 被x 替换；第二步，由生成规则x x y ，x 被x y 替换。单词x y 由两个字母组成，在下一步两个均被同时替换，得到新 的单词x y x ；然后，由x y x 生成x y x x y ，接着x y x x y 再x y x x y x y x ，然后是 x y x x y x y x x y x x y ，上述过程一直进行下去，到最后得到一个由字母x 和y 组成的字符串 序列。 下面给出l 系统的一个定义：令v 表示字母集，v 木表示v 上所有单词( 由符号 或字符组成的字符串) 的集合，一个字符串0 l 系统是一个有序的三元组g = ， 这里是一个非空单词，称作公理( 也称为起始元) ，p 是产生规则的有限集合，产 生规则写作a x ，字母a 和单词x 分别称作产生式的前驱和后继。规定对任何字母a v ，至少存在一个非空x ，使得a x 。若对给定的前驱a e v 无明确的产生式，则规 定a a 这个特殊的产生式属于p 。对每个a e v ，当且仅当恰有一个非空单词x ，使 得a x ，那么就说0 l 系统是确定的，记作d o l 系统 1 。 依据上述定义给出的迭代过程是先从公理开始，把中的字符作为第o 次 迭代的结果字符；调用p 中的相应规则，改写第i 次迭代的结果字符，得到第i + 1 次 7 东北师范大学硕士学位论文 迭代的结果字符( i = o ，l ，2 ，3 ，) ；迭代过程可以在有限次内进行。根据l 系统的 定义，我们可以写出上述字符串的生成过程： 公理( 1 ) ：b 产生规则p l ：b a p2 ：a a b 然后根据产生规则去替换初始字符串中的每一个字符，就得到最后要得到的字符串 1 】 2 2 2 随机l 系统 为了避免利用确定的d o l 系统生成的植物图像显得死板的情况，又有学者提出引 入了随机l 系统。随机性可用在字符解释上( 例如f 中步长d 可以是随机的) ，也可 用在产生式上。前者保持基本拓扑结构不变，后者则表示基本拓扑结构发生变化，几何 性质也发生变化，利用随机l 系统模拟出的虚拟植物更为生动、逼真，更接近真实的植 物。一个随机l 系统是一个有序的四元组： g n = 其中字符集v ，公理w 和产生式集p 与d o l 系统相同，函数7 c ：p 一 0 ，1 用来确 定每个产尘式p 被应用的概率。设a 为v 中任意字符，以a 为前驱的产生式可以有 多个，但这些产生式的概率之和应该为l ，随机o l 系统的产生式记作： p r e d 一( p r o b ) s u c c 其中p r e d ，和s u c c 分别称为前驱和后继，p r o b 为本产生式被应用的概率。这样， 在随机o l 系统中，对于同样的产生式模块，经过相同的迭代次数可以生成不同的植物 结构 1 。 下面是一个随机0 l 系统实例： ( ) ：a b b a p 1 ：a 一( 0 3 ) a p 2 ：a 一( o 7 ) b p 3 ：b b b a 产生式p 1 ，p 2 表示的意思是可以用a 或b 代替a ，迭代的概率不同，相产生的 产生式也是不同的。根据被应用的概率随机决定是应用产生式p 1 或是p 2 。在产生式 p 3 中没有明确指定应用概率，系统默认为1 。 例如在a a b a - - - a b b a b 中，p l 被应用到第一个字符a 的改写，p 2 被应用到第二个 字符a 的改写。 2 2 3 参数l 系统 参数l 系统的概念及规则 参数l 系统把最基本的平行重写概念，从仅有字符组成的单词，扩展到带参数的 单词。最初只是把这种基于l 系统的扩展用到了仿真程序中，而没有上升到理论的高 8 东北师范大学硕士学位论文 度进行研究，称为c e l l a ( c e l l u l a rl i n e a ri t e r a t i v e a r r a ys i m u l a t o r ) 。最早利用参 数进行建模的学者有b a k e r 、h e r m a n 和l i n d e n m a y e r 。后来，又有相继的许多学者定 义了l 系统的带参数字符的操作，对其进行了补充。 这罩我们用“模块”表示带参数的字符。规定：字符属于字符集v ，参数属于实数 集r 。由字符a v 和参数a 1 ，a 2 ，a n r 组成的模块记作a ( a 1 ，a 2 ，a n ) 。每 一个模块都存在一个集合m = vxr 木中，其中r 木表示所有有限参数序列的集合，所有 模块字符串集合和非空字符串分别记为m ，l c = ( y r 木) 木和m + = ( vxr 水) + e 1 。出现在 单词中的实参和相应的l 系统规则中的形参相对应。如果是形参集合，则c ( ) 意 思是由集合中的参数组成的逻辑表达式，( ) 的意思是由这些参数组成的数学表达 式。这两种类型的表达式中可以同时包括形参和常量，表达式中频繁出现的操作符有数 学运算符+ 、一、，幂运算、关系操作符 = ，一，逻辑运算符! ( 非) ，( 与) ，i i ( 或) ，和小括号( ) 等。表达式中也可以包含标准的数学函数，如自然对数、正弦，返回 随机数的函数等。操作符号和规则与c 语言的语法结构相同。为了更方便使用者运用， 在合适的时候也用希腊字母和下标。关系和逻辑表达式等于0 表示结果为假，等于1 表示结果为真。参数0 l 系统是一个四元组 g = ( v ，( i ) ，p ) 其中： v 表示系统字母表： 为形式参数集合： d ( vx ：l c ) + 是非空的带参数的单词，叫做公理： p ( v x 木) x c ( ) ( v xe ( ) 木) 水为产生式的有限集。 参数o l 系统产生式的写法是首先写前驱，然后是冒号和条件，之后是一和后继， 即： p r e d ：c o n d - 一s u c c 例如，前驱为a ( t ) ，条件为t 5 ，后继是b ( t + 1 ) c d ( t “0 5 ，t - 2 ) 的产生式记做： a ( t ) ：( t 5 ) - - * b ( t + 1 ) c d ( t 5 ，t 一2 ) 0 l 系统中的“0 的具体含义是不考虑前驱字符的上下文语义。如果满足以下所有 条件，就说一个产生式和一个带参数的模块相匹配： 模块中的字符和产生式的自i 驱字符相同： 模块中的实参个数和产生式中的形参个数相等： 用实参代替产生式中的形参，条件表达式为真 1 。 当某个产生式和某个模块匹配时，则就用该产生式的后继代替这个模块中的字符 串，并用实参代替相应位置的形参。如果某个模块没有和某个模块相匹配，则在字符串 重写的过程中就用它自身来替换。在这种情况下，当且仅当对每一个模块a ( t 1 ，t 2 ， t n ) v r 木，只对应一个应用产生式，则这种参数o l 系统称为参数d o l 系统，即确 定的参数0 l 系统。 2 2 4 语义相关l 系统 9 东北师范大学硕士学位论文 从上下文关系上，将l 系统分为o l 系统、l l 系统、2 l 系统三类。o l 系统表示 的是一种上下文无关语法，写规则前辈出现的上下文关系。在有些情况下必须考虑上下 文关系，这对模拟植物的各个部分之间的相互影响是非常重要的，如植物的营养、水分 的传递等。1 l 系统仅考虑了一边的语法关系，即左语义相关文法或右语义相关文法， 左语义相关文法可以模拟从植物的根向植物的茎、叶的传播过程：而右语义相关文法则 可以模拟从叶到茎、根的传播过程。2 l 系统既考虑左语义又考虑右语义，是一种对上 下文要求最严格的方法 1 。在非随机的情况下，语义相关l 系统的产生式形式如下： l c r c ：c o n d - - * s u c c “ 把前驱分成三个部分：不带括号的左语义1 c ，直接前驱p r e d 和一个 自嵌套的右语义r c ，c o n d 、s u c c 分别为条件和后继n 1 。 2 3 子结构基本原理 l 系统应用已经很广泛，得到了大多研究者的认可，但一般l 系统算法效率低，建 模速度慢针对这些缺点，目前引入了递归算法来改进l 系统，并对相同结构的重复解 释问题，引入子结构算法这一解决办法，该算法较之一般的l 系统算法从空间复杂度及 时间复杂度上都有了一定的改进。作者认为子结构算法不仅可以用于相同结构的计算， 也可以用于相似结构。 2 3 1 基本概念 子结构算法主要思想是以子结构为单位来生成植物结构，即提前计算重复出现的子 结构，这些子结构在其他结构中重复出现时，则直接调用，而不再逐个重复模拟。由于重 复的子结构只被计算一次，因此对于复杂植物可以有效地减少模拟时间。 子结构是个相对的概念，又是个递归的概念，如植物主干上的侧枝是植物的子结 构，当植物处在群落中时，则植物本身就成为群落的子结构。以子结构为单位进行植物 形态构造的算法称为子结构算法乜3 。子结构算法是首先模拟出一个( 对于确定性生长) 或 若干个( 对于随机生长) 具有相同属性的子结构，而当在其他子结构中出现这些子结构的 时候，则直接复制已有的信息，不再重复计算乜1 。这样则大大简化了计算的步骤，从而 改进了系统算法的时间复杂度与空间复杂度。子结构也可以应用比例缩放、旋转、颜色 渐近等方法构造出更多的相似结构而避免了大量的重复运算。 虽然l 系统现在已经得到广泛的应用，但随着叠代次数的增多，一般l 系统算法的 效率较低，建模速度慢。由于在叠代过程中第i + 1 次一定会用到第i 次的计算结果，如 果把第i 次计算结果保存下来，再进行第i + 1 次计算时直接调用保存好的第i 次计算结 果，这样便大大减少了重复计算的时间，子结构的思想正是如此。 子结构算法是适用于l 系统的，因为l 系统模拟出的植物具有明显的分形性质，生 长年龄大的植物结构中会出现年龄结构小的结构子结构算法首先模拟出一个( 对于确 定性生长) 或若干个( 对于随机生长) 具有相同属性的子结构，而当在其他子结构中出现这 l o 东北师范大学硕士学位论文 些子结构的时候，则直接复制已有的信息，不再重复计算心1 。此外，由于模拟中可以只 保留重复信息的索引，而仅根据需求来获取详细信息，因此还可以达到降低存储量的目 的。 2 3 2 构造过程 在l 系统中实现子结构的构造步骤如下： 1 、生长轴每个节间的位置、方向的确定植物生长模型确定生长点轴每个节间的 方向、位置等，通过生长模型可以计算出每个给定生长年龄和生理年龄的节间长度。生 长轴的弯曲程度确定每个节点的位置和方向，生长轴根据重力影响计算，其相关的参数 有轴的弹性模量、离竖直方向的初始方向角等。 2 、子结构的生成和派生利用l 系统和b 4 z i e r 曲面，对植物器官进行建模，模拟出 具有代表性的子结构模型。 形状相似、位置方向不同的子结构由于有相当一部份的植物具有大量相似子结 构，例如，一棵松树其叶子形状很相像，只是有些叶子位置、方向有些不同，这是则可 以利用旋转、变换等方法即可生成相似子结构。公式：x = x c o s 步一y s i n 步，y = s i n k 爹+ y c o s 爹，其中，旋转坐标是以坐标原点( o ，o ) 为旋转中心，这时平面上一点( x ，y ) 旋转了爹角度后变成点( x ，y ) 。 大小不同的子结构对于大小不同的子结构则可利用比例缩放的知识并结合旋转 知识对现有子结构进行变化。例如，一棵松树其越靠近上端叶子越小，而越靠近下端其 叶子形状较大。这样就可以将子结构模型进行比例缩放衍生出大量类似子结构。 公式：x = x s x ，y = y s y 其中，如果s x = s y = l ，则为恒等比例变换；如果s x = s y l ，则子结构被放大了：如果s x = s y 1 ，则子结构被缩小了。 颜色不同的子结构我们都知道一个一个常识性的知识，即越靠近轴的顶部，出 现得越晚，生长年龄越小，而子结构颜色越明亮；越靠近轴的底部，出现的越早，生长 年龄越大，子结构颜色越深暗。根据这个特点可以利用明暗处理方法进行调解调节生成 的子结构的颜色即可区分顶端子结构、中端子结构和底端子结构。 当然以上三种情况并一定非要单独进行的，在很多时候这三种情况往往是交叉进行 的。例如，植物顶端的叶子往往即需要颜色调解、位置旋转，还同时需要比例变换。 3 、轴上的子结构的粘贴每个子结构包括结构的位置、空间方向、以及在轴上的 粘贴位置，这些因素可根据实际具体情况而确定。叶序角度、侧枝角度以及轴本身的方 向影响子结构的空间方向，其中，a 表示侧枝角度，即子结构与生长轴的夹角，表示生 长轴本身与z 轴的夹角，y 表示叶序角度，即围绕生长轴上下两片相邻叶子间的角度， 这里为1 8 0 。，而子结构在所属结构中的方向就是由这些角度联合决定的。 己生成的所有子结构均按统一的初始方向存放，当被调用到其他子结构中时，将经 过由上述角度决定的旋转变换，旋转矩阵可由下式计算： 东北师范大学硕士学位论文 v = v b v c 、，a = 然后根据旋转矩阵和子结构在轴上的位置就可以对已有子结 转平移操作。注意这罩没有对子结构进行拉伸变形。子结构构造过程如图2 2 所示： 图2 2 子结构构造示意图 2 3 3 存储与检索 在模拟植物生长过程中，如果我们在调用子结构时，直接将子结构数组中的数据进 行旋转变换，然后再添加到当前结构中去，则会消耗大量的内存和c p u 时间。为了在解决 这个问题，我们可以只保存所用到的子结构特征。所以我们可以将子结构的特征写入一 个文件中，这个文件称为“