（计算机应用技术专业论文）面向太湖流域虚拟森林的建模与实现.pdf

面向太湖流域虚拟森林的建模与实现 中文摘要 面向太湖流域虚拟森林的建模与实现 中文摘要 森林环境的改变过程是不可逆转的，林业管理者一旦做出管理决策并给予实施， 将对森林今后的生长和经营起着决定的作用，因此林业管理者迫切需要引入能够对林 业信息进行准确、可靠描述的技术。虚拟森林环境是虚拟现实技术与林业科学知识相 结合的新型研究领域，其构建复杂的森林对象、表达及分析复杂的森林生长规律的能 力为林业科学研究提供了一个新型的研究平台。 本文是为苏卅i 某管理部门开发的“虚拟太湖流域 项目中的一个子课题，主要以 太湖流域的植被生长规律为依据，构建并实现面向太湖流域的虚拟森林模型。该模型 包括虚拟植物模型、虚拟植物模拟器、环境模拟器、环境模型和环境因子( 阳光、温 度等) ，将建模与实现分开处理，方便了将来系统的扩展与移植。目前关于虚拟森林 的研究大多停留在通过林业中的统计数据重现森林在某一具体时刻的状态，对于实现 其模拟森林动态生长全过程的功能却未有深入研究。受达尔文生物进化论思想的启 发，本文借鉴生物界自然选择和进化机制，从植物种群着手，利用遗传算法模拟虚拟 森林中植物个体之间的竞争关系，体现了优胜劣汰的自然选择规律，在一定程度上实 现了虚拟森林反演过去、再现现实、预测未来的功能。在构建虚拟植物模型时提出了 基于二叉树的新型l 系统，传统l 系统在动态生成环境敏感型虚拟植物过程中，其 线性表示方法使得上下文搜索过程繁琐和效率不高，基于二叉树的l 系统弥补了这一 不足之处，从底层的存储结构出发，在模拟环境对植物的影响过程中，缩小了上下文 搜索范围，提高了整个系统的执行速度。 关键词：虚拟森林，l 系统，二叉树，遗传算法 作者：何伟 指导老师：李云飞 a b s t r a e t m o d e l i n ga n dr e a l i z a t i o no f v i r t u a lf o r e s tf o rt a i h ul a k eb a s i n m o d e l i n ga n dr e a l i z a t i o no f v i r t u a lf o r e s tf o r t a i h ul a k eb a s i n a b s t r a c t f o r e s te n v i r o n m e n tc h a n g ei sa l li r r e v e r s i b l ep r o c e s s ，i ft h em a n a g e m e n td e c i s i o ni s m a d eb yf o r e s tm a n a g e r , t h ef u t u r eo ff o r e s tw i l lb es e t t h e r e f o r et h et e c h n o l o g yw h i c h c o u l da c c u r a t e l yd e s c r i b et h ef o r e s ti n f o r m a t i o ni su r g e n t l yn e e d e db yf o r e s tm a n a g e r s v i r t u a lf o r e s te n v i r o n m e n ti san e wr e s e a r c ha r e aw h i c hi st h ec o m b i n a t i o no fv i r t u a l r e a l i t ya n df o r e s ti n f o r m a t i o n i ti san e wp l a t f o r mw h i c hc o u l dc o n s t r u c tt h ec o m p l e x f o r e s to b j e c t sa n da n a l y z ec o m p l e xf o r e s tg r o w t hl a w t h i sp a p e ri sas u b s e to f v i r t u a lt a i h ul a k eb a s i n p r o j e c tw h i c hi sd e v e l o p e df o r s u z h o um a n a g e m e n td e p a r t m e n t t h i sv i r t u a lf o r e s tm o d e li sc o n s t r u c t e da n dr e a l i z e d b a s e do nt h el a wo fv e g e t a t i o ng r o w t hi nt a i h ul a k eb a s i n v i r t u a lp l a n t sm o d e l ，v i r t u a l p l a n t ss i m u l a t o r , e n v i r o n m e n ts i m u l a t o r , e n v i r o n m e n tm o d e la n de n v i r o n m e n tf a c t o r s ( s u c h a ss u na n dt e m p e r a t u r e ) a r ei n c l u d e di nt h i sm o d e l m o d e l i n ga n dr e a l i z a t i o na r es e p a r a t e d t of a c i l i t a t et h ef u t u r ee x p a n s i o na n dt r a n s p l a n t a t i o no fs y s t e m w i t ht h ed e v e l o p m e n to f v i r t u a ln a t u r a ls c e n e r y , al o to fv i r t u a lf o r e s tm o d e l sh a v e b e e nr e p o r t e d h o w e v e r , m o s to f t h e ma r eb a s e do nt h es t a t i s t i c a ld a t at op o r t r a yt h eo b j e c t sa tac e r t a i nt i m e e n l i g h t e n e d b yd a r w i n se v o l u t i o nt h e o r y , t h i sp a p e ru s et h ei d e ao fn a t u r a ls e l e c t i o na n de v o l u t i o n m e c h a n i s m ，f o c u so nt h es p e c i e so fp l a n t sa n dt h ep r o c e s so fe v o l u t i o n ，a n dr e a l i z et h e s i m u l a t i o na b o u tt h ef o r e s te v o l u t i o nt od e s c r i b et h ec o m p e t i t i o nr e l a t i o n s h i pa m o n gp l a n t s i nv i r t u a lf o r e s t p a s t ，p r e s e n ta n df u t u r eo ft h ev i r t u a lf o r e s ti ss i m u l a t e di ns o m ed e g r e e 。l s y s t e mb a s e do nb i n a r yt r e ei sp u tf o r w a r dt oc o n s t r u c tt h ev i r t u a lp l a n t sm o d e l t h i s m e t h o ds i m p l i f i e st h ep r o c e s so fc o n t e x ts e a r c ha n di m p r o v e st h ee f f i c i e n c yo ft i m ea n d s p a c ei nt h ep r o c e s so fg r o w t hs i m u l a t i o na n dd y n a m i cs i m u l a t i o no fe n v i r o n m e n ti m p a c t i ti sv e r yi m p o r t a n tf o rv i r t u a lf o r e s ts i m u l a t i o n , a n dt h ee f f i c i e n c yo fs y s t e mi si m p r o v e d k e y w o r d s ：v i r t u a lf o r e s t ，ls y s t e m ，b i n a r yt r e e ，g e n e t i ca l g o r i t h m w r i t t e nb yh ew e i s u p e r v i s e db yl iy u n f e i i i 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名： 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名： 导师签名： e t 期：力) f r 留 日 期：一 面向太湖流域虚拟森林的建模与实现第一章绪论 1 1 虚拟森林技术 第一章绪论 虚拟森林环境( v i r t u a lf o r e s te n v i r o n m e n t s ，v f e ) 是虚拟现实技术在林业科学 上的应用实践，它以林业空间数据为依托，以虚拟现实技术为特征，构建森林对象， 表达及分析复杂的森林现象，这种不同与以往二维图形的表达方式诱发了三维可视化 的新方法。虚拟森林环境是一个可进行森林实验的虚拟工作室或人与人交流研讨、协 同工作的媒介平台，在虚拟森林环境中可用于对现实世界的森林数据进行模拟、分析、 解释、预测等，帮助理解复杂的森林生长现象，支持林业规划、决策和调控。因此， 面向林业的虚拟森林环境的研究，是一个十分复杂而迫切需要解决的问题，它将为林 业建设提供一个广泛而形象化的信息处理环境及支撑工具，为专家提供林业决策的新 平台，有效推动森林资源的合理保护和营林生产等林业各个环节的信息化进程，进而 提高林业的现代化管理水平。 2 0 世纪8 0 年代中期，随着植物模拟在纯计算机图形学方面的逐渐成熟，美国、 芬兰、日本等国逐渐开始将其应用于林业研究。从大学的实验室到商业上的产品都开 始采用虚拟技术对森林进行管理。 伊利诺斯大学图像系统实验室和美国农业部( u n i t e ds t a t e dd e p a r t m e n to f a g r i c u l t u r e ，u s d a ) 林务局合作开发，后由芬兰赫尔辛基大学森林可视化实验室更 新的s m a r t f o r e s t 是一个交互的三维可视化森林系统【1 】。通过设置可以在森林场景中 交互式地移动，用户能近距离观察树，也可以自定义调节飞行高度在高处俯视整个森 林，与以往固定的南北方向观察不同的是，在s m a r t f o r e s t 中可以真正实现实时地漫 游。s m a r t f o r e s t 系统包含了经营管理尺度和景观尺度两种模式。经营管理模式中的 树木是用简单的规则几何体表示的，地面用不同颜色来表达不同的林分，从而达到快 速、高效查询和分析林分和树木的特征。景观模式中的树木和地面则用二维图像纹理 映射到复杂的对象几何面上，该模式构建的森林真实感强，但景观模式数据库中包含 的树种仅仅有三种，构建一个这样虚拟森林场景，需要完善图像库，收集每个树种从 幼龄到成熟各个不同生长阶段的纹理，而且还要包括不同地面纹理。绘制时通过减小 第一章绪论面向太湖流域虚拟森林的建模与实现 图像的视野范围( 裁剪) 或者根据视点远近减少像素来提高交互速度。 u s d a 林务局和太平洋西北研究站的林分可视化系统( s t a n dv i s u a l i z a t i o n s y s t e m ，s v s ) ，可以生成代表林分生长条件的一系列林分内的树木、灌木、草木等 三维几何图像，通过这些图像便于理解林分的生长条件，从而帮助森林经营管理。 景观管理系统( l a n d s c a p em a n a g e m e n ts y s t e m ，l m s ) 创建于1 9 9 4 年，主要由 美国华盛顿大学的森林资源学院营林实验室、耶鲁大学的森林环境研究学院、u s d a 林务局联合开发的。l m s 设计的目的是帮助景观、森林生态系统的分析和规划。l m s 包括林分预测、图形或表格的统计输出、林分尺度可视化( 主要利用美国农业部门的 林分可视化系统s t a n dv i s u a l i z a t i o ns y s t e m ，s v s 的可视化功能) 和景观尺度的可视 化( 主要利用u s d a 林务局和太平洋西北研究站的e n v i s i o n 的可视化功能) 。l m s 底层应用了生长预测模型和可视化工具相结合的方法。在森林景观模拟中，用户可以 根据不同时间间隔预测不同生长阶段下的树木的胸径、高度和体积1 2 。 2 0 世纪8 0 年代起，我国在虚拟森林环境方面出现了多个重要的森林生长模型， 如邵国凡的生长竞争模型【3 】、于正中的径阶动态模型、迈利思的树种更替模型以及孟 宪宇的直径分布模型【4 】，建立的模型大多数是基于国内用途比较广的树种，例如马尾 松、杉木、落叶松等。2 0 世纪9 0 年代初，北京林业大学的郝小琴先后推出了多种森 林景物的建模法和绘制算法。在研究初期，曾采用一种旋转扫描法来绘制树木，树木 的三维图形是根据视点和树木在林中的位置坐标计算出每株树在屏幕上的实际位置， 再经过消隐即可。由此方法生成的树木图形信息量少，逼真度低，较适合于绘制森林 的远景图。为了能绘制更为逼真的树木个体的三维图，郝小琴提出了基于t r e e d o l 文法规则的单木生长的视景仿真模型，利用文法所具有的很强的描述结构能力，仅以 若干个字符组成的链语言即可描述一株结构复杂的树木形态，并结合单木生长的预测 模型动态地生成不同生长期的树木图形。但由于以链语言描述的景物模型不包含几何 信息，在图形绘制过程中仍需做相应的几何解释，所需中间存储量也较大。1 9 9 9 年， 郝小琴又提出了基于分形几何的3 d i f s 建模法，以3 维迭代函数系统i f s 作为树木 的形体模型，其模型不仅包含了拓扑信息，也包含了几何信息，有利于图形的绘制。 并采用了概率驱动的随机算法来绘制图形，无需保留中间结果，所需存储量将大大减 少，同时还有利于色彩的分配与纹理的生成，简单快速。北京林业大学的宋铁英【5 j 2 面向太湖流域虚拟森林的建模与实现第一章绪论 在1 9 9 8 年利用计算机图形与图像结合的方法，提出一种基于图像的林分三维可视模 型，以一株典型形体的现实树木图像为原型，应用图像重采技术对该原型林木图像按 比例缩放生成林分中各株林木的图像，根据投影远近，计算每株林木在投影平面上的 坐标和放缩比例，对各林木图像再次缩放移动到林木的平面坐标合成一幅有立体感的 林分图。这种基于树的图像的林分三维可视模型与林木的树高和冠幅的生长模型相结 合就可得到林分逐年变化的三维图，并产生林分生长的动画。 1 2 虚拟植物建模技术 虚拟植物，即应用计算机模拟植物在三维空间中的生长发育情况，是近2 0 年来 随着信息技术的发展而迅速崛起的虚拟现实的一个重要分支。虚拟植物的模拟涉及众 多领域，包括植物生理学、作物栽培学、农业气象学和微气象学、土壤学、微生物学、 计算机科学等众多学科，吸引了许多计算机科学家，植物学家以及数学家等，提出了 各自模拟植物的方法和模型【6 】。 1 2 1l 系统 l 系统【7 ，8 】是美国生物学家a 。l i n d e n m a y e r 于1 9 6 8 年提出的，它是一种字符重写系 统或形式化语言方法，通过对植物对象生长过程的经验式概括和抽象，构造公理与产 生集，生成字符发展序列，以表现植物的拓扑结构。此后不久，s m i t h 等人将l 系统引 入计算机图形学领域，用以解决植物模拟中分枝的拓扑问题。2 0 世纪8 0 年代，加拿大 c a l g a r y 大学学者p r u s i n k i e w i c z 等人的工作进一步拓宽了l 系统的研究范围，并给出了 大量由l 系统产生的分形集与植物结构的例子。图1 1 所示的是l 系统构建的虚拟树。 应用l 系统理论模拟植物形态与生长过程，不仅是计算机图形学的研究范畴，2 0 世纪 9 0 年代后该系统理论亦已被列入人工生命的研究范畴，l 系统以其高度简洁和多级结 构，为描述树木生长和增殖过程的形态和结构特征，提供了行之有效的理论与方法， 但l 系统也存在一定的局限性，如l 系统的字符串，既不能提供树木的基本信息，也 不能提供三维拓扑关系，因此，l 系统在实际应用过程中还必须进一步充实和发展， 才能更好地描述现实世界中的三维树木，目前已有人将l 系统与分形几何描述相结合， 筹一章绪论 面向太湖流域虚拟舞韩的建横与实现 以便对各种分枝情况复杂的树木及形态进行模拟，l 系统的理论与方法正不断地发展 其应用领域也在不断地扩大。 i2 2 迭代函数系统( i f s ) 圈1 1l 系统构建的树 i f s n 是确定几何对象的全貌和局部，通过若干仿射变换，将整体形态变换到局 部，并将这一过程迭代下去，直到生成满意的造型。i f s 可定义为由一组满足一定条 件的映射函数及一组变化发生的概率组成。使用i f s 生成的树木造型如图1 - 2 所示。 图i - 2 i f s 构建的树 近年来，i f s 理论有了较大的发展，它在一大类物体的建模问题中，特别是在自 然景物的计算机模拟生成中具有很大的优势。国内外许多学者对此也做了大量的研究 和探索。i f s 的研究范围在自相似分形图的基础上不断扩展，其范围己不再局限于仿 射变换。在用i f s 建模的研究中，实现了对原图形的几何变换，将i f s 中的线性变换 推广到非线性变换，对自然景物的建模研究也由二维推广到三维i 。 面向太湖流域虚拟森林的建模与实现第一章绪论 1 2 3 粒子系统 粒子系统方法是迄今为止被认为是模拟不规则物体最为成功的图形生成算法之 一。粒子系统不是专门针对某一类自然景物设计的，而是从微观上着手，将自然景物 定义为微观粒子的集合，通过采用随机过程理论对微观运动的动态性进行约束，从而 在宏观上达到对不规则模糊物体的动态性和随机性的描述，因此粒子系统可以用统一 的模式来描述不同的动态自然景物【1 1 1 。 粒子系统采用随机过程建立粒子的运动模型，并通过大量粒子的运动来表现不规 则模糊物体的整体动态性。用纯粹的粒子系统去模拟，一方面需要大量的粒子；另一 方面需要对粒子的运动采用能满足一定真实感的约束。因此粒子系统在发展过程中面 临的问题和难点主要集中在以下三个方面： ( 1 ) 大量粒子运算的实时性和真实感之间的矛盾。理论上来讲，粒子数量越多， 模拟的真实感越强，但是粒子系统中粒子更新和绘制的运算复杂度与粒子数量成正 比，因此增大粒子数量必然会使实时性下降。解决这个矛盾必须要采用一些方法在保 证一定真实感的基础上减少粒子的数量。粒子团纹理映射方法，以及后期出现的粒子 包络线方法等都是寻求解决这个问题的不同手段。 ( 2 ) 粒子动态模型的真实性约束方面，简单的构造模型有一定的局限性，必须 从物理原理中寻求更加精确的建模。因此基于粒子系统的模拟方法已经越来越多的和 基于物理原理的方法相结合。物理原理的使用从最初简单的外力或速度场的动态建模 逐步渗透扩展到各种粒子属性变化的动态建模。 ( 3 ) 粒子的绘制方法。由于粒子数量众多，采用真实的光照模型绘制要耗费大 量的计算资源和时间，因此在粒子系统的实时真实感绘制过程中必须寻求快速高效的 绘制方法。纹理映射和混合是解决这个问题很好的一种途径。 1 2 4 随机过程法 随机过程法【6 】主要包括参考轴技术、多尺度自动机及双尺度自动机等植物生长建 模方式。基于有限自动机的参考轴技术，是将理论上的植物轴描述成参考轴，它包括 植物从种子到开花可能经历的所有不同阶段，每个阶段对应一个给定的生理年龄，该 5 第一章绪论面向太湖流域虚拟森林的建模与实现 轴是沿着逐步前进的方向变化的，在计算机程序中使用有限自动机的结构表示参考 轴，自动机的状态与参考轴的不同阶段相联系，利用马尔代夫链理论和状态转换图方 式描述植物的发育、生长、休眠、死亡等过程。在此基础上又产生了多尺度自动机和 双尺度自动机模型，多尺度自动机能够以不同的时间尺度描述植物的拓扑结构，该建 模方法数据输入简单、过程分析直观、物理意义明确。双尺度自动机 1 2 , 1 3 】是在自动机 模型的基础上结合随机建模思想，根据植物的生理年龄来组合植物的生长参数，以更 为简单、通用的图形方式表示各种植物构造模型，能更有效地模拟真实植物的生长过 程。它将植物表示成宏状态和微状态两种，植物的叶元( 节、节间及节上的侧生器官 的集合) 定义成个微状态，宏状态则是由微状态组成。宏状态的循环对应着生长单 元在植物轴上的周期性生长。双尺度自动机模型通过微状态和宏状态的组合和循环来 模拟植物的生长过程，生成植物的拓扑结构。 1 3 太湖流域森林特征 森林环境是地理环境的重要组成部分，是以森林为主体、与一定地理条件结合的 地理空间。目前全球陆地仅覆盖了2 5 的森林，原生林所剩无几，被大面积的次生林、 人工林所替代。我国森林覆盖率由新中国成立初期的8 6 提高到1 8 2 1 ，居世界前 列，人工林保存面积达8 亿多亩。由于地域表面自然环境条件并非均匀一致，植被的 类型及分布状况也十分多样，决定植被分布的重要条件是气候，主要是热量、水分及 其配合状况。地球上的气候条件按纬度、经度与高度这三个方向改变，植被也沿着这 三个方向交替分布。太湖流域地跨北亚热带与中亚热带，农业开发历史悠久，广大平 原地区以栽培植被为主，丘陵山地现存自然植被大多是次生性，但仍具有明显的地带 性分布规律。太湖流域从北向南气温、雨量递增，植被的种类组成和类型逐渐复杂。 宜尖、溧阳以北的北亚热带典型地带性植被类型为落叶、常绿阔叶混交林，此线以南 的中亚热带典型地带性植被类型为常绿阔叶林。由于垂直分布和自然植被的高度次生 性，常见落叶阔叶林和落叶、常绿阔叶混交林的跨带分布现象【1 4 1 。 常绿阔叶林树木的叶片革质，有光泽，表面无茸毛，所以又称为照叶林或樟叶林。 组成常绿阔叶林的树木以樟木、壳斗科、山茶科、木兰科、金缕梅科的树种为典型代 表。树皮深色而粗糙，枝端的芽有鳞片保护以度过寒冷的冬季。树木叶片中等大小， 6 面向太湖流域虚拟森林的建模与实现第一章绪论 椭圆，渐尖，叶片排列方向与太阳光线垂直，树冠表层的叶子多少有早生结构。在群 落外貌上，林冠比较整齐，色彩比较一致，常年以暗绿色为主。 落叶阔叶林又称夏绿木本群落，是温带湿润海洋气候条件下的森林群落。其分布 地气候的特点是四季分明，夏季炎热多雨，冬季寒冷。由于植物生长季节内水、热条 件充分，使植物有可能繁盛发育，落叶树叶的质地较薄，无革质，通常无茸毛，呈鲜 绿色。树干和枝条都有厚的皮层，也常受树脂保护，芽有坚实的芽鳞。代表的树种有 桦属、赤杨属、杨属、柳属等。 1 4 主要工作 目前，人工林已成为全国森林资源重要的组成部分，在我国的经济建设和生态环 境保护中发挥着巨大的作用。传统的森林经营方法是通过森林资源调查，对调查数据 统计、分析得出一些文字、图标或简单的二维表格作为森林调查资料的最终表现形式。 但随着森林经营集约程度的不断提高，人们对森林动态信息的要求也日益增多。为了 更直观、形象、真实的反映现实森林的生长状况、空间结构以及预测森林的发展趋势， 虚拟森林环境的构建研究应运而生，并受到越来越多有识之士的热切关注。 本文的研究工作主要包括以下几个方面： ( 1 ) 提出了基于环境敏感型植物的虚拟森林模型。该模型包括了虚拟植物模型、 虚拟植物模拟器、环境模拟器、环境模型和环境因子( 阳光、温度等) ，将建模与实 现分开处理，为虚拟森林今后的功能扩展奠定了基础。 ( 2 ) 利用基于二叉树的l 系统构建虚拟植物。l 系统反映了植物的并行生长特 征，该系统应用广泛，描述具有分形结构的植物是非常合适的，但是l 系统的字符串 表示存在难以理解和使用的缺点。功能扩展了的各种l 系统虽然可以描述更加复杂的 自然物体，但这种用字符串表达的形式语言在产生式中将植物的几何结构信息和拓扑 结构同时描述，理解和使用都比较困难，特别是在植物生长完成后，调节部分字符来 改变植物生长状态是非常繁琐的。森林的一个显著特征就是其中植物个体数量之多， 因此，l 系统的描述速度直接影响整个系统的执行效率。本文从l 系统底层的存储结 构出发，提出了新型的基于二叉树的存储结构。该结构在模拟环境对植物的影响过程 中，缩小了上下文搜索范围，提高了虚拟植物的重绘速度。 7 第一章绪论 面向太湖流域虚拟森林的建模与实现 ( 3 ) 利用遗传算法构建虚拟植物模拟器，模拟自然界中植物个体间优胜劣汰的 竞争关系。目前关于虚拟森林的研究大多数停留在通过林业中的统计数据重现森林在 某一具体时刻的状态，对于实现其模拟森林动态生长全过程却未有深入研究。本文受 达尔文生物进化论思想启发，借鉴自然界的选择和进化机制，从植物种群着手，利用 遗传算法构建了虚拟植物模拟器，为实现虚拟森林的反演过去、再现现实、预测未来 的功能提供了实现手段。 1 5 论文结构 第一章绪论，主要介绍虚拟森林技术的国内外研究现状，目前比较流行的虚拟 植物建模技术以及本文的主要工作。 第二章相关理论基础，主要介绍了分形，l 系统及层次细节等相关理论。 第三章虚拟植物模型，主要介绍了树木构筑概念及虚拟植物的数据结构、建模 方法和枝条弯曲模型。 第四章虚拟森林环境建模，主要介绍基于环境敏感型植物的虚拟森林模型，该 模型包括了虚拟植物模型、虚拟植物模拟器、环境模拟器、环境模型和环境因子。 第五章系统的实现与分析，主要介绍了系统的软硬件环境和实验效果。 第六章总结与展望，主要介绍了本文完成的工作及对将来工作的展望。 面向太湖流域虚拟森林的建模与实现第二章相关理论基础 2 1 分形 2 1 1 分形的起源 第二章相关理论基础 自两千多年前希腊人欧几里得( e u c l i d ) 创立了几何学以来，人们对某个数学集 合，总是习惯于在e u c l i d 空间( r ”，e u c l i d e a n ) 对其研究和度量，其中字母n 表示该 空间的维数，通常它是一个整数。对于有限个点，取”= 0 ；一条线段或一条平面上 的曲线，取疗= 1 ；一个有限平面，取刀= 2 ；有限的空间几何体，则取刀= 3 ，同时也 可分别得到它们的定常度量。但在一个世纪以前，相继出现了一些被称之为“数学怪 物”( m a t h e m a t i c a lm o n s t e r s ) 的现象，这些现象无法用传统的e u c l i d 几何语言去描述 它们的局部和整体性质，典型的“数学怪物 有以下几种【1 5 】： 1 冯科克( v o nk o c h ) 曲线 1 9 0 4 年瑞典数学家v o nk o c h 设计了一条被称之为k o c h 曲线的图形，其设计步 骤如下：设岛为单位区间【o ，1 】，第一步，即胛= 1 ，以厶的中间三分之一线段为底向 上作一个等边三角形，然后去掉区间( 1 3 ，2 3 ) ，得到一条四折线段的多边形e 。； 第二步，即n = 2 ，对e ，的四条折线段重复第一步的过程，得一条十六折线段多边形 e ：；以此类推，由e 。到e ，当聆趋于无穷时，便得到了一条k o c h 曲线，如图2 - l 所示。 图2 - 1k o c h 曲线 9 第二章相关理论基础面向太湖流域虚拟森林的建模与实现 k o c h 曲线在( r i , e u c l i d e a n ) 中的长度如式( 2 1 ) 所示。 l e n g t h ( e o ) = 1 l e n g t h ( e 1 ) = 4 3 l e n g t h ( e 2 ) = 1 6 9 l e n g t h ( e ) = l i m ( 1 e n g t h ( e n ) ) = l i m ( 4 3 ) ”= o o n - - a o n ( 2 1 ) k o c h 曲线在一维e u c l i d 空间的度量为0 0 ，在( r 2 ，e u c l i d e a n ) 中其面积为o ， 换而言之，k o c h 曲线在传统的e u c l i d 几何领域不可度量。 2 希尔宾斯基( s i e r p i n s k i ) 三角形 由波兰数学家s i e r p i n s k i 命名的三角形，又称s i e r p i n s k i 筛、s i e r p i n s k i 垫片等。 令瓯为边长为1 的等边三角形，第一步，即刀= l ，连接三条边的中点，得到四个全 等三角形，去掉中间一个，保留其余三个，得s ；第二步，即n = 2 ，对s 的三个三 角形重复第一步过程，得s ：，含有9 个小三角形；以此类推，得s 。，当刀趋于无穷 大时，得到s i e r p i n s k i 三角形，如图2 2 所示。 图2 2s i e r p i n s k i 三角形 在( 天1 ，e u c l i d e a n ) 中，由于n o 。时，原先的黑色三角形变成了无穷个小点， 故每个小点的边缘长度之和l e n g t h ( s ) = l i m 3 ( 3 2 ) ”= o o 。在( r 2 , e u c l i d e a n ) 中，& 挣呻 1 0 面向太湖流域虚拟森林的建模与实现第二章相关理论基础 面积为3 4 ，以后每一步都分四留三，所以s i e r p i n s k i 三角形的面积 a r e a ( s ) = l i m 3 4x ( 3 4 ) ”= 0 ，同样，在传统的e u c l i d 几何里，s i e r p i n s k i 三角形不 i - i , a a 可度量。 上述两个“数学怪物”都是由数学家创造出来的，在自然界中同样有这种不可思 议的现象存在。气象学家理查森( r i c h a r d s o n ) ( 1 8 8 1 1 9 5 3 ) 在测量英国海岸线长度 时，发现了一个规律：绘制地图的比例尺由大变小时，如由l c m 代表l o o k m 减小到 l c m 代表l k m 时，海岸线长度却变得越来越长。令a 为比例尺度，s 为海岸线长度， s 为口= 1 0 0 0 时的长度，则英国西海岸线长度s 的对数如式( 2 2 ) 所示。 l o g s = l o g s l 一0 2 2 1 0 9 a ( 2 2 ) 根据式( 2 2 ) ，海岸线长度实际上是不确定的。由此可知，在自然界中也存在 着不能用e u c l i d 几何来描述的现象。 2 1 2 分形的定义 2 0 世纪7 0 年代美籍法国数学家曼德勃罗( b e n o i tm a n d e l b r o t ) 在对“数学怪物 及许多物理和经济现象进行研究后，创立了分形几何( f r a c t a lg e o m e t r y ) 。他打破了 传统e u c l i d 几何的整数维空间的思想束缚，得到了空间维数d 的表达式： d = - ( i n n i n r ) ( 2 3 ) 对k o c h 曲线而言，在第胛步时，其等长折线总数为4 ”，每段长度为( 1 3 ) ”，于 是k o c h 曲线的维数d 应为： d = 一l i l 4 ”l h a ( 1 1 3 ) ”= l n 4 l n 3 1 2 6 1 8 6 ( 2 - 4 ) s i e r p i n s k i 三角形的维数为： d = l n 3 l n 2 1 5 8 4 9 6( 2 5 ) 对于英国西海岸，曼德勃罗将其维数确定为d = 1 2 5 。 分形来源于拉丁文f r a c t u s ，其英文意思是破碎的。曼德勃罗想用此词来描述 自然界中传统欧氏几何学所不能描述的一大类复杂无规则的几何对象，例如，蜿蜒曲 折的海岸线、起伏不定的山脉、粗糙不堪的断面、变幻无常的浮云、九曲回肠的河流、 第二章相关理论基础 面向太湖流域虚拟森林的建模与实现 纵横交错的血管、令人眼花缭乱的满天繁星等。它们的特点是极不规则和极不光滑。 1 9 7 5 年，曼德勃罗在巴黎出版了法文著作( l e so b i e c t sf r a c t a l s ：f o r m e ，b a s a r de t d i m e n s i o n ) ) ，1 9 7 7 年在美国出版了其英文版( f r a c t a l ：f o r m ，c h a n c e ，a n dd i m e n s i o n ， 它们都可译为分形，机遇和维数。1 9 8 2 年，随着( t h ef r a c t a lg e o m e t r yo f n a t u r e ) ) 第二版的问世，在美国乃至欧洲，迅速形成了“分形热。 分形迄今为止还没有一个严格的定义，本文引用k f a l c o n n e r 对分形集合f 的描 述1 5 】： ( 1 ) f 具有精细的结构，即可以说在任意小的尺度下，它总有复杂的细节； ( 2 ) f 是如此的不规则，以至它的整体和局部都不能用传统的几何语言来描述； ( 3 ) f 通常具有某种自相似性，这种自相似性可以是近似的，也可能是统计意 义上的； ( 4 ) f 在某种意义下的分形维数通常都大于它的拓扑维数； ( 5 ) 在多数令人感兴趣的情况下，f 以非常简单的方法定义，或许以递归过程 产生。 2 1 3 分形的测度和维 1 h a u s d o r f f 测度与维 在被使用的各种“分形维数”中，以c a r a t h e o d o r y 构造为基础的h a u s d o r f f 定义 是最古老的也可能是最重要的一种。h a u s d o r f f 维数具有对让任何集都有定义的优点， 由于它是建立在相对比较容易处理的测度概念的基础上，因此数学方面也较方便。主 要缺点是在很多情形下用计算的方法很难计算或估计它的值17 1 。 ( 1 ) h a u s d o r f f 测度 设u 是疗维e u c l i d 空间r ”的任意非空子集，u 的直径iuj 定义如式( 2 6 ) 所示： i u l - s u p i x - - y l l ：x ，y 研，( 2 6 ) 即u 中任意两个点的最大距离。 如果集合fcu 配，且v 的最大直径为万，即oq 峰6 ，则说 是，的一个 艿一覆盖。假定f 是r ”的子集，p 是非负数，对任意的万 0 ，定义 1 2 面向太湖流域虚拟森林的建模与实现第二章相关理论基础 日多( f ) = i n f tu , l p ： q 是州临一覆盖) ( 2 - 7 ) 并约定空集i 囝i p = 0 。当万递减时，式( 2 - 7 ) 的下界是非递减的。记 日p ( f ) = l 洲i m 群( ，) 称日，( ，) 为集合f 的p 维h a u s d o m 测度1 引。式( 2 - 8 ) 的一个等价定义是 定理1 ( 定比性) 如果fcr ”且五 0 ，则 h p ( 兄f ) = 五p h p ( ，) 式( 2 1 0 ) 中力f = 2 x ：工f ) 定理2 设f c r ”，f ：f 专r ”是一个具有以下性质的映射 ( 2 8 ) ( 2 9 ) ( 2 1 0 ) f ( x ) - f ( y ) i o , a 0 ，则对于每个p ，有 h p , 2 ( 厂( ，) ) c p h p ( ，) ( 2 1 2 ) ( 2 ) h a u s d o r f f 维 对于任意给定的集合f 和万 p 且 u 是f 的万一覆盖，有 从而有 i uf - - e l qr u ii t - p g 卜p i l 尹 ( 2 - 1 3 ) ji， 珥( f ) 叩彤( f ) ( 2 1 4 ) 令万专0 ，若o 日尹( f ) ，必有磁( f ) 万卜，蟛( f ) 。同理可证，当f p 时，若万专。 时，0 h p ( f ) o o ，必有( ，) = 0 0 。存在一个临界点p ，在p 点上，h p ( f ) 从0 0 降 为零，这个临界值称为f 的h a u s d o r f f 维数【1 8 1 ，记为d i m 日f ，也称其为 第二章相关理论基础面向太湖流域虚拟森林的建模与实现 h a u s d o r f f - b e s i c o v i t c h 维。 2 盒维( b o xd i m e n s i o n ) 盒维 1 5 j 8 】是应用最广泛的维数之一，它的普遍应用主要是由于这种维数的数学计 算及经验估计相对容易一些。对这种定义的研究可追溯到2 0 世纪3 0 年代，并被冠以 其他名称，如k o l m o g o r o v 熵、熵维数、容度维数、度量维数、对数密度和信息维数 等。 设，是只”中任一非空有界子集，记为n ( f ，万) 表示最大直径为万且能覆盖f 集合 的最小数，则f 的上下盒维定义为 d i m bf ：l i mi n n ( f , 6 ) ( 2 1 5 ) 占，o i n ( 1 们 d i m 。f ：l i m i n n ( f , 6 ) ( 2 1 6 ) 。5 - + 0 i n ( 1 万1 如果上下维相等，则，的盒维定义为 d i m bf = l 湖i m 酱篇 协 式( 2 1 5 ) 与式( 2 1 6 ) 中的上下极限定义为 期厂( j ) 2 烛s u p 厂万) ：o 万 ，) ， ( 2 1 8 ) l i m f ( a ) = f i m i n f f ( j ) ：0 0 ，令n ( a ，s ) 表示覆盖彳所 需要的以占 0 为直径的闭球的最小数目，如果式( 2 1 9 ) 存在，则d 就叫做a 的分 形维( f r a c t a ld i m e n s i o n ) ，简称分维并记为d = d ( 4 ) i s 】。 d ：i i m i nn ( a , e ) 。o i n ( i ) 1 4 面向太湖流域虚拟森林的建模与实现第二章相关理论基础 2 2l 系统 自然界中的大多数植物都具有分形性质。维数在常青藤的1 2 8 和车轮藤( 蔷薇 科的矮树) 的1 7 9 之间，全品种的平均维数约为1 5 1 1 4 1 。随着计算机图形学的发展， 人们一直在探讨用计算机模拟生物各种形态的可能性，分形最基本的性质是自相似 性，这个基本性质为分形图形的计算机模拟提供了理论基础。l 系统是目前用于模拟 植物形态最成功的系统之一。 2 2 1l 系统的定义 l 系统的第一个字母l 源于美国生物学家a l i n d e n m a y e r ( 1 9 2 9 1 9 8 9 ) 姓氏中的 l 字母【1 9 1 。开始是作为描述植物的形态与生长的一种方法，继而发展成计算机图形学 中一种模拟大自然景物的有效方法，是一种重要的分形生成方法。l 系统实质上就是 一个并行重写系统，其核心概念是重写，重写的基本思想是根据预先定义的重写规则 ( 生成规则) 集不断地生成复合形状并用它来取代初始简单物体的某些部分以定义复 杂物体。 如图2 3 所示的过程可归结为如下的形式化定义： 令y 表示字母集，y 表示矿上所有单词( 由符号或字符组成的字符串) 的集合， 一个字符串0 l 系统是一个有序的三元组g - - ，这里缈是一个非空单词，称 为公理( 也称为起始元) ，尸是产生规则的有限集合，产生规则写作d 专x ，字母口和 单词x 分别称为产生式的前驱和后继。规定对任何字母口y ，至少存在一个非空x ， 使得a 专x 。若对给定的前驱a 矿无明确的产生式，则规则a 寸a 这个特殊的产生式 属于p 。对每个口矿，当且仅当有非空单词z ，使得口一x ，则认为0 l 系统是确定 的，记作d o l 系统。 第二章相关理论基础 面向太湖流域虚拟森林的建模与实现 a a b a b