（计算机应用技术专业论文）真实感树木实时绘制研究.pdf

辽宁科技大学硬士论文 摘要 摘要 真实感树木实时绘制研究一直以来都是计算机图形学的一个热点领 域，因为树木复杂的细节结构使其无论是在建模、存储还是绘制上都存在 相当大的困难。真实感实时绘制有两个指标：真实感和实时性，而这两个 指标往往又是一对矛盾。 在真实感方面，本文根据树木在宏观形态结构上是由主干、分枝和树 叶构成的分层结构，提出了一种描述树木各枝条之间关系的拓扑结构。在 此基础上，利用三次b 样条曲面中光滑闭合曲线的绘制功能来构造枝条的 表面。将每棵树枝的表面视为一个柱面，按照枝条间的关系将不同柱面连 接在一起形成一棵完整的树木。树木的纹理主要通过表面颜色纹理来完 成。树叶则采用纹理映射以及b m p 图透明处理相结合的方法来绘制，能够 达到较高的真实感效果。 在实时性方面，本文提出了一种基于动态i m p o s t o r 技术的树木绘制 方法。这种方法首先基于树木模型进行平面投影去创建i m p o s t o r 平面， 然后将纹理映射到已经创建好的i m p o s t o r 平面上，最后通过绘制 i m p o s t o r 纹理平面形成树木图像；并且当参考视点进行移动时，可以根据 误差来决定是否动态更新i m p o s t o r 平面的内容。此外，利用存点的思想， 将一棵树木的模型视图坐标、纹理坐标、基本面的法线坐标等存入数组然 后改变其树木的模型视图坐标，读出数组的点建立一棵新树木从而完成多 棵树木的快速绘制工作。 关键字：真实感，实时，树木绘制 辽宁科技大学硕士论文 a b s t r a c t r e s e a r c ho nr e a lt i m er e n d e r i n go fr e a l i s t i ct r e ei saf o c u sf i e l do f c o m p u t e rg r a p h i ca l lt h et i m e b e c a u s ec o m p l i c a t ed e t a i l s t r u c t u r eo ft r e e m a k e si tv e r yd i f f i c u l tt om o d e l ，s t o r e ，r e n d e r i n g r e a lt i m er e n d e r i n go f r e a l i s t i ch a st w oi n d e x e s ：r e a l i s t i ca n dr e a l t i m e ，a n dt h et w oi n d e x e sa r eo f t e n ap a i ro fc o n t r a c t i o n s i nr e a l i s t i c ，b a s e dt h a tt r e ei sf o r m e dh i e r a r c h i c a ls t r u c t u r eb yt r u n k ， b r a n c ha n dl e a fo nt h em a c r o s c o p i c a ls h a p es t r u c t u r e ，t h i sp a p e rp r e s e n t sa t o p o l o g i c a l s t r u c t u r ew h i c hd e s c r i b e st h e r e l a t i o n s h i p b e t w e e na l lt h e b r a n c h e s o nt h i sb a s i s ，i tu t i l i z e sd r a w i n gf u n c t i o no fs m o o t ha n dc l o s ec u r v e o ft h r e eb s p l i n ec u r v es u r f a c et oc o n s t r u c tt h es u r f a c eo fb r a n c h r e g a r d st h e s u r f a c eo fe v e r yb r a n c ha sac y l i n d e r ，a n dm a k e st h ed i f f e r e n tc y l i n d e rl i n k t o g e t h e ra c c o r d i n gt ot h er e l a t i o na m o n gt h eb r a n c h e st of o r ma ni n t a c tt r e e t h et e x t u r eo ft r e ei sm a i n l yf i n i s h e sb ys u r f a c ec o l o rt e x t u r e l e a v e sa d o p t t h em e t h o do f c o m b i n i n gt o g e t h e r t e x t u r e m a p p i n g a n db m pp i c t u r e t r a n s p a r e n c ed i s p o s a lt or e n d e r i n g ，w h i c hc a nr e a c hh i g h e rr e a l i s t i ce f f e c t i nr e a l - t i m e ，t h i sp a p e rp r e s e n t sam e t h o do nt r e e r e n d e r i n gb a s e d d y n a m i ci m p o s t o rt e c h n o l o g y t h i sm e t h o df i r s t l yp r o j e c t s t ot h ep l a n et o c r e a t et h ep l a n eo fi m p o s t o rb a s e dt r e em o d e l ，s e c o n d l ym a p st h et e x t u r eo n t h ep l a n eo fi m p o s t o rw h i c hh a sc r e a t e d ，t h i r d l yf o r m st r e ei m a g et h r o u g h r e n d e r i n gi m p o s t o rt e x t u r ep l a n e w h e nr e f e r e n c ev i e w p o i n tm o v e s ，i tc a n d e c i d ew h e t h e rd y n a m i c a l l yu p d a t et h ec o n t e n to fi m p o s t o rp l a n ea c c o r d i n g e r r o rm e t r i c i na d d i t i o n ，i tu t i l i z e st h et h o u g h to fs t o r ep o i n t ，s t o r e sm o d e l v i e wc o o r d i n a t e ，t e x t u r ec o o r d i n a t e ，n o r m a lc o o r d i n a t eo fb a s i cp l a n eo ft r e e i nt h ea r r a yt oc h a n g em o d e lv i e wc o o r d i n a t eo ft r e e ，a n dr e a d sp o i n to ft h e a r r a yt oc r e a t ean e wt r e et of i n i s ht h ef a s tr e n d e r i n gw o r ko fm a n y t r e e s k e y w o r d s ：r e a lis t i c r e a it i m e t r e er e n d e r i n g 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得辽宁科技大学或其它教育机构的学位或证书而使用过的材料，与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 签名：槛日期：丛：! ：墨苎： 关于论文使用授权的说明 本人完全了解辽宁科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅：学校 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手 段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 褴薤导师签名：窭鹾泼日期：趔3 ：三：丛 辽宁科技大学硕士论文第一章绪论 第一章绪论 1 1 真实感实时绘制概述 真实感实时绘制是在当前图形算法和硬件条件限制下提出的在一定 时间内完成真实感绘制的技术。基于场景几何和光照模型，在计算机中 生成真实感图形，重现真实世界场景的过程称之为真实感绘制他1 。“真实感” 的涵义包括几何真实感、行为真实感和光照真实感，并且实现的难度是依 次递增的。几何真实感指与描述的真实世界中对象具有十分相似的几何外 观；行为真实感指建立的对象对于观察者而言在某些意义上是完全真实 的：光照真实感指模型对象与光源相互作用产生与真实世界中亮度和明暗 一致的图像。而“实时”的涵义则包括对运动对象位置和姿态的实时计算 与动态绘制，画面更新达到人眼观察不到闪烁的程度，并且系统对用户的 输入能立即做出反应并产生相应场景以及事件的同步。由于要描述的真实 世界的复杂性和软、硬件等条件的约束，目前真实感实时绘制都存在一定 的不足之处：通过损失一定的实时性能来达到绘制真实感的目的或者通过 损失一定的真实感性能来达到实时绘制的目的。 真实感绘制是一种计算机图形生成技术，它首先在计算机中构造出所 需场景的几何模型，然后根据假定的光照条件，计算画面上可见的各景物 表面的光亮度，使观者产生身临其境，如见其物的视觉效果。真实感绘制 的主要任务是要模拟真实物体的几何属性和物理属性，即物体的形状和动 作、物体间的相对位置、遮挡关系、光学性质、表面的纹理和粗糙程度。 光照技术则是真实感绘制的重点和难点，光学物理是真实感图形的重要理 论基础，因为真实感图形是通过景物表面的颜色和明暗色调来表现景物的 几何形状、空间位置以及表面材料的，因此必须建立合适的光照模型。已 有的光照模型大致可分为简单光照模型、局部光照模型和整体光照模型。 从绘制方法上看有模拟光线实际传播过程的光线跟踪法，也有模拟能量交 换的辐射度方法。依托一定的光照模型，就可以采用插值明暗处理技术、 阴影生成技术、透明混合技术、纹理映射和扰动技术对物体表面进行真实 辽宁科技大学硕士论文第一章绪论 感的刻画。3 。综上所述，用计算机生成真实感图形一般有以下四个步骤： 1 用数学方法建立所需的三维场景的几何描述，并将其输入至计算机； 2 将三维几何描述转换为二维透视图； 3 确定场景中的可见面： 4 计算场景中可见面的颜色，也就是基于光学物理的光照物理和光照模 型，计算可见面投射到观察者眼中的光亮度大小和色彩分量，将它们 转换成适合图形的颜色值，并使用纹理和混合等技术绘制图元的细节， 从而确定投影画面上每一像素的颜色，最终生成图形。 实时绘制技术的研究重点是加速算法，力求能在最短时间内绘制出最 真实的场景。例如求交算法的加速、光线跟踪的加速、包围体、自适应八 叉树、二叉空间剖分都是著名的加速算法“”。 1 2 真实感实时绘制研究现状 真实感图形实时绘制主要有两个指标：一个是图形的真实感，即尽量 达到现实感觉的水平；一个是实时性，即至少能够达到满足人机交互所需 要的实时性。这两个指标往往又是一对矛盾。由于描述的几何模型所包含 的几何细节太丰富，因此，几何的绘制往往需要大量的计算时间，无法达 到交互实时。而现有的各种实时绘制方法又往往牺牲了大量的图形细节从 而降低了图形的真实感，因此真实感实时绘制成为一个难于解决的问题。 目前的真实感实时绘制技术主要有以下两种方法： 1 层次细节简化技术：l o d ( l e v e lo fd e t a i l ) 几何场景模型中含有大量的可见面细节，但是其中许多可见面在屏幕 的投影小于一个像素，可以合并这些可见面而不损失绘制的效果。c l a r k 在1 9 7 6 年首次提出了层次细节技术的概念“1 。层次细节就是在保证一定相 似度、不影响画面感知效果的条件下，从物体场景的几何模型出发，通过 逐次简化景物的表面细节来减少场景的几何复杂性，也就减少了需要绘制 的场景面片数目，从而提高绘制算法的效率。层次细节简化的目的是为了 对多边形模型或场景进行多分辨率表示，即在应用中依据模型和视点的距 离，通过选择适当分辨率的模型表示来进行绘制”1 。如果模型离视点较远 辽宁科技大学硕士论文第一章绪论 且在屏幕空问的投影区域覆盖较少的像素，则用粗糙的模型来进行表示； 如果模型离视点较近，则采用精细的模型进行绘制。对于较复杂场景而言， 这种方法不仅可以减少场景的复杂度，同时对于生成真实感质量的损失还 可以控制在给定的阈值以内，而且生成图形的速度也可以大幅度的提高。 主要的步骤如下： ( 1 ) 建立不同层次细节的模型，对任意给定的复杂多边形网格m ，由精细至 粗糙建立模型序列：m 。、m 。、m 。； ( 2 ) 建立相邻层次多边形网格m i 、m 。( 0 i n ) 之间的几何形状过渡： m i _ m “1 。 但是，需要注意的是，当视点连续变化时，在两个不同层次的模型之 间就存在一个明显的跳跃，有必要在相邻层次的模型之间形成光滑的视觉 过渡，称之为几何形状过渡，使生成的真实感图形序列在视觉上是光滑的 0 】 o 2 基于图像的绘制技术 基于图像的绘制技术是从一些预先生成好的真实感图像出发，通过一 定的插值、混合、变形等操作，生成不同视点处的真实感图像。在这种技 术中，不需要知道复杂场景的完全几何模型，需要的仅是与这个场景有关 的一些真实感图像，因而图形的绘制是与场景的复杂度是相互独立的，从 而彻底摆脱传统方法场景复杂度的实时瓶颈。它有着明显的特点： ( 1 ) 图形绘制独立于场景复杂性，仅与所需生成画面的分辨率有关； ( 2 ) 预先存贮的图像既可以是计算机合成的，亦可以是实际拍摄的画面， 而且两者可以混合使用； ( 3 ) 该绘制技术对计算资源的要求不高，因而可以在普通工作站和个人计 算机上实现复杂场景的实时显示。 基于图像绘制的方法能够达到很高的实时绘制质量，但是自身有不足 之处：只适用于静态光照的静态场景，不能改变模型外观、光照条件和反 射属性等；而且视点被限制在一定范围内。 基于图像的绘制技术主要有两类： ( 1 ) 全景技术 3 辽宁科技大学硕士论文第一章绪论 在一个场景中选择一个观察点，用相机或摄像机每旋转一下角度拍摄 得到一组照片，再采用各种工具软件拼接成一个全景图像，它所形成的数 据小，对计算机要求低，适用于桌面型真实感绘制系统中，建模速度快， 但一般一个场景只有一个观察点。因此交互性较差。 ( 2 ) 图像的插值及视图变换技术 根据在不同观察点所拍摄的图像，交互地给出或自动得到相邻两个图 像之间的对应点，采用插值及视图变换的方法求出对应于其他点的图像， 生成新的视图，根据这个原理可实现多点漫游。 1 3 真实感实时绘制的应用价值 真实感实时绘制的应用领域非常广阔，它的影响正迅速地向工业生产 和社会生活的各个领域渗透，可以预料在未来社会里它必将发挥更为重要 的作用。 计算机动画是真实感实时绘制技术的一个重大应用领域。在电影和电 视广告中，要达到某些特定的效果，往往需要进行许多次的试验和拍摄。 那些危险场面、破坏场面和需要动物配合的场面不但令电影工作者们非常 为难，而且提高了电影的制作费用，还可能对人员造成伤害。另外，有些 事物和景象更是现实世界无法找到的，比如科幻片或者灾难片，无法实景 拍摄。通过计算机实时绘制出高度真实感的场景，这些困难都可以方便地 解决。可以说，真实感实时绘制技术给影视工作者和艺术家提供了一个尽 情发挥想象力的舞台。 虚拟现实是当前的一个热门研究课题，它在飞行训练、战斗模拟、计 算机游戏等许多领域具有十分广阔的应用前景。真实感实时绘制技术是基 于图形的虚拟现实的核心技术之一，直接关系到人机交互速度和图像输出 质量。 科学计算可视化是当前的另一热门课题，它已在医学、地球科学、天 文物理、化学、机械工程等许多方面取得了巨大成就，将大批工程技术人 员和医务人员从大量繁琐的数据中解放出来。真实感图形实时绘制是科学 计算可视化的输出手段之一，绘制质量及速度将直接关系到工程技术人员 4 辽宁科技大学硬士论文第一章绪论 对原始数据的理解，具有突出的现实意义。 1 4 论文的研究内容及安排 论文的主要工作： 1 对树木建模的三种常用方法( i f s 方法、l 系统方法、粒子方法) 进行了 详尽的介绍： 2 通过对树木生态结构的分析，提出了一种描述树木各枝条之问关系的 拓扑结构。并且采用b 样条曲面来建立树木的三维几何模型，利用三 次b 样条曲面中光滑闭合曲线的绘制功能来构造枝条的表面。将每棵 树枝的表面都视为一个柱面，按照枝条间的关系将不同柱面光滑的连 接在一起形成一棵完整的树木，使得枝条间可以做到光滑连接，枝条 的几何形状更加逼近真实； 3 树木的纹理主要通过表面颜色纹理来完成，树叶则采用纹理映射和b m p 图透明处理相结合的方法来绘制，既体现了树叶的真实感又不影响绘 制速度； 4 提出了一种基于动态i m p o s t o r 技术的树木实时绘制方法，不仅可以实 时地绘制树木，而且具有较高的真实感效果。利用存点的思想，完成 多棵树木的快速绘制工作。 本文按照树木真实感建模、实时绘制的顺序展开论述，各章内容安排 如下： 第一章对真实感实时绘制技术做了简单而系统的概述，列举了一些前 人所做的工作，并阐述了本课题的主要研究内容和应用价值。 第二章对树木建模进行了理论性的描述。对于树木建模的三种常用方 法( i f s 方法、l 系统方法、粒子方法) 进行了详尽的介绍，并列举了每一 种建模方法的应用结果。 第三章介绍真实感树木的建模方法。根据树木在宏观形态结构上是由 主干、分枝和树叶构成的分层结构，提出了一种描述树木各枝条之间关系 的拓扑结构。在此基础上，采用b 样条曲面来建立树木的三维几何模型， 利用三次b 样条曲面中光滑闭合曲线的绘制功能来构造枝条的表面。将每 5 辽宁科技大学硬士论文第一章绪论 棵树枝的表面都视为一个柱面，按照枝条间的关系将不同柱面光滑的连接 在一起形成一棵完整的树木，使得枝条间可以做到光滑连接，枝条的几何 形状更加逼近真实。树木的纹理主要通过表面颜色纹理来完成。树叶是树 木真实感中重要的部分，也是树木组成的重要部分，采用纹理映射以及b m p 图透明处理相结合的方法绘制树木树叶，既体现了树叶的真实感又不影响 绘制速度。 第四章简要地讨论了各种加速树木绘制性能的技术，分析了这些方法 的优缺点。在此基础上，提出了一种基于动态i m p o s t o r 技术的树木绘制 方法，不仅可以实时地绘制树木，而且具有较高的真实感效果。这种方法 首先基于树木模型进行平面投影去创建i m p o s t o r 平面，然后将纹理映射 到已经创建好的i m p o s t o r 平面上，最后通过绘制i m p o s t o r 纹理平面形成 树木图像；并且当参考视点进行移动时，可以根据误差来决定是否动态更 新i m p o s t o r 平面的内容。此外，利用存点的思想，完成多棵树木的快速 绘制工作。 第五章简要地叙述了o p e n g l 的简介、发展历史、基本特征、工作机 制、数据处理过程等等。 第六章做出结论，对本文工作做出总结并指出今后的研究方向。 6 辽宁科技大学硕士论文第= 章树木建模方法 第二章树木建模方法 在树木模型的发展过程中，人们提出了各种各样的建模方法。目前较 为广泛应用的树木建模方法主要有3 大类分别是：i f s 方法、l 系统方法、 粒子方法。下面分别详细地介绍这些方法。 2 1if s 方法 h u t c h i n s o n 于1 9 8 1 年首先提出可以用压缩映射方法产生分形“”，1 9 8 5 年b a r n s l e y 发明了迭代函数系统i f s ( i t e r a t e df u n c t i o ns y s t e m ) 。针对 这个系统，b a r n s l e y 提出了一整套理论，派生了一系列算法规则，做了大 量开创性的工作，并将之运用于许多方面“。i f s 是以仿射变换为框架， 根据几何对象整体与局部具有自相似的结构，将总体形状以一定的概率按 不同的仿射变换迭代下去，直至得到满意的分形图形。i f s 的理论包括以 下几方面的内容：压缩映射、度量空间、不变紧缩集的存在以及测度理论 等。 迭代函数系统在物体的建模问题中具有很大的优势，特别是对自然景 物的计算机建模优势更为明显。迭代函数系统的理论和方法是分形自然景 观和分形图形压缩的理论基础，是分形几何学的重要分支之一，是分形图 形中最富生命力并有着广阔应用前景的领域之一。实际上，只需给出几个 仿射变换的系数，就可基本确定一个物体的迭代函数系统。正因为如此， i f s 在图形学中有着广泛的应用。 2 1 1 基本原理 定义1 仿射变换仿射变换是一种线性变换，一般会改变图形中向量的夹 角、点与点之间的距离、图形的面积等，但不改变共线、平行、相交、共 线点的顺序、中心对称、二次曲线的次数等。它可以将图形进行缩放、伸 7 辽宁科技大学硕士论文第= 章树木建模方法 长、剪切、扭曲等。变化w 舻- 帮具有形式为：i 。 三 乏 匡】+ i 】， 射变换当x 舻时，上式可写为w c x ，= a x + t ，其中a - 匡 乏】，t _ e ；a 和一个有限压缩映射集：睨：x x ，n = l ，2 ，n 组成，用i f s x ； w ：，n = 1 ，2 ，n ) 表示，则变换w 定义为：形p ) - u w ( b ) ，v b e x ( x ) 是 备空间( x ( x ) ，h ( d ) ) 上具有压缩因子s ( $ = n l a x s ；n = l ，2 ，n ) ) 的压缩 映射，即h ( w ( a ) ，w ( b ) ) 0 ，n = 1 ，2 ，n ，而每个概率只对应于变换睨，所以一个i f s p , 就是 x ； 形：只，n = l ，2 ，n ，一般情况下只由下式给定： p ，址。! 生尘二垒g l n 驴i 善m 一蚓 8 辽宁科技大学硬士论文 第= 章树木建模方法 2 1 2 一般l f s 的扫f 木建模 当确定了迭代函数系统i f s 代码参数后，生成分形图形的可运用随机 迭代法，大致可分为以下步骤： 1 给出概率分布 只，只 且满足号- 1 ； 2 任取一个初始点x o ； 3 产生一个随机数t ( o t o ， x ； 形，n = l ，2 ，n 是一个压缩仿射的i f s 码，其压缩因子为o s ，其中g 是字符集，这里g = f ，- f ，一， ， ) ；w 是起始符号， 用以确定字符串的初始状态且w g ，是g 上所有非空的单词集。此处w = “f ”；p 为该类植物的生成规则( 即替换法则) 集，是所谓产生式的有限集 合，产生式写作a x ，字母a 和单词x 分别称作产生式的前驱和后继。规 定对任何字母a v ，至少存在一个非空单词x ，使得a x 。若对给定的前 驱a v 无明确解释的产生式，则规定a a 这个特殊的产生式属于p 。对每 个a v ，当且仅当恰有一个非空单词x ，使a x 依据原理，按照一定的 重写规则，并加以参数控制，即可模拟植物的各种形态及其生长过程。此 1 9 辽宁科技大学硬士论文第= 章树木建模方法 处p = f f f + + f - f - f 卜 - f + f + f ，+ 一+ ，一一， 一 ， 一 ) 以”f ” 为种子，经过多次迭代，可以生成描述一颗树的字符串： 深度l 系统产生的字符串 of 1f f + + f - f - f 一 - f + f + f 2f f + + f - f - f j 一 一f + f + f f f + + f - f - f 一 一f + f + f + + f f + + f - f f 一 - f + f + f - f f + + f - f - f 一 - f + f + f - f f + + f - f f 一 - f + f + f 一 - f f + + f f - f 一 一f + f + f + f f + + f f f 一 一f + f + f + f f 以深度2 转深度3 为例，根据替换法则p ，在深度2 中f 用 “f f + + f f f 卜 一f + f + f ”代替，f f 贝0 变成“f f + + f f f 一 一f + f + f f f + + f f f 卜 一f + f + f ”，依此类推，便可得到如上表深度为3 的l 系统算 法产生的字符串，如图2 - 1 0 所示。 。叶 n = ln = 2n = 3 n = 4 图2 一1 0l 系统的树木实现 其算法简单描述如下： l 系统树木建模( d e p t h ) 每次读取字符串中的一个字符c h ； w h i l e ( c h ! = ” ”) s w i t c h ( c h ) ( c a s e “f ”：画线段： c a s e “+ ”：顺时针旋转； c a s e “一”：逆时针旋转； c a s e “ ”：纪录当前状态压栈；l 系统树木建模( d e p t h 一1 ) ； 2 0 辽宁科技大学硕士论文第= 章树木建模方法 ) 可是这样生成的树木效果并不理想，因为它的树枝和树叶没有区别 ( t g 可以说只有树枝没有树叶) ，生成的树也千篇一律。一般的解决办法是： 为每次迭代生成字符设置不同的参数。为此，对以上的算法做了一些小修 改：首先，在字符串“f f + + f - f - f - 一f + f + f ”中，把前两个“f ”看成 树干，用“g ”表示，字符串就成了“g g + + f - f - f 一 _ f + f + f ”，“f ”和 “g ”的替换相同。接下来，画树的过程中，把“f ”画成树叶，把“g ” 画成树干，并且让树干随d e p t h 的递减而变细。在样式方面，准备了三种 替换方案，在字符串替换时随机选择方案。这样生成的树木就生动多了。 有了字符串替换生成树木的思想后，还可以写出不同形态的树木的生成规 则。下面给出一些例子，以供参考： 图形编号初始符深度生成规则 图2 - 1 1 g6g ，g f x + + + + + g f g 一g f g x 一一f x f 图2 1 2 f6f - f + + + + + + + + + + + + + + + f - f 一一 一f f 图2 1 3x1 0x f + x f - x + x f f f 图2 1 4 x1 0x f + x - x f x f - f f 图2 一1 5y1 0x x - f f f + f f f f x f ，y f x + y i - v 图2 1 6 f5 f - f + f f - f f f f + f f 辽宁科技大学硕士论文 g - = 章树木建模方法 2 3 粒子系统 图2 - 1 1 图2 - 1 3 图2 - 1 5 图2 一1 2 图2 一1 4 图2 一1 6 粒子系统方法“7 1 是r e e v e s 在1 9 8 3 年提出来的，它是一种随机算法， 将单个形状简单的粒子作为景物造型的基本元素，通过这些粒子的位置排 列或运动效果来表示不规则的模糊景物，从而形成景物的动态变化。 辽宁科技大学硕士论文第= 章树木建模方法 r e e v e s 在1 9 8 5 年提出了基于粒子系统模拟树木的方法“”：树枝、叶 子等是基本粒子，树枝与树枝之间、叶子与树枝之间有复杂的连接关系， 通过随机递归算法，由一些简单的输入数据生成复杂的自然场景。根据这 种思想，可以用圆台状粒子组成树木的枝条，用小球状或小立方体粒子组 成树木的叶子，只要建立了这些粒子组合或排列的模型，就可以实现树木 形态结构的模拟，粒子在生命周期中的变化就会反映出树木生长发育最终 枯萎的过程。 基于粒子系统方法的树木形态结构模拟，关键是确定组成树木枝干和 树叶的粒子以及由这些粒子生成枝干和树叶的数据结构与算法模型“”。 根据树木枝干的结构特征，枝干骨架可以定义为一组由交互方式绘制 的枝干中轴线段的集合，如图2 - 1 7 所示。枝干端点的位置和枝干间的连 接关系采用二叉树结构来存储，如图2 - 1 8 所示。 图2 - 1 7 枝干骨架及其绘制顺序 雠e x t l lh f u n k l a y c r lll c h i i d 0 i ：降h 2 囝 2b l 0 旧3 卜纠 一表冢孛攒针 2 3 1 枝干生成模型 图2 1 8 枝干存储的数据结构 一个上、下底中点都在骨架线上的填充梯形，下底长为l ，高为h ，上 辽宁科技大学硕士论文第= 章树木建模方法 底缩短比例为k = 上底l ( o k 1 ) ，如图2 1 9 所示。 卜一l 一 图2 1 9 枝干生成粒子 生成算法如下： 1 遍历枝干的二叉树结构，取第一根枝干进入遍历序列； 2 从枝干的下端点开始向上堆砌梯形，直到上端点为止( 每一个梯形都以 前一个梯形的上底为下底画起) ； 3 如果所画的不是最后一根枝干，则取下一根枝干并调整下底和高返回 2 ，否则结束枝干生成。 算法的结果如图2 - 2 0 所示。 2 3 2 树叶生成模型 图2 2 0 树干生成示意图 根据不同的树种，树叶粒子可以是一条长度为l 的小线段：或者是一 个半径为r 的小圆；或者是一个边长为l 的小等边三角形；甚至是一束针 形的松树叶等。所有粒子的几何半径统一为r ，其位置参考点均为它们的 几何中心点。 生成算法如下： 1 遍历枝干的二叉树结构，取第一根枝干进入遍历序列； 2 以枝干的上端点为圆心，枝干骨架线为一边，确定一个半径为r ，圆 心角d 为的扇形区域： 辽宁科技大学硕士论文第= 章树木建模方法 3 以放置在枝干上端点位置上的粒子为种子，在扇形区域内实现粒子的 随机布朗运动并凝聚足够的粒子( 允许粒子有适当的放大倍数和旋转 角度) ； 4 如果生成的不是最后一根枝干的叶子，则取下一根枝干并返回2 ，否则 结束树叶生成。 算法的结果如图2 2 1 所示。 图2 2 1 树叶生成不意图 基于粒子系统方法的树木模型可从植物生长去描述，即从树高、树宽、 分枝及树叶去描述： 1 树高= 平均树高+ r a n d 0 树高变化量，其中平均树高及树高变化量与 树种有关，r a n d 0 是 - 1 ，1 上均匀分布的随机函数。 2 树宽= 树高( 平均树宽+ r a n d 0 树宽变化量) ，其中平均树宽及树宽 变化量也与树种有关，r a n d ( ) 也是 一1 ，1 上均匀分布的随机函数。 3 树的分枝有单分枝和双分枝两种模式，单分枝模式是指在树的节点上 生长出一条方向不同于主枝的枝叉，双分枝模式是指在树的节点上生 长出两条方向不同于主枝的枝叉。分枝角。是分枝与主枝的夹角，与 树种有关，随树的高度增加而减小。分枝关于其主枝的转角妒与树种有 关，一般毋的取值1 8 0 。、1 2 0 。、1 4 4 。、1 3 5 。 4 树枝( 包括主枝和分枝) 用圆台状粒子表示，树叶用小球状( 或小立方体) 粒子表示。 图2 2 2 是利用粒子系统模型生成的树木的粒子。图2 2 2 ( 1 ) 使用的粒 子是一个小圆圈，图2 2 2 ( 2 ) 使用的例子是一个小等边三角形。 辽宁科技大学硕士论文 g - 章树木建模方法 图2 2 2 ( 1 ) 小圆圈粒子树木模型( 2 ) 小等边三角形粒子树木模型 2 4 本章小结 树木模型一直以来都是人们研究的方向之一，本章详细地介绍了树木 的三类建模方法，它们分别是：模拟随机表面的i f s 方法、模拟树木生长 的l 系统和模拟不规则模糊景物的粒子系统。这三类方法在某种程度上反 映了9 0 年代在树木建模方面所取得的研究成果。其中，基于分形的l 系统 方法是这三种方法中最好的一个，它建模的效果最好。 辽宁科技大学硕士论文 第三章真实感树木建模 第三章真实感树木建模 3 1b 样条曲线曲面 3 1 1e 样条的定义 设x = “，而，) 为一向量，其中而 鼍+ l ，满足如下条件的函数n 为k 次( k + l 阶) 多项式样条函数，即： ( 1 ) 在每一子区间( 薯，鼍+ 。) 上，n 是k 次多项式； ( 2 ) n 在其1 阶、2 阶、k - i 阶导数处处连续。其中点x ；称为节点i ， x 称为节点向量。 b 样条是由一个称节点向量的非递减的参数序列t ：气f 1 。所 决定的k 次分段多项式，由下列递推关系： 哪) 一佬巍q + l ， 得妒基- m 糕- ( f ) o 舯蠊和橼， 双下标中，第一个下标i 表示b 样条的序号，第二个下标k 表示b 样条的 次数。若j 1 j 一j “- 一，+ 。d m ，则称从j 到，。d 的每一个节点为m 重 节点。递推公式表明任意k 阶b 样条可由两个相邻的k - 1 阶b 样条线组合 而成，如要确定一个b 样条m 。o ) ，需用到，。t 。共k + 2 个节点。 b 样条本身是一种样条，在计算机辅助几何设计领域内，b 样条又是 构造b 样条曲线的基函数。b 样条的特性直接影响b 样条曲线的特性，b 样条具有如下性质： ( 1 ) 局部性。v , j o ) 只有在区间( ，t 。) 中取正值，其他为0 ，每个区间 j ，