（计算机软件与理论专业论文）实时三维地形渲染系统的研究和开发.pdf

摘要 摘要 由丁近年来计算机显示埂什能力的e 速提升使得对复杂三维场景特别是人 尺度二维地形的实时渲染得到日益j “泛的应_ l _ i 。由于大尺度三维地形场景的复杂 度远远超过了现今显示硬件的处理能力，为了保证良好的实时浏览效果，必须采 h 某种措施对场景的复杂度进行控制和调整。而目前常片；| 的基于多级模型的复杂 度控制和渲染算法计算过程人都较为复杂，在配合高速3 d 硬什使用时效果欠佳。 冈此寻求更好的关丁人尺度地形实时渲染的解决方案就具有了重要的研究干实用 价值。1 本文主要探讨的即是关丁人尺度室外地形的实时渲染问题，其主要内容包括： ( 1 ) 介绍了目前在处理和显示三维地形中常片j 的典型数据结构和和相应的算法： ( 2 ) 分析研究了典酗算法在现代3 d 硬件环境f 的缺陷；( 3 ) 提出了一种不完全 依赖多级模型的分块结构来组织地形数据；( 4 ) 以该数据结构为基础，改进了原 有的地形简化算法，提高了渲染系统的吞吐率和对显示设备的利用率：( 5 ) 并实 现了一套原型系统以验证算法的效果。 r 本文的主要特色和贡献在丁：( 1 ) 在处理和显示人尺度的三维地形时，不以 构杂原始地形最佳的简化表示为目的，提出了“使用快速简单的算法、构造次优 化的数据集合以及配合3 d 硬件需求”的原则：( 2 ) 使用了不同于以往的混合了 分块和层级结构的地形数据组织方式，对经典的地形简化算法进行了简化和改进 从而有效的降低了算法运行时的计算量，并使得处理后的地形数据能够方便快速 的送入显示硬件。( 3 ) 实现了一套实时地形渲染原型系统，验证了上述算法的有 效性。并且，该系统具有良好的体系结构和可扩展性，再经过进一步的_ 歼发和优 化后，即可构成一套完整的、具有实用价值的三维地形渲染系统。 关键字：益实莳渣桑，高度场，地形，四叉树，多级筷堑，细节度，视矩亲近关键字：3 d ，实时渲染，高度场，地形，四叉树，多级模型，细节度，视矩拣选 遮挡拣选 、一r a b s t r a c t a b s t r a c t w i t ht h er a p i de v o l u t i o no fm o d e md i s p l a yh a r d w a r e ，r e a l t i m er e n d e r i n go fc o m p l e x3 d s c e n e ，e s p e c i a l l yl a r g es c a l e do u t d o o rl a n d s c a p e ，h a sa t t r a c t e dg r o w i n g i n t e r e s ti nt h el a s tf e wy e a r h o w e v e r ，i n t e r a c t i v ev i s u a l i z a t i o no fl a r g es c a l e dt e r r a i ni ss t i l lah a r dp r o b l e m ，b e c a u s eo fi t s o v e r - c o m p l e x i t y t h a te v e nm o d e m3 dh a r d w a r ec a n n o th a n d l e t oa c h i e v es m o o t hv i s u a l i z a t i o n ， s c e n ec o m p l e x i t ym u s tb ec o n t r o l l e da n da d j u s t e dt o a d a p tt h eh a r d w a r ec a p a b i l i t y m o s to f c u r r e n tr e a l - t i m er e n d e r i n ga l g o r i t h m sf o rl a r g es c a l e dt e r r a i nw e r ei n v e n t e dl o n gb e f o r eh a r d w a r e r e n d e r i n g b e c a m et h e i n d u s t r y ss t a n d a r d ，a n dh a v et h e l i m i t a t i o no fh e a v yc p uo v e r h e a d ， c o m p a r i n g w i t hm o d e mh a r d w a r e sp r o c e s s i n gs p e e d ，a n dt h e r e f o r em a y n o tb es u i t a b l et ob eu s e d i nc o n j u n c t i o nw i t h t o d a y s3 d h a r d w a r e r e n d e r i n ga n y m o r es of i n d i n gm o r ea p p r o p r i a t es o l u t i o n a b o u tt h i sp r o b l e m g e t sf a i r l yv a l u ei np r a c t i c e t h i st h e s i sd e s c r i b eas o l u t i o nf o re f f e c t i v e l yr e n d e r i n go f l a r g e s c a l eo u t d o o rl a n d s c a p ei n r e a l 。t i m e ，i n c l u d i n g ：( 1 ) i n t r o d u c i n g t h et y p i c a lt e r r a i nd a t a o r g a n i z a t i o n a n dc o r r e s p o n d i n g a l g o r i t h m s i n t h i s f i e l d ；( 2 ) a n a l y z i n gt h ed e f e c t i o n s o ft y p i c a l a l g o r i t h m su n d e rm o d e m3 d h a r d w a r ee n v i r o n m e n t ；( 3 ) d e s c r i b i n gan e w h y b r i dd a t as t r u c t u r ef o ro r g a n i z a t i o no fl a r g es c a l e d g r i d ，( 4 ) a n d a l l i m p r o v e dt e r r a i ns i m p l i f i c a t i o na l g o r i t h mb a s e do nt h a td a t as t r u c t u r e ；( 5 1 i m p l e m e n t i n gap r o t o t y p et e r r a i nr e n d e r i n gs y s t e mw i t ha b o v ea l g o r i t h m s t h em a i nf e a t u r e sa n dc o n t r i b u t i o n sa r e ：( 1 ) p r e s e n t i n gan e w p r i n c i p l eo f “c o a r s ea n df a s t s i m p l i f i c a t i o nw i t hs i m p l ea n df a s ta l g o r i t h m ，a n dc o m p l y i n gw i t hr e q u i r e m e n t so fm o d e r n 3 d h a r d w a r e ”；( 2 ) t r y i n gt og s eac o m b i n a t i o no fb l o c k b a s e da n dq u a d t r e e - b a s e dd a t as t r u c t u r e a n di m p r o v i n gt h et y p i c a ls i m p l i f i c a t i o n a l g o r i t h m ，w h i c hg r e a t l yi n c r e a s i n gt h et h r o u g h p u to f w h o l es y s t e ma n du t i l i t yf a c t o ro fd i s p l a yh a r d w a r e ；( 3 ) i m p l e m e n t i n ga p r o t o t y p er e a l t i m e r e n d e r i n gs y s t e m w i t h g o o d a r c h i t e c t u r ea n d e x p a n d a b i l i t y , w h i c hn o to n l ya p p r o v et h e e f f e c t i v e n e s so fa l g o r i t h m si nt h et h e s i s ，b u ta l s oc a nb eu s e da sap r a c t i c a lr e n d e r i n gs y s t e mi n r e a la p p l i c a t i o nw i t h o u tt o om u c he f f o r t k e y w o r d s ：3 d ，r e a l - t i m er e n d e r i n g ，h e i g h t - f i e l d ，t e r r a i n ，q u a d t r e e ，m u l t i r e s o l u t i o nm o d e l ，l o d v i e w - f r u s t u m c u l l i n g ，o c c l u s i o nc u l l i n g 第1 章 1 1 引言 第1 章绪论 观代计算机i ? 业的发展使计算机的i 耋算述度以令人炫目的迷度向上攀升，特别是在实时 二维幽形的计算平显示方面。目前即使是个人p c 的幽形运算速度已经达到或超过了) l i f 前 的 业幽7 口 作站的水平。壁什能力的提高使得二维实时幽形在现代国民生产生活的符个领 域如计算机辅助设计与制造( c a d & c a m ) 、地理信息系统( g | s ) 等方面中得到了迅述 而j i 泛的应用。 土日前的主流图形埂什已经能够以令人满意的速度显示由上万个二角形绷成的逼真的 二维场景。但是，住许多实际的应垌中，几何模，议的规模和复杂度仍l r 远远超过了现今蚓形 - 自f 的处理能力。这个问题在某些交互处理人规模二维多边形数据的麻瑚，如本文要讨论的 人尺嗖二：维地形的交且显示中，显得尤为尖山。冈此寻找更女r 的处理人规模二维数据的方法 一直是近年米隆l 彤学_ 【j j f 究的热点。 列r 人尺度的地形模 口的米说，有许多冈素影响对其交互的显示，其中最主要的就是；宣 染效率。由r 当今显示慢什的处理能力相对有限，地形的复杂度必须被尽可能的降低，唰f | f 义不能严重影响最终的输出结果，为此发展出了一系列的专f j 的算法。这些算法人部通过建 立原始地形的不同精度的多级模型，实时的建立原始地形的简化表示，从而完成对人尺度地 形的交且显示。 本文的土要 窬就是研究如何实时的建也 l l 显示人尺度地形模型的简化表示，并建立一 套桐天的系统。 1 2 主要的研究和开发内容 l研究i j 前典，w 的川r 地形渲染的数据结构和算法： 2 分忻它州住当今硬什环境p 存在的缺陷： 3 建j ：一套适圳y - 人尺皮室外地形渲染和高速3 d 硬件的地形模型，爿以此模，弘为基础实 现地形简化、视矩拣选( v i e w f i u s l u n lc u l l i n g ) 和遮挡拣选( o c c l u s i o nc u l l i n g ) 苫算 法。 4 以上述摸让和1 弹法为基础建立一个实n , t 的2 维地形渲染系统。 l 1 3 本文的内容安排 形 是 地 章 的 6朋第 常 ； 前 现 目 实 些 和 一 构 绍 结 介 系 将 体中的章统 4 系 第似 钒 章豫第 组 蠡罴 形 耻 地 圳 留 使 介 扣 。 饨 缈 献艏繇锹种峨黪 第 法 最 盘 算 一 显 总 笫2 章 _，一。+“。+-。1_。1。一 第2 章地形数据的定义和组织 本章将士要介2 “计算机幽形学中地形数据的基本组织形式，同时对一些基本术语做出定义雨 滢明。 2 1 高度场( h e i g h t f i e l d ) 简单的说，一个高度场就是一个元的方稗：= 、( x ，y ) ，其中变量x 和y 定义证 个近续的一维f 域d 上。由这个定义可以石山，高度场是定义在一个连续区域上的概念 口、l 此我们无法通过存储一系列的数值点米完全的表示整个高度场。通常情况f 舀：计算机图形 学中处理的高度场事实上只是理论的高度场的一个离散的近似，即矗d 上定义多个采样点 然后 r 据这些采样点的值米构造一个多边形的、离散的近似表示。根据采样点的不同，存在 着多种万式米近似的表示一个高度场。当采样点在z 、y 方向上以1 矧定的间隔分布时，所有 的采样点就绀成了一锕规删的格点( g r i d ) ( j ? 。由丁在本系统中将使刚格点作为存储地形数 据的丛本数据结构，冈此在术特圳 & 明的情况f ，本文中的“高度场”即指代理论高度场 的规则近似表示一格点。 兄外，由r 高度场的最典型的应h j 就是米表示一个地形( t e l t a i n ) ，从而导致住1 7 r 多 情况f ，高度场( h e i g h tf i e l d ) 和地形( t e r t i a n ) 被当作是同义词。但严格的说，这两个概 念，f 不相同，有些地形是无法用高度场米表示的。在不发生混淆的情况f ，本文将混埘这西 个概念，即本文中的“地形”即指代可以j j 高度场( 即“格点”) 米表示的地形。 逊常情况f ，我们在二维空阃中指定一个点时，需要其x 、y 、z 二个方向的坐标。越对 高度场，只需要x 、y 两个值就可以定义高度场上的一点。事实上，有些时候高度场铍称 作是“25 d ”的数据结构【2 1 。冈为它比籽通的2 - d 数据要复杂，但义称不上是真止的3 - d 致据。这个特r 主使得我们处理高度场d 十，可以使州一些不同丁_ ；i 孚通二维场景的技术。 2 2 地形数据的树形表示 住儿乎所有的实时渲染应_ l f 中，都将原始的高度场数据以树形的结构米组织和表示。这 是由1 i 高度场中通常包含的数据最非常巨火，直接逐点处理高度场中数据的效率十分低f ， 而树形结构为高度场的数据带来了继承关系，这为加速高度场的处理提供了条件，而且树形 第2 帝 结构也是构造f 两章中适j ；j 的多级模型( m u l t i r e s o l u t i o nm o d e l ) 3 ) 的基础。 r 面我们介 “一些儿种经常h 到的地形数据的树形表示： 2 2 1 四叉树( q u a d t r e e ) 在二维计算机幽形。学中，八义树( o c t r e e ) 最常地的空间递门划分方法。它将给定的k 方体空间递9 7 的划分成8 个子空间，j i ：据此定义一个除了叫竹点咀外每个竹点都有8 个子1 i j 1 的树形结构。目jr 八义树在x 、y 、z 二个坐标轴方向e 都是对等的，冈而可以h j 未表示 任意结 勾的二二维场景。显然，封丁只有25 维的高度场米说，八义树显得有些过分复j ! 丁。 对 一个高度场，由r 住给定的( x ，y ) 坐标上至多只能仃个z 值，冈此我们可以消七八义 耐的第：二维，从而将八义树简化成一个一维的皈本一四义树。与八义树类似，四义树通过将 个l ： ：方形的平面l 趸域递归的划分成4 个子区域来定义一个具有4 义的树形结构。 四义树具有个良女f 的特肚，就是对丁一裸给定的凹义树、7 f 一个1 1 4 - 的旧边形刚络! j 填对应，反之亦然，如幽2l 所示。闪而可以很方便的川四义树米表示任意的凹边形网格， 比如高度场及其近似表示。另外，由r 原始高度场数据的定义域多为比方形，和四义树确儿 似上的相似性，从而使四义树成为目前最通瑚的矧织地形数据的数据结构。 12 ， 56 3 ， 78 夕八 图21四边形网格与对应的四叉树 分级的、基r 四义树的参数曲面三角化技术首先是出现在论文【4 中。其基本思想是： 在参数空间中，对曲面进行递归的四义划分，商到每一一个取样医域都满足对曲线近似的误筹 的边界条俐。住论文【4 中对递门划分添加了个特别的限制条件，即：相邻1 7 点的闻的划 分级 ；i j 之芹限制在一级以内。在如此限制条什r 构造山的四义树称为：限定性四叉树。如蚓 一8 一 旃2 章 2 2 所示 l i l ( a il h广一一j 怍 ” i i 图2 2 非限定性四叉树( a ) 和限定性四叉树( b ) ( b ) 从高度场构造限定性四义树的基本过f ￥如h 1 首先将整个高度场右作是一个单一的区域： 2 根据某个谩筹计算公式对当前每个r 域的误著进行估芹： 3 当某个p 瓦，则将该i ，点划分成四个子* 点，并对每个f1 ，点递归执行本步骤： 否! j l c j ，结求对本竹点的计算过程。 最后，检奋四义树是否符合限定性规则，j 1 ：加以必要的凋祭。 以及相应的四义树的：i 角化方法： 从四义树的根1 y 点起执行r 面的步骤： 如果当前m s 宵j ：m j t ，刘j 二1 ，1 递9m 目川本步骤；否则，如果构造四义树州 本1 ，点的j 。、 瓯t 0 将本1 7 点二角化为两个共享剁边的锋暇直角二角形， 如果4 巧。、j h ! l | j 删除木伊点中瞑。 r e s u l t t h e n c o m p u t e 。m “f o r l e v e lf ； i f 。，。x r t h e n r e s u l t 卜1 ： e n d i f e n d l f e n d f o r r e t u r nr e s u l l 3 5 3 构造匹配的三角网络 从单元块构造= 角形网络的基本方法是：将单元块中每个小矩形分割成两个直角二角 形。但当相邻的两个单元块的可见层不同时，它们相接的地方便有可能出现裂缝。这就是本 章前面曾提剑的“匹酉己”问题。为了保证整个地形网格的匹配，我们必须对基本的构造方法 做一些修改。 如幽313 所示，假设幽中该单元块的左方是一个可见层级别高一层的单元块，而f 面 是一个可见层级别高两层的单元块，则按照图3i 3 中的方式所构造出的三角网络就能够与 左方利j 、方的单元块很好的吻合了。 这种修改方法的一个额外优点是，我们只需改变它们之间的迎接方式，而无需触及顶点 本身，这也止女，符合我们“减少对顶点的读操作”的思想。 2 5 鹅3 帝 o 一o 一o i j o o o l i i 0 一 图31 3 为构造匹配的三角网络而调整过的单元块 图中灰色的顶点将不包含在最终的三角网络中 2 6 o lolj ioo | 3么飞趁 弛4 帝 第4 章基于四叉树的拣选计算 浏览人尺度的一j 维地形时，对丁二一个给定的视点位置平视线方向，通常只有小部分的 地形是可见的。那些处丁视野以外的部分、被其它物体遮挡的部分，对屏幕上的最终幽像则 完全没订贡献。为此，住对整个模型作进一步( 比如送入显示埂件中进行儿何变换和光栅化 处理) 的处理前，我们i 】以根据当前视点的位置以及视线7 j 向等参数对地形进行拣选，剔除 琊些不叨址的部分，减小后续处理中的数据量，从而提高帮个系统的渲染效率。 本章土要介 f j ，本系统中h j 剑的儿种拣选算法。 4 1 视矩拣选( v i e w - f r u s t u mc u l l i n g ) 我州在浏览一个= 维场景时，帮个场景往往有很人一部分是处往我们视野范席f 以外的， 它们对最终的屏幕i 划像完全没有贡献，冈为住将二维数据送入显示埂什以前，我们完全可以 将视野以外的部分剔除，从而减小显示硬什的负担。冈为在计算机幽形学中，人的视野微抽 象成一个四棱台，即“视矩体( v i e w f i h s | u m ) ”，冈此这种拣选技术就破称作“视矩拣选 ( v i e w f 1 f u s t u i l lc u l l i n g ) ”。 最直接的视矩拣选的方法就是对r 二维场景中的每一个物体，或者个二维模7 hr 的俅 一个顶点，汁算其与视矩体的位萱芙系，然后剔除那些处枉视矩体外面的部分。但当场景1 常复杂、域数据量1 f 常人时，这种拣选的算法会耗费太多的时间，以至丁完全抵消了减轻显 示埂什的负担所带米的性能提升。为了提高视矩拣选的效率，可以将场景瑚树状结构组纵起 来。j f 使该树形结构具有如f 的特性：当父i ，点完全处丁i 视矩体外时，其所有的子1 ，点也必 定处l ：视矩体外；相应的，当父竹点完全处丁视矩体内时，其所有的于节点也必定处r 视矩 体内。这就为我们提供了一条高效率的实现视矩拣选的途径。这利，依赖树形结构的视矩拣选 算法被称作：h i e r a r c h i c a lv i e w f r u s t u mc u l l i n g 11 4 1 1 视野的定义一视矩体 一个视矩体由视点位置、视线方向、视野夹角、近拣选平面和远拣选平面等参数米定义 如幽31 所示。在浏览三维场景时，只有处 一视矩体以内的部分是可见的。 笫4 章 ( a ) 远、近拣选平面问的部分就是视矩体 视点位置舅 一 视女 k ， 视野夹角i 远剪裁 沂宦g j战平而、 ( b ) 灰色部分是视矩体 图4 1 视矩体的定义 4 1 2 轴对齐的长方体和视矩的空间位置判定 面 此处的艮方体特指各个边部分别和x 、y 、z 坐标轴平行的i = 方体。此类k 方体干视矩 的空间位置判定是地形视矩拣选的基础。 i ) 求解视矩备平面的平面方程： 由上1 ，的介 f j 可知，一个视矩是由八个平面所包用起来的空间，为了判定艮方体和视矩 的俺置关系，我们首先必须知道包围视矩体的六个平面的平面方程。 为了简化计算，这里我门假发视点位置为坐标原点，视线方向为z 轴负方向，观察者 一 堡三至一一一 的右手方向为x 轴二方向，头顺的方向为y 轴正方向。 令三。，和z m 为近、远拣选平面到视点的距离，_ n 和4 ，分别为观察者的水平视角和垂 直视角。则包翮视矩体的六个平面的方程分别为： z = 一z 。， 一z = 乙， 一y + z t a b 爿，= 0 y + = t a n 爿、= 0 一+ z t a l l a 。= 0 + z t a n 爿。= 0 对r 处r 空间任意位置的视矩体，则要根据视点的位置、视线方向、以及观察者的局部 上方向计算出空间变换矩阵m ，然后将上述方程根据m 进行变换。 2 )长方体和与空间平面的位置关系判定 i 殳空间平面p 的方程为：a x + 缈十c = d ，则平面的法向鬣为霄= a b c ，1 ： 面的外侧即为力所指的方向。k 方体c 由其顶点，i 2 ，1 6 定义。 则k 方体和平面的位置芙系判定算法如f ： 1当c 的j i 个顶点都处rp 的外侧，即对长方体的任意一个顶点r 。，都有 刃曙d ，则该长方体完全处丁平面的外删： 2当c 的八个顶点都处rp 的内侧，即对k 方体的任意一个顶点圪，都有 嘭d ，则该k 方体完全处r 平面的内侧： 3若i 、2 都不满足，则该长方体于平面相交。 3 )长方体与视矩体的空间位置关系判定 有r 以上的知识，我们就可以判定一个给定的轴对齐的长方体和一个给定的视矩体是否 相交其刿定算法是： 依次计算长方体r 视矩体各个平面的位置关系，根据其结果有以f 三种结论： 1当长方体完全处丁某一平面的外侧时，则该长方体完全处在视矩体的外面： 2若对于视矩体的每一个平面，长方体均完全