（计算机应用技术专业论文）基于l系统的虚拟植物生长算法研究及软件实现.pdf

浙江大学硕士学位论文摘要 摘要 虚拟植物生长研究如何利用计算机模拟植物的生长发育过程，随着计算机软 硬件技术的飞速发展，它已成为计算机领域的一个研究热点，且在农业、教育、 园艺、商业和娱乐等领域得到广泛的应用。 l 系统是虚拟植物生长和分形图形研究中非常经典的模型和方法。本文着重 研究了l 系统的基本算法，实现了一个可扩展性的、上下文相关的、带参数的 随机l 系统p a r a l s y s 。并通过对比p a r a l s y s 和开源软件l p a r s e r 的模拟能力， 验证了p a r a l s y s 的实用性。 本文第1 章介绍了项目的研究背景和相关领域的国内外研究现状。 根据l 系统的建模方式，将其分为确定性l 系统、随机l 系统、上下文相关 l 系统和参数l 系统。本文第2 章分别对这几类l 系统进行详细的介绍。 第3 章介绍了p a r a l s y s 的设计和实现。它基于q t 和o p e n g l ，集成了一套 自定义的l 系统描述语言，由五个功能模块组成：文本编辑模块、器官模型处 理模块、字母含义设置模块、状态演化模块和图形显示模块。算法层面，本文提 出了一种基于二叉树的l 系统并行重写算法。实验表明，和采用线性数组实现 的l 系统相比，新系统在生长模拟环节时空效率更高。 第4 章对比了p a r a l s y s 和l p a r s e r 。研究了l p a r s e r 系统和p a r a l s y s 系统的 数据互通机制，算法实现的关键在于将l p a r s e r 中的龟行指令、几何参数变化指 令等翻译成p a m l s y s 的描述语言。实例表明，p a m l s y s 能模拟l p a r s e r 的绝大部 分功能，鉴于l p a r s e r 系统在很多领域已获得重要的应用，我们期望p a r a l s y s 系统也能应用到相同的领域。 第5 章总结全文，并就未来工作给出展望。 关键词：l 系统，虚拟植物，二叉树，龟形图，并行重写，l p a r s e r 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t v i r t u a l p l a n tg r o w t hs t u d i e sh o wt o s i m u l a t et h ep r o c e s so fp l a n td e v e l o p m e n ti n c o m p u t e r s w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , i th a sb e c o m eah o tr e s e a r c h a r e ai nc o m p u t e rs c i e n c e ，a n db e e na p p l i e di n t om a n yp r a c t i c a lf i e l d s ，s u c ha sa g r i c u l t u r e ， e d u c a t i o n ，g a r d e n i n g ，b u s i n e s sa n de n t e r t a i n m e n ta tp r e s e n t l s y s t e mi sac o m m o n l yu s e dm a t h e m a t i c a lm e t h o d o l o g yt og e n e r a t ef r a c t a l sa n d r e a l i s t i c m o d e lp l a n t s i nt h i sd i s s e r t a t i o nw es t u d ys o m eb a s i ca l g o r i t h m so fl s y s t e m , a n dd e v e l o pa l l e x t e n d i b l e ，c o n t e x t - s e n s i t i v e ，b r a c k e t e d ，a n ds t o c h a s t i cl s y s t e m ，c a l l e dp a r a l s y s b e s i d e s ，i n o r d e rt od e m o n s t r a t et h ea v a i l a b i l i t yo fp a r a l s y s ，t h ed a t ae x c h a n g es c h e m eb e t w e e nac l a s s i c o p e ns o u c el s y s t e mi m p l e m e n t a t i o n ，l p a r s e r , a n dp a r a l s y si ss t u d i e d i n c h a p t e r1 ，t h er e s e a r c hb a c k g r o u n d i si n t r o d u c e d ，a n dr e l a t i v er e s e a r c hw o r ki s r e v i e w e d a c c o r d i n gt ot h em o d e l i n gw a y s ，l - s y s t e mi sc l a s s i f i e di n t os e v e r a lc a t e g o r i e s ，s u c ha s d o l s y s t e m ( d e t e r m i n i s t i ca n dc o n t e x t f r e el - s y s t e m ) ，s t o c h a s t i cl - s y s t e m ，c o n t e x t - s e n s i t i v e l s y s t e ma n dp a r a m e t r i cl s y s t e m i nc h a p t e r2 ，t h e s el s y s t e m s w i l lb ed i s c u s s e d r e s p e c t i v e l yi nd e t m l i nc h a p t e r3 ，t h ed e s i g na n di m p l e m e n t a t i o ni s s u e so fp a r a l s y sa r ei l l u s t r a t e d i ti sb u i l t o nt h eo p e n g lg r a p h i c a ll i b a r a r ya n dt h eq tu il i b r a r y , a n di n t e g r a t e d 、析t l las e l f - d e f i n e d d e s c r i p t i v el a n g u a g e f i v em o d u l e sa r ec o n t a i n e di np a r a l s y s ，t h e i rf u n c t i o n a l i t i e sa r et oe d i t t h ed e s c r i p t i o nt e x t s ，t os e t u pm e s h ，t os e t u pa l p h a b e t ，t oe v o l v et h es y s t e m ，a n dt ov i e wt h e r e s u l t s ，r e s p e c t i v e l y i no r d e rt oi m p r o v et h es i m u l a t i o ne f f i c i e n c y , t h ea l g o r i t h m sa r eb u i l to n b i n a r yt r e e sr a t h e rt h a nt r a d i t i o n a ls e q u e n ta r r a y s e x p e r i m e n ts h o w st h a tb e t t e rt i m i n ga n d s p a c i n gp e r f o r m a n c ei sa c h i e v e dw i t l lt h en e w d a t as t r u c t u r e i nc h a p t e r4 ，p e r f o r m a n c eo fl p a r s e ra n dp a r a l s y si sc o m p a r e d i m p l e m e n t a t i o no fd a t a e x c h a n g es c h e m eb e t w e e nb o t hs y s t e m si sd i s c u s s e d ，w h e r et h ef o c u si s h o wt ot r a n s l a t e c o m m a n d si nl p a r s e r , s u c ha st h em a l eo r i e n t a t i o n ，t u r t l em o v i n g ，i n c d e c ，i n t ot h ed e s c r i p t i v e l a n g u a g ei np a r a l s y s t w oe x a m p l e sa r ep r e s e n t e dt op r o v et h a tm a j o rf u n c t i o n a l i t i e so f l p a r s e rc o u l db ei m i t a t e db yp a r a l s y s s i n c el p a r s e rh a sb e e ns u c c e s s f u l l ya p p l i e di n t om a n y i m p o r t a n ta r e a s ，i ti se x p e c t e dt h a tp a r a l s y sc o u l da l s ob eu s e dt or e s o l v e t h es a n l ep r o b l e m s f i n a l l y , i nc h a p t e r5 ，t h ed i s s e r t a t i o ni ss u m m a r i z e da n ds o m ep r o p o s a l sf o rf u t u r ew o r k a r eg i v e n k e y w o r d s ：l s y s t e m s ，v i r t u a lp l a n t ，b i n a r yt r e e ，t u r t l ei n t e r p r e t a t i o n ，p a r a l l e lr e w r i t i n g ， l p a r s e r i i 浙江大学硕士学位论文表目录 表目录 表3 1 字母含义设置模块输入媒介一2 5 表3 2 图形显示模块输入媒介3 0 表3 3 不同数据结构包含节点数比较例子1 4 4 表3 4 不同数据结构包含节点数比较例子2 4 4 表3 5 生长时间以及规模比较实例1 4 4 表3 6 生长时间以及规模比较实例2 4 4 表3 7 生长时间以及规模比较实例3 4 4 浙江大学硕士学位论文图目录 图目录 图1 1 利用参数化l 系统模拟植物生长过程。3 图1 2x f r o g 生成的一些植物图形6 图2 1 龟行图对f + ，指令的反馈一9 图2 2 龟行图对于字符序列f f f f f f f + f + f f f f f f 的几何解释9 图2 3 龟行图在三维空间对指令的反馈1 1 图2 4 带中括号的龟行图1 1 图2 5 一个d o l 系统的重写过程示例图1 2 图2 6 一个含中括号的d o l 系统示例1 2 图2 7 同一个随机0 l 系统5 次产生的植物图形一1 3 图2 8 一个模拟树形l 系统。1 4 图2 91 l 系统中信息从下往上传递效果1 5 图2 1 0ll 系统中信息从下往上传递效果。15 图2 1 1h o g e w e g 和h e s p e r 构造的2 l 植物图形1 6 图2 1 2h o g e w e g 和h e s p e r 构造的2 l 系统模型1 6 图2 1 3l 系统描述的直角三角形1 7 图3 1 软件系统总体结构2 1 图3 2 文本编辑模块处理过程一2 2 图3 3 文本编辑模块主界面。2 3 图3 4 器官模型处理模块的处理过程。2 3 图3 5 器官模型处理模块主界面2 4 图3 6 字母含义设置模块处理过程2 5 图3 7 重写规则设置模块主界面。2 6 图3 8 状态演化模块流程图2 7 图3 9 生长状态演化流程图2 8 图3 1 0 状态演化模块主界面2 9 图3 1 1 图形显示模块流程图3 0 图3 12 图形显示模块单图模型主界面31 图3 1 3 图形显示模块多图模型主界面3 2 图3 1 4 生长状态树示意图3 3 图3 1 5 新状态项节点和已形成节点之间逻辑关系图3 4 图3 1 6 字母管理类c a l p h a b e t 3 5 图3 1 7 生长规则管理类3 5 图3 1 8 生长状态管理类3 6 浙江大学硕士学位论文 图目录 图3 1 9 状态演化管理类3 6 图3 2 0 字符型l 系统管理类3 7 图3 2 1 字符绘制类3 7 图3 2 2 植物器官模型绘制管理类3 8 图3 2 3 可视化l 系统管理类3 8 图3 2 4 生长状态树的创建算法伪码4 0 图3 2 5 生长方式树的创建算法伪码4 l 图3 2 6 获取左上下文算法伪码4 1 图3 2 7 获取右上下文算法伪码4 1 图3 2 8 字符序列的获取算法伪码4 2 图3 2 9 单节点生长演化算法伪码4 3 图4 1 移动指令效果示例图4 8 图4 2 绕x 轴旋转文法。4 9 图4 3 绕x 轴旋转效果图4 9 图4 4p a r a l s y s 中随机效果文法实例5 0 图4 5p a r a l s y s 随机效果图5 0 图4 6 粗细参数变化效果图5 l 图4 7l p a r s e r 中树叶器官图例5 2 图4 8p a r a l s y s 载入的器官模型示例5 2 图4 9l p a r s e r 实例l 文法5 2 图4 1 0p a r a l s y s 实例1 文法5 3 图4 11p a r a l s y s 中载入的植物器官模型5 3 图4 1 2l p a r s e r 生成的实例l 图形5 4 图4 13p a r a l s y s 生成的实例l 图形5 4 图4 1 4l p a r s e r 实例2 文法5 5 图4 15p a r a l s y s 实例2 文法5 5 图4 16l p a r s e r 生成的实例2 图形。5 6 图4 17p a r a l s y s 生成的实例2 图形5 6 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得迸姿盘堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：澎k 私痦 签字日期： 加。万年月7 日 学位论文版权使用授权书 本学位论文作者完全了解逝江态鲎有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 林弼痛 签字日期：加d g 年6 月 日 日 浙江大学硕士学位论文第一章绪论 1 1 论文的研究背景 第一章绪论 在大自然中，植物无处不在，和人类的生存息息相关。随着当今时代的发展，科学技 术水平的提高，信息技术的日新月异，虚拟植物生长模拟的研究已经发展成为一个新的 领域，是当今计算机领域研究的一个热点。虚拟植物生长研究如何利用计算机模拟植物 的生长发育过程，其关键是虚拟植物模型的建立，这通常是在现实中的植物外观形态， 生态特性的研究基础之上获得的。植物的生长发育过程是十分复杂的，受气候、温度、 湿度、土壤、水和植物间的竞争关系等因素影响。因此虚拟植物生长的研究涉及到众多 的科学研究领域，如植物生理学、生态生理学、作物栽培学、土壤学、气象学、微生物 学和计算机科学【l j 。 虚拟植物生长根据不同应用需求，研究影响植物生长的各种因素，建立数字化模型， 进行数字化模拟，从而达到缩短时间、节约成本等目的。应用不同，对各种影响因素的 选择、侧重获简化策略也不同。从植物形态结构的角度来看，植物的地上部分与地下部 分的形态结构，分别产生不同作用影响植物的生长。地上部分，如冠层表面积对于光照 截获能力的影响，地下部分，如根系的对于土壤中水分、养料的吸收和竞争能力，这些 因素最终决定植物的生理状态。因为植物在此刻的形态结构，决定了植物对于各种资源 的获取强度和能力，例如光照截获能力影响植物进行光合作用，蒸腾作用，而光合作用 的产物的积累和分配反过来决定植物的生长速率和竞争能力，最终作用于植物下一时刻 的形态结构特征。植物的生长过程就是由这样的循环组成的，植物的形态结构对此作用 显著【2 】。 用于构造虚拟植物模型的方法有很多，大体可以分为两类：静态模型和动态模型【3 1 。 静态模型是指运用三维数字化技术测定植物的形态数据后，直接应用这些数据建立植物 的形态模型。静态模型能够精确地再现植物的外观形态，但是需要大量的测试数据，并 且不适合研究植物的动态过程。动态模型则是根据对植物生长过程中拓扑结构演变和几 何形态变化规律的研究，提取植物的生长规则而建立，能够模拟植物的动态生长发育过 程，例如l i n d e n m a y e r 于1 9 6 8 年提出的以其名字首个字母命名的l 系统1 4 j 就属动态建模 范畴。 本文的重点在基于研究l 系统理论的基础上，实现虚拟植物可视化系统。 1 2 研究的现实意义 根据不同的研究目的和应用领域，可以将虚拟植物生长模拟的研究分为两个方面：一 方面注重植物生态的真实性，另外一方面专注于植物形态的真实性。 l 浙江大学硕士学位论文 第一章绪论 注重于植物生态的真实性模拟要求植物生长过程符合植物学理论。其主要应用是农林 业研究领域，如土地生产力评测、作物产量预测、资源环境分析、作物栽培指导、作物 生长机理研究、调控作物生长发育、对环境的反应研究和最近发展起来的精确农业等方 面【纠。具体的应用前景有很多，如【6 ，7 】 1 ) 在虚拟农田种植方面应用虚拟植物生长的技术，可部分替代现实世界中耗时耗 力、成本高昂的实验，如研究种子多少、光照强度、土壤和作物搭配等因素对作 物生长的影响。从而为作物种植预先提供信息，争取收益的最大化，并避免不必 要的损失。 2 ) 通过虚拟技术获得农田中害虫群体的藏匿时间和取食规律，确定农药的喷洒时间 和范围。这不仅能达到杀害害虫的目的，同时能够保护作物，减轻乃至避免对环 境造成污染，为培育降低病虫害的作物提供依据。 3 ) 通过虚拟技术分析土壤养分和水分的时空变化，确定正确的施肥灌溉时机，从而 达到资源利用合理化和效益最大化的目的，为精准农业应用提供依据。 4 ) 通过建立虚拟农场，同其他智能化农场管理软件系统相结合，人们只需要通过操 作软件来控制农场，如漫游农场，观察作物的生长状况，并且可以通过改变作物 生长环境来查看作物的生长结果，以获得先进的农场管理技术并加以推广。 注重植物外观形态真实性的研究着重于探讨自然景观的再现，具体的应用场景也很 多，如： 1 ) 教育。用于制作数字图书馆、虚拟植物模拟生长教育软件以及和生物相关的课堂 教学软件。 2 ) 娱乐。用于制作三维动画、电脑游戏中的虚拟场景以及影视中特技场景。 3 ) 商业。用于制作广告，通过网络销售花卉等。 4 ) 计算机辅助设计。用于园林布局的规划、建筑环境的设计和城市规划等方面。 1 3 国内外研究现状 1 3 1 国外研究现状：理论和方法 早在计算机发展的初期，即二十世纪六十年代，植物学家便开始研究虚拟植物生长模 拟。1 9 6 8 年，美国生物学家l i n d e n m a y e r ( 1 9 2 5 1 9 8 9 ) 在生物杂志上发表了名为 “m a t h e m a t i c a lm o d e l sf o rc e l li n t e r a c t i o n si nd e v e l o p m e n t 的论文1 4 j ，提出了以其名字首 个字母命名的字符串重写系统( s t r i n gr e w r i t i n gs y s t e m ) _ i ，系统。所谓重写，即基于 一定规则利用其它字符串来替换特定的字符串。若赋予字符特定的几何含义，整个字符 串则表示特定植物的拓扑结构。l 系统适合描述分形模型，也适合于描述植物模型。l 系统的本质表明，在纷繁复杂的自然现象背后，有着简单的准则。 为了不断完善植物模型，l 系统不断进行扩展。最简单的l 系统是d o l 系统，只能 2 浙江大学硕士学位论文第一章绪论 描述形状规则的植物模型。“随机l 系统 克服了这个局限，能够描述随机的植物拓扑模 型。“参数化l 系统 使l 系统能够模拟时延信息【引。图1 1 给出了利用参数化l 系统模 拟植物生长发育过程的示例。 图1 1 利用参数化l 系统模拟植物生长过程 在d o l 系统的基础上，为了表现植物器官之间相关性的生理性态特征，发展了“上 下文相关( c o n t e x t s e n s i t i v e ) l 系统 ，称之为1 l 系统。l l 系统是只包含单边上下文相 关的系统，当采用左上下文相关时，可以模拟植物器官的生长顺序，如开花在结果实之 前。也可以模拟植物内部水分从下到上的传递顺序，即从根到茎到叶的顺序。若采用右 上下文相关时，表达效果相反。 。 上述l 系统都被认为是封闭的系统，不能模拟植物与植物之间，植物与周围环境的 之间的交互。为了解决这个局限，加拿大学者m e s h 和p r u s i n k i e w i c z 进一步扩展了l 系 统，提出了能与周围环境交互的“开放式l 系统( o p e nl s y s t e m ) 【9 】。该l 系统引入 “交流单元( c o m m u n i c a t i o nm o d u l e s ) ”，以实现l 系统与周围环境并发过程的模拟研究。 他们给出的实例是对植物根系的模拟，建立植物根系生长的模型，还有土壤中水分的模 型，根系吸水效应改变了土壤中水分的分布，而水分的不同分布又反过来影响植物根系 的发育，从而模拟植物根系和周围局部环境交互的过程。这类l 系统可以模拟土壤中养 分、光照、气候等环境因素对作物生长的影响，对农业的科学研究有重要的意义。此外， 为了模拟植物的连续生长过程，p r u s i n k i e w i c z 等又提出了时变( t i m e d ) l 系到1 0 】，能够 生成植物生长过程的计算机动画。为进一步模拟植物生长的连续过程，p r u s i n k i e w i c z 把 微分方程引入到l 系统，提出了微分l 系统( d i f f e r e n t i a ll s y s t e m ) 【l 。这类l 系统能 够较好地模拟植物的叶序、美丽的花朵、弯曲的枝条等，以及模拟植物在生长竞争、和 周围环境交互等情况下的生长状况。 除了不断改进和扩展l 系统以外，还有研究者探讨了基于分形理论的植物建模方法。 即根据植物的形态结构，采用具有自相似性的模型工具来描述植物生长的拓扑和形态结 构。分形方法的典型代表之一是迭代函数系统( i f s ) ，根据整体与局部具有自相似性的 特点，将整体以设定的仿射变换迭代下去，将整体变换到局部，直到得到想要的形状为 止。早期b a m s l e y 与d e m k o 就应用该方法生成了具有极强自相似性特征的蕨类植物叶片 i l 引。1 9 8 9 年b a r n s l e y 等提出了“再现迭代函数系统( r e c u r r e n ti f s ) ”方法【l 引。该方法在 浙江大学硕士学位论文第一章绪论 自相似性生成方面更加灵活多变，植物局部自相似性之间可以有更多不同。1 9 9 1 年 p r u s i n k i e w i c z 与h a m m e l 等提出了“语言约束式迭代函数系统( 1 a n g u a g e r e s t r i c t e di f s ) 方法，该方法通过加入不同变换顺序的约束条件，能够比较通用地概括各类不同的i f s 方法。除i f s 方法外，表达植物分形结构的另外一种方法是分枝矩阵模型。该模型利用 矩阵来表达植物分枝节点的个数以及彼此之间的关系，然后通过迭代的方法来生成植物 的分形结构1 1 4 1 。 1 9 8 3 年美国学者w t r e e v e s 提出了“粒子系统方法州”】，粒子系统由很多形状简单 的颗粒组成，每个粒子在一定时间内都会经历产生、移动、变化和消亡的过程，且具有 随机性。该方法不适合表示单株植物的拓扑和结构形态，绘制时会有很重的人工痕迹， 缺乏真实感，但是比较适合表示森林和草地等宏观景象。 v i e n n o t 提出了模拟植物形态结构的分枝矩阵模型( r a m i f i c a t i o nm a t r i x ) 1 6 1 。通过矩阵 来描述植物分枝节点的个数以及彼此之间的关系，加上自定义的一些几何结构参数，通 过迭代产生植物的分形结构。 为了描述障碍物对植物生长发育的影响，g r e e n e 利用体元素空间( v o x e ls p a c e ) 方法 来实现i l ，即分割立体空间为大小相同的体元素，运用它们近似描述在三维空间中的植 物体。该方法通过检测植物与障碍物之间的碰撞，可模拟蔓生植物沿着墙壁爬行生长。 h o n d a 在模拟植物的枝条结构方面做了卓有成效的工作。他应用递归分支结构模型， 通过变化分枝角度、分枝比率、母枝条与子枝条的长度等参数，生成了一些树木图形。 为了获得更加逼真的效果，它强调不同子枝条和母枝条之间的角度要有变化，且子枝条 的长度要短于母枝条的长度。 a o n o 和k u n i 在h o n d a 工作的基础上，提出了g m t l 、g m t 2 、g m t 3 和g m t 4 四 种新的几何结构模型，针对早期l 系统不能生成三维枝条结构的缺点，提出了构造植物 形态的a 系统( a s y s t e m ) 1 8 j 。a 系统按照一定规律随机变化分枝角度，能模拟单轴分枝 结构和合轴分枝结构等植物分枝结构特征，从而形象地模拟多种植物。并通过吸引子 ( a t t r a c t o r ) 算法，模拟光照、风和重力对于植物的影响【1 4 1 。 1 3 2 国外研究现状：软件与实现 近年来，研究人员开发了很多虚拟植物模拟软件。根据应用目的不同，这些软件大致 可以分为两类：以农林业应用为背景的软件和不以农林业应用为背景的软件。下面分别 举例加以说明。 开发以农林业应用为背景的应用软件需要先对植物做长期、大量的研究测试工作，利 用实验数据拟合出植物的各个参数的变化规律，建立植物的生长发育模型，并结合植物 的其他生态模型，定量模拟植物生长发育过程。1 9 7 0 年，s t a p l e t o n 等人在美国亚利桑那 州发表了一个植物棉花模型。d u n c a n 等人在此基础上开展了更为详尽的研究，于1 9 7 2 年，建立了s i m c o t 模型。该模型以气象资料和土壤数据作为输入，模拟单株棉花的生 长过程。1 9 7 8 年，b a k e r 和l a m b e r t 基于s i m c o t 模型建立了动力学棉花系统模型，该 4 浙江大学硕士学位论文第一章绪论 模型考虑了温度、水分和氮素等因素对于棉花生长发育的影响。另外一方面提供了棉花 根系土壤系统模拟模型，于1 9 8 3 年建立了迄今为止最为完善的机理模型g o s s y m t l 9 1 ， 该模型通过系统分析碳、氮等元素和水分的供求平衡，并且将该模型与专家系统c o m a x 相结合【2 0 - ，增加了棉花管理操作方面的内容，包括种子播期、种植密度和施肥灌溉等。 c o r o n p l u s 是在g o s s y m c o m a x 基础上发展起来的棉花种植管理系统。它可实时计算 并显示单株棉花的生长发育、形态变化和产量数据，以及土壤中水分、氮、氨等元素的 变化。以上这些模型在国内外的实际应用中，都取得了不错的经济效益l z 。 澳大利亚c p a i 研究中心开发了一款基于l 系统的软件v i r t u a lp l a n t s ，该软件包含新 的植物器官产生规则以及已有器官的大小及形状变化规则。主要用于模拟棉花、大豆等 作物的生长发育过程和害虫对于作物的影响，研究了棉花与害虫之间的交互作用。该软 件目前还只能用于定性研究模拟，距实际应用于农林业生产还有一定距离。 早期的作物生长模拟软件局限于某种作物对象，从2 0 世纪9 0 年代开始，人们开始研 究具有通用性的植物生长模拟软件。这些软件中比较著名的有：a p s m 2 2 1 、g e p s i l 2 3 】， g p s f l 2 4 | 、s p a s s 2 1 】和o ws i m u 2 5 】等。 19 7 8 年，植物学家h a l l e l 2 6 】等定义了2 3 种植物结构模型来模拟植物遗传规则。基于 这些模型，d er e f f y e 提出了忠于植物学知识的自动机原理【2 。基于上述理论成果，法国 c i r a d 开发了a m a p 系列软件。该软件在植物生长机理可视化模型方面取得显著进展1 2 8 ， 2 9 1 ，适合模拟高大的植物。它利用参考轴技术描述植物的拓扑结构，用体元素空间方法 表示植物枝条、生长过程中枝条间相互碰撞的效果、障碍物和光照等对于植物生长的影 响。a m a p 包括若干个实现不同功能的子系统软件、一个庞大的植物数据库、一个植物 生长引擎和可以应用g i s ( 地理信息系统) 数据的三维地形编辑系统。应用该软件可以 制作各种植物模型，并且可以调节树干、树叶、四季色相变化等各种参数。并可以制作 地形，以生成完整的自然景观动画。 开发以模拟植物外观形态为主要应用目的的软件不需要对于生长机理的大量测试数 据，也不需要严格符合植物学知识，其目的是简单快速地生成逼真的植物图形，并可用 于自然景观的再现。著名的x 舶g 植物模拟软件就可归为此类，它是由德国k a r l s r u h e 大 学的l i n t e r m a n n 等人开发研制的【30 。其产生的一些植物图形如图1 2 所示。该软件运用 了基于功能图符的交互式植物构造模型，该模型以整个枝条为单位构造植物。该软件定 义了一些表示植物器官、植物结构、全局变量和功能函数的小图符，每个图符具有描述 其具体属性的参数表。用户只需要通过与软件简单的人机交互就可以得到相当逼真的植 物图形。其最大的优点就是人机交互方便，还可以模拟光照和重力等因素对于植物枝条 的影响。 浙江大学硕士学位论文 第一章绪论 图1 2x f r o g 生成的一些植物图形 德国k u r t z f e r n h o u t 公司开发的p l a n ts t u d i o 软件，应用一些图符表示植物的分枝结 构、分生组织、节间、花序、花朵、叶片和果实等属性，用户不需要很多的植物学知识 就能通过人机交互输入植物参数，制作出视觉上逼真的植物图形。而且其生成的文件格 式多种多样，如3 d s 、d f x 、w r l 、p o v 和l w o 等，可以通过现有的图形工具软件对 其生成的植物图形进行修改和润色，增加其视觉上的真实性。 加拿大c a l g a r y 大学开发了基于l 系统的植物模拟软件c p f g ，用户首先根据其预先 定义好的解释符号，编写所要模拟的植物的l 系统生长规则，然后根据这些生长规则进 行生长模拟，生成所要的植物图形。该软件的优点是功能强，理论上能够生成各种植物 图形，但是由于使用复杂，理解困难，交互性差，不易快速生成用户所需要的植物图形。 该大学还开发其他软件如l s t u d i o ，v i r t u a ll a b o r a t o r y 等。这些软件已经成功用于再现灭 绝的树种、辅助景观设计和教学等领域。 美国的o n x y 公司利用其开发的t r e ec l a s s i c 和t r e ep r o f e s s i o n a l 软件生成了具有二百 多种常见植物的三维植物图形库。a m a p 软件也模拟了4 0 0 多种植物，这些植物图形库 已经在m a y a 和s o f l i m a g e 等三维动画商用软件中得到应用。 1 3 3 国内研究现状 同国外在虚拟植物生长模拟方面的研究相比，我国的研究起步比较晚。我国的作物模 拟研究起源于上世纪八十年代，主要集中在水稻、小麦、棉花和玉米等大田农作物，目 前比较著名的模型有：高亮之和金之庆建立的水稻计算机模拟模型( r i c e m o n ) 3 l 】；殷新 佑等建立的水稻生长日历模拟模型( 砌c a m ) 【3 2 】；冯利平等建立的小麦发育期动态模拟模 型 3 3 , 3 4 l ；潘学标等研制成功的棉花生长发育模拟模型c o t g r o w 等【3 5 】。 中科院自动化所与法国c i r a d 公司的a m a p 实验室合作建立的中法实验室从1 9 9 7 年开始进行了虚拟植物生长的合作研究。其研究主要是基于a m a p 公司的虚拟植物生长 方法，系统采用了参考轴技术和双尺度自动机模型1 3 6 3 8 1 。该实验室从19 9 8 年开始还开发 6 浙江大学硕士学位论文第一章绪论 了基于功能反馈机制的植物模型软件g r e e n l a b ，该软件以植物器官为空间尺度，生长周 期为时间尺度，采用双尺度自动机模型产生植物拓扑结构。 赵星等从植物学的角度出发提出了微状态和宏状态的双尺度概念，建立了虚拟植物生 长的双尺度自动机模型，该模型考虑了植物的生长机理，参数物理意义明确，结构简洁 条理，形象直观，易于理解和编程实现，并且应用了符合植物顶芽和腋芽发育过程的概 率模型，更适合模拟真实植物的生长过程【3 引。另外，自动机模型不容易描述与生长周期 有关的一些植物生长特点，而双尺度自动机模型则避免了这一点。 1 4 本文结构组织 本文研究的内容主要是在详细研究相关植物学知识和l 系统的基础上，实现了基于 带参数的上下文相关随机l 系统，为探讨所有基于l 系统的虚拟植物生长软件产生的虚 拟植物都移植到本文实现的系统中，选择了一个经典的软件l p a r s e r ，研究了如何将其描 述的l 系统产生的植物图形翻译至本文实现的系统中。论文共分五章，各章内容安排如 下： 本文第1 章介绍了项目的研究背景和相关领域的国内外研究现状。 根据l 系统的建模方式，将其分为确定性l 系统、随机l 系统、上下文相关l 系统 和参数l 系统。本文第2 章分别对这几类l 系统进行详细的介绍。 第3 章介绍了p a r a l s y s 的设计和实现。它基于q t 和o p e n g l ，集成了一套自定义的 l 系统描述语言，由五个功能模块组成：文本编辑模块、器官模型处理模块、字母含义 设置模块、状态演化模块和图形显示模块。算法层面，本文提出了一种基于二叉树的l 系统并行重写算法。实验表明，和采用线性数组实现的l 一系统相比，新系统在生长模拟 环节时空效率更高。 第4 章对比了p a r a l s y s 和l p a r s e r 。研究了l p a r s e r 系统和p a r a l s y s 系统的数据互通 机制，算法实现的关键在于将l p a r s e r 中的龟行指令、几何参数变化指令等翻译成 p a r a l s y s 的描述语言。算例表明，p a r a l s y s 能模拟l p a r s e r 的绝大部分功能，鉴于l p a r s e r 系统在很多领域己获得重要的应用，我们期望p a r a l s y s 系统也能应用到相同的领域。 第5 章总结全文，并就未来工作给出展望。 7 浙江大学硕士学位论文第二章l 系统理论概述 第二章l 系统理论概述 2 1l 系统的基本理论 2 1 1l 系统的概念 l 系统本质上是一个基于字符串的并行重写系统，其核心概念就是重写。通过对植物 形态结构进行经验式总结、概括和抽象，可定义出一系列的重写规则( 或称生长规则) 和初始状态。一般来说，重写就是对一个简单的初始状态应用重写规则进行连续替换从 而得到一个复杂状态的过程。由于植物产生分枝和节间伸长等生长现象可视为迭代替换 的过程，因此很适合利用l 系统对其进行模拟。 最简单的l 系统可形式化表示为一个三元组g = ，其中y 表示l 系统的字 母表( a l p h a b e t ) 国表示l 系统的初始状态，是一个非空字符串，并且满足c o v + ( v + 表示由字母表中字母组成的所有的非空单词) ；p 表示生长规则的有限集合，且pcv xv ( v 表示字母中的字母组成的所有单词) 。一条生长规则( 口，z ) p 记作： aj z 其中字母a 和单词z 分别表示生长规则的前驱和后缀。 对于每一个字母a ，都会存在一个单词z v + 与之对应，组成规则口寸z 。如果字母 口不存在这条规则，那么默认和字母a 对应的生长规则为口专a 。 假设= a t 。a m 为y 中的任意一个单词，单词，= 石厶v + 是从直接生长( 演化) 而得，记为j 1 ，该命题的充要条件是： 当且仅当对于每一个扛1 。朋都有a j 专石。 如果存在一个字符发展序列，记为h ，以，使得心= 彩，以= 1 ，z oj “j 心， 那