（计算机应用技术专业论文）草地场景的模拟与真实感绘制.pdf

摘要 摘要 本文主要讨论了自然场景特别是草地的模拟和绘制。草地的地形是通过人工 输入和随机分形的方法生成。植物在草地中的分布使用随机的方法。单株植物的 造型则是采用上下文有关的带参数的随机l 系统。我们为模拟植物生长而编写了 l 系统编译器来实现可定义规则的植物造型，并把随机因子和环境参数扩充到l 系统中。植物叶面的造型采用b e z i e r 参数曲线描述叶子中脉的形状，然后将叶 子的纹理图象嵌入到叶脉曲线的局部标架中。将造型好的地形、植物和其他参数 整合之后，采用多种先进的绘制手段如点采样技术、多分辨率技术等，绘制出具 有高度真实感的草地场景。文章的最后我们给出用上述方法模拟绘制的几种草地 场景，并指出进一步的研究方向。 关键词：自然场景模拟，l 系统，编译器，植物造型，多分辨率。 a b s t r a c t a b s t r a c t i nt h i sp a p e rw ed i s c u s sa na p p r o a c ho f m o d e l i n ga n dr e n d e r i n gn a t u r a ls c e n e s ， e s p e c i a l l yt h em e a d o w s c e n e t h et e r r a i ni sm o d e l e db yac o m b i n a t i o no fm a n u a la n d r a n d o mf r a c t a lm e t h o d p l a n t sa r e r a n d o m l y d i s t r i b u t e d t h r o u g h o u t t h et e r r a i n i n d i v i d u a lp l a n ti sm o d e l e dw i t hp a r a m e t r i ca n dr a n d o mc o n t e x ts e n s i t i v el s y s t e m w ed e s i g nac o m p l i e ro fp a r a m e t r i ca n dr a n d o mc o n t e x ts e n s i t i v el - s y s t e mt o s i m u l a t et h ed e v e l o p m e n to f p l a n t sa n di n t e r p r e tt h er u l e st h a td e c i d et h ew a yp l a n t s g r o w w ea l s oe x t e n d t h el s y s t e mw i t ht h ee n v i r o n m e n tf a c t o r w eu s eb e z i e rc u r v e s t od e s c r i b et h es h a p eo fl e a fm i d r i ba n de m b e dt h ei m a g eo fl e a fi n t ot h es p a c eo f l o c a lf l a r n e sa l o n gt h em i d r i bc n l w e a f t e rw ea d j u s tt h em o d e l so ft e r r a i na n dp l a n t s 谢mo t h e ri m p o r t a n tp a r a m e t e r s 。w eu s es o m et e c h n i q u e ss u c h 嬲s a m p l ep o i n t s ， m u l t i - r e s o l u t i o nt og e n e r a t et h ew h o l em e a d o ws c e n ew i t hh i g hs e n s eo fr e a l i t y s a m p l e s h a v eb e e ng i v e ni nt h ee n do ft h i sp a p e r , a n ds o m ef u t u r er e s e a r c hd i r e c t i o n s h a v eb e e n p o i n t e do u t k e yw o r d s ：n a t u r a ls c e n em o d e l i n g , l - s y s t e m ，s y n t a xe o m p l i e r , p l a n tm o d e l ， m u l t i - r e s o l u t i o n m o d e l i n g i i 第一章自然场景模拟综述 第一章自然场景模拟综述_ 帚一早曰蕊砌京俣t 以环硷 1 1 自然场景模拟的背景 覆盖大量植物的地表的场景绘制是计算机图形学领域一个富有挑战性且具 重要意义的课题。这些地表场景包括有自然生态系统( 如森林、草地等) ，人造 环境( 公园) ，中间环境等( 如对森林火灾或伐木后的荒地进行重新种植后的场 景) 。这一课题的难度源于地表场景的多样性和绘制场景的复杂度，而对此课题 的相关研究工作也具有重要的潜在应用领域，其中包括有g i s 、计算机辅助园林 设计、模拟用于研究和数学目的的生态系统模型、计算机动画中场景的合成、驾 驶与飞行模拟、游戏和计算机艺术等。 作为自然场景的重要构成部分，对植物对象例如草与树木进行有效的造型和 绘制一直都是图形学的研究热点。植物种类繁多，形态各异，复杂的结构使其无 论在造型、存储还是在绘制上都具有相当的难度。目前对草地模拟绘制的相关研 究开展较少，而对于绘制要求不高的场景通常只用二维纹理映射实现。 植物的造型和包含有植物的自然场景的模拟可以从很多角度来进行研究。例 如，重点可以放在：对某植物结构进行静态描述；生成植物生长的动画；控制 植物生长的物理力学方法的模拟；运用实验数据( 植物的具体测量值) 进行造型； 对造型过程进行人工控制：单一植物组织造型，仞j 如茎、叶、花和果实的造型： 开发植物造型软件，包含特殊的植物描述语言，对植物造型系统的可视化界面， 和有关模拟技术、数据组织和算法；基于照片的植物与自然场景的真实感绘制等 等。本文涉及到的工作主要有植物描述语言，对造型的人工控制和场景的真实感 绘制。 1 2 常用的植物造型和绘制技术 1 2 1 植物造型 随着计算机图形学的发展，自6 0 年代末起，人们在植物造型方面的研究工 作有了长足的进步。1 9 6 8 年l i n d e n m a y e r 提出了l 系统，并与p r u s i n k i w i c z 将 其用于树木及其它植物的造型【1 9 】；a n n o 和k u n i i 引入枝间的相互吸引、抑 制作用及其夹角的统计变化机制，对子干在主干上的分布作了详细的估算【2 】； 第一章自然场景模拟综述 d er e f f e e 等提，“格的植物学模型【7 】：h o l t o i l 还考虑重力的作用【1 4 】： o p p e n h e i m e r 运f _ j 分形技术对树木进行造型【3 1 】；r e e v e s 等用粒子系统方法模 拟森林【4 2 】；w e b e r 等从整体几何结构出发用参数对树木造型进行控制，并对 森林的绘制进行了探讨【4 6 。以上方法都取得了良好效果，植物造型的理论也 随之日益成熟起来。目前常见的植物造型方法可归纳为以下三类，即分形，粒子 系统和三维结构模型。 ( 一) 分形方法： 这是一种利用植物形态结构的分形性质( 结构自相似性) 产生植物图形或图 像的方法。其中主要有l 系统，i f s ( 迭代函数系统) 法和d l a ( 受限扩散凝聚) 模型法等。 l 系统以形式化的语言描述植物的结构和生长，用形式化语言的终结符与植 物结构相对应，由文法生成的句子代表植物，而句子生成的中间过程是植物的生 长发育过程。l 系统能简洁地描述植物的拓扑结构，例如枝条和花序结构，但较 难模拟复杂的植物形态。 迭代函数系统( i t e r a t e df u n c t i o n s y s t e m ) j 里论是h u t c h i n s o n ( 1 9 8 1 ) 和b a r n s l e y ( 1 9 8 5 ) 提出并发展的一种研究分形集的数学方法。i f s 可以定义为由一组能满 足一定条件的映射函数w i ( 例如收缩的仿射变换) 及一组变换发生的概率p i 组 成：i f s i = ( w i ，p i ) ，i = l ，2 ，n ) 。而利用i f s 生成植物图像的方法是对初始植物图 像，按照己知概率选择函数而实施的一种迭代变换。 d l a 模型，即受限扩散凝聚模型( d i f f u s i o n - - l i m i t e da g g r e g a t i o n ) 模型的 方法是：在一个平面网格上选定一个静止的微粒作为种子，然后在距种子较远的 格点上产生一个微粒，令微粒沿网格上下左右的方向随机行走。如果该微粒在行 走过程中与种子相碰，就凝聚到种子上：如果微粒走到边界上，就被边界吸收而 消失。如此重复上述步骤，就会以种子为中心形成一个不断增长的凝聚集团。利 用d l a 和其修改的模型可以对部分植物的形态结构进行模拟，例如植物根系的 生长过程模拟和海藻类植物的形态结构模拟等。 ( 二) 粒子系统( p a r t i c l es y s t e m ) 粒子系统方法是由w t r e e v e s 在1 9 8 3 年提出的，最初用于模拟火、烟雾等 自然现象，逐渐的被用于生成具有真实感的自然景物。其基本思想是采用许多形 第一章自然场景模拟综述 状简单的微小粒子( 例如点、小立方体、小球等) 作为基本元素来表示自然界中 不规则的模糊景物。粒子的创建、消失和运动轨迹由需要造型的物体的特性控制， 并由粒子的运动形成景物的动态变化。 根据这种思想，我们可以用圆台状粒子组成植物的枝条，用小球状或小立方 体粒子组成叶，只要建立了这些粒子组合排列的数学模型，就可以实现植物形态 结构的模拟。而粒子的运动变化就会反映出植物生长发育甚至死亡的过程。在大 多数里子系统的应用中，都会选取一些决定性的参数控制粒子的基本组合形态， 同时加入随机变量以引发必要的变化。如果用粒子系统对树进行造型，通常会有 3 0 个左右的基本参数用于控制分枝的角度和长度。 粒子系统的一个主要优点是由于其几何图元是点，所以易于迸行几何变换， 也易于在时间和空间上过滤粒子轨迹，因此易于实现反走样。其主要缺点是绘制 需要大量的基本图元和大量简单的元对象的集合，因此算法时间和空间复杂度较 高，而且必须有专用的阴影计算方法。 ( 三) 三维结构模型 三维结构模型是一种基于植物形态结构的三维几何描述的造型方法。目前这 一方法包括基于静态结构及其控制的几何设计方法和基于动态结构及其调节的 生长法两种。 几何设计法以一组几何描述量和描述规则产生植物的几何结构，并以此建立 植物的三维结构模型。这种模型以植物特定的分技模式为基础，使用分枝角、分 枝长度比例、吸引因子等参数，实施对植物几何结构的控制修改。这种方法能迅 速直观地产生植物形态结构，但依赖于设计者对植物外观的认识，而且不能产生 按时间顺序的生长序列，不能反映植物形态的发展变化。相对于几何设计法，动 态调节的方法能够生成一系列的植物外形，能表达出植物生命周期中各个时期的 外观形态，但亦存在着这一系列的植物造型中的每一个都较为粗糙的缺点。 1 2 2 植物绘制 随着植物造型理论的丰富与完善，如何有效的利用造型后产生的抽象数据进 行植物绘制，这一问题越来越得到研究者的重视。到目前为止，植物的绘制方法 可以大致分为如下三类： ( 一) 粒子系统绘制 4 2 1 第一章自然场景模拟综述 r e e v e s 等运用粒子系统所绘制的森林是早期计算机生成自然景物最有说服 力的例子之一，然而粒子系统构造的树木看起来有比较明显的人工痕迹，而且粒 子系统绘制的光照效果无法根据客观事实严格计算，因此缺乏高度真实感。 ( 二) 多边形绘制【2 3 ，2 4 】 多边形是绘制物体最常见的工具，对于可以用几何曲面定义的物体，尤其是 若它在屏幕上的投影面积比较大( 比如近距离阔叶树) ，通常可用多边形进行描 述。该方法适用于中低等复杂度的场景，但是不适于复杂度高的自然场景。由于 自然场景通常都高度复杂，一片山坡就可能包括成千上万的草的叶子，一棵树也 可能包含有数量巨大的不同形状不同方向的枝条和叶子，因此完全用多边形描述 这样的场景是非常困难的。 采用多边形进行绘制的优点在于，多边形绘制有着各种成熟的真实感图形绘 制手段，如各种光照模型，z b u f f e r 深度消隐和阴影生成方法、光线跟踪方法、 辐射度方法等。考虑到场景的复杂性，一般采用z b u f f e r 深度消隐和阴影生成方 法绘制近距离的阔叶植物。对于远距离的植物，w e b e r 等人采用模型简化的方法， 根据植物的远近采用多分辨率的绘制手段进行绘制【4 6 】。虽然w e b e r 提供的绘 制结果总体质量比较高，但是远处植物简化后颜色过于单一。 ( - - ) 三维体纹理绘制【6 ，2 8 - 3 0 1 9 8 9 年由k a j i a y a 和k a y 提出的纹元，是指用来近似表示许多微面总体光学特 性的一个三维参数数组。纹元数组空间中的任意一个纹元都存储着如下三个部分 的内容：密度标量p ，表示的是该体元包含的所有微面的近似投影面积；结构场 b ，表示的是该体元中各微面的局部方向；光照模型沙，它决定将有多少光线从 微面散射出来。作为三维数据场，纹元在绘制的时候采用的是体绘制技术。 体纹理是构造复杂场景的重要工具，上述的纹元就是一种特殊结构的体纹 理。同二维纹理一样，三维纹理使用的依据也是自然景物的重复性。相同物种在 形态和结构上通常都比较类似，比如相同品种的树木、杂草等。对每一品种的植 物构造有限个体纹理模型，再将这些体纹理映射到自然场景中，只要对纹理的映 射大小、形状和方向有一定的随机性以避免单一，这样构造出来的自然场景在视 觉效果上就相当接近真实场景。 三维纹理是最几年才被引入到植物的构造和绘制中，它的优点是可以简化场 景，消除几何面造成的混淆，使构造和准确绘制高度复杂的自然场景成为可能。 4 第一帝自然场景模拟综述 缺点则是由于绘制算法通常是结合体绘制技术的光线跟踪方法，实现比较复杂， 运算时间复杂度较大。 1 3 自然场景暨草地的模拟现状 1 3 1 真实感自然场景的造型与绘制 1 9 8 5 年，r e e v e s 和b l a u 创造了优美的森林和草地场景，并且应用在计算机动画 t h ea d v e n t u r e so fa n d r ea n dw a l l y 中。他们通过下面以下步骤组织场景造型： 首先制定一个地形提供场景中的高度点，然后交互或由程序定位场景中的植物， 再造型单株植物( 草和树) ，最后绘制这些实体。这些概要性的流程在c h i b a e t a l 绘制森林时被仿效，并且成为综合生成自然场景的基础理论。 自然场景的复杂性决定了绘制时必须仔细的分配c p u 时间、内存和存储空间等 计算机资源。而表示场景的数据量尤其是一个关键问题，这是因为表示场景所需 的几何数据量通常都很大，而且随着场景细节的丰富而急剧增加。 对应于粒子系统绘制，r e e v e s 和b l a u 用结构粒子系统模拟场景，单株植物所 需的粒子数是百万的数量级。为了处理组成场景的大量的图元，单株植物粒子的 生成和绘制以顺序方式进行，一株树绘制结束时顺序释放该模型，因此场景所需 的内存和单株植物的粒子数成正比，而不是与场景总的粒子数成正比。采用这种 方法时只能进行近似的阴影计算，因为一株树周围的细节是无法得到的。 在多边形绘制中，控制表示场景的数据量的方法是减少场景中不重要的细节 的表述。复杂场景的简化技术已经成为当前研究的热点，但是其结果并不能方便 地被应用到具有多层分叉的植物结构中来。为此，w e b e r 和p e n n 提出了多分辨率 表示植物的方法，该方法可以有效的减少模型中投影只占据屏幕- d , 部分区域的 几何图元的数量。 而绘制中体纹理的使用能减少表示场景内存和磁盘的存储空间，因为相同的 体素可以被重复应用到多个区域。同样的思路可以应用到绘制复杂场景中来。一 个在场景中多次被绘制的物体可以只被定义一次，然后通过仿射变换改变外形， 因而整个场景只需要存储基本的物元和描述仿射变换的参数，从而大大减少了需 要绘制大量相似物体时表示整个场景的空间。 第一章自然场景模拟综述 1 3 2 草地的模拟与绘制 草地是自然植被的重要组成部分，通常来说，因为草地的叶子数量庞大，构 造和绘制高度真实感的草地是比较困难的。早期比较成功的例子是r e e v e s f i ：l b l a u 等用粒子系统模拟草地。到1 9 9 5 年，n e y r e t 提出利用纹元和体纹理构造和绘制草 地，并采用多分辨率的层次结构以提高绘制效率，真正高效的进行了三维草地造 型和绘制a1 9 9 9 年d e u s s e n 等人提出植物生态系统的真实感造型与绘制方法，他 们开发了由一系列工具流水线组成的系统。地形由图形交互输入；植物分布通过 手工、生态模拟或两者的综合实现；给定参数过程进行植物造型：通过在绘制之 前把近似的植物、群落或植物组织加以代表性的实例化，实现场景的几何复杂度 压缩。 1 4 本文的工作 本文的主要任务是实现草地这一自然场景的模拟与绘制。通过前文的综述， 我们可以知道前人的研究工作已经对植物和草地的模拟提出了一系列方法， 这些方法各有优缺点，主要体现在模拟绘制后的效果、耗用的资源、绘制 的速度等方面的不同。本文在总结前人研究成果的基础上，通过采用先进 的造型技术和绘制方法，高效高质的实现了对草地的模拟与绘制。 我们将草地的模拟与绘制划分成下列步骤进行：首先利用随机的分形 系统和人工数据生成地形( 第3 章) ，包括地形高度、坡度( 用法向量表 示) ，构造出草地的地基。再根据地形决定植物的类型、位置、朝向和单 株植物的参数，确定植物的密度和植物的分布，得到草地上植物的位置和 朝向参数。然后，用三维的上下文有关的随机带参数的l 系统进行单株植 物的造型( 第4 、5 章) ，并自行开发实现了l 系统规则解释迭代器( 附录) ， 从而能提供可进行人工控制的植物造型手段( 即通过符合l 系统语法的语句 来控制植物的外形特征) ；而绘制叶片时建立采用多分辨率的基于点的l o d 结构，减少了资源需求。最后，将造型好的植物按照分布位置和朝向等参 数大量的绘制于地基上，生成最后的草地场景( 第6 章) 。在草地的绘制 过程中同样考虑到效率问题，采用了类似m i p - m a p p i n g 的技术思想。 6 第二章系统结构 第二章系统结构 拥有成千上万的植物的自然场景的模拟有许多问题需要解决。首先地形必须 生成，生长在其上的植物分布必须能反映植物和植物、植物和环境之间的相互关 系，而且单株植物的几何模型应和它在生态系统中的位置相符合。通常组成场景 需要上百万甚至上亿的图元，这种场景的复杂性使得在创建场景时必须仔细分配 计算机的有限资源，如c p u 、内存和存贮空间等等。用于绘制的场景的数据量 应该仔细考虑，这是因为用于表示详细的场景的几何数据量通常远远超过般计 算机的处理能力。另夕 ，场景应能在考虑光照的情况下进行有效的绘制。 2 1 系统结构 在对整个系统仔细考虑、权衡与分析之后，我们决定采用以下的系统结构实 现对整个场景造型和绘制 图2 1 系统结构框图 7 第二章系统结构 造型过程首先对地形进行造型，输出地形文件，文件包括地的高度、法向( 表 示局部坡度) 和一些环境信息如湿度等。然后是决定特定地形上的植物的分布， 用画刷程序指定植物的分布或明确指定单株植物的位置。植物的模拟必须考虑植 物与环境之间的交互作用，反映这一相互作用的环境因素作为参数扩充到参数化 的随机l 系统中，影响植物造型。植物的分布必须包含植物的类型、位置、朝向 和单株植物的参数等，而单株植物的参数如枝干之间的夹角、比例关系等也都作 为随机l 系统的参数决定着单株植物的几何造型。最后，将造型好的植物按植物 分布绘制于地形上，就最终完成整个场景的绘制。 本章的余下部分将对各个部分做简要的说明，在本文以后的论述中，会详细 介绍各个部分的实现细节。 2 2 地形生成 地形被分划为一x n 的网格，每个网格的顶点被赋予不同的高度值，在网格之 间的点的高度值，为将网格四边形傲三角剖分后线性插值获得。 为了在造型中提供足够的细节并充分利用分形方法，我们将地形的生成过程 分为以下两个部分： 1 ) 人工数据输入 通过输入地形数据文件，获得地形的三维表示。 2 ) 分形数据产生 利用随机分形的方法生成地形数据。 2 3 植物分布 确定特定地形上的植物分布的基本方法可分为两类：空间占有和基于单株植 物的技术。本文采用空间占有方法中的明确指定方法确定植物分布范围。而在确 定了一种植物的分布范围之后，在此范围之内某一株植物的具体位置由随机方法 生成。 2 4 单株植物造型 确定了特定地形上的植物分布后，我们开始对单株植物进行几何造型。植物 测量技术的最新进展使得能根据植物结构的详细测量数据构造特定植物的几何 模型【3 9 】。但是，对于随着年龄、生命力和其它参数形态不同的植物，更适合 于把植物的几何模型处理成过程模型。我们使用参数化的随机l 系统模拟植物的 第二章系统结构 形态，通过不同的参数( 如枝干之间的夹角、分枝形式、叶序类型) 就可以模拟 不同形态的植物。 由于自然场景的植物种类数量繁多、类型各异，想只用一种造型方法对所有 的植物都精确的造型是不实际的。实例化方法【4 0 】在曾成功地用于紧凑的表示 复杂户外场景。根据实例化范式，任何几何物体，如果进行相似变换后外形相同， 即为同一对象的实例。我们可以通过实例化相似的物体来减小几何描述的大小。 将整个场景分解为一群植物、单株植物、分枝结构、植物器官( 如叶子) 等层次， 在不同层次进行实例化。在本文中，我们对草的叶子、植物的分枝结构、整株草 进行实例化。我们预先计算好一组叶子中脉的变形控制曲线，然后把不同纹理图 像嵌入到参数曲线的局部标架中，通过点绘制的方法在每片叶面上建立相应的 l o d 结构。这样只需要存储一组叶子数据，就可以绘制具有相似弯曲程度的所 有叶子，然后我们再通过相似变换把这些叶子变换到不同的位置和方向，这样做 既节省了绘制需要的资源，又有着良好的视觉效果。我们用同样的思想，把同一 种分枝结构应用到相似的植物上，而外观类似的一群草可以通过对一株革的变形 和坐标变换得到。 2 5 绘制模块 通过地形生成、植被分布、单株植物的造型之后，我们已经拥有地形数据、 植物环境地形数据、单株植物的几何数据，除此之外还有可能场景的其他一些参 数( 例如，在有河或小溪的场景中，水的绘制也是一个必要元素) 及与绘制有关 的光照、材质及大气的效果等参数。在绘制模块中将有关绘制数据进行整合处理。 在具体绘制中，单株植物绘制的时候采用点绘制，利用叶面上建立的l o d 结构， 选择性的绘制相应的点，在尽量不减低绘制效果的基础上，提高单株植物的绘制 速度。在整个草地绘制时，我们采用m i p m a p p i n g 的方法对远近不同的植物做有 选择性的绘制，从数量上减少绘制的株数。 第三章地形生成及植物分布 第三章地形生成及植物分布 任何植被都需要依存的是土壤，因此我们把地形生成作为整个场景生成的第 一步。地形生成模块的基本目标是生成具有高度数据、局部方向的地形，此外还 可以生成一些与地形有关的特征，例如在土壤中水的分布，这会对在不同水分布 土壤上生长的植物产生影响，从而影响植物分布。本章的前半部分详细讨论了场 景的地形生成。 植被在地形上的分布直接关系到自然场景的真实表现。是否有一个合乎自然 并且容易进行绘制的植物分布模型是场景绘制能否成功的重要因素，这种模型也 是符合生物学的人工控制与自然的植物分布折衷的结果。在本章的后半部分讨论 了场景中实现植物分布的方法。 3 1 地形生成 在本系统中地形是这样被三维表示的，地形被分划为咒h 的网格，每个网格 的顶点被赋予不同的高度值，在网格之间的点的高度值，为将网格做三角割分后 线性插值后获得。 地形数据的获取可能多种不同的方式，最为真实的地形数据，可以从美国国 家地质勘测局( u s g e o l o g i c a ls u r v e y ) 的数据库中获得，此外也有多种技术创 造人工的地形数据：手工绘制的等高图输入 4 5 】，多种的分形方法产生分形地 形 2 7 1 ，基于土壤腐蚀模拟模型的造型技术等。在本文中，我们采用手工输入 数据然后分形处理的方法产生地形。为了在造型中提供足够的细节并充分利用分 形方法，我们将地形的生成过程分为以下两个部分： 1 ) 人工数据的输入： 通过输入地形数据文件，获得地形的三维表示。 2 ) 分形处理： 利用随机分形的算法处理地形数据。 3 1 1 人工数据输入 人工数据即地形的空间数据。如果有一个具有足够细节，足够详细真实的数 据集，那么整个地形都可以用人工输入的方式获得。在我们的系统中，出于简便 1 0 第三章地彤生成及植物分布 的考虑，人工数据的输入只作为最初的模板，允许很粗糙的输入。输入数据需要 用分形方法处理之后才能接近真实的数据。我们首先用人工的方法在平地中加入 一条低于地平线的沟作为初始数据，为分形处理提供基础。初始地形如图3 1 所 示： 图3 1 人工输入模板后的地形 3 1 2 分形处理 1 9 2 3 年w i e n e r 提出了模拟类似于在布朗运动中观察到的随机现象的严格的 数学模型。 3 1 2 1 一维布朗运动 1 ) w i e n e r 过程 假设一个随机过程x ( t ) 是实变量t 的函数，对每个给定的时刻t ，是一个随 机变量，则两个时刻的函数差 x ( t ：) 一x ( ，1 ) 也是一个随机变量，称为“函数增量”。 w i e n e r 提出的数学模型称为“w i e n e r 过程”，他假定增量z o + r ) 一x ( t ) n 从正态分布，均值为0 ，方差为仃2 f ，概率密度为： 即，= 赤e 啾一豪， ( 3 1 ) w i e n e r 提出用不相关的白色高斯噪声w ( s ) 对时间的积分来模拟布朗运动 的路径增量： “ 第三章地形生成及植物分布 ( r ) = ( s ) a s 2 ) 随机中点移位法 ( 3 2 ) 在二维上使用的中点变换算法，这是一个简单而直观产生布朗运动的方法。 程序伪代码： 以一条水平地平线段开始 重复足够多次 对场景中的每条线段做 找到线段的中点 在y 方向上随机移动中点一段距离 减小随机数取值范围 入入八、 图3 2 随机中点移位法的中点剖分过程 3 1 2 2 高维布朗运动 将一维布朗运动推广到高维情况，采用d i a m o n d - s q u a r e 算法 算法描述如下：从一个2 的i 1 次方加1 的2 d 数组开始。将四个角设为相 同高度。以一个5 x 5 的数组为例。图a 的四个角种上了初始高度值，表示为黑 点，称为s q u a r e 点。 圈田田田田 0 bd 图33d i a m o n d s q u a r e 算法示意图 这是递归细分过程的起始点，递归过程分两步： 1 2 第三章地形生成及植物分布 d i a m o n d 步：取四个点的正方形，取正方形的中点，中点的高度值是平均四 个s q u a r e 点的高度值再加上一个随机量计算得到的。这样就得到了一个d i a m o n d 点。 s q u a r e 步：取2 个s q u a r e 点和2 个d i a m o n d 点( 另一d i a m o n d 点是由跟此 正方形相邻的正方形生成的) 形成的棱锥，平均这4 个点的高度值再加上与 d i a m o n d 步有相同取值范围的随机量，计算出正方形每条边中点的高度值，产生 新的s q u a r e 点。 这样，已经生成了一个种子正方形并经过单独一次细分过程将得到四个方 形。第二次经过该过程得到1 6 个方形，第三次得到6 4 个方形。增长得很快。 方形数目等于2 “，其中i 为递归经过细分过程的次数。 仍旧对于上图，下面示意使用d i a m o n d s q u a r e 算法两次后发生的情况。 对于第一遍经过d i a m o n d 步时，我们平均四个s q u a r e 点的高度值在正方形 中心生成一个值，并加上一个一1 0 到1 0 之间的随机值，生成正方形中心 d i a m o n d 点的高度值。在插图b 中，新值显示成黑色，已经存在的点显示为灰 色。 对于s q u a r e 步，我们在相同的范围内生成随机值。这一步时有四个棱锥； 他们在正方形中心相交，这样我们需要计算四个新s q u a r e 点。棱锥的4 个顶 点的高度值被平均以找出新s q u a r e 点高度值的基数。然后加上随机量，即为新 s q u a r e 点的高度值。插图c 用黑色显示新值，现存值为灰色。 以上是第一遍，如果用线将这9 个点边起来，就可以得到一个线框的表面， 如下图： 现在进行第二遍。再次从d i a m o n d 步开始。第二遍与第一遍有两点不同。 第一，现在有四个正边形不是一个，需要计算四个正方形的中心。第二，生成随 机数的范围需要减小。在第一遍中如果随机量的取值范围是( 一1 0 ，1 0 ) ，那么第 第三奄地形生成及植物分布 二遍的取值范围应该小于这个值域，例如，可以是( 一0 5 ，0 5 ) 。在插图d 中， 我们这一步计算得到的四个正方形中心值显示为黑色。 最后，我们进行第二遍的s q u a r e 步。有1 2 个棱锥中心，我们现在需要计 算1 2 个新值，如图e 中黑色所示。 现在数组中全部2 5 个元索都已经生成。我们可以得到如下的线框曲面。 3 1 2 3 最终地形效果的生成 将手工输入的模板数据，通过d i a m o n d s q u a r e 算法处理，我们最终得到如 下的地形图，作为场景绘制的基础。从图中可以看到，经过分形运算，综合噪声 信号之后，人工数据明显的人工痕迹已经变得真实自然，接近自然地形。 图3 5 最终生成的地形场景 地形数据建立之后，贝0 可以在地形数据之上添加更多参数，做植被生态模拟， 也直接做植物造型的环境输入，对植物的生长施加地形的影响。影响的结果参见 第五章2 3 3 节。 3 2 植物分布 确定特定地形上的植物分布的基本方法可分为两类：空间占有方法和基于单 株植物的方法。空间占有方法描述特定地域的植物密度，植物的分布可由以下两 1 4 第三章地形生成及植物分布 种方法得到： ( 1 ) 明确指定：植物的分布密度通过测量得到( 计数采样区域的植物的数目) 或用画刷交互创建。 2 ) 过程生成：植物的分布密度用生态模型通过模拟植物之间的交互作用得到 【1 1 ，1 3 】。 基于单株植物的方法指定单株植物的位置和属性，同样的可分为两种： ( 1 ) 明确指定：植物的位置和属性通过测绘实际的森林得到【1 2 】或用户交互 确定。 ( 2 ) 过程生成：植物的位置和属性使用点模式生成模型，创建的点具有统计属 性 4 4 1 ；或用基于单株植物的分布模型【9 ，3 8 1 。 在本文中，我们将地形的每个网格作为最小的分布单元，采用空问占有方法 中的明确指定的方法确定植物的分布，通过人工指定特定地域的植物的数量和类 型。用画刷程序产生的位图确定植物的分布，植物的类型可由位图中的不同颜色 确定，分布密度可由某种颜色占有位图的面积表示，在一种植物分布范围之内一 株植物的具体位置则由随机方法确定。 植物分布的位置信息建立之后，作为绘制的必备参数，除供后面的绘制程序 处理外，也可以作为植物分布文件输出。 第四章叶面造型 第四章叶面造型 叶子是单株植物的一个基本组成部分，如何真实地实现对叶子的造型，并 对其数据结构进行合理的管理，是影响单株植物造型一个主要因素，如何真实 的绘制叶子也是影响单株植物绘制的一个重要因素。以前一般采用多边形造型 来表示叶子，但是对于形状复杂的叶子很难造型，而且采用固定分辨率的造型 方法难以靠近观察叶子的细节。本章对叶子的造型和绘制进行了讨论，用三维 b e z i e r 曲线作为轴变形的控制曲线对叶子的形状进行变形，把叶子的纹理图象 嵌入到参数曲线的局部坐标标架中，并采用o p e n g l 的口完成实现透明纹理映 射。在此基础上利用已有的叶子纹理图像的参数曲面的标架，用多分辨率的点 采样绘制的方法将叶面的带拓扑信息的纹理图采样为不含拓扑信息的点集，并 在其上建立了l o d ( l e v e lo fd e t a i l s ) 的四叉树结构。对离视点较远的物体， 根据物体的深度值和物体的面积基于l o d 结构选取不同的采样点绘制物体，以 提高绘制的速度。 4 1 现有叶面造型方法 对植物的叶子一般采用曲面模拟，主要可以分为以下两种 4 1 。1 预定义曲面 计算机图形学方法中通常采用双三次曲面片定义任意曲面。面片分别定义 为参数s 和t 的三次多项式。曲面片上点的x 坐标按下式定义： x ( s ，f ) ；a l l s 3 t 3 + a 1 2 s 3 r 2 + q 3 s 3 t + 口1 4 j 3 + 口2 1 s2 t 3 + 口2 2 s 2 ，2 + a 2 3 s 2 ，+ a 2 4 5 2 + a 3 1 s t 3 + a 3 2 s t 2 + a 3 3 s t + a 3 4 s + 口4 l t 3 + 口4 2 f 2 + 口4 ，+ 口4 4 类似的可定义y ( s ，) 和z ( s ，0 。所有的系数可根据历要设计的形状交互给定。 复杂曲面可由若干曲面片拼接而成。 4 1 2 生成的曲面模型 预定义曲面的基本形状保持不变。为了模拟植物的发展过程，有必要提供 一种机制，随着时间的改变能同时改变叶子的形状和大小。方法之一是跟踪曲 1 6 第四章叶面造型 面的边界，并填充结果多边形。实际中，跟踪多边形边界产生特定形状的曲面 只适用于小的扁平曲面。在其他情况下，可使用树的结构作为框架。多边形的 顶点由一系列龟的位置指定。用字母g 替代字母，表示括弧中的线段不解释为 所构造的多边形的边。 4 2 基于弧长参数的轴变形方法 三维空间曲线可以表示物体的路径或曲面片的边界，它们同样可作为轴线 控制物体的几何形状。我们可以利用轴变形和纹理映射技术控制叶子的形状， 将纹理嵌入到由曲线的弧长参数署d f r e n e t 标架所形成的变形空间中。 4 2 1 引言 轴变形( a x i a ld e f o r m a t i o n ，a x d f ) 是一种由参数曲线控制物体自由变形的 方法。它是对基于参数体( - - 维) 和参数曲面控制的物体变形方法的完善。 l a z a r u s1 2 0 1 等人首先明确提出a x d f 方法。在a x d f 方法中，用户首先定义一 条参数曲线，作为变形体的轴线，这条参数曲线既可以位于物体的内部，也可 以位于物体的外部，物体上的点根据最近点的规则嵌入到参数曲线上对应点的 局部坐标系中。当用户编辑控制曲线时，附在曲线上的物体会随之变形。这里 物体嵌入的局部坐标由曲线上的参数和旋转最小标架确定。 用三次b e z i e r 曲线作为变形控制曲线，首先根据曲线的切向的变化对曲线 进行自适应剖分，并在离散点建立f r e n e t 标架，然后将需要变形的物体嵌入到 这些局部坐标系中。通过广义d e c a s t l j a u 算法，嵌入局部坐标系中的物体被 变形为b e z i e r 曲线的形状。通过改变b e z i e r 曲线的控制顶点的位置，就可改变 物体的形状。 4 2 2 变形与控制 4 2 2 1 方法概述 记五( r ) = ( x ( f ) ，y ( r ) ，：( f ) ) 为空间参数曲线。首先，我们提出微分几何中与参 数曲线有关的几个概念： 1 正则曲线：如果在参数曲线的定义域中，五( f ) 0 ，则称该曲线为正则曲线。 2 逗留点：如果在参数曲线，= “处，有j i ( f 。) 豆( f 。) = 0 ，则称f = f 。为逗留 点，当曲线是平面曲线时，称之为拐点； 第四章叶面造型 3 线上的坐标活动标架：在一条正则曲线上，常用的局部坐标活动标架有 f r e n e t 标架、改进的f r e n e t 标架【1 7 1 、旋转最小标架( r o t a t i o nm i n i m i z i n g f r a m e ) 【1 8 】。对于g2 的正则曲线k ( t ) ，f r e n e t 标架( 匠( ，) ，( ，) ，尹( f ) ) 可以 由以下公式解析地求出： 卜尚弛卜尚筠及泸弛( 3 1 ) 但是，在逗留点附近，f r e n e t 标架的法向厅和副法向尹会反向或产生不必 要的旋转，而且在逗留点处，f r e n e t 标架没有定义。改进的f r e n e t 标架可以在 一定程度上克服这个问题。但是消除曲线上局部活动标架不必要的旋转的个 方法是采用旋转最小标架，它是通过一个微分方程定义的： 霄u ) = 一( j i ( f ) 霄。) ) j i ( f 堋j l ( f 2 画( f ) = 一( j ( r ) 莉) j ( r 堋j ( 哪 ( 3 2 ) 膏( o ) = 或，反o ) = 磊 其中露、藏、磊为互相垂直并组成右手系的单位向量，盂为曲线在f = 0 处的切向。上述初值问题( 3 2 ) 对于g 连续的正则曲线有唯一解，并且z m 、 霄0 ) 、百( f ) 相互垂直并组成右手系。与前两种坐标标架相比，定义旋转最小 标架方程的解的存在性对曲线的要求较低，并且标架的变化较平稳，还能够克 服平面曲线的活动标架在拐点处反向( 否则会扭曲) 的问题。但是，对于一般 的样条曲线，如b s p l i n e 曲线，上述微分方程( 3 2 ) 的解析解一般是不存在的。 4 2 2 2 参数曲线的离散查找表的建立 下面讨论空间三次参数曲线的坐标标架的建立，设曲线的系数分别为三维 向量a 、b 、c 、d 。曲线上点p 的位置可由其参数f 得到： p = a t 3 + b r 2 + c r + d ( 3 3 ) 考虑f r e n e t 标架：标架由单位切向量t 、中心轴一主法向量n 和副法向量b 组 成。t 可由单位速度向量v 计算得到，v 是曲线的导数： v ：3 a t2 + 2 b t + c 主法向通常定义为曲线的曲率方向，k = v q v i v l 4 ，q 是曲线的加速度， 第四章叶面造型 即速度的导数6 a t + 2 b 。 因此，t = v i l v l l ，n = 和b = t x n ，如下图。 图4 1 曲翠吲4 2f r e n e t 标栗 旋转最小标架即在曲线的起始点定义一初始的坐标标架，该标架沿着曲线 作小角度的旋转生成其它点的标架。初始的标架可用曲率计算得到。如果曲率 为零，则n 可以是垂直单位法向量t 的任意单位向量。给定初始标架，新点的 标架可以按顺序通过计算p 和该点的t 得到。对初始始标架通过旋转使得初始 的切向t 和新点的t 重合。旋转产生新的n 和b ，这样就定义了新的坐标标架。 旋转轴a 由t 0 t l 帆i | t l 涉定义。在下图中， e o ，t o ，n 。，b 。 变为 僻，t 1 ，n 。，b ， 。当t 0 、t l 变化小时，曲线相对较直。当t o = t l 时，旋转为 零。n ，可由n 。和旋转矩阵r ( 表示从原始标架旋转到新的标架) 相乘得到。其 中假设t 0 、王、a 为单位向量。 计算公式如下，需要1 次开方、1 9 次乘法和1 5 次加法： fs q ，+ ( 1 一s q ：j c o s x y c o s l + z s i nz x c o s l y s i n l r = i x y c o s l z s i n s q y + ( 1 一s q y ) c o s y z c o s l + x s i n l ( 3 4 ) l = c o s + y s i ny z c o s l - x s i ns q ：+ ( 1 - s q ：) c o si 图4 3由前一个标架计算下个标架 记三次b e z i e r 曲线为 i ( f ) = 窆只b 。o x r e 【o ，1 】 ( 3 5 ) 1 = 0 第州章叶面造型 其中b 小o ) 为b e r s t e i n 基函数。设阮，n o ，磊) 平口抗，霄。豆) 分别为其始末两端处的 f r e n e t 标架。由f r e n e t 公式于= 腩可知，曲线切向的变化反映了曲线曲率k 的 变换。我们根据曲线两端点处的f r e n e t 标架的变化程度对i ( r ) 进行自适应剖分， 弧长可用线段近似计算，占是衡量f r e n e t 标架变化程度的参数，在实际应用中， 有如下估计公式： 占= 1 一c o s 0 = 2 s i n 2 昙 ( 1 口0 5 。)( 3 6 ) 上 对于上述经过剖分得到的直线段，应用上述的方法，可以计算出直线段的 端点处的坐标标架。最后我们可以在曲线上建立一关于个弧长、采样点的空间 位置以及局部坐标标架的查找表： ，只，盂，冠b 。u 其中j 为起始点到该点的弧长，m 为b e z i e r 曲线被最终离散成的直线段 的数目。 4 3 叶面纹理图象附着于参数曲线 植物的叶子由于形态各异，很难用多边形逼真的表示，因此考虑利用叶子 的纹理图像，但是用曲面构造叶子的形状，再根据叶子的实际形状求取实现纹 理映射较为困难。因此