（教育技术学专业论文）genesis3d开放场景terrain扩展模块.pdf

g e n e s i s 3 d 开放场景t e r r a i n 扩展模块 教育技术学专业 研究生黄鹭指导教师张松副教授 摘要；t e r r a i n 渲染是当前g a m e 开发中很热门的一个领域。传统的基于b s p 的3 d 引擎在渲染开放大场景时候往往显得无能为力。由于b s p 的场景分割原 理，导致过多的多面体会进入到渲染流水线中，造成瓶颈。基于l o d ( l e v e lo f d e t a i l ) 计算的场景渲染算法在一定程度上可以解决这个问题。然而，传统的给 予高度图的t e r r a i n 算法，会导致两个问题： o ) 表示场景中的活动物体 ( 比如：门，升降台) m o d e l 0 对应一个b s p 树m o d e l 中还有f i r s t l e a f , n u m o f l e a f s 来记 录对应的l e a f s m o d e l 结构中有一个i n t a r e a 2 l l 勺结构，对于本身是活动门的m o d e l ，正好 可以记录连通的两个a r e a a r e a ： 相当于我们上面所说的r e g i o n 的概念，g e n e s i s 3 d 的一个场景中最多允许 2 5 6 个a r e a l 这可以从它的w o r l d 结构中的a r e a c o n n e c t i o n 2 5 6 2 5 6 看出，1 表示连同，0 表示不通a r e a 之间的连通性通过m o d e l i ( i 0 ) 来控制：b o o lv i s f r a m e 表示a r e a 是否 可见 n o d e ：b s p 上的结点，b o o lv i s f r a m e 表示n o d e 是否可见 l e a f ： 划分世界的b s p 的叶子，每个l e a f 上都有一个a r e a 的i n d e x ，每个l e a f 上都有一个c l u s t e r 的i n d e x ，以及一个p o l y g o nl i s t 的指针 a c t o r ：活动的角色 v i s _ v i s w o r l a ( i ：x 器攮测冀设嫠霹堡璧 r e n d e r s c e n e ( ：i ：) ： 毫 8 3 2 改良方案 t e r r e i n 引擎是让g e n e s i s 3 d 实现室外场景渲染的最好办法。它采用一系列 自适应的动态的s u b d i v i s i o n 技术来动态地生成和渲染室外的场景。所谓 s u b d i v i s i o n 是一种使用了一系列启发式的方法来决定地形的哪一部分需要看 起来有更多的细节的技术。在这里，对于地形渲染的许多技术挑战的最困难的 是如何存储一个地形的特征。高度图是事实上的标准解决方案，简单的说，就 是保存地形每点高度的二维数组。 3 3g e n e s i s 3 dt e r r a i n 渲染引擎 3 3 1 实时t e r r a i n 对于实时t e r r a i n 生成和渲染的算法有三篇著名的论文，作者分别为 1 】微 软的h o p p e 2 l i n d s t r o m 3 d u c h a l n c a u 。 在第一位作者的论文中描绘了一个基于p r o g r e s s i v em e s h e s 的法则，这是 一个与增加三角形到任意网格来达到你需要的细节相关的新的和绝妙的技术。 但这项技术的缺点是需要大量的内存。 第二篇论文的作者是l i n d s t r o m ，他阐述了基于四叉树( q u a dt r e e ) 的地 形细分算法，用一个四叉树递归的把一个地形分割成一个一个小块( t e s s e l l a t e s ) 并建立一个近似的高度图。四叉树非常简单但很有效。 第三篇论文的作者是d u c h a l n e a u ，他描述了一个基于二元三角树结构的算 法r o a m ( r e a l 。t i m eo p t i m a l l y a d a p t i n gm e s h e s ) 实时优化自适应网格。这里每 一个小片( p a t c h ) 都是一个单独的正二等边三角形，从它的顶点到对面斜边 的中点分割三角形为两个新的正等边三角形，分割是递归进行的可以被子三角 形重复直到达到希望的细节等级。由于r o a m 法则的简单和可扩展性。不幸的 是这片论文非常短，仅仅只有少量的伪代码。但无论如何，他可以在连续的范 围实现从最基本的平面到最高级的优化。而且r o a m 分割成小方块非常快速， 而且可以动态更新高度图。 l o 3 3 2 基本思路 一个概述来介绍这个法则，然后讨论单独的小块是如何相互影响的： a 高度图文件被载入内存并和一个m e g a t e r r a i n f a c t o r y 类的实例相联系，多 个m e g a t e r r a i n f a c t o r y 物体连接起来产生无限的地形。 b 一个新的m e g a t e r r a i n f a c t o r y 物体把载入的高度图的一部分包裹到新的 m e g a t e r r a i n s e c t o r 类物体中，这一步的目的是： 使用基于树的结构来控制随着深度而呈指数增长的内存，这样可以保持它们 的深度在一个很小的有限的范围。 动态更新高度图需要在变更场景时有一个完整的变更树m e g a t e r r a i n s e c t o r 类实例会导致较严重的延滞。 州k c l s e c t ll 、 ；e c t o r 图1 ：t e r r a i n 结构概图 c 每一个m e g a t e r r a i n s e c t o r ，包含若干事先定义好的t i l e ，如上图( 图1 ) 大方格中的小方格m e g a t e r r a i n t i l e ，被用来建立一个m e s h 的近似值。 m e g a t e r r a i n t i l e 类物体使用了二元三角树的结构来存储即将显示在屏幕上 的三角的坐标m e g a p a t c h 。这些三角形顶点坐标被非常合理的存储，r o a m 使用 3 6 字节以上的内存来存储每一个三角形。 d 在分割完高度图后，引擎已经建立了二元三角树。树的叶节点保存了需 要进入图形渲染流水线的三角形。 3 3 3 二元三角树b i n a r yt r i a n g l et r e e s r o a m 使用了二元三角树来保持三角坐标而不是存储一个巨大的三角形坐 标数组来描绘地形。这个结构可以看作是一个测量员把地形切断为一个一个小三 角块的结果。这些三角块逻辑上看就象一组相连的邻居一样( 左右邻居) 。同样 的当一个三角块把土地当作遗产时，他需要平等的分给两个儿子。如( 图2 ) 用这样进行扩展，这个三角块就是二元三角树的根节点，其他三角块也是他 们各自树的根节点。我们用m e g a t e r r a i n t i l e 保存着所有三角块的索引，同时也 保存它们之间的层次关系。 图2 二元三角树结构等级0 - 3 二元三角树被m a g e p a t c h 结构保存，同时他还保存r o a m 需要的五个最 基本的数据，参考( 图二) 。 1 2 c l a s sm e g a e a t c h p u b l i c ： m e g a p a t c h 0 ； m e g a p a t c h ( m e g a t e r r a i n s e c t o r + p p a r e n t ， m e g a v e r t e x + i v ， m e g a v e r t e x + r v ， m e g a v e r t e x + t v ， m e g a b i n t r i t r e e + p t r e e ， i n tn t r e e i d ) ； m e g a p a t c h ( ) ； v o i dc l e a r c h i l d t r e e 0 ； v o i dr e n d e r ( ) ； v o i du p d a t e p o s i t i o n o ； m e g a p a t c h +mp n e x t ； f o rl i n k e dl i s t s i n t m _ n t r e e i d ；f o rv a r i a n c et a b l el o o k u p m e g a b i n t r i t r e e +m _ p o w n e r t r e e ； m e g a v e r t e x + m _ _ p l e f t v e r t ；i v m e g a v e r t e x + m _ _ p r i g h t v e r t ；r y m e g a v e r t e x + m _ p t o p v e r t ； t v m e g a v e r t e x + m _ p s u b v e r t ； m e g a p a t c h + m _ p p a r e n t ； m e g a p a t c h + m _ p l e f t c h i l d ； m e g a p a t c h + m _ p r i g h t c h i l d ； m e g a p a t c h + m _ p l e t 【n e i g h b o r ； m e g a p a t c h + m _ p r i g h t n e i g h b o r ； 1 3 m e g a p a t c h + m _ p b o t t o m n e i g h b o r ； m e g a t e r r a i n s e c t o r + m _ p t e r r a i n m a p t o pv e r t e x 图3 基本的二元三角树的节点m e g a p a t c h 的结构 当对高度图建立一个网格模拟值时，我们需要向二元三角树中添加子节点 直到达到我们需要的细节。这一步完成后重新遍历整个树，此时把子节点中保 存的三角形数据渲染到屏幕上。这就是一个最基本的引擎了但需要重新设置每 一帧，这种递归的方法最大的优点是我们不需要保存每一个顶点的数据，可以 释放大量的内存给其他物体。实际上，m e g a p a t c h 结构需要多次的建立和销毁， 为此我们创建了一个m e g a p a t c h p o o l 的静态内存池。这种方法是非常高效的， 容许我们频繁建立和销毁几万个这样的结构而不致在内存中造成内存上的空 洞。 1 4 图4 典型的地形p a t c h ，从左至右依次是网格模式，光照模式，纹理模式 33 4 m e g a t e r r a i n s e c t o r 类的详解 m e g a t e r r a i n s e c t 。r 类对地形的细节渲染进行了高级的封装，通过一些简 单的函数调用我们可以在屏幕缓冲中进行从简单的点的显示到复杂的地形渲 染工作。这里是g a t e r r a i n s e c t o r 类的定义。 c l a s sm e g a t e r r a i n s e c t o r p u b l i c ： m e g a t e r r a i n s e c t o r ( ) ) ； m e g a t e r r a i n s e c t o r ( q x t e r r a i n d e n n i t i o n & t e r r a i n d e f ) ； v i r t u a l m e g a t e r r a i n s e c t o r 0 ； v i r t u a lb o o l r e n d e r ( ) ； v i r t u a lb o o l r e n d e r w i r e f r a m e ( ) ； v i r t u a lv o i d d r a w ( ) ； v i r t u a li n t f r a m e ( ) ； v i r t u a lb o o i i n i t b a s e v e r t s ( ) ； v i r t u a lv o i d l i g h t v e r t e x ( m e g a v e r t e x + p v e r t ) ； v i r t u a lv o i d l i g h t v e r t e x w i r e f r a m e ( m e g a v e r t e x + p v e r t ) ； v i r t u a lv o i d l i g h t v e r t e x ( m e g a v e r t e x + p v e r t ，g e r g b a + p c o l o r ) v i r t u a lv o i d v i r t u a lv o i d v i n u a lv o i d v i r t u a lb o o li n i t 0 ； v i r t u a l v i r t u a l l i g h t a l l v e r t s ( g e _ r g b a + p c o l o r ) ； l i g h t a l l v e r t s ( f l o a ta l p h a ) ； l i g h t a l l v e r t s 0 ； g e b i t m a p + g e t t e x t u r e 0 r e t u r nm _ p t e x t u r e ；) g e b i t m a p g e t t e x t u r e ( i n ti ) r e t u r nm _ p t e x t u r e ；) v o i dp u t p o l y ( m e g a p a t c h ”p ) m _ p p o l y p o o l - p u t p o l y ( p ) ；) v o i dp u t v e r t ( m e g a v e r t e x ”p ) m _ p v e r t p o o l - p u t v e r t ( p ) ；) v i r t u a li m l6g e t e l e m e n t h e i g h t ( i mx ，i n tz ) 2 o ； v i r t u a lb o o ls e t c u r r e n t v e r t h e i g h t ( m e g a v e r t e x + p v e r t ) ； v i r t u a li m l 6g e t e l e m e n t h e i g h t u n s c a l e d ( i n tx ，i n tz ) r e t u r n g e t e l e m e n t h e i 曲t ( x ，z ) ； i n t s e t d i s t a n c e d e t a i l ( i n tn e w d e t a i l ) ； i n t g e t p o l y c o u n t 0 r e t u r nm _ n p o l y c o u n t ；) v o i d s e t n o r m a l d i s t a n c e t o c a m e r a ( f l o a td m _ f n o r m a l d i s t a n c e t o c a m e r a 2 f ， v i r t u a lv o i dr e b u i l d a l l t e x t u r e s 0 ) 1 6 v i r t u a lv o i ds h a d e t e x t u r e ( ) ； v o i d s e t r e n d e r f l a g s ( i n tn ) mn r e n d e r f l a g s = n ；) p r o t e c t e d ： i n t m _ n r e n d e r f i a g s ； h e i g h m a pl e n g t ha n dw i d t h i n t m _ n h e i g h t m a p w i d t h ； i n t m _ n h e i g h t m a p l e n g t h ； i n t m _ n h e i g h t m a p s i z e ； i n d i v i d u a lt i l el e n g t ha n d w i d t h i n t m _ n t i l e s i z e ； n u m b e ro f t i l e si nw i d t ha n dl e n g t h i n t m _ n t i l e s c o u n t x ； i n t m _ n t i l e s c o u n l z ； i n t m _ n t i l e s c o u n t t o t a l ； i n t m _ n h e i g h t e l e m e n t s p e r t i l e ； i n d e xo f t h i sp a t c h p o s i t i o ni nt h ew o r l d ( x ，z ) i n t m _ n m a p o f f s e t l n d e x x ； i n t m _ n m a p o f f s e t i n d e x z ； i tw o r l dc 0 0 r d i n a t eo f f s e t s i n t m _ n m a p o f f s e t z ； i n t m _ n m a p o f f s e t x ； t h ea c t u a lw o r l ds i z eo f t h i st e r r a i n i n t m _ n m e g a t e r r a i n f a c t o r y s i z e ； i n t i n t m _ n p o l y c o u n t ； m _ n d e s i r e d p o l y c o u n t ； 1 7 m t c s t r i n g c s t r i n g m _ n m i n p o l y c o u n t ； m s t r t e x t u r e f i l e ； m _ s t r a l p h a f i l e ； m _ b u p d a t e ； b o o l m _ b r e n d e r b a c k f a c e ； g e r g b am _ c u r r e n t v e r t c o l o r ； | | t h e s ea r ep o i n t sw h i c hl i eo nt h ev i e wf i a l s t r u mh a l f s p a c ep l a n e s | | g e v e c 3 df m s t m m l e f t ； g e v e c 3 df m s t r u m r j g h t ； g e v e c 3 df r u s t r u m t o p ； g e v e c 3 df m s t r u m b o t t o m ； g e v e c 3 df r u s t r u m n e a r ； g e v e c 3 df r u s t r u m f a r ； | | n o r m a lf o re a c hh a l f s p a c ep l a n e | | g e v e c 3 dn o r m a l l e f t ； g e v e c 3 dn o r m a i r i g h t ； g e v e c 3 dn o r m a l t o p ； g e v e c 3 dn o r m a l b o t t o m ； g e v e c 3 dn o r m a l n e a r ； 1 8 g e v e c 3 dn o r m a l f a r ； g e b i t m a p +m _ p t e x t u r e q x v e r t p o o l +m _ p v e r t p o o l ； m e g a p a t c h p o o l +m _ _ p p o l y p o o l ； m e g a t e r r a i n t i l e + +m p p b a s e t i l e s ；p o i n t e rt oa r r a yo f ) m e g a t e r r a i n s e c t o r 类管理了一个大的正三角块，同时可以和其他 m e g a t e r r a i n s e c t o r 物体一起工作。 在初始化过程i n i t i a l 中，高度图被分割成大量的可管理的小块m e g a t i l e ， 将m _ p v e r t p o o l 指向我们分配的静态内存池。同时将每个属于该s e c t o r 的t i l e 和一个新的m e g a p a t c h 实例联系起来。 3 3 5 m e g a p a t c h 类详解 m e g a p a t c h 类是这个引擎的灵魂，可以分为两部分，一半是递归部分，另 一半是基本函数部分，下面就是这个类的数据成员和基本函数描述： c l a s sm e g a p a t c h p u b l i c ： m e g a p a t c h ( ) ； m e g a p a t c h ( m e g a t e r r a i n f a c t o r y + p p a r e n t ， m e g a v e r t e x + i v , 9 m e g a v e r t e x + i v , m e g a v e r t e x + t v , m e g a b i n t r i t r e e + p t r e e ， i n tn t r e e i d ) ； m e g a p a t c h ( ) ； v o i dc l e a r c h i l d t r e e ( ) ； v o i dr e n d e r o ； 根据定点的位置设定更新p a t c h 的位置 v o i d u p d a t e p o s i t i o n 0 ； 更新所有的v i e w - f r u s t r u m 旗标 v o i du p d a t e v i e w f l a g s 0 ； 更新优先级 i n tc a l c p r i o r i t y ( i mn n e a r e s t l s h i g h e s t 2 o ) ； p r i v a t e ： v o i ds e t v i e w f l a g s a u o u t 0 ； v o i ds e t v i e w f l a g s a l l l n 0 ； g e v e c 3 dp o s i t i o n ； # 3 d p o i n t ，c e n t e r o f p a t c h ( p o l y g o n ) u s e d f o r p r i o r i t y i n s t e a d 一t r u ei f p o l yi sr e n d e r e d e l s e f a l s ei f h a ss u b p o l y s r e n d e r e d b o o l m _ b a c t i v e ； m e g a p a t c h +m _ p n e x t ；f o r l i n k e dl i s t s i n tmn t r e e i d ；f o rv a r i a n c et a b l el o o k u p m e g a b i n t r i t r e e +m _ p o w n e r t r e e ； m e g a v e r t e x + m _ p l e r v e r t ；l v m e g a v e r t e x + m _ p r i g h t v e r t ；i v m e g a v e r t e x + m _ p t o p v e r t ； t v + s u b v e r t - c h i l dv e r t e x w i l lb et h e ”t o p _ v e r t ”o f i t sc h i l dt r i s c o d e t h i s ，s i n c en o t r im a n a g e si t so w n v e r t s ( e a c hv e r ti sm a n a g e db y t h en e x t h i g h e rs t r u c t u r e ， w h e t h e ri t st h ep a r e n tm e g a t e r r a i n f a c t o r y ( f o rt h et o p - l e v e lp o l y s ) ，o r i t sp a r e n t + m e g a v e r t e x + m _ p s u b v e r t ； m e g a t e r r a i n t i l e + m _ p p a r e n t ； m e g a t e r r a i n t i l e + m _ p l e f t c h i l d ； m e g a t e r r a i n t i l e + m _ p r i g h t c h i l d ； m e g a t c r r a i n t i l e + mp l e f l n e i g h b o r ； m e g a t e r r a i n t i l e + m _ p r i g h t n e i g h b o r ； m e g a t e r r a i n t i l e m _ p b o t t o m n e i g h b o r ； m c g a t e r r a i n f a c t o r y + m _ p t e r r a i n m a p ； 在上面的代码中，下面要解释的基本函数被每一个p a t c h 物体所调用， p a t c h 类的方法名类似于调用他们的m e g a s e c t o r 类的方法，这些方法或许太 单纯化这里需要详细的解释一下： i n i t ( ) 函数需要高度图和世界坐标的偏移值，他们用来对地形进行缩放，指 向高度图的指针已经经过调整，指向了这个p a t c h 物体所需要数据的第一个 字节。 r e s e t ( ) i n 数释放所有无用的m e g a b i n t r i t r e e 结构，接着重新连接两个二元 三角树成为一个p a t c h ，现在这些还没有被提及，但是每一个p a t c h 物体都 有两个单独的二元三角树构成一个正方形( r o a m 论文中称为d i a m o n d t ) 。 t e s s e l l a t e o i 函数简单的传递适当的高级三角形参数( 每一个p a t c h 物体的两 个根节点) 给一个递归版本的函数，函数r e n d e r ( ) 并1 c o 叫) u t e v a _ r i a i l c e ( ) 也是这 样。 3 3 6r o a m 核心 以上讨论了支持r o a m 运算法则的基本思路，在这点上我们或许从 r o a m 的论文中唾手可得，我要讲一下我是如何做的。参考一下图3 的三角 形关系。首先我们要为网格的近似值定义一个最小可视距离值，我使用的是 q u a k e l l i 引擎中的一个叫v a r i a n c e 的方法，我们将需要他来决定当分割一个节 点( 增加细节) 时需要分割到什么程度。在r o a m 论文中使用了一个基于嵌 套空间范围的方法( n e s t e dw o r l d s p a c eb o u n d s ) ，非常精确但很慢。v a r i a n c e 是对二元三角树节点中，正三角形斜边中点在高度图中的不同高度进行插值， 这个计算非常快。 t r i v a r i a n c e = a b s ( c e n t e r z - ( ( t e f t z + d g h t z ) 2 ) ) ： 但我们不能仅仅计算每一个p a t c h 物体的两个二元三角树v a r i a n c e 值， 因为这样计算带来的误差太大了。因此还应该计算树的深度，在本d e m 0 中 计算的深度可以在编译时指定。通常，v a r i a n c e 计算每一帧都需要进行。除非 高度区域发生变化，这个数值一般不应该发生变化。为此，可以产生提出一个 和二元三角树一起工作的v a r i a n c e 树，一个v a r i a n c e 树是一个填充高度值的二 元树，用一个连续的数组来表示。一些简单的宏可以让我们有效的操纵这个树， 我们填充到里面的数据是每个不同节点的单字节值。这个结构可以参考以下图 5 ，两个v a r i a n c e 树被存储在m e g a s e c t o r 类中，分为左右两个。 图5 二元树结构 现在我们可以重新去做建立近似网格的工作了。获得我们的误差值 ( v a r i a n c e ) ，如果它的v a r i a n c e 非常大，我们将把二元三角树的节点分割成很 小的三角块，这是指，如果当前地形下的三角形非常起伏不平，这样做可以更 好的模拟它。分割必须建立两个可以精确填充父三角形区域的子三角形( 见图 2 ) 。对于子三角形重复进行这样的操作，在一些点上我们或许发现一个单独的 三角形可以足够光滑的模拟地形或者我们的操作超过了预定的步数。所有的这 些之后我们可能仅仅建立了个达到高度区域的网格。 图6 地形渲染测试截屏 这还是有一点复杂，当分割在地形上相邻的二元三角树时，在网格里经常 出现裂缝，这个裂缝是由于不连续的分割穿过p a t c h 边界的树造成的。这个 问题如图7 。 图7 网格上的裂缝 为了解决这个问题，r o a m 使用了网格本身关于邻节点的一个有趣规律： 一个细节节点和它的邻节点只存在两种关系：共直角边关系( 如左右邻节点， 和共斜边关系( 如下邻节点) 【可参考图2 的s u b d i v i s i o n 3 ，我们可以应用这 个原理到建立网格上以保持相邻的树的无缝结合。下面看一下如何使用这个规 则：对于个节点，我们只在它与它的下邻节点呈相互下邻关系时才进行分割 ( 如图7 ) ，这个关系可以把它当作一个菱格来看，这样形容是因为在菱格上 分割一个节点可以很容易的镜象到其他节点，因此在网格上不会出现裂缝。 图8 在一个菱格上进行分割操作 当分割一个节点时存在三种可能： 1 节点是菱格的一部分分割它和它的下邻节点。 2 节点是网格的边只分割这个节点。 3 节点不是菱格的一部分强制分割下邻节点。 强制分割指的是递归的遍历整个网格直到发现菱格样的节点或网格边。这 旱是它的工作流程：当分割一个节点时： 首先，看是不是菱格的一部分，如果不是，然后在下邻节点上调用 第二，个分割操作建立一个菱格，然后继续最初的分割。第二个分割操作 将做同样的工作，重复处理下一个节点，一旦一个节点被发现可以递归的分割， 就一直分割下去，看一下图9 ： 图9 强制分割操作 3 3 7 高级话题 在本论文只很粗略的谈到了g e n e s i s 3 dt e r r a i n 扩展的实现的部分思路和实 现代码，还有很多该模块用的的高级技术： 3 3 7 1 三角形排列 三角形排列是当所有的三角形都共享一个中心点时你才可以使用的一 项优化技术( 也就是三角形是按扇形排列的) 。它允许你对相同数目的三角形 指定一些顶点，并进行改进处理。在g e n e s i s 3 d 中三角形排列对每个三角形的 点进行处理时是按照顺时针进行的，因此你将不得不去转换待处理三角形所面 对的方向否则g e n e s i s 3 d 将剔除所有的三角形。为了获得正确的三角形输出， 三角形排列将帮助用于改变在每一级别( l o d 级别) 的渲染过程中遍历子节 点的顺序。也就是况如果我们在s u b d i v i s i o n l 上首先遍历左子节点，那么在 s u b d i v i s i o n l 2 中必须首先遍历右子节点，而s u b d i v i s i o n l 3 又首先是遍历左子 节点。 在这罩顶点的顺序是非常重要的，第一个被指定的顶点必须是围绕其他三 角形“扇形扩展”方向的中，t l , 点。这样做是通过传送一个参考值给来做为“最佳 中心点( b e s tc e n t e rp o i n t ) 一个三角形顶点。在每一个级别上，这个 值都被改变为指向一个新的每级“最佳中心点”。当一个叶节点被发现时，它被 添加到个很小的顶点缓冲中，这个缓冲是以一个“最佳中心点”丌始，其他顶 点以顺时针方向排列。在下一个子节点中，我们只需要把“最佳中心点”和缓冲 中的第一个顶点进行比较，如果他们不相等，把扇形输出到g e n e s i s 3 d 中并终 止。无论如何，如果两个顶点相等的话，那么测试缓冲中最后一个顶点是否等 于三角形中按顺时针方向的下一个顶点，如果他们不相等，那么输出扇形到 g e n e s i s 3 d 并终止。另外要注意添加三角形的最后一个顶点到顶点缓冲的结尾 部分。在这个方法中扇形的长度不能超过8 个三角形，而平均长度应该为每一 个扇形不超过3 - 4 个三角形。 图1 1 未运用l o d 后的渲染效果 图1 2 运用l o d 后的渲染效果 33 7 2g e o m o r p h i n g 使用动态l o d 进行渲染的一个不好的边缘效果是当三角形从m e s h 中 插入或移出时会产生突然的看的见的裂缝，这个现象可以被顶点变形体 ( m o r p h i n g ) 简化为忽略不计，也叫几何变形体( g e o m o r p h i n g ) 。它 是指一个顶点在几帧的过程中随着从不分割点位置到它的新分割点位置而他 的高度随着逐渐升高或降低。 几何变形体并不难，在分块过程中m e g a p a t c h 结构保存有一个等于这个三 角形的“m o r p h ”的值，这个“m o r p h ”值将被保持在0 0 1 o 的范围。在渲染 过程中，把插值高度值改变为实际的高度区域值需要使用下面的函数： m o r p h e d z = ( f m o r p h + a c t u a l z ) + ( ( 1 一f m o r p h ) 4 i n t e r p o l a t e d z ) ； 3 3 7 3 帧的一致性 帧的一致性是r o a m 中的高级优化技术，对于这项技术来说，最后一 帧建立的网格可以被再次使用。这个特性也可以用束进行动态帧定时，允许你 连续的改进当前帧的网格真到这帧结束。在一个高速动作游戏中，这意味着你 不必花费时间进行地形分块，相反可以先处理其他最重要的快速动作部件，而 在帧时间静止时进行地形分块，而在结束时进行渲染。如果一个玩家在进行交 火时，地形将用一个低级细节来动态渲染以保存时间。用本文的没有足够的空 间来解释帧的一致性，但是只用一点小小的技巧就可做到：建立一个不做s p l i t o 操作的m e r g e o 甬数，使用一个优先队列或其他优先结构来保存整个m e s h 中 的叶节点。在分块过程中，随着分割这一帧中非常租糙的节点的操作，合并所 有本帧中足够d e t a i l 的节点( 或直到时间结束) 。 3 3 7 4 大拓扑结构支持 本引擎是用来构造一个非常大的世界，在为每一个m e g a t e r r a i n s e c t o r 类进行高度图载入和渲染每一个地形时，都没有限制它的大小! 可是还有其他 限制如内存和计算机性能。m e g a t e r m i n s e e t o r 类被设计用来保存一个分页的世 界块，连同其他m e g a t e r r a i n s e c t o r 的实例被m e g a t e r r a i n f a c t o r y 管理。每一个 m e g a t e r r a i n s e c t o r 由m e g a t e r r a i n f a c t o r y 连接到其他m e g a t e r r a i n s e c t o r 。这是 由m e g a t e r r a i n f a c t o r y ：g e t * * * n e i g h b o r ( m e g a t e r r a i n s e c t o r * p ) 完成。 参考文献： 1 h u g u e sh o p p e v i e w d e p e n d e n tr e f i n e m e n to f p r o g r e s s i v em e s h e s i n s i g g r a p h 9 7 p r o c ，a u g u s t19 9 7 【2 】t h a t c h e ru l r i c hc o n t i n u o u sl o d t e r r a i nm e s h i n g u s i n ga d a p t i v e q u a d t r e e sh t t p ：w w w g a m a s u t r a c o m 【3 】m a r kd u c h m n e a ur o a m i n g t e r r a i n ：r e a l t i m eo p t i m a l l y