地形图:ROAM实时动态LOD地形渲染

on 2009-2-12 in 游戏开发 | 0 Comment


译者注:翻译这篇文章目是国内有关这方面内容东西太少了而ROAM做为现今最流行地形渲染技术已经在国外游戏中大行其道只有不断学习才能不断进步希望通过这篇文章能使大家得到进步我就已经满足了这篇文章你可以转载但必须署上我名字并发到我邮箱告知我我EMAIL是:[email protected],有什么交流或建议也可以给我发信

本文DEMO可以在这里下载

如同大多数人样每当我看见起伏山脉和险峻峡谷照片时都会令我震撼但不幸是对于玩家来说我们却不能纵情于大自然美景中去仅仅只有小部分当前和将来游戏可以给我们眼睛带来震撼享受(例如Tribes 1 & 2, Tread Marks, Outcast, Myth 1 & 2, and HALO)这些游戏把3D动作游戏带进了下个时代

在本文中我将简要讲述下在硬件加速地形引擎中使用技术和运算法则每个法则都将被详细描述、讨论和最终实现作为个起点任何人都应该把地形加入到他下个项目中现在我假设你已经有中级C知识和般3D渲染知识如果没有话建议你马上补习下

1 引言

如果没有接触过涉及到细节等级(LOD)地形生成法则恐怕你就不能在地形可视化世界里任意挥舞你指挥棒了细节等级是种使用了系列启发式思路方法来决定地形哪部分需要看起来有更多细节技术在这里对于地形渲染许多技术挑战的是如何存储个地形特征高度图是事实上标准解决方案简单说他们就是保存地形每点高度 2维

2 LOD地形法则概论

个LOD地形法则优秀概述可以被 3篇论文来描述作者分别为[1微软Hoppe][2 Lindstrom][3 Duchaineau]在第位作者论文中描绘了个基于Progressive Meshes法则这是个和增加 3角形到任意网格来达到你需要细节相关新和绝妙技术这篇论文是篇精彩读物但有点复杂同时这项技术需要大量内存第 2篇论文作者是Lindstrom他描述了个叫 4叉树(Quad Tree)结构用于描绘地形碎片(PATCH)个 4叉树递归把个地形分割成个个小块(tessellates)并建立个近似高度图 4叉树非常简单但很有效第 3篇论文作者是Duchaineau他描述了个基于 2元 3角树结构法则ROAM(实时优化自适应网格)这里每个小片(PATCH)都是个单独正 2等边 3角形从它顶点到对面斜边中点分割 3角形为两个新正等边 3角形分割是递归进行可以被子 3角形重复直到达到希望细节等级由于ROAM法则简单和可扩展性吸引了我目光不幸是这片论文非常短仅仅只有少量伪代码但无论如何他可以在连续范围实现从最基本平面到最高级优化而且ROAM分割成小方块非常快速而且可以动态更新高度图

3 ROAM执行初步

代码用Visual C 6.0来写使用OPENGL来渲染

ROAM资源介绍说明

让我使用个概述来介绍这个法则然后讨论单独小块是如何相互影响:

1高度图文件被载入内存并和个Landscape类例子相联系多个Landscape物体连接起来产生无限地形

2个新Landscape物体把载入高度图部分包裹到新Patch类物体中这步目是:

(1)使用基于树结构来控制随着深度而呈指数增长内存这样可以保持他们深度在个很小有限范围

(2)动态更新高度图需要在变更场景时有个完整变更树从算操作过大Patch类物体在实时重新计算时非常慢

3每个Patch类物体被来建立个MESH近似值(分割成小块)Patch类物体使用了个叫 2元 3角树结构来存储即将显示在屏幕上 3角坐标这些 3角形顶点坐标被非常合理存储ROAM使用36字节以上内存来存储每个 3角形高效坐标计算也是渲染部分(见下)

4在分割完高度图后引擎已经建立了 2元 3角树树叶节点保存了需要进入图形渲染流水线 3角形

高度图文件格式

高度图使用个RAW数据格式来保存这个格式包含了8位高度信息通常高度图必须从头至尾保存在内存中在高级标题中我将讨论如何扩展法则来呈现大数据集

