（计算机科学与技术专业论文）大尺度地形植被的实时绘制技术.pdf

摘要 摘要 地形、植被等自然景物是虚拟场景的重要组成部分，但是它们的结构往往 十分复杂，表面细节丰富，并且数据量极为庞大，给自然场景的快速绘制带来 了很大的困难。考虑到用户在自然场景漫游中，由于视野广袤，因此更在意场 景的整体效果，并且人眼对细节的分辨能力有限，即使面片位置出现一定偏差， 从视觉上仍然难以察觉。为此，本文利用自然景物的特点和人眼的观察特点， 提出了一种采样逼近的方案。该方案是对自然场景进行采样，构造出原始数据 的逼近模型。使用这种模型的绘制结果具有原始场景的近似形态，并且可以通 过控制参数改变其逼近精度，从而有利于自然场景的绘制速度和质量之间的平 衡。本文把这一方案应用到大尺度地形和植被的绘制过程中，主要取得了以下 三个研究成果。 地形是构造自然场景的基础部分，传统地形绘制算法的模型数据量往往十 分庞大，限制了地形绘制的应用范围。本文提出了一种地形的过程式逼近与绘 制算法，能够以较少的数据量，快速绘制出大尺度的地形场景。该算法首先在 预处理阶段建立地形的层次树结构，记录着统计分形信息，然后在绘制时根据 设定的阈值，通过g p u 生成视点依赖的地形网格。这种分形层次树结构是对原 始地形的逼近表示，能够获得较高的数据压缩比。实验证明，该算法可用于地 形压缩、地形合成等应用领域。 在虚拟场景中增加树木等植被，可使绘制结果更加丰富多彩。森林场景包 含了大量的树木，并且树木结构复杂，细节信息丰富，以每棵树为单位进行处 理，其效率必然低下。本文提出了基于分级层次深度拼图集的森林绘制技术， 把整个森林看成一个整体，建立多级的层次结构。这样在绘制森林时，只需遍 历这种结构，就可以快速选择出结点并进行绘制。该算法需要对每个结点进行 采样，才能够建立这种层次结构。为了在采样中能够很好地逼近原始树木的形 态，本文提出了基于遮挡因子的采样度量标准，根据树木的遮挡情况与深度信 息，构造出自适应大小的纹理绘制单元。同时通过光线跟踪算法采样出树木的 颜色信息，从而在绘制速度与绘制质量之间获得了很好的平衡。 如何表现动态光照下的自然场景是个具有挑战性的问题，本文提出了一种 层次多项式纹理，既能够表现出植被丰富的层次信息，又能够快速获得动态光 t 摘要 照的绘制效果。草地等植被的材质是以漫反射为主，而高光性很弱。因此层次 多项式纹理丢弃了高光部分，采用函数拟合的方法近似表现出材质的漫反射光 照。每个纹理单元包含了多层的光照信息。并可以通过( m u 计算出拟合的函数 值，从丽快速获得了动态光照下材质的逼近绘锚效果。本文通过纹理拼图块的 方法，把采样得到的层次多项式纹理拼接成大范围的草地场景，就能够快速绘 制出动态光照下的草地层次多项式纹理是对多层数据的一种紧缩表示，数据 量小，运算代价低，而且能够推广到树的表示，也可以实现树的动态阴影效果。 关键词自然场景绘制，实时绘制，阴影。分形，四叉树，g p u ，硬件加速 摘要 a b s t r a c t n a t u r a ls c e n e r i e s ，s u c ha st e r r a i na n dv e g e t a t i o n ，a l ei m p o r t a n tc o m p o n e n t si nv i r - t u a lr e a l i t y h o w e v e r ，t h em o d e l so fn a t u r a ls c e n e r i e sa l eu s u a l l yv e r yc o m p l i c a t e d i n c l u d i n ga l o to f s u r f a c ed e t a i l s ，s ot h ed a t as t o r a g e sa r el a r g e ，w h i c hl e a d st ot h ed i f - f i c u l t yo ff a s tr e n d e r i n g w h e nu s e r sa r er o a m i n gi nt h en a r n a ls c e n e ，t h 盯o f t e n c o n c e n t r a t eo nt h ew h o l ee f f e c tb e c a u s eo f t h ev a s tv i s u a lf i e l do f t h es c e n e f u r t h e r - m o r e ，s i n c et h ed i s t i n g u i s h i n ga b i l i t yo f h u m a nv i s i o ni sl i m i t e d , e v e nt h o u g ht h es p a - t i a lp o s i t i o n so ft h em o d e lp o l y g o n sa r ed e f l e c t i v ef r o mt h e i ro r i g i n a lo n e s ，i ti sh a r d t oo b s e r v et h ed i f f e r e n c e si nv i s i o n t h e r e f o r e ，a c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h e n a t a r a ls c e n e r i e sa n dt h eo n e so fh u m a n v i s i o n ，w ep r o p o s eas a m p l i n ga n da p p r o x i - m a t es c h e m ei nt h i st h e s i s t h ea p p r o x i m a t em o d e li so b t a i n e db ys a m p l i n gt h en a t a - r a ls c e n ei np r e p r o c e s s i n gs t a g e ，a n dt h es c e n ei sr e c o n s t r u c t e di nr e n d e r i n gs t a g eb y t h em o d e l t h er e c o n s t r u c t e dr e s u l t a p p r o x i m a t e st h eo r i g i n a ls c e n e , a n dt h ea p p r o x i m a t ep a r a m e t e r sc o u l dm o d u l a t et h ee l t o r sb e t w e e nt h e m i nt h i st h e s i s ，w ea p p l yt h es c h e m et or e n d e r i n go fl a r g e s c a l et e r r a i na n dv e g e t a t i o n ，a n da c h i e v et h r e e r e s e a r c hr e s u l t sa sf o l l o w s t e r r a i ni st h eb a s i cc o m p o n e n to f t h en a t u r a ls c e n e t h em o d e ls t o r a g e so f t h ei r a - d i t i o n a la p p r o a c h e sa r eu s u a l l yv e r yh u g e ，w h i c hr e s t r i c t st h ea p p l i c a t i o no ft e r r a i n r e n d e r i n gt e c h n i q u e s ap r o c e d u r a la p p r o x i m a t ea n dr e n d e r i n gt e c h n i q u eo ft e r r a i ni s p r e s e n t e di nt h i st h e s i s ，w h i c hc o u l dr e n d e rt h el a r g e s c a l et e r r a i ns c e n ew i t hl e s sd a t a s t o r a g e t h eh i e r a r c h i c a lt r e es t r u c t u r eo ft e r r a i ni n c l u d i n gt h ef ：r a c t a li n f o r m a t i o ni s c o n s t r u c t e di np r e p r o e e s s i n gs t a g e ，a n dt h e ni nr e n d e r i n gs t a g e ，t h ev i e w - d e p e n d e n t t e r r a i nm e s h e sa r eg e n e r a t e dt h r o u g hg p ua c c o r d i n gt ot h eu s e r - d e f i n e dt h r e s h o l d t h ef t a c t a lh i e r a r c h i c a lt r e em o d e la p p r o x i m a t e st ot h eo r i g i n a lt e r r a i n ，t h u st h e h i g h e rd a t ac o m p r e s s e dr a t i oc o u l db ea c h i e v e d e x p e r i m e n t sd e m o n s t r a t et h a tt h e a p p r o a c hc o u l d b eu s e di ns e v e r a la r e a s ，s u c ha st e r r a i nc o m p r e s s i o na n dt e r r a i ns y n t h e s i s a d d i n gv e g e t a t i o n , s u c ha st r e e s ，i n t ot h ev i r t u a ls c o n ec o u l dm a k et h er e n d e r i n g r e s u l tm o r ev i v i d t r e e sc o n t a i nc o m p l e xs t r u c t u r e sa n da b u n d a n td e t a i l s b e c a u s e f o r e s tc o n t a i n sl o t so ft r e e s ，i fe a c ht r e ew a sr e n d e r e dr e s p e c t i v e l y , t h er e n d e r i n ga l - t 丌 摘要 g o r i t h r aw o u l db ei n e f f i c i e n t t h i st h e s i sp r e s e n t saf o r e s tr e n d e r i n gt e c h n i q u eb a s e d o nh i e r a r c h i c a ll a y e r e dd e p t hm o s a i c s ( r t l d s o ，w h i c hr e g a r d st h ew h o l ef o r e s ta sa u n i t e do n e t h eh i e r a r c h i c a ls l n l e t o r ei sb u i l ti np r e p r o c e s s i n gs t a g e ，a n dd u r i n gt h e r e n d e r i n gs t a g e ，t h er e q u i r e dt r e en o d e sc o u l db es e l e c t e da n dr e n d e r e dq u i c k l yb y t r a v e r s i n gt h eh i e r a r c h i c a lf o r e s t e a c hn o d en e e d st ob es a m p l e dt oc o n s t r u c tt h e w h o l eh i e r a r c h i c a ls t r u c t u r e i no r d e rt ob e t t e ra p p r o x i m a t et h eo r i g i n a lt r e e s ，w e p r o p o s eas a m p l i n gt o l e r a n c ec r i t e r i o nb a s e do no c c l u s i o nr a t i o t h et e x t u r ee l e m e n t s w i t l la d a p t i v es i z e sa r ec a l c u l a t e da c c o r d i n gt ot h ed e p t hr a n g e sa n do c c l u s i o nr a t i o s o ft h et r e es a m p l e si np r e p r o c e s s i n gs t a g e t h ec o l o ri n f o r m a t i o no ft r e e si ss a m p l e d b yr a yt r a c i n ga l g o r i t h m b yt h i sm e a l l $ ，ab e t t e rt r a d e o f fb e t w e e nr e n d e r i n gs p e e d a n dq u a l i t yc o u l db er e a c h e d r e n d e r i n go f t h en a t u r a ls c e n eu n d e rt h ed y n a l ：n i cl i g h t i n gc o n d i t i o ni sac h a l l e n g e w e p r e s e n t sal a y e r e dp o l y n o m i a lt e x t u r e ( l p t ) t oe x h i b i tr i c hl a y e r e di n f o r m a t i o no f v e g e t a t i o n , a n dt of a s ta c h i e v et h er e n d e r i n gr e s u l t sw i t ht h ed y n a m i cl i g h t i n gs o l i c e b e c a u s et h em a t e r i a lp r o p e r t yo fv e g e t a t i o n , s u c ha sg l a s s ，i sm a i n l yd i f f u s e ，a n di t s h i g h l i g h ti sw e a k , t h ef i t t i n gf u n c t i o ni sa d o p t e dt oa p p r o x i m a t et h ed i f f u s ep r o p e r t y e x c e p tf o rt h eh i g h l i g h t e a c h 啪e l e m e n ti n c l u d e sm u l t i l a y e rl i g h t i n gi n f o r m a t i o n t h ea c t u a ll i g h t i n gv a l u e sc o u l db ec a l c u l a t e db yg p uq u i c k l ya c c o r d i n gt ot h el p t p a r a m e t e r si nr e n d e r i n gs t a g e ，a n dt h ea p p r o x i m a t er e n d e r i n gr e s u l ta r ea c h i e v e di n r e a l t i m ep e r f o r m a n c e w ea d o p tt h et e x t u r et i l ea p p r o a c ht om a pt h es a m p l e dl p t o n t ot h et e r r a i n ，a n dt h el a r g e - s c a l eg r a s s l a n di sc o n s t m e t e df o rr e a l - t i m er e n d e r i n g u n d e rt h ed y n a m i cl i g h t i n gc o n d i t i o n l p ti sac o m p a c t e ds t r u c t u r ef o rt h ec o m p l e x l a y e r e di n f o r m a t i o n ；t h es t o r a g ei ss m a l la n dt h ec o m p u t a t i o n a lc o s ti sl o w f u r t h e r - m o t l p tc o u l db ee x t e n d e dt or e n d e rt r e e sw i t hd y n a m i c 出a d o w k e y w o r d s n a t u r a ls c e n er e n d e r i n g ，r e a l - t i m er e n d e r i n g ，s h a d o w , f r a c t a l ， q u a d t r e e ，g p u ，h a r d w a r ea c c e l e r a t i o n i v 第一章绪论 第一章绪论 虚拟现实是近几年信息技术领域的一个前沿研究方向，它通过计算机构造 出逼真的三维场景，以自然的交互方式，为用户提供诸如视觉、听觉、触觉等 感知信息，让人们感受到一种具有真实效果的三维虚拟环境【1 】【2 】。地形、植被等 自然景物是虚拟场景的重要组成部分，但由于其复杂的结构和庞大的数据量， 给它的交互可视化带来了极大困难。如何高效地组织和实时绘制复杂的自然场 景，已成为当前虚拟现实技术的一个重要研究课题。 自然场景的复杂性主要体现在以下两个方面：一方面，其几何和表面纹理 形态千变万化，极不规则，难以有效表达：另一方面，自然景物种类繁多，数 量巨大，要想准确细致地描述每个对象，则需要庞大的数据，计算量也极大， 难以在有限时间内绘制出高精度的场景图像。由于人眼的分辨能力有限，难以 注意到每个场景细节，因此，在飞行模拟等许多应用中，并不需要在图像上显 示出详尽的细节，而只需一些较为宏观的细节就可理解场景。这是本文研究的 基本出发点。 通用的图形绘制加速算法面向一般场景模型，虽然直接用来绘制自然场景 也能提高效率，但是由于没有考虑自然场景的特点，这种效率的提高是非常有 限的，甚至会失效。例如，为了加速绘制城市场景，学者们常采用遮挡剔除算 法，从而在绘制时跳过那些不可见的房屋，但是这种算法应用到森林场景时可 能会失效。这是因为房屋等基本结构是封闭的多面体，因此易于判断是否被遮 挡，但树木叶片之间的缝隙很多，即使近处树木遮挡了远处树木的大部分，用 户通过近处树木叶片之间的缝隙，仍然可能观察到较远的树木。近年来，许多 学者从自然场景的特点出发，结合通用的绘制技术，设计出了多种自然场景的 快速绘制算法【3 】【4 】闭。这些方法主要通过简化自然场景来提高绘制速度。注意到 自然景物的丰富细节对绘制质量有重要影响，但过于关注细节的处理需要大量 计算。将严重制约绘制速度，而构造过于简化的模型又会降低质量。因此，如 何在这两者之间进行折衷，实现高效、高质量的绘制是问题的关键。 不同于己有方法，本文综合考虑了自然场景的特点和人眼的观察特点，来 解决自然场景的高保真实时绘制问题。我们主要基于以下观察：首先，由于自 第一章绪论 然场景视野广袤，用户往往关注整体的效果，对细节表现会有所忽略；其次， 自然景物的几何面片纷繁复杂，互相遮挡、交错现象普遍( 例如植被、烟云) ， 而人眼的分辨能力有限，即使面片位置出现偏差，从视觉上仍然难以察觉。因 此，问题的关键是如何在整体与局部细节之间作出合理的平衡和过渡，以保持 视觉效果的真实性。为此，我们提出一种采样逼近的方案，对自然场景进行采 样，构造出原始数据的逼近模型。使用这种模型进行绘制，可得到原始场景的 近似形态，并且可以通过控制参数改变该模型的逼近精度，从而达到自然场景 的绘制速度和质量之间的平衡。下面，本文分别就地形与植被绘制技术的研究 现状作一分析。 1 1 地形绘制技术 近年来，许多学者对大尺度地形的实时绘制进行了深入的研究，主要集中 在两个方面，一方面是创建地形的层次细节模型，并在绘制时生成视点依赖的 几何网格；另一方面是对地形层次细节模型的海量数据进行多级调度，从外存 ( 例如硬盘) 动态载入绘制所需要的几何数据。但是，这种地形层次细节模型 的数据量通常比原始数据要庞大，甚至会成倍增加，因此限制了传统地形绘制 算法的应用范围。 1 1 1 地形的层次细节模型 建立地形的层次细节模型是解决大尺度地形实时绘制的一个重要方法。其 基本思路是，在不影响画面视觉效果前提下，通过逐次简化地形的几何细节， 来减少地形网格的复杂度，从而提高绘制的效率。处理过程一般分成两个阶段： 预处理阶段和绘制阶段。在预处理阶段，建立整个地形的连续层次细节模型， 包含从最粗糙几何到最精细几何。在绘制阶段，根据视点选择合适的层次细节， 并建立依赖于视点的几何网格，使得距离视点较近和起伏较大的地形网格较精 细，而距离视点较远和比较平坦的地形网格较粗糙，这样，参与绘制的三角形 数量不大，可以达到实时绘制的要求。 按照地形的层次细节模型所采用的网格规则性，可以分成两类，一类是不 规则网格模型( t r i a n g u l a t o di r r e g u l a rn e t w o r k s ，t i n ) ，另一类是规则网格模型 ( r e g u l a rs q u a r eg r i d , r s g ) 。绘制时，使用不规则网格模型获得的三角形更少， 2 第一章绪论 但是调度更加复杂，容易产生狭长三角形；而规则网格模型结构简单，易于误 差计算和快速绘制，并且便于从外存进行数据调度。下面分别对这两类模型进 行介绍。 1 1 1 1 不规则地形网格模型 1 9 9 7 年，h o p p e 提出了一个累进式的几何网格生成框架，可以根据当前摄 像机的参数，简化任意拓扑的网格【6 。随后，f o p p e 又把该算法应用于地形绘制， 构造不规则网格【7 】。他把地形分成大小相等的块，对每个地形块构造累进式的几 何网格( p r o g r e s s i v em e s h ) 。该算法可以使用较少的三角形数量构造地形的绘制网 格，但构网过程比较复杂，这将消耗较多的绘制时间。 h o p p e 的方法是以地形块为单位进行构网，当地形规模较大时，需要建立大 量地形块，其构网效率将会降低。为此，t o l e d o 等人扩展了h o p p c 的工作，把 规则网格与不规则的累进式网格相结合，提出了q l o d 网格模型f 8 】。q l o d 包 含一个正规四叉树，每个四叉树结点对应一个地形块，包含一个不规则的累进 式网格。该结构可以快速进行视域剔除，易于构造满足误差要求的绘制网格。 t i n 模型中，三角形网格顶点的选择更加灵活，因此可以获得优化的绘制网 格，在同样的误差条件下，三角形数量比r s g 模型要少。但是，t i n 构网时需 要占用较大内存，计算量大，数据结构组织高度复杂，基于外存调度比较困难， 所以目前的大尺度地形可视化系统，更多采用r s g 模型。 1 1 1 2 规则地形网格模型 r s g 方法的特点是，认为原始的地形数据是一个均匀采样的高度场，对这 个高度场建立规则三角形层次树结构，一般为四叉树或者二叉树，在绘制中遍 历这种树结构，并构造三角带进行绘制。虽然r s g 方法生成网格的三角形数目 比较多，但易于视域剔除和自顶向下简化。此外，三角形顶点的连接关系隐含 在规则网格中，因此数据紧凑，易于从外存调度。 基于四叉树的自适应三角网格 四叉树是一种常见的空间数据结构，构造方式是，连接地形高度场的四条 边的中点，得到四个子区域，然后用同样方法递归地剖分这些子区域，使得树 中的每一结点对应着一块地形区域。这类方法构网速度很快，但其中一个关键 3 第一章绪论 问题是，具有不同网格分辨率的结点邻接时，如何避免它们连接处的裂缝 现象。 h e r z e n 等人首次提出基于四叉树的自适应三角形剖分算法，并应用到参数 曲面上【9 】。为了避免三角形网格出现裂缝，他们提出了一种约束型四叉树的方法 ( r e s t r i c t e dq u a d t r e e ) ，要求相邻的四叉树结点只能相差一个层次细节。虽然这种 方法有效地解决了裂缝问题，但是模型的网格结构不紧凑，存在着许多不必要 的三角形。 为了有效减少三角形的数目，建立优化的地形网格，l i n d s h o m 等人设计了 一个实时绘制地形算法，也是基于四叉树表示【3 】。概括来说，他们使用基于三角 形块的四叉树来记录顶点，并自底而上递归地合并三角形，直到屏幕误差大于 用户定义的阈值，从而减少了地形绘制所需要的三角形数量。为了保证相邻三 角形之间没有裂缝，必须建立顶点间的相互依赖关系。该算法的优势在于，通 过计算基于视点的屏幕误差，来选择合适的三角形进行条带化构网，使得绘制 误差可控，在绘制精度和速度上有了很好的平衡。缺点是为了避免裂缝，需要 额外的数据来记录顶点的依赖关系，并且自底而上的简化需要最精细的网格结 点，将会消耗较大的内存。 文 1 0 】使用一种约束的四叉树三角化算法来绘制大尺度地形( r e s t r i c t e d q u a d t r e et r i a n g u l a t i o n , r q t ) ，有效地减少了l i n d s l r o m 方法中存在的数据冗余， 使用的内存更少。r q t 的顶点依赖关系与上一方法相同，以此构造满足绘制误 差的最小四叉树，并进行三角化，与前一方法相比，不需显示表示四叉树，只 需记录地形采样点的数字高程和误差，需要的数据量更小。 上述算法都需要在绘制时构造动态的自适应网格，当绘制精度要求较高时， 将会消耗较多的绘制时间构造网格。u m c h 提出了一种c h u n k e dl o d 结构，首 先构造地形的静态层次细节模型，然后建立四叉树结构，每个结点对应一块地 形网格。该算法在绘制时直接以四叉树结点为单位进行构网，从而简化了网格 的构造过程【1 1 】。由于结点的地形网格是预先建立好的，所以结点的连接关系可 以在预处理中完成，避免了绘制时的裂缝问题，但不足是，预先建立的静态网 格不一定是绘制时的最优网格。 基于二叉树的自适应三角嘲格 使用二叉树结构来表示地形网格，可以更精确地控制绘制网格的精度。 4 第一章绪论 d u c h a i n e a u 等人提出的r o a m 算法( r e a l - t i m eo p t i m a l l ya d a p t i n gm e s h e s ) ，在基 于二叉树的地形网格绘制方法中具有代表性【l2 1 。该算法在构网时通过强制剖分 三角形，有效地避免了t 连接，解决了裂缝问题。r o a m 算法根据视点依赖的 屏幕误差准则，在地形网格的二叉树上选择合适的三角形结点。为了利用帧与 帧之间的连贯性，他们构造了两个优先级队列进行三角形的分裂和合并操作， 对前一帧获得的这两个队列中的三角形进行调整，避免了每帧自项向下地遍历 整个地形二叉树。由于考虑了视点的连贯性，所以当视点变化不大时，三角形 数量变化不大，更新效率很高。但是，因为每一帧都需要计算队列中所有三角 形的优先级，当要求地形的绘制精度较高时，队列中的三角形数量很多，优先 级的计算将占用大量的时间，严重降低绘制速度。 为了进一步提高r o a m 算法的效率，学者们提出了多种改进算法u ”。在误 差测度计算方面，r o a m 算法使用了基于w e d g 耙的空间测度进行判断，w e d g i e 是带有一定厚度的三角形楔状体，包含了所有子三角形，这种方法计算精确， 但计算量大。为此，t u r n e r 采用一种相对误差度量方法，即计算每个三角形的斜 边中点高度和相同位置处地形的实际高度值之问的差异，作为误差度量值i l m ， 并预处理成误差树的结构，用于绘制时构网，简化了误差计算。r o a m 算法需 要较多的c p u 时间构造地形的绘制网格，当绘制精度要求较高时，构网效率低 下。p o m e m n z 对r o a m 算法进行优化，以三角形簇为基本单位进行构网，从而 减少了c p u 的消耗 1 5 】。这种算法产生的三角形数量将比r o a m 算法更多，但 精细度更高，并易于构造成三角带。l e v e n b e r g 也是从降低c p u 消耗的角度出发， 提出c a b t t ( c a c h e d a g g r e g a t e db i n a r yt r i a n g l et h 曲算法【。与p o m e r a n z 方法 不同的是，c a b t t 算法把连续多帧用到的三角形簇缓存在显存中，从而进一步 加速绘制。但该算法对视点运动的连贯性依赖较大，如果视点变化过大，会引 起缓存的三角形簇失效，反而降低绘制速度。 r o a m 算法中，为了能够访问三角形的子三角形和邻接三角形，需要记录 它们的位置，这将消耗一定的数据空间。e v a n s 等人提出了右则三角形网格算法 ( 砌g h t t r i a n g u l a t e d i r r e g u l a r n e t w o r k s ，r t i n ) ，能够高效地组织成三角形二叉树， 减少了数据冗余【1 8 】。该算法把三角形的左、右子三角形分别标记为0 和l ，这 样，二叉树的每个三角形可以使用一个二进制序列表示，称为顶点索引。通过 这种编码方法，每个三角形只需记录一个顶点的高程值和顶点索引，三角形的 5 第一章绪论 子三角形和邻接三角形都可以通过顶点索引访问得到，有效地节省了数据空间。 基于层次地形块的网格 对于图形处理器来说，一次性处理大批量的三角形比分别处理单个三角形 要快得多，随着近几年图形处理器的飞速发展，这种差距更加明显。因此先把 多个三角形组织成三角带或显示列表，然后一次性传给图形处理器进行绘制， 其效率更高。为了利用这一特点，研究者常常把地形分割为多分辨率的矩形块 结构，称作层次地形块，并建立整个地形的二叉或四叉树结构，绘制时选择多 个地形块，每个地形块内部网格的分辨率保持一致，而不同块的分辨率可能不 同。这类方法不注重进行精确的绘制构网、视域剔除，而更注重图形处理器的 批处理绘制功能，从而绘制效率很高 1 9 2 0 1 2 1 】【”，但是如何消除不同分辨率的地 形块之间的裂缝，成为这类方法的一个主要问题。 b o e r 提出了一种基于四叉树的地形块结构，称为g e o m i p m a p ( g e o m e t r i c a l m i p m a p ) 瞄w 。该结构的每个结点对应一块地形块，处于四叉树同层的地形块具有 相同的分辨率。绘制时，该算法根据视点遍历g e o m i p m a p ，并选择合适的多个 地形块拼接成完整的地形网格。但是，当相邻地形块的分辨率不同时，就会出 现裂缝。为此，作者修改较高分辨率的相邻地形块，移去地形块边界上的一些 三角形，从而消除了这种裂缝。该算法简单实用，地形块包含的三角形有规律， 易于条带化，从而便于图形处理器的批量绘制。但较高分辨率地形块的三角形 对绘制往往更重要，减少了这些地形块的三角形，会降低绘制精度。 为此，w a g n e r 通过在较低分辨率地形块上增加三角形，来消除地形块之间 的裂缝，从而保证高分辨率的地形块不受影响【2 4 】。但无论是调整低分辨率地形 块的三角形，还是高分辨率地形块的三角形，都需要耗费一定的c p u 时间，不 利于地形的快速绘制。l a r s e n 提出了一种地形掩码块的方法，可以有效减少这部 分的时间消耗瞄】。他把地形分割成大小相等的地形块。称为r e g u l a rt i l e ，为了 消除不同分辨率地形块之间的裂缝，他构造了一组掩码块，记录地形三角带的 顶点连接关系，绘制时对每个r e g u l a r t i l e 选择合适的掩码块，构造地形的绘制 网格。但该算法必须以r e g u l a r t i l e 为单位进行绘制，对于大规模的地形，参与 绘制的r e g u l a r t i l e 很多，因此绘制效率不高。 大部分地形绘制算法需要预先创建地形的层次细节模型，然后才能进行绘 6 第一章绪论 制。然而，这些地形的层次细节模型通常包含用于绘制构网的额外信息，需要 占用一定存储空间。文 2 6 1r # ，l o s a s s o 和h o p p e 把地形几何看作纹理，把c l i p m a p 结构【2 7 引入到地形中，称作g e o m e t r yc l i p m a p ，不需要记录过多的额外信息。 与前面介绍的方法不同，该算法使用的地形块是中空的矩形框，并分成四段三 角形带，绘制效率很高。但是不同分辨率的矩形框在邻接的位置会出现裂缝， 因此作者采用了一种垂直的三角形面片在邻接处进行缝补，当地形起伏不大时， 缝补的痕迹不明显。该算法的优点是，使用了纹理压缩算法来压缩地形几何， 并在绘制时根据要求进行解压缩，从而减少了地形数据量。 d a c h s b a c h e r 和s t a m m i n g e r 提出了一种为粗糙的高程图增加细节的地形绘制 算法【“。他们首先根据当前摄像机的位置，从原始地形网格中抽取出一块地形 块，称作s k e t c hm a p ，然后根据s k e t c hm a p 中每个顶点的重要性进行w a r p i n g 操作，再通过分形算法生成地形细节并绘制。这种算法并不改变地形块各顶点 的连接关系，所以不会出现裂缝现象，但是由于仅使用一块地形块，因此视域 范围受限。 1 _ 1 _ 2 基于外存的多级调度 大规模地形包含海量的几何数据，无法一次性载入内存，所以需要利用访 问速度较慢的外存( 例如硬盘) ，根据绘制需求，在外存和内存间进行调度。这 种基于外存的多级调度的方式称为o u t o f - c o r e 技术，是实现大尺度数据实时绘 制的有效手段。因为外存和内存之间的传输速度要比内存和图形处理器之间慢 得多，往往是o u t o f - c o r e 技术中的一个瓶颈，所以需要合理组织地形数据，优 化调度性能。 为了提高效率，需要对原始地形数据重新组织，使得同一区域的数据具有 很好的连续性和局部性 3 0 1 ” f 3 2 】洲。但这些算法没有考虑数据压缩，传输的数据 比较大，因此g e r s t n e r 对地形数据进行编码压缩，从而减少了每次调度的数据量 【3 6 1 。他把地形网格组织成二叉树结构，并对三角形顶点进行索引编码，使得顶 点以一维数组形式存储，便于从外存进行调度。但该算法限制了数据调度的顺 序，不能进行数据段的任意访问。为了优化数据调度，l i n d s t r o m 对如何提高内 存和外存的数据一致性问题进行研究，有效地减少了由于数据失配而造成的反 复调度操作【3 邢8 】【3 9 1 。他提出了一种三角形顶点布局方法，把顶点按照空间填 7 第一章绪论 充曲线的顺序保存，但是计算索引比较繁琐。 l i n d s t r o m 的算法可以一次性读入多个三角形顶点，但是仍然以三角形为单 位构造地形的绘制网格，进一步耗费了处理时间。c i g n o n i 等人把批量的三角形 读入操作和构网操作结合起来，提出了b d a m 技术【4 1 】【4 2 1 。他们把邻接的三角形 集合组合成不同的组，构成三角形簇，并采用t i n 结构形式，绘制时以三角形 簇为单位进行调度和构网，提高了o u t - o f - c o r e 技术的效率。 总之，o u t o f - c o r e 技术通过多级调度解决了大规模地形无法实时绘制的问 题。但由于硬盘等外存的访问速度要比内存慢得多，往往会造成绘制效率的下 降，尤其在单c p u 的计算机上，当视点运动较大时，需要等待数据调度完成， 结果出现绘制停滞的现象。所以学者们一般把算法设计成多线程的方式，并在 多c p u 的计算机上运行，才能更好体现o u t o f - c o r e 技术的优势。 1 2 植被的绘制技术 植被是自然场景的重要组成部分，具有良好绘制效果的植被可以增强虚拟 场景的真实度。但是植被结构复杂，形态各异，难以通过统一的场景建模方法 进行绘制。因此，如何表现虚拟环境中的植被景观，使其既具有一定逼真度又 能满足实时交互。多年来一直受到研究者的关注。 交互式绘制植被的。个主要思路是简化原始模型，并重组优化。按照绘制 基元的不同，植被的绘制技术分为以下五类：基于几何l o d 的绘制技术、基于 b i l l b o a r d 及其扩展类型的绘制技术、基于体纹理的绘制技术、基于图像的绘制 技术和点绘制技术。这些算法能够快速绘制一定规模的植被场景，但大都是以 单个植被样本为单位进行处理的，当场景规模进一步增大时，其绘制效率会显 著降低，难以适用于大尺度自然场景的快速绘制。 1 2 1 基于几何l o d 的绘制技术 基于几何l o d 的绘制技术是虚拟环境绘制的主要方法，很多学者把该技术 应用到植被场景的绘制中，主要过程是，计算多个植被的多边形层次模型，绘 制时根据视点，选择合适的层次构造植被。 八九十年代，研究者们主要关注于植被的生成研究，受计算机硬件条件的 限制，他们般利用树木等植被的自相似特性，使用分形等方法表示植被。这 8 第一章绪论 种表示的数据量很小，但是不能直接通过图形处理器进行绘制，必须转变成几 何多边形，因此绘制速度很慢。o p p e n h e i m e r 提出了一种基于统计自相似原理的 树木分形建模方法【4 3 】，用户通过操纵分形参数，可以快速修改树木的形态，从 而根据分形参数得到绘制的几何数据，并使用凹凸纹理增强树皮的表面细节。 该算法构造的树木模型是自相似形态的，由于自然界的树木受环境影响，生长 的结果不可能完全白相似，所以一些研究者们并没有从严格的几何意义出发， 而是强调树木的整体形态，根据用户的设计要求，就可以自动生成树木几何模 型洲【4 5 。根据这种方法所设计的植被建模软件x 如g 【忉已成功应用到工业设 计中，但生成的植被模型的几何数据往往很大，难以满足交互式绘制的需求。 d e t t s s e n 等人提出了一个过程式表示的植被场景绘制算法，有效地减少了参 与绘制的几何面片数 4 8 】。他们使用l s y s t e m 表示各种植被，因此整个场景的数 据量很小。绘制时，把植被的l s y s t e m 模型转换成视点依赖的几何网格，然后 采用光线跟踪算法进行计算，获得了栩栩如生的自然场景。该算法适用于绘制 高质量的自然场景，但是计算时间相当长，难以对虚拟场景进行交互式地访问。 随后，他们使用点、线、面形式的层次结构来简化植被模型，从而能够以交互 的速度绘制自然场景【4 9 】。但由于植被的层次结构不统一，在层次切换时难以避 免视觉的跳跃现象。 为了减弱不同层次切换时的跳跃现象，一些学者预先建立植被的连续几何 层次模型，在绘制时进行面片级的切换，但计算量更大c s o 5 1 】【5 2 【5 5 1 。r e m o l a r 等 人考虑到树叶占据了树木的大部分，提出了一种自动的外观保持的树叶简化算 法【”。在预处理阶段，该算法把两个相邻树叶合并后用新的树叶代替，建立所 有树叶的层次二叉树结构，在绘制时就可以根据视点，从该结构中选择出合适 的树叶。该算法在获得树木的整体形态同时，有效地减少了树叶的多边形数量， 但选择树叶的工作十分耗时，绘制效率不高。 总之，由于植被结构复杂，包含丰富的细节信息，往往需要大量的几何面 片来描述，因此这类技术难以承受大规模自然场景的交互绘制，而主要应用于 小范围的植被场景。 1 2 2 基于b i l l b o a r d 及其扩展类型的绘制技术 b i l l b o a r d 技术，是指将物体的采样图像，以纹理映射方式贴在多边形面片 9 第一章绪论 上，并随着观察角度的变化，多边形面片的方向随之改变【矧。该技术主要用于 复杂物体的简化绘制，例如树木、云朵、火焰、爆炸等，广泛应用于游戏引擎、 虚拟环境中。但是这种方法对植被表示过于简化，丢失了大量的细节信息。使 用多个b i l