（计算机应用技术专业论文）基于三维分枝模型的树木模拟算法研究及其实现.pdf

硕士学位论文 摘要 虚拟自然场景一直是图形学研究领域中个富有挑战性的课题。树木是自然 场景的重要组成部分，其模拟算法的研究得到了广泛的重视。树木的形态复杂且 种类繁多，其造型、存储及绘制都存在相当的难度。 根据应用目的不同，树木生长模拟技术可分为两大类：以农林业应用为目的 和以非农林业应用为目的的模型。两者在建模原理和仿真结果的真实性要求上有 着很大差别。前者遵循树木的生态生理原理；后者追求基于视觉效果的真实性。 论文的研究属于第二类。在对已有的树木模拟算法进行分析和研究的基础 上，探讨出一种基于三维分枝模型的改进算法。该算法首先将树木的结构分为三 个层次：树干树枝和树叶，利用树木的自相似原理，建立树木的层次模型；然后 将光照和重力对树木形态的影响加入模型中，通过设置受光照和重力影响树枝偏 转的角度，实现树木的趋光与屈地的特性；算法再利用随机繁衍l 系统的分技 算法，通过设置分枝产生式以控制树木的分枝。为了体现树木的顶端优势，加入 了侧枝控制参数；最后，在模型绘制时，利用l o d 原理，按照树木到观察者距 离的不同，设置相应的模型复杂度，提高了树木的绘制效率。 论文实现了基于上述算法的原型系统。实验结果表明，采用以上改进算法建 立的树木模型，能较好地反映树木的空间特性，并且可以体现出树木的趋光性、 屈地性及顶端优势等特征，具有较高的真实感。 关键词：树模型；三维分枝模型；随机繁衍l 系统；多分辨率；真实感 基于三维分枝模型的树木建模算法研究及其实现 a b s t r a c t v i r t u a ln a t u r es c e n e si sac h a l l e n g i n gt o p i ci nc o m p u t e rg r a p h i c s a sav e r y i m p o r t a n tp a r to fn a t u r a ls c e n e r y , t h ea l g o r i t h mr e s e a r c ho nm o d e l i n go ft r e e sh a s a t t r a c t e dm u c ha t t e n t i o n t r e e sh a v ec o m p l e xs t r u c t u r ea n dv a r i o u sk i n d s ，w h i c ha r e d i f f i c u l tt oc r e a t e ，s t o r a g ea n dr e n d e r a c c o r d i n gt od i f f e r e n ta p p l i c a t i o n s ，t h et r e e sg r o w t hs t i m u l a n t i o nt e c h n o l o g y c a nb ed i v i d e di n t ot o wc l a s s e s ：a p p l i e di n a g r o f o r e s t r ya n dt h ea n o t h e rc l a s si s a p p l i e di no t h e rf i e l d t h et w oc l a s s e sa r ed i f f e r e n to np r i n c i p l eo fm o d e l i n ga n dt h e s t a n d a r do fr e s u l t s r e a l i s t i c r e q u i r e m e n t s t h e f i r s ts h o u l db ef a i t h f u lt o p h y s i o l o g i c a lp r i n c i p l es t r i c t l y ，t h el a t t e r i sb a s e do nr e a l i s t i ci m a g es y n t h e s i st o r e p r e s e n tn a t u r a ls c e n e t h er e s e a r c ho ft h i s p a p e rb e l o n g st ot h es e c o n dk i n d a f t e ra n a l y z e da n d s t u d i e do ns o m ea l g o r i t h m sa b o u th o wt oc r e a t ea n dr e n d e rt r e em o d e l s ，ai m p r o v e d a l g o r i t h m w h i c hi sb a s e do nt h r e e d i m e n s i o n a l g e o m e t r i cm o d e l i n gm e t h o d p r o p o s e d t h i sa l g o r i t h md i v i d e st h es t r u c t u r eo ft r e ei n t ot h r e el e v e l sa n dc o n s t r u c t s t h el e v e lm o d e lu s i n gt r e e s s e l f s i m i l a rc h a r a c t e r i s t i c t h e n ，w ec a na d j u s tt h e d e f l e x e da n g l e st ol e v e lm o d e l ，w h i c hi si n f l u e n c e db yl i g h t i n ga n dg r a v i t a t i o n u s i n gt h et r e e sr e p r e s e n t e da l g o r i t h mt oc o n t r o lt h en e wb r a n c h e s c r e a t i n g a d d i n g t h ep a r a m e t e r st oc o n t r o ls i d e - b r a n c h e s ，i ts o l v e st h ef c f p ( f i r s tc o m i n gf i r s t p r o s e s s i n g ) p r o b l e mi nt r e e s f i n a l l y , u s i n gt h et h e o r yo fl o d ，m u l t i c o m p l e xt r e e m o d e ma r eu s e dt oe x p r e s st r e e si nd i f f e r e n tv i e wd i s t a n c e s i ti m p r o v e st h ee f f e c to f r e n d e r i n g i tp r e s e n t sad e m os y s t e mt ov e r i f yt h i sa l g o r i t h m e x p e r i m e n t a lr e s u l ts h o wt h a t t r e em o d e lr e n d e r e db yt h ei m p r o v e da l g o r i t h mc a nr e f l e c tt r e e ss p a c ec o m b i n a t i o n ， a n dr e f l e c tt h ec h a r a c t e r i s t i co fp h o t o t a x i s ，g e o t r o p i s ma n df c f et h ea l g o r i t h m i m p r o v e st h er e a l i s t i co ft r e e s k e y w o r d s ：t r e em o d e l ；t h r e e - d i m e n s i o n a lg e o m e t r i cm o d e l i n gm e t h o d ；p a r a m e t r i c e l s y s t e m s ； m u l t i r e s o l u t i o n ：e a l i s t i c 硕士学位论文 插图索引 图1 1 论文结构图3 图2 1i f s 吸引子进行参数控制的结果【25 1 8 图2 2 两个十字交叉的面建立一颗树模型1 26 1 9 图2 3l 系统绘制的树1 3 图2 4 树木分层分枝结构模型图一1 5 图2 5 三种叶序1 5 图2 6 树叶模型一1 6 图3 1 基础模型1 9 图3 2x y z 系在变换后形成相对应坐标系盖一l ，一z 2 2 图3 3 迭代1 0 次生成的连续枝段一2 2 图3 4 不同细节层次的同一树木模型【5 ”一2 5 图3 5 垂直视点位置在一个模型上设置不同分辨率【5 1 1 一2 7 图3 6 三维透视投影原理图2 8 图3 7 利用简化的模型来加快绘制速度2 9 图4 1 系统的总框架图3 1 图4 2 树木模拟模块的框架图3 1 图4 3 模型选择模块3 2 图4 4 分枝模块3 3 图4 5 枝段模块3 4 图4 6 同一树木不同仰角观察结果3 9 图4 7 同一树木不同角度观察结果4 0 图4 8 同一树木不同距离观察结果4 0 图5 1p o l 系统中同一参数生成结果对比4 1 图5 2p o l 系统中不同参数生成结果对比4 1 图5 3 无树叶的树木模型4 2 图5 4 树木模型4 2 图5 5 场景中的树木4 3 图5 6 近距离观察的树木4 4 图5 6 树木的阴影4 4 1 1 1 湖南大学 学位论文原创性声明 本人郑熏声叫j ：所早交的论文是本人存导师的指导卜 独立进行研究所 取得n 勺研究收果。除了义中特别f 】= | 以标往0 j 的内容外，本沦义卅i t ：! _ 龠仃 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均己任文中以明确方式标明。本人完全意识到本声叫的 法律后果山本人承担。 作者签名：耘 日期：0o 西年、厂月p 日 学位论文版权使用授权书 本学何沦文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交沦文的复印件种j 电f 版，允许论文 被夼i ；f 【| 和f 叶阅。本人授权湖南大学n j 以将本学位沦文的全部或部分l 容编 入铂+ 关数撕库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 小学位沦文属于 l 、保密口，伍年解密后适用本授权l ；。 2 、不保密团。 ( 请在以卜相应方框内打“ ，”) 鬃曼勃彩 喇巾签纠侈 肌毋。嗲 ：f 月引f 日期：弘巧珲厂碉7 曰 第1 章绪论 1 1 植物建模技术的出现 利用模型研究自然界中的事物、现象和过程是科学研究中的一种重要方法。 数学模型是人们为了达到某种特定目的而对研究对象所做的一种抽象与简化，通 过对数学关系的分析，了解过程的本质特征和发展规律，可以在实践中提供对未 知情况的预测。在人们许多的活动领域，利用模型方法可以避免盲目性和纯经验 思想，更多地以理性方式认识事物【。 近年计算机图形学的研究进展使得三维图形水平已经接近真实化图形的目 标，随着虚拟现实应用需求的不断增加，植物模拟在真实感上的要求越来越高。 植物模拟是利用虚拟现实技术在计算机上模拟植物在三维空间中的生长、发育过 程。从2 0 世纪6 0 年代起，研究人员就开始了植物模拟的研究。植物的模拟涉及 到众多领域，包括植物生理学、作物栽培学、农业气象学和微气象学、土壤学、 微生物学、计算机科学等众多学科，吸引了许多计算机科学家，植物学家以及数 学家等，提出了许多模拟植物的方法和模型。 植物的生长发育是一个十分复杂的过程，不仅受遗传因子的控制，在各种环 境条件和随机因素的影响下，植物的生长随时间和空间呈现随机性，非线性和突 变性【2 】【3 】【4 】。植物的生理过程和生态过程动态耦合、交互作用，具有众多的外部 控制变量和内部状态变量。因此，人们一般从特定的研究目的和兴趣出发，针对 植物生长的某一个层面，做出适当的假定而建立相应的模型。这些数学模型是研 究植物生命现象的一个很重要的方法和手段，具有解释现象、发现规律、预测未 知等功能。对于人们的生活、科研等许多方面具有很重要的意义和应用价值。 1 2 植物建模技术的研究意义及其应用领域 虚拟植物的应用领域十分广泛，在三维动画制作、建筑环境的整体规划、园 林植物布局设计和航空航天仿真技术中都有着重要的用途，而且在它在农林业的 研究方面占据很重要的作用。在相当长的一段时间内，影视、广告、游戏、虚拟 现实等领域纹理映射仍然是创建植物的主要手段，虽然人们投入了很大的精力去 研究植物的造型和绘制算法。但植物的三维建模仍然是一个难题。 目前植物模拟的算法研究主要有两类方向。第一类是研究如何真实的反映植 物的生长过程，其结果必须严格遵循植物学理论，该方向的目的在于植物生长过 程的研究，可应用于对作物产量预测、土地生产力评价、资源环境分析、作物栽 基于三维分枝模型的树木建模算法研究及其实现 培指导、作物生长机理的研究以及最新发展起来的精确植物技术应用等方面。 第二类是对植物外观形态进行模拟，其结果注重形态的逼真性，不需要大量 的植物学知识，也不要求结果必须遵循植物学中的理论。该方向的目的是为了自 然景观的再现，其主要应用领域如下： 1 教育：用于制作数字图书馆，植物生长模拟教育软件。让用户对人们赖以生 存的植物有更加形象的认识和了解； 2 娱乐：用于三维动画场景的制作，电子游戏中虚拟场景的生成，影视特效的 制作等； 3 计算机辅助设计：用于园林及城市规划和生活区设计等： 4 商业：用于网上销售观赏植物等商务方面，广告的创意制作等； 总之，虚拟植物模拟能给我们带来许多精神和物质方面的益处。随着各个学 科研究水平的提高，特别是计算机领域超乎想象的飞速发展，虚拟植物模拟研究 领域也产生了巨大的变化。 1 3 研究内容 论文的研究属于第二类，研究如何利用少量的植物学知识，对树木进行模拟， 达到真实反映树木外观特征的目的。为了实现此目的，首先对树木的形态进行研 究，分析树木拓扑结构，寻找简单的方式来建立树木的模型；然后结合一些简单 的植物知识对树木模型进行修改，使得树木外形更加逼真。对植物形态有比较大 影响的特性有：植物的趋光性，屈地性以及顶端优势。趋光性是指植物具有向着 光源的来向生长，以便获得更充足的阳光进行光和作用的特性；屈地性是指植物 都有克服重力影响，朝着与重力相反的方向生长的特性；而顶端优势是指植株的 顶芽在生长上占有优势，顶芽的存在控制侧芽的生长的特性。针对这些问题，文 中探讨了一种改进的三维分枝树木生成模型，该模型能较已有的模型生成真实感 更强的树木，并且能考虑到植物的趋光性、趋地性及顶端优势对树木形态的影响。 在构建了此模型的基础上，我们进一步研究了对于此模型的优化，提高运行效率， 使之能满足微机环境下显示速度的需求。最后，依据此模型，我们完成了一个具 有高度参数化特征的原型系统，它能根据要求灵活地进行修改树木的各项参数， 控制树木形态的变化。 1 4 主要工作 文中所探讨的改进算法以三维分枝模型为基础，利用了随机繁衍l 系统的 分枝原理，对树木模型进行了以下改进： 1 以三维分枝模型的枝干模型为基础，将植物的屈地性和趋光性对树木的影响 加入算法中。使用分枝角度，扭转度，分枝长度比例等几何参量，对树木的 几何结构进行控制与修改； 2 利用随机繁衍l 系统的分枝算法。通过设立几个分枝产生式来控制树木的分 枝。在设置分技产生式中考虑了树木的顶端优势，在层数较大时进行顶端优 势的控制。加入了侧枝控制参数，使得同一枝段生成的不同枝段的长度和半 径有所差别，增强了生成树木的真实感： 3 模型绘制时利用l o d 原理，按照村木到观察者距离的不同，设置相应的模型 复杂度，实现了与视点相关的动态多分辨率树木模型，提高了树木的绘制效 率，加快了场景渲染的速度。 1 5 论文结构 论文的结构如图1 1 所示 论文的结构如图1 1 所示 第一章绪论 f第二章相关研究综述 + 第三章基于三维分枝模型的跛进 + i 第心章演示系统的构件与实蹰方法 + l第五章性能潮试 + 结论 图1 1 论文结构图 基于三维分枝模型的树木建模算法研究及其实现 第2 章相关研究综述 2 1 国内外的研究现状 从2 0 世纪6 0 年代中期开始，研究人员利用数理统计、人工智能等方法建立 植物模型，研究植物生长过程。由于植物结构以及生长过程极为复杂，且受外界 因素影响较大，所以早期的模型主要是针对植物形态结构对植物生长的影响方面 进行简化。2 0 世纪8 0 年代，一些学者开始将植物形态结构模型和生理生态模型 结合起来用以更准确地模拟植物的生长过程。两者的结合成为植物建模技术研究 发展的新方向和必然趋势。2 0 世纪9 0 年代，研究人员又开始将三维可视化技术 用于虚拟植物的研究之中，人工智能领域中的模期系统，人工神经网络等代表性 方法的综合应用，使得植物的仿真研究得到了进一步的发展。 综合这几十年来的研究历史，可以看出植物生长与结构的建模发生了很大的 变化，从模型的功能和目的来看主要是沿着两条路线进行的：一是建立基于过程 的生态生理模型，此模型注重于农艺学和造林学知识的综合，绝大部分是作物生 长模拟模型；二是树木生长的计算机模拟，利用过程算法模拟树木形态结构的变 化，此模型的主要目的是为了在计算机上产生逼真的树木图形。 2 1 1 作物生长模拟模型 关于作物生长模拟模型的研究工作，国内外已经发表了许多综述性的文章 【6 】【7 】【8 1 。 作物模拟是在作物生理研究深化与计算机硬件发展的共同产物。2 0 世纪6 0 年代是作物模拟的开创时期。国际上最早的在计算机上模拟作物群体生产过程的 模型是1 9 9 5 年d ew i t 研制成的玉米光和生产模型和d u n c a n 等人于1 9 6 7 发表的 玉米叶面积与叶片角度对群体光和作用的影响模型。他们的开创性工作在国际上 产生了重大影响。2 0 世纪7 0 年代是作物模拟在深度和广度上同时发展的时期， 美国，荷兰，英国，澳大利亚，日本和前苏联等国家研制成1 0 多种作物的模拟 模型。2 0 世纪8 0 年代则是作物模拟向综合化和应用化方向发展的时期，其重要 标志是美国c e r e s 模型( c r o p e n v i r o n m e n t a lr e s o u r c es y n t h e s i s ) 的研制成功。 r i t h c i e 等人研制的c e r e s 系列覆盖了玉米、小麦、水稻、高粱、木薯、大豆、 花生、马铃薯等多种作物，不仅能模拟作物的生理和生长过程，还能模拟土壤养 分平衡和水分平衡。此外，较为成功的模型还有棉花模拟模型g o s s y m 模型1 1 8 1 1 1 9 ( d n b a k e r ，1 9 8 3 ) ；e p i c ( e r o s i o n p r o d u c t i v i t yi m p a c tc a l c u l a t o r ) 模型可以模 拟土壤侵蚀对作物生产力的影响，并用于经济评价研究；s i c m ( s o y b e a n 硕士学位论文 i n t e g r a t e dc r o pm o d e l ) 大豆综合作物模型可以模拟天气，土壤水分，经济条件 和虫害对大豆作物生长发育的影响，并对灌溉、肥料、农药、土壤水分和劳力等 的成本进行经济分析。在2 0 世纪6 0 至8 0 年代，荷兰w a g e n i n g e n 大学的科学家 们先后研制成e l c r o s ( 初级作物生长模拟器) ，b a c r o s ( 基本作物生长模拟 器) ，s u c r o s ( 简单和通用作物生长模拟器) 。此后，p e n n i n gd ev r i e s 等于1 9 8 9 年研制成a c r o s ( m o d u l e sf o ra n n u a lc r o ps i m u l a t i o n ) ，即一年生作物模拟模 型。这些模型多偏重于理论研究。9 0 年代以来，国际上农业模型的研究几乎遍 及到农业的各个领域：作物育种、作物施肥、作物灌溉、植物病理学、畜牧学、 林学等等。 我国的作物模型的研究开发起步于8 0 年代初期，发展比较快，已经开发的 较成功的模型有高亮之的水稻钟模型 9 1 ，戚昌翰的水稻生长日历模型r i c a m t l o 】， 潘学标的棉花生长发育模拟模型c o t g r o w l l l 】，以及夏北成开发的评价小麦产 量病虫害损失的麦田生态系统模拟模型。对国外成功模型的引进改造和本土化工 作也取得了许多成果【1 2 】【1 引。 2 1 2 树木生长模拟模型 自然景物的模拟是计算机图形学的一个重要研究内容，其中树木模拟占相当 大的比重。已经发展了许多过程模型或算法模型( p r o c e d u r a l m o d e l ) ，致力于动 态的再现树木丰富的细节。 自从美国生物学家a r is t i dl i n d e n m a y e r 于1 9 6 8 年提出l 系统【1 4 】并被 s m i t h 引入到图形学之后，已经出现了许多树木模拟的方法，在二维树木图形绘 制方面，模拟的方法归纳起来主要有分形、l 系统、随机过程等。但是二维的树 木图形过于简单，不能很好的体现出树木的空间特性。因此，在树木的三维建模 方面的研究有了很大的进展，目前主要有l 系统、i f s 吸引子、d l a 模型、粒子 系统1 1 5 、几何设计法、特征综合推理法和基于图像的建模方法。 美国科学家w i t t e n 和s a n d e r 于1 9 8 1 年提出的d l a 模型 1 6 1 ，利用d l a 或 其修改模型可以对部分树木的形态结构进行计算机模拟；1 9 8 4 年a o n o 与 k n n i i 【1 7 l 提出了树木的三维几何模型，以树木特定分枝模式为基础，使用分枝角、 开度角、分枝长度比例等几何参量，实施对树木几何结构的控制和修改。 t o r o n t o 大学景观研究中心构造的数学建筑物模型，模型中对树木的表达采 用了图像的方式。这种方式简单，且具有较高的观赏性，在处理数字建筑物图片， 或用于艺术家作图时，效果比较理想。其实质是在一个空间长方形区域通过融合 方式粘贴植物图像。这种方法将具有三维空间复杂特性的树木对象用一个空间长 方形替代，生成的树木只有一定的空间位置，而失去了其它空问特性。a r c v i e w 3 d x 是e x r i 公司的一个三维g i s 模块，它曾采用过简单矢量植物模型，显然这 基于三维分枝模型的树木建模算法研究及其实现 种模型效果很不理想。g r u e na 1 等人开发过一种称之c c 2 m o d c l e r 的三维交互 式建模系统，利用该系统他们建立了一些城市景观模型。在他们的研究中对树木 采用了实体型的矢量模型，即将棵树木作为一个实心体来处理，虽然这种处理 方式简单，而且也具有粗略的树木形体，但对于景观而言，真实性较差。另外， l - s y s t e m 经过多年的研究，已有了很多新的发展，如d o l s y s t e m s 、b r a c k e t e d o l s y s t e m s 、s t o c h a s t i cl - s y s t e m s 、p a r a m e t r i co l s y s t e m s 、t i m e do ls y s t e m s 、 b r a c e dl s y s t e m s ，它们都有其各自的特点及适用对象。 另一方面，虽然树木的绘制已有了相当多的有效的方法，但是大规模的植物 群的渲染和漫游，如森林等生态群的漫游仍然是一难点。r e e v e s 等人提出了粒 子系统方法，所绘制的森林是早期计算机生成虚拟自然景物最有说服力的例子之 一，然而粒子系统构造的树木看起来有比较明显的人工痕迹，而且粒子系统的 光照效果无法根据客观事实严格计算，因此缺乏高度真实感；对于几何面所构造 的远距离的树，w e b e r 采用的是对模型进行简化，根据树木的远近采用多分辨率 的绘制手段虽然w e b e r 提供的绘制结果质量比较高，但是远处树木简化后颜 色过于单一，造成绘制结果模糊不清。 总体说来，树木生长模拟得到了很大的发展，但是真实感的生态植物群场景 渲染简化与漫游，以及创作带有复杂演变和生命特征的自然生态群动画仍然是富 有吸引力和挑战性的难题。 2 2 国内外主要研究成果 以植物为对象的计算机模型有很多形式，根据植物生长模型与可视化仿真的 应用背景不同，可以归结为两大类模型：以非农林业应用为背景的模型和以农林 业应用为背景的模型。两者在建模原理和仿真结果的真实性要求方面有着很大的 差异。前者追求视觉效果的真实性，主要包括形态发展模型和可视化模型，基本 不涉及植物的生态生理模型；后者基于植物学，模型必须建立在植物的生态生理 原理之上。 另外，根据模型通过计算机提供给用户和显示方式不同，有三类模型：纯图 形学模型，植物动态结构模型和植物静态结构模型：这三类模型是现今虚拟植物 的主流建模方式，以这三类模型为基础的虚拟植物模拟系统会得到更为准确、真 实地效果。 2 2 1 纯图形学模型研究成果 纯图形学模型属于计算机图形学的范畴，比较注重视觉效果的逼真性，主要 研究如何用简单的植物学知识，方便快捷的生成具有植物特性的图形。该类模型 不需要复杂的植物生长机理模型，所以+ 般不合适模拟植物生长发育过程，而主 硕士学位论文 要用于建筑配景、电影特效、园林规划、景观设计等方面。该类模型比较典型的 有：分形、迭代函数系统、d l a 凝聚模型、基于交互的植物建模方法、布告板技 术以及基于图像的建模技术。 2 2 1 1 分数维几何学( f r a c t a l ) 分形理论 2 0 ，1 5 是研究非线性问题的门热门学科。自从2 0 世纪7 0 年代， b b m a n d e l b r o t 首先提出分形以来，这门学科无论在其数学基础还是在其他学 科的应用方面都得到了迅速发展。目前，分形理论在物理、化学、生物学、医学、 材料科学、地质地震、经济学等学科以及工程技术中都有着广泛的引用，特别是 随着计算机技术的迅速发展和广泛应用，分形的思想和方法在模式识别、图像处 理、自然景物的模拟、信息讯号的处理以及艺术制作等领域取得了极大的成功。 由于蕴含于自然景物中的图形具有无穷多地随机纹理细节，即使选择简要造 型，也需要使用一个庞大的数据结构，而随着对自然景物观察尺度的变化，在自 然景物中又有无穷细节需要描述，已存储在数据结构中的细节资源可能就会因此 陷入枯竭，所以采用一般的图形生成方法中所使用的静态数据结构来表示一个自 然景物是不可取的。因此，考虑到自然景物中纹理的随机性和自相似性，研究者 利用随机过程的理论，采用过程迭代模型来生成各种特定的自然景物。采用这种 方法，可以从少量数据出发生成复杂的、用传统数学方法无法表达出的形态。大 量分形例子是由数学方法，特别是迭代和递归算法生成的图形或图像。分形在创 建以假乱真的景物方面的发展和潜在的前途，使得无论怎样估计它的影响都不为 过。 2 2 1 2 迭代函数系i f s ( i t e r a t e df u n c t i o ns y s t e m s ) i f s 是混沌分形理论研究的一个重要部分，其理论和方法是分形自然景观模 拟以及分形图像压缩的理论基础。i f s 的基本思想是选定若干仿射变换，将整体 形态变换到局部，这一过程可以一直进行下去直到得到满意的结果。j c s p r o t t 利用一系列可变的随杌参数来控制函数系，在一定的参数取值区间自动生成i f s 的吸引子【2 1 2 引。 i f s 方法是分形迭代生成的“反问题”，根据拼接定理( c o l l a g et h e o r e m ) ， 对于一个绘定的图形，求碍几个生成规则，就可以大幅度压缩信息。在利用分形 模拟树木时可以采用i f s 吸引子的参数变动控制，通过已有的模拟树木的i f s 调整其参数，达到控制其吸引子模拟不同树木的目的。可以采用确定性算法与随 机性算法相结合的办法生成树木杆茎或叶片。“确定性”指用以迭代的规则是确 定性的，它们由一组仿射变换( 如疋1 ，足2 ，足3 等等) 构成；“随机性”指迭 代过程是不确定的，每一次究竟迭代哪一个规则，即r _ i 中具体哪一个，不是预 基于三维分枝模型的树木建模算法研究及其实现 _ _ _ 墨置墨e 胃_ 五皇自皇e 置_ - e 芒皇詈詈置舅_ - l = 覃墨墨詈_ _ 目- i _ 皇日_ | 兰曩詈昌，- 詈岂e 昌! 冒_ 詈昔芒暑= 霉l 詈篁芒搴= 置i 先定好的，而是随机据决定的。设虽终要生成的植物形态图为m ，它要满足下 述集合方程： 胪疋1 u c 2 u u 疋n 上式的含义是，随机地从足j ( = 1 ，肋中挑选一个迭代规则迭代一次， 然后再随机地在足，( 扛l ，朋中选一个规则迭代一次，不断重复此过程，最 后生成的极限图形m 就是欲求的植物形态图。每个迭代规则疋，都是一个仿射变 换。正交变换保持几何图形的度量性质( 向量的夹角，点与点之间的距离，图形 的面积等) 不变；而仿射变换一般会改变图形中向量的夹角、点对间的距离、图 形的面积等，但仿射变换不改变共线、平行、相交、共线点的顺序、中心对称、 二次曲线的次数等。增减规则足j ，可以改变最终植物m 的形态。即使不改变迭 代规则，采用同样的程序，只改变参数也可以生成完全不同的植物形态。 图2 1 if s 吸引子进行参数控制的结果【2 5 】 i f s 吸引子有着及其丰富的表现范畴，是模拟自然的有力工具，尤其是它对 参数的连续依赖性使用户能够通过参数的调整连续控制其吸引子的形状，在模拟 自然景观，虚拟现实等技术中广泛应用。但是这种连续的参数控制在模拟过程中 并不容易实现。怎样能够在模拟过程中实现连续的参数调整也是现今的研究方向 之一。 2 2 1 3 布告板技术( b i l lb o a r d i n g ) r o h l f 扩展了纹理映射技术，称为布告板技术( b i l lb o a r d i n g ) 【2 6 】。布告板技 术通过渲染2 d 对象，使之呈现3 d 对象的视觉效果，从而获得较高性能。这种 技术可以用一个纹理映射多边形来近似一个放射状或球对称状的对象。 人们对一颗树的观察，一般只注意它的外形，有一个圆柱形树干和圆锥形的 树冠，而对于从各个方向观察同一颗树的形状有哪些不同并不非常注意。基于这 一思想，产生了用一个多边形面来描述一一颗树的方法，这个面称为b i l l b o a r d 多 硕士学位论文 边形。用来模拟植物的基本原理为：从树的某一方向拍摄照片作为纹理，通过编 辑使其非树枝，树叶部分保持透明，并映射至多边形面上，当视点变化时，多边 形绕其中心轴旋转，使得多边形的正面始终保持面向视点，这里的中心轴通过树 干中心且与z 轴平行。 b i l l b o a r d 建模对于那些外观对称并呈圆柱形或圆锥形，细节复杂不容易建 立三维立体模型的物体的模型表示非常有用，它的建模过程非常简单。在植物模 拟中，由于其简便性，是应用最为广泛的技术之一。但是，它也有一个很大缺点， 就是在实时漫游时，计算量非常大。当漫游时，每一时刻视点都在发生变化，因 此对每一颗树利用b i l l b o a r d 建立的树模型都要进行一次旋转，旋转变换时矩阵 相乘运算，具有较大的运算量，而同时还要进行隐藏面的计算和阴影计算，这两 者计算量都较大。所以，当场景中树木很多时，就会因计算量过大而导致帧显示 变慢的结果，甚至达到无法实时显示的目的。基于这一原因，场景中也不宜过多 使用b i l l b o a r d 多边形。 因此利用人在视觉上的差异，可以用两个十字交叉的面来建立一颗树的模 型。与前者相比，场景中树木模型的多边形数增加了一倍。但是计算量却大大减 少，从实时漫游的效果来看，图形的显示帧将得到极大的提高。 图2 2 两个十宇交叉的面建立一颗树模型f ”1 不过这种方法也存在缺点。首先，在加入光照时，由于面遮挡产生的阴影将 会导致光照效果不均匀，出现由亮到暗的跳跃性变化现象。其次，一棵树的包围 盒大于数。包围盒的大小为，树的最大高度树的最大宽度，当漫游从树底下通 过时，会发生碰撞。另外，还有个缺点就是，当视点距离树木非常近时，树木 的外形看上去缺乏真实感。 2 2 2 植物动态模拟的研究成果 植物动态模型是通过对植物实际生长发育过程的研究。根据植物在生长过程 中拓扑结构演变和几何形态的变化规律，通过测得的大量数据来分析植物的生长 规律，建立植物生长模型，用以模拟植物的生长真实过程。通过改变模型参数可 以得到该植物的多种形态结构。最成功的动态结构模型有：l 系统，自动机模型， 9 基于三维分枝模型的树木建模算法研究及其实现 g o s s y m 模型和c o t t o n p l u s 模型以及粒子系统等等。 2 221 粒子系统( p a r t i c l es y s t e m ) 粒子系统【”】是迄今为止被人们认为模拟不规则模糊物体最为成功的一种图 形生成算法。由于自然景物的计算机模拟中的其他算法模型中往往是针对某一类 自然景物而设计的，因而无法用统一模式来生成，而粒子系统采用一种完全不同 于以往造型的方法来构造，绘制景物。景物被定义为由成千上万个不规则的随机 分布的粒子所组成的集合，而每个粒子均有一定的生命周期，它们不断改变不断 运动。在粒子系统中，最关键的是景物的总体形状和特征的动态变化，而不是各 个粒子本身。 粒子系统是一个复杂的动态系统，随着时间的推移，系统中已有粒子不断改 变形状，不断运动，而且不断有新的粒子加入，并有旧粒子消失。为模拟生长和 死亡过程，每个粒子被赋予一定的生命周期，它将经历出生，成长，衰老和死亡 的过程。同时为了使粒子系统所表示的景物具有良好的随机性，与粒子相关的每 个参数均受到一个随机过程的控制。粒子系统的这一特征，使它充分体现了不规 则模糊物体的动态性和随机性，因此能够很好地模拟火，云，水，森林和原野等 自然景观。生成粒子系统某瞬间画面的基本步骤如下： 1 将产生的新粒子加入系统中； 2 赋予每一粒子一定的属性； 3 删除那些已经超过其生命周期的粒子； 4 根据粒子的动态属性对粒子进行移动和变换； 5 绘制并显示有有生命的粒子组成的图形。 上述步骤中每一步的操作都是过程计算模型，因而它可以与任何描述物体运 动和特征的模型结合起来。为表达粒子系统的随机性，还可以采用一些非常建华 的随机过程来控制粒子在它所在系统的形状，特征及运动。对每一粒子参数均确 定其变化范围，然后在该范围内随机确定它的值，而其变化范围则由给定的平方 期望值和最大方差确定，粒子数目在很大程度上影响模糊物体的密度及其绘制色 彩，这可以通过确定每一时刻进入系统的粒子来控制系统中的总粒子数目。 粒子系统在模拟单独的树木时效果可能不是很理想，但是将粒子系统运用于 整个景观中，模拟随风飘动的花草树木，或者远处的森林原野还是非常研究前景 的。 2 2 2 2l 系统 l 系统【2 t 2 8 1 实质上就是一个重写系统，它可以用形式语言的方法来描述植物 的生长过程。应用分形l 系统理论模拟植物形态与生氏过程，不仅是计算机图 形学的研究范畴，9 0 年代该系统理论亦已被列入人工生命的研究范畴，l 系统以 1 0 硕士学位论文 其高度简洁性和多级结构，为描述树木的生长和增殖过程的形态和结构特征，提 供了行之有效的理论与方法但目前l 系统也存在一定的局限性，如l 系统的字 符串，既不能提供树木分枝的长度，也不能提供三维拓扑信息因此l 系统在 实用中还必须进一步充实和发展，才能更好地描述现实世界的三维树木目前已 有人将l 系统与分形几何描述相结合，以便对各种分枝情况复杂的树木及形态 进行模拟l 系统的理论与方法正不断地发展，其应用领域也在不断地扩大。 2 2 2 3 自动机模型( a m a p ) 法国c i r a d 开发的a m a p 2 9 】系列软件在植物生长机理模型与可视化模型结 合方面取得了卓有成效的进展，该软件包括了若干子系统软件，以完成不同的应 用功能。并对数据库中的数据进行提炼，以图表的方式显示出来，用来与描述植 物芽功能的概率模型产生的植物生长参数曲线进行比较，验证和调整模型参数。 并用多尺度树图方法根据植物体的不同尺度来定义和描述被测量植物体的拓扑 结构和几何结构，最终建立基于实际测量数据的植物生长模型。 a m a p 合并了离散的单个体和它们之间的结合，更新过程，以及离散马尔科 夫过程，依靠一系列标准的形式来对植物实体间的拓扑结构，几何结构以及树的 尺寸结构进行描述和编码。用了多尺度树图像的形式对树进行了模拟。通过选择 和视觉化不同类型的数据，如每个生长周期的节间平均数量，进一步描述了不同 类型的环境因素对生长和分枝过程的影响。 2 2 3 植物静态模拟的研究成果 静态结构模型就是对特定的植物，利用三维数字化方法测定其形态结构后， 直接利用所测数据来构造该树木的形态结构的模型。静态模型的最大优点是能够 精确的再现特定树木的形态结构，可用来研究与树木空间结构有关的定量和定性 特征以及生理生态过程等。但是该模型需要测量大量的数据和人工干预处理，不 适合反应树木形态结构的动态变化规律。 这种方法主要成果是基于图像的建模技术。基于图像的建模技术是当前的研 究热点之一，它从一组图像序列中提取图像中物体的几何信息，然后对物体进行 三维建模，i b m 是基于实物的照片图像来提取建模信息的，因而所建立的三维 模型带有实物的明显特征，具有较强的真实感。经过多年的发展，基于图像的建 模技术出现了许多研究方向，大致分为：基于体数据的立体逆投影 3 0 , 3 1 , 3 2 1 ，给予 轮廓的曲面重建【3 引，基于立体视觉的三维点重建1 34 1 。 1 基于体数据的立体逆投影法 在树木建模时，基于体数据的立体逆投影法主要用来针对枝繁叶茂的树木， 建立一个外形相似的模型，达到景物模拟的效果。 麻省理工学院的i l y as h 】y a k h t e r 【3 0 】将基于图像的建模技术与过程化方法相 基于三维分枝模型的树木建模算法研究及其实现 结合，采用透视投影的摄像机模型，首先将每幅图像从摄影机光心沿图像中树的 二维轮廓按照数据进行逆投影，得到空间中的若干锥体，各锥体相交得到树体的 外轮廓，然后从树体中根据外轮廓提取中心线作为树的主干骨架。最后，根据外 轮廓数据运用l 系统从主干骨架上模拟生长出一颗与原树形态相似的树模型。 日本a t r 实验室的s a k a g u c h i 3 5 】将摄像机模型简化为正交投影，把一颗树的 各个视点的灰度图象中的树区域归一化，用正交逆投影得到树的三维体数据。给 这个三维型体中的每个体素赋以所有输入图像相应像素灰度的平均值。然后根据 一定的分枝规则，限制条件及体素值在树体中重建树模型。 2 基于立体视觉的三维点重建 可以看出，基于体数据的立体逆投影法得到的树模型在枝干结构上与原树还 相差很多。在某些领域，为了获取较为精确的树木枝干模型，需要针对无叶树类 物体来进行建模，一般采用基于立体视觉【3 6 l 的三维点重建方法。 当空间一点投影在两幅图像中时，根据两个投影点坐标，两个摄像机的内部 参数和位置关系，将从摄像机光心通过投影点的两条射线求交，可以计算空间点 的三维坐标。o k u t o m i 和k a n a d e l 3 4 l 将这一技术推广到多视点图像，提高了重建 的准确度。一个主要难点在于如何找到空间同一点的各个投影点，即建立各幅图 像二维点的对应关系。目前主要的求对应方法的基本思想都是基于相似性的度量 和连续性假设的。 树木的表面点在图像中很难寻找对应关系，因为一颗树木的表面纹理非常相 似或近似于没有纹理，而且树木的圆柱形状使得相同点在另一不同视角可能就看 不到，所以通过树木表面点的对应来重建一般是不可取的。针对无叶类树木的三 维重建，目前一般采取基于骨架重建的策略。即首先从树木二维骨架重建出树木 的三维骨架，然后在三维骨架点处加上宽度信息，生成树木的表面模型。国内中 科院软件所的严涛【7 l 实现了一种基于骨架重建的树木建模方案