2元 3角树Binary Triangle Trees

ROAM使用了 2元 3角树来保持 3角坐标而不是存储个巨大 3角形坐标来描绘地形这个结构可以看作是个测量员把地形切断为个个小 3角块结果这些 3角块逻辑上看就象组相连邻居样(左右邻居)同样当个 3角块把土地当作遗产时他需要平等分给两个儿子

用这样进行扩展这个 3角块就是 2元 3角树根节点其他 3角块也是他们各自树根节点Landscape类如同个局域土地注册表保存所有 3角块索引同时也保存他们的间层次关系由于大量子 3角块产生分割土地也成为个沉重负担但是大量细节可以被需要更好模拟区域种群\'population\'来简单处理看图:

\" width=381 border=0>

图 2元 3角树结构等级0-3

2元 3角树被TriTreeNode结构保存同时他还保存ROAM需要 5个最基本数据参考图 2

struct TriTreeNode {
TriTreeNode *LeftChild;
// Our Left child
TriTreeNode *RightChild;
// Our Right child
TriTreeNode *BaseNeighbor;
// Adjacent node, below us
TriTreeNode *LeftNeighbor;
// Adjacent node, to our left
TriTreeNode *RightNeighbor;
// Adjacent node, to our right
};

\" width=402 border=0>

图 2 基本 2元 3角树子和邻节点

当对高度图建立个网格模拟值时我们需要向 2元 3角树中添加子节点直到达到我们需要细节这步完成后重新遍历整个树此时把子节点中保存 3角形数据渲染到屏幕上这就是个最基本引擎了但需要重新设置每帧这种递归思路方法最大优点是我们不需要保存每个顶点数据可以释放大量内存给其他物体实际上TriTreeNode结构需要多次建立和销毁但这种思路方法是非常高效同时我们或许需要建立几万个这样结构因此我们需要个指针指向我们需要内存TriTreeNode结构是通过个静态内存池来分配而不是动态分配他也给了我们个快速重新设置状态思路方法



\" width=130 border=0>\" width=164 border=0>\" width=163 border=0>

图 3 典型地形PATCH从左至右依次是网格模式光照模式纹理模式

4 Landscape类详解

Landscape类对地形细节渲染进行了高级封装通过些简单我们可以在屏幕缓冲中进行从简单点显示到复杂地形渲染工作这里是Landscape类定义

Landscape {
public:
void Init(unsigned char *hMap);
// Initialize the whole process
void Re;
// Re for a frame
void Tessellate;
// Create mesh approximation
void Render;
// Render current mesh
TriTreeNode *AllocateTri;
// Allocate a node for the mesh
protected:
m_NextTriNode;
// Index to the next free TriTreeNode
TriTreeNode m_TriPool;
// Pool of nodes for tessellation
Patch m_aPatches;
// Array of patches to be rendered
unsigned char *m_HeightMap;
// Poer to Height Field data
};

Landscape类管理了个大正 3角块同时可以和其他Landscape物体起工作在化过程中高度图被分割成大量可管理小块同时把他和个新Patch物体联系起来Patch类及其它思路方法我们将在下面花费更多时间讲解注意这些简单性Landscape物体本身是设计用于个简单渲染流水线尤其是在可以免费使用Z缓冲今天

5 Patch类详解

Patch类是这个引擎灵魂他可以分为两部分半是递归部分另半是基本部分下面就是这个类数据成员和基本描述:

Patch {
public:
void Init( heightX, heightY, worldX, worldY, unsigned char *hMap);
// Initialize the patch
void Re;
// Re for next frame
void Tessellate;
// Create mesh
void Render;
// Render mesh void
ComputeVariance;
// Update for Height Map changes
...


protected:
unsigned char *m_HeightMap;
// Adjusted poer o Height Field
m_WorldX, m_WorldY;
// World coordinate off for patch

unsigned char m_VarianceLeft;
// Left variance tree
unsigned char m_VarianceRight;
// Right variance tree

unsigned char *m_CurrentVariance;
// Poer to current tree in use
unsigned char m_VarianceDirty;
// Does variance tree need updating?

TriTreeNode m_BaseLeft;
// Root node for left triangle tree
TriTreeNode m_BaseRight;
// Root node for right triangle tree
...

在上面代码中下面要解释基本被每个PATCH物体所PATCH类思路方法名类似于他们Landscape类思路方法这些思路方法或许太单纯化这里需要详细解释下:

Init需要高度图和世界坐标偏移值他们用来对地形进行缩放指向高度图指针已经经过调整指向了这个PATCH物体所需要数据第个字节

Re释放所有无用TriTreeNodes结构接着重新连接两个 2元 3角树成为个PATCH现在这些还没有被提及但是每个PATCH物体都有两个单独 2元 3角树构成个正方形(ROAM论文中称为\'Diamond\')如果不明白话再看下图 2详细内容下节再讨论

Tessellate简单传递适当高级 3角形参数(每个PATCH物体两个根节点)给个递归版本Render和ComputeVariance也是这样

6 ROAM精华

讲了这么多我们只是讨论了支持ROAM运算法则结构现在时间我们将讨论ROAM精华部分在这点上你或许从ROAM论文中唾手可得但是我要讲下我是如何做参考下图 2 3角形关系首先我们要为网格近似值定义个最小可视距离值我使用是Tread Marks引擎中个叫\'Variance\'思路方法我们将需要他来决定当分割个节点(增加细节)时需要分割到什么程度在ROAM论文中使用了个基于嵌套空间范围思路方法(nested world- space bounds)他非常精确但很慢Variance是对 2元 3角树节点中正 3角形斜边中点在高度图中区别高度进行插值这个计算非常快

triVariance = abs( centerZ - ((leftZ + rightZ) / 2) );

但是等等我们不能仅仅计算每个PATCH物体两个 2元 3角树Variance值这样计算带来误差太大了因此还应该计算树深度在本DEMO中计算深度可以在编译时指定通常Variance计算每帧都需要进行除非高度区域发生变化他般不会发生变化因此我们提出个和 2元 3角树起工作Variance树个Variance树是个填充高度值 2元树用个连续来表示些简单宏可以让我们有效操纵这个树我们填充到里面数据是每个区别节点单字节值如果你没有遇到过这个结构可以参考以下图 4两个Variance树被存储在PATCH类中分为左右两个

\" width=400 border=0>

图 4 2元树结构

现在我们可以重新去做建立近似网格工作了获得我们误差值(Variance)如果它Variance非常大我们将把 2元 3角树节点分割成很小 3角块这是指如果当前地形下 3角形非常起伏不平这样做可以更好模拟它分割必须建立两个可以精确填充父 3角形区域子 3角形(见图)对于子 3角形重复进行这样操作在些点上我们或许发现个单独 3角形可以足够光滑模拟地形或者我们操作超过了预定步数所有这些的后我们可能仅仅建立了个达到高度区域网格



\" width=130 border=0>\" width=130 border=0>\" width=130 border=0>

图 5 地形显示 低级优化和高Variance设置

这还是有点复杂当分割在地形上相邻 2元 3角树时在网格里经常出现裂缝这个裂缝是由于不连续分割穿过PATCH边界树造成这个问题如图 6

\" width=227 border=0>

图 6 网格上裂缝

为了解决这个问题ROAM使用了网格本身有关邻节点个有趣规律:个细节节点和它邻节点只存在两种关系:共直角边关系(如左右邻节点)和共斜边关系(如下邻节点)[可参考图等级 3]我们可以应用这个原理到建立网格上以保持相邻树和我们同步下面看下如何使用这个规则:对于个节点我们只在它和它下邻节点呈相互下邻关系时才进行分割(如图 7)这个关系可以把它当作个钻石来看这样形容是在钻石上分割个节点可以很容易镜象到其他节点因此在网格上不会出现裂缝

\" width=360 border=0>

图 7 在个钻石上进行分割操作

当分割个节点时存在 3种可能:

1 节点是钻石部分---分割它和它下邻节点

2 节点是网格边---只分割这个节点

3 节点不是钻石部分---强制分割下邻节点

强制分割指是递归遍历整个网格直到发现钻石样节点或网格边这里是它工作流程:当分割个节点时首先看是不是钻石部分如果不是然后在下邻节点上第 2个分割操作建立个钻石然后继续最初分割第 2个分割操作将做同样工作重复处理下个节点旦个节点被发现可以递归分割就直分割下去看下图 8:

\" width=500 border=0>

图 8 强制分割操作

现在让我们重新看下给出个PATCH物体建立两个包含高度区域细节 2元 3角树我们将进行下列操作:

1 计算Variance树----为每个 2元 3角树建立包含Variance数据 2元树Variance是个我们用来决定模拟是否足够逼真数值它是直角 3角形斜边中点和斜边两端点高度经过插值产生区别高度取样

2 对地形分块---如果第级Variance不是我们希望高度就使用Variance树分割我们 2元 3角树

3 强制分割---如果我们分割节点不是钻石部分就强制分割它将给我们个能进行基本分割操作完整钻石

4 重复---在子节点上重复对分块操作直到在 2元 3角树所有 3角形达到当前帧Variance值或者我们分割节点溢出我们静态内存池

7 重新讨论PATCH

现在我们已经明白ROAM所有细节了让我们重新完成我们PATCH类吧所有递归(分割除外)都需要从即将渲染 3角形中获得坐标数据这些坐标需要在栈中进行计算并传送到下级运算或通过OPENGL进行渲染在 2元 3角树最深级别在栈内运算 3角形不会超过十 3个下面使用了最基本递归运算:

centerX = (leftX + rightX) / 2;
// X coord for Hypotenuse center
centerY = (leftY + rightY) / 2;
// Y coord...
Recurs( apexX, apexY, leftX, leftY, centerX, centerY);
// Recurs Left
Recurs( rightX, rightY, apexX, apexY, centerX, centerY);
// Recurs Right

Recursive Patch Class Functions:

void Patch::Split( TriTreeNode *tri);

unsigned char Patch::RecursComputeVariance(
leftX, leftY, unsigned char leftZ,
rightX, rightY, unsigned char rightZ,
apexX, apexY, unsigned char apexZ,
node);

void Patch::RecursTessellate( TriTreeNode *tri,
leftX, leftY,
rightX, rightY,
apexX, apexY, node);

void Patch::RecursRender( TriTreeNode *tri,
leftX, leftY,
rightX, rightY,
apexX, apexY );

Split进行了包含强制分割处理ROAM分割它功能包括选择合适钻石分配子节点连接他们到网格和我们需要其他分割操作

RecurseComputeVariance用于获得当前 3角形所有坐标设置和我们保存在栈内部分扩展信息 3角Variance值是和它子 3角起合并计算我选择通过传送每个点X和Y坐标而不是每点高度值来减少在高度图数据内存采样

RecurseTessellate完成LOD功能在计算完到CAMERA距离后它调整当前节点Variance值以便于适应距离变化它也可以让个闭合节点有个比较大Variance值调整后MESH将在近处使用比较多 3角形而在远处使用较少 3角形距离计算使用了个简单平方根计算(他比较慢我将用个较快思路方法来替换它)



RecurseRender这个非常简单但是你必须看下在下面高级话题中 3角形排列优化技术简单说来就是如果当前 3角形不是个叶节点那么就把它重新并入到子节点中另外输出个 3角形使用了OPENGL注意OPENGL渲染并没有被优化这是为了使代码容易阅读现在所有都完成了你需要做是去理解代码接下来将介绍些高级话题了

8 引擎性能

Platform: Win98, AMD K6-2 450 Mhz, 96 Mb RAM, NVIDIA GeForce 256 DDR video.
Resolution: 640x480, 32 bit color

Roam Engine Qualiers

Desired # of
TriTree Nodes
Textured FPS
Solid-Fill FPD

5000
57
62

10000
30
36

15000
20
25

20000
16
19


Variance值注意事项:Variance值在本引擎中是个非常重要变量它被用在整个框架内试着更改下用于Variance树计算思路方法或树深度例如设置深度值为非常小值如3再试个比较大数如13注意下渲染性能差异

9 高级话题

作为个承诺这里有些有关引擎优化和高级特性暗示和秘密他们中每个都可以论述成篇论文因此在每个标题中我都尽可能用最少段落来描述最重要内容

1 3角形排列

3角形排列是当所有 3角形都共享个中心点时你才可以使用项优化技术(也就是 3角形是按扇形排列)它允许你对相同数目 3角形指定些顶点并进行改进处理在OPENGL中 3角形排列对每个 3角形点进行处理时是按照顺时针进行因此你将不得不去转换待处理 3角形所面对方向否则OPENGL将剔除所有 3角形为了获得正确 3角形输出 3角形排列将帮助用于改变在每级别(LOD级别)渲染过程中遍历子节点顺序也就是说如果我们在级别1上首先遍历左子节点那么在级别2中必须首先遍历右子节点而级别3又首先是遍历左子节点

在这里顶点顺序是非常重要第个被指定顶点必须是围绕其他 3角形“扇形扩展”方向中心点这样做是通过传送个参考值给来做为“最佳中心点(BEST CENTER POINT)”个 3角形顶点在每个级别上这个值都被改变为指向个新每级“最佳中心点”当个叶节点被发现时它被添加到个很小顶点缓冲中这个缓冲是以个“最佳中心点”开始其他顶点以顺时针方向排列在下个子节点中我们只需要把“最佳中心点”和缓冲中第个顶点进行比较如果他们不相等把扇形输出到OPENGL中并终止无论如何如果两个顶点相等话那么测试缓冲中最后个顶点是否等于 3角形中按顺时针方向下个顶点如果他们不相等那么输出扇形到OPENGL并终止另外要注意添加 3角形最后个顶点到顶点缓冲结尾部分在这个思路方法中扇形长度不能超过8个 3角形而平均长度应该为每个扇形不超过3-4个 3角形

2 GeoMorphing

使用动态LOD进行渲染个不好边缘效果是当 3角形从MESH中插入或移出时会产生突然看见裂缝这个现象可以被顶点变形体(MORPHING)简化为忽略不计也叫几何变形体(GEOMORPHING)它是指个顶点在几帧过程中随着从不分割点位置到它新分割点位置而他高度随着逐渐升高或降低

几何变形体并不难但他也有些棘手地方在分块过程中TriTreeNode结构或许保存有个等于这个 3角形“MORPH”值这个“MORPH”值将被保持在0.0-1.0范围在渲染过程中把插值高度值改变为实际高度区域值需要使用下面:



MorphedZ = (fMorph * actualZ) + ((1-fMorph) * erpolatedZ);

3 帧致性

帧致性是ROAM中高级优化技术对于这项技术来说最后帧建立网格可以被再次使用这个特性也可以用来进行动态帧定时允许你连续改进当前帧网格直到这帧结束在个高速动作游戏中这意味着你不必花费时间进行地形分块相反可以先处理其他最重要快速动作部件而在帧时间静止时进行地形分块而在结束时进行渲染如果个玩家在进行交火时地形将用个低级细节来动态渲染以保存时间用本文空间来解释帧致性是远远不够但是对于他有些小标题步骤:增加个父节点指针到TriTreeNode中建立个不做Split操作Merge使用个优先队列或其他优先结构来保存整个MESH中叶节点在分块过程中随着分割这帧中非常粗糙节点操作合并所有本帧中足够DETAIL节点(或直到时间结束)

4 大拓扑结构支持

本引擎是用来构造个非常大世界在为每个Landscape类进行高度图载入和渲染每个地形时都没有限制它大小！可是还有其他限制如内存和计算机性能Landscape类被设计用来保存个分页世界块连同其他Landscape类保存其他块每个Landscape必须连接它patches到附近其他Landscape中这是在Patch::Re完成另外设置邻节点指针为NULL

　

PS:终于翻译完成希望大家看到好文章也能翻译过来



Tags:  roam地形 地形图

延伸阅读

最新评论

发表评论