ROAM實時動態LOD地形渲染

REALTIME DYNAMIC LOD TERRIAN RENDER WITH ROAM

作者：Bryan Turner

翻譯：Dreams Woo

譯者注：翻譯這篇文章的目的是國內關于這方面內容的東西太少了，而ROAM做為現今最流行的地形渲染技術已經在國外的游戲中大行其道，只有不斷的學 習才能不斷的進步，希望通過這篇文章能使大家得到進步，我就已經滿足了，這篇文章你可以轉載，但必須署上我的名字，并發到我的郵箱告知我，我的EMAIL 是：dreams_wu@sina.com,有什么交流或建議也可以給我發信。

本文的DEMO可以在這里 下載

如同大多數人一樣，每當我看見起伏的山脈和險峻的峽谷的照片時都會令我震撼，但不幸的是對于玩家來說，我們卻不能縱情于大自然的美景中去。僅僅只有一小部分當前和將來的游戲可以給我們的眼睛帶來震撼的享受（例如 Tribes 1 & 2 , Tread Marks, Outcast, Myth 1 & 2, and HALO）。這些游戲把3D動作游戲帶進了下一個時代。

在本文中我將簡要的講述一下在硬件加速地形引擎中使用的技術和運算法則。每一個法則都將被詳細的描述、討論和最終實現，作為一個起點任何人都應該把地形加入到他的下一個項目中。現在我假設你已經有中級的C++知識和一般的3D渲染知識，如果沒有的話建議你馬上補習一下。

1 引言

如果沒有接觸過涉及到細節等級（LOD）的地形生成法則，恐怕你就不能在地形可視化的世界里任意揮舞你的指揮棒 了。細節等級是一種使用了一系列啟發式的方法來決定地形的哪一部分需要看起來有更多的細節的技術。在這里，對于地形渲染的許多技術挑戰之一是如何存儲一個 地形的特征。高度圖是事實上的標準解決方案，簡單的說他們就是保存地形每點高度的二維數組。

2 LOD地形法則概論

一個LOD地形法則的優秀概述可以被三篇論文來描述，作者分別為[1微軟的Hoppe][2 Lindstrom][3 Duchaineau]。在第一位作者的論文中描繪了一個基于 Progressive Meshes的法則，這是一個與增加三角形到 任意網格來達到你需要的細節相關的新的和絕妙的技術。這篇論文是一篇精彩的讀物但有點復雜，同時這項技術需要大量的內存。第二篇論文的作者是 Lindstrom，他描述了一個叫四叉樹（ Quad Tree ）的結構用于描繪地形碎片（PATCH），一個四叉樹 遞 歸的把一個地形分割成一個一個小塊（tessellates）并建立一個近似的高度圖。四叉樹非常簡單但很有效。第三篇論文的作者是 Duchaineau，他描述了一個基于二元三角樹結構的法則ROAM（實時優化自適應網格）。這里每一個小片（PATCH）都是一個單獨的正二等邊三角 形，從它的頂點到對面斜邊的中點分割三角形為兩個新的正等邊三角形，分割是遞歸進行的可以被子三角形重復直到達到希望的細節等級。由于ROAM法則的簡單 和可擴展性吸引了我的目光。不幸的是這片論文非常短，僅僅只有少量的偽代碼。但無論如何，他可以在連續的范圍實現從最基本的平面到最高級的優化。而且 ROAM分割成小方塊非常快速，而且可以動態更新高度圖。

3 ROAM執行初步

代碼用Visual C++ 6.0來寫的，使用OPENGL來渲染。

ROAM資源說明

讓我使用一個概述來介紹這個法則，然后討論單獨的小塊是如何相互影響的：

1高度圖文件被載入內存并和一個 Landscape類的實例相聯系，多個Landscape物體連接起來產生無限的地形。

2一個新的Landscape物體把載入的高度圖的一部分包裹到新的Patch類物體中，這一步的目的是：

（1）使用基于樹的結構來控制隨著深度而呈指數增長的內存，這樣可以保持他們的深度在一個很小的有限的范圍。

（2）動態更新高度圖需要在變更場景時有一個完整的變更樹從算操作。過大的Patch類物體在實時重新計算時非常慢。

3每一個Patch類物體被調用來建立一個MESH的近似值（分割成小塊）。Patch類物體使用了一個叫二元三角樹的結構來存儲即將顯示在屏幕上的三角 的坐標。這些三角形頂點坐標被非常合理的存儲，ROAM使用36字節以上的內存來存儲每 一個三角形。高效的坐標計算也是渲染的一部分（見下）。

4在分割完高度圖后，引擎已經建立了二元三角樹。樹的葉節點保存了需要進入圖形渲染流水線的三角形。

高度圖文件格式

高度圖使用一個RAW的數據格式來保存，這個格式包含了8位的高度信息。通常高度圖必須從頭至尾保存在內存中，在高級標題中我將討論如何擴展法則來呈現大的數據集。

二元三角樹 Binary Triangle Trees

ROAM使用了二元三角樹來保持三角坐標而不是存儲一個巨大的三角形坐標數組來描繪地形。這個結構可以看作是一個 測量員把地形切斷為一個一個小三角塊的結果。這些三角塊邏輯上看就象一組相連的鄰居一樣（左右鄰居）。同樣的當一個三角塊把土地當作遺產時，他需要平等的 分給兩個兒子。

用這樣進行擴展，這個三角塊就是二元三角樹的根節點，其他三角塊也是他們各自樹的根節點。 Landscape類如同一個局域的土地注冊表，保存所有三角塊的索引，同時也保存他們之間的層次關系。由于大量子三角塊的產生，分割土地也成為一個沉重的負擔，但是大量的細節可以被需要更好模擬的區域的種群'population'來簡單的處理。看圖一：

圖一 二元三角樹結構等級0-3

二元三角樹被TriTreeNode結構保存，同時他還保存ROAM需要的五個最基本的數據，參考圖二。

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
};

圖二 基本的二元三角樹的子和鄰節點

當對高度圖建立一個網格模擬值時，我們需要向二元三角樹中添加子節點直到達到我們需要的細節。這一步完成后重新遍 歷整個樹，此時把子節點中保存的三角形數據渲染到屏幕上。這就是一個最基本的引擎了但需要重新設置每一幀，這種遞歸的方法最大的優點是我們不需要保存每一 個頂點的數據，可以釋放大量的內存給其他物體。實際上，TriTreeNode結構需要多次的建立和銷毀，但這種方法是非常高效的，同時我們或許需要建立 幾萬個這樣的結構，因此我們需要一個指針指向我們需要的內存，TriTreeNode結構是通過一個靜態內存池來分配的，而不是動態分配，他也給了我們一 個快速的重新設置狀態的方法。

圖三 典型的地形PATCH，從左至右依次是網格模式，光照模式，紋理模式

4 Landscape類的詳解

Landscape 類對地形的細節渲染進行了高級的封裝，通過一些簡單的函數調用我們可以在屏幕緩沖中 進行從簡單的點的顯示到復雜的地形渲染工作。這里是Landscape類的定義。

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

Landscape 類管理了一個大的正三角塊，同時可以和其他Landscape物體一起工作。在初始化過程中，高度圖被分割成大量的可管理的小塊，同時把他和一個新的 Patch物體聯系起來。Patch類及其它的方法我們將在下面花費更多的時間講解。注意這些函數的簡單性， Landscape物體本身是設計用于一個簡單的渲染流水線的，尤其是在可以免費使用Z緩沖的今天。

5 Patch類詳解

Patch類是這個引擎的靈魂，他可以分為兩部分，一半是遞歸部分，另一半是基本函數部分，下面就是這個類的數據成員和基本函數描述：

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

protected:
unsigned char *m_HeightMap;
// Adjusted pointer into Height Field
int m_WorldX, m_WorldY;
// World coordinate offset for patch

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

unsigned char *m_CurrentVariance;
// Pointer 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物體所需要數據的第一個字節。

Reset()函數釋放所有無用的TriTreeNodes結構，接著重新連接兩個二元三角樹成為一個 PATCH，現在這些還沒有被提及，但是每一個PATCH物體都有兩個單獨的二元三角樹構成一個正方形（ROAM論文中稱為'Diamond'）。如果不 明白的話再看一下圖二，詳細的內容下一節再討論。

Tessellate()函數簡單的傳遞適當的高級三角形參數（每一個PATCH物體的兩個根節點）給一個遞歸版本的函數，函數Render()和ComputeVariance()也是這樣。

6 ROAM精華

講了這么多我們只是討論了支持ROAM運算法則的結構，現在的時間我們將討論ROAM的精華部分，在這點上你或許 從ROAM的論文中唾手可得，但是我要講一下我是如何做的。參考一下圖二三角形關系。首先我們要為網格的近似值定義一個最小可視距離值，我使用的是 Tread Marks引擎中的一個叫'Variance'的方法，我們將需要他來決定當分割一個節點（增加細節）時需要分割到什么程度。在ROAM論文中使用了一個 基于嵌套空間范圍的方法（nested world- space bounds），他非常精確但很慢。Variance是對二元三角樹節點中正三角形斜邊中點在高度圖中的不同高度進行插值，這個計算非常快。

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

但是等等，我們不能僅僅計算每一個PATCH物體的兩個二元三角樹Variance值，因為這樣計算帶來的誤差太大了。因此還應該計算樹的深度，在本DEMO中計算的深度可以在編譯時指定。通常， Variance計算每一幀都需要進行，除非高度區域發生變化，他一般不會發生變化。因此我們提出一個和二元三角樹一起工作的 Variance樹，一個Variance樹是一個填充高度值的二元樹，用一個連續的數組來表示。一些簡單的宏可以讓我們有效的操縱這個樹，我們填充到里面的數據是每個不同節點的單字節值。如果你沒有遇到過這個結構可以參考以下圖四，兩個 Variance樹被存儲在PATCH類中，分為左右兩個。

圖四 二元樹結構

現在我們可以重新去做建立近似網格的工作了。獲得我們的誤差值（ Variance）， 如果它的Variance非常大，我們將把二元三角樹的節點分割成很小的三角塊，這是指，如果當前地形下的三角形非常起伏不平，這樣做可以更好的模擬它。 分割必須建立兩個可以精確填充父三角形區域的子三角形（見圖一）。對于子三角形重復進行這樣的操作，在一些點上我們或許發現一個單獨的三角形可以足夠光滑 的模擬地形或者我們的操作超過了預定的步數。。所有的這些之后我們可能僅僅建立了一個達到高度區域的網格。

圖五 地形顯示 低級，優化和高Variance設置

這還是有一點復雜，當分割在地形上相鄰的二元三角樹時，在網格里經常出現裂縫，這個裂縫是由于不連續的分割穿過PATCH邊界的樹造成的。這個問題如圖六。

圖六 網格上的裂縫

為了解決這個問題，ROAM使用了網格本身關于鄰節點的一個有趣規律：一個細節節點和它的鄰節點只存在兩種關系： 共直角邊關系（如左右鄰節點）和共斜邊關系（如下鄰節點）[可參考圖一的等級三]，我們可以應用這個原理到建立網格上以保持相鄰的樹與我們同步。下面看一 下如何使用這個規則：對于一個節點，我們只在它與它的下鄰節點呈相互下鄰關系時才進行分割（如圖七），這個關系可以把它當作一個鉆石來看，這樣形容是因為 在鉆石上分割一個節點可以很容易的鏡象到其他節點，因此在網格上不會出現裂縫。

圖七 在一個鉆石上進行分割操作

當分割一個節點時存在三種可能：

1 節點是鉆石的一部分---分割它和它的下鄰節點。

2 節點是網格的邊---只分割這個節點。

3 節點不是鉆石的一部分---強制分割下鄰節點。

強制分割指的是遞歸的遍歷整個網格直到發現鉆石樣的節點或網格邊。這里是它的工作流程：當分割一個節點時，首先看 是不是鉆石的一部分，如果不是，然后在下鄰節點上調用第二個分割操作建立一個鉆石，然后繼續最初的分割。第二個分割操作將做同樣的工作，重復處理下一個節 點，一旦一個節點被發現可以遞歸的分割，就一直分割下去，看一下圖八：

圖八 強制分割操作

現在讓我們重新看一下，給出一個PATCH物體建立兩個包含高度區域細節的二元三角樹，我們將進行下列操作：

1 計算Variance樹----為每一個二元三角樹建立包含Variance數據的二元樹，Variance是一個我們用來決定模擬是否足夠逼真的數值，它是直角三角形斜邊中點與斜邊兩端點高度經過插值產生的不同高度取樣。

2 對地形分塊---如果第一級的Variance不是我們希望的高度就使用Variance樹分割我們的二元三角樹。

3 強制分割---如果我們分割的節點不是鉆石的一部分，就調用強制分割，它將給我們一個能進行基本分割操作的完整鉆石。

4 重復---在子節點上重復對分塊操作直到在二元三角樹的所有的三角形達到當前幀的Variance值或者我們分割的節點溢出我們的靜態內存池。

7 重新討論PATCH

現在我們已經明白ROAM的所有細節了，讓我們重新完成我們的PATCH類吧。所有的遞歸函數（分割函數除外）都 需要從即將渲染的三角形中獲得坐標數據，這些坐標需要在棧中進行計算并傳送到下一級運算，或通過OPENGL進行渲染。在二元三角樹的最深級別，在棧內運 算的三角形不會超過十三個。下面的函數使用了最基本的遞歸運算：

int centerX = (leftX + rightX) / 2;
// X coord for Hypotenuse center
int 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(
int leftX, int leftY, unsigned char leftZ,
int rightX, int rightY, unsigned char rightZ,
int apexX, int apexY, unsigned char apexZ,
int node);

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

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

Split()函數進行了包含強制分割處理的ROAM分割。它的功能包括選擇合適的鉆石，分配子節點，連接他們到網格和調用我們需要的其他分割操作。

RecurseComputeVariance()函數用于獲得當前三角形的所有坐標設置和我們保存在棧內的一部 分擴展信息。三角的Variance值是和它的子三角一起合并計算的。我選擇通過傳送每一個點的X和Y坐標而不是每點的高度值來減少在高度圖數據數組的內 存采樣。

RecurseTessellate()完成LOD功能。在計算完到CAMERA的距離后，它調整當前節點的 Variance值，以便于適應距離的變化。它也可以讓一個閉合的節點有一個比較大的Variance值。調整后的MESH將在近處使用比較多的三角形而 在遠處使用較少的三角形。距離的計算使用了一個簡單的平方根計算（他比較慢，我將用一個較快的方法來替換它）。

RecurseRender()這個函數非常的簡單，但是你必須看一下在下面高級話題中的三角形排列優化技術。簡 單的說來就是如果當前的三角形不是一個葉節點那么就把它重新并入到子節點中。另外輸出一個三角形使用了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 Qualifiers
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三角形排列

三角形排列是當所有的三角形都共享一個中心點時你才可以使用的一項優化技術（也就是三角形是按扇形排列的）。它允許你對相同數目的三角形指定一些頂點，并 進行改進處理。在OPENGL中三角形排列對每個三角形的點進行處理時是按照順時針進行的，因此你將不得不去轉換待處理三角形所面對的方向否則 OPENGL將剔除所有的三角形。為了獲得正確的三角形輸出，三角形排列將幫助用于改變在每一級別（LOD級別）的渲染過程中遍歷子節點的順序。也就是說 如果我們在級別1上首先遍歷左子節點，那么在級別2中必須首先遍歷右子節點，而級別3又首先是遍歷左子節點。

在這里頂點的順序是非常重要的，第一個被指定的頂點必須是圍繞其他三角形“扇形擴展”方向的中心點。這樣做是通過 傳送一個參考值給來做為“最佳中心點（BEST CENTER POINT）”一個三角形頂點。在每一個級別上，這個值都被改變為指向一個新的每級“最佳中心點”。當一個葉節點被發現時，它被添加到一個很小的頂點緩沖 中，這個緩沖是以一個“最佳中心點”開始，其他頂點以順時針方向排列。在下一個子節點中，我們只需要把“最佳中心點”和緩沖中的第一個頂點進行比較，如果 他們不相等，把扇形輸出到OPENGL中并終止。無論如何，如果兩個頂點相等的話，那么測試緩沖中最后一個頂點是否等于三角形中按順時針方向的下一個頂 點，如果他們不相等，那么輸出扇形到OPENGL并終止。另外要注意添加三角形的最后一個頂點到頂點緩沖的結尾部分。在這個方法中扇形的長度不能超過8個 三角形，而平均長度應該為每一個扇形不超過3-4個三角形。

2 GeoMorphing

使用動態LOD進行渲染的一個不好的邊緣效果是當三角形從MESH中插入或移出時會產生突然的看的見的裂縫，這個現象可以被頂點變形體 （MORPHING）簡化為忽略不計，也叫幾何變形體（GEOMORPHING）。它是指一個頂點在幾幀的過程中隨著從不分割點位置到它的新分割點位置而 他的高度隨著逐漸升高或降低。

幾何變形體并不難，但他也有一些棘手的地方。在分塊過程中TriTreeNode結構或許保存有一個等于這個三角形的“MORPH”的值，這個“MORPH”值將被保持在0.0-1.0的范圍。在渲染過程中，把插值高度值改變為實際的高度區域值需要使用下面的函數：

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

3 幀的一致性

幀的一致性是ROAM中的高級優化技術，對于這項技術來說，最后一幀建立的網格可以被再次使用。這個特性也可以用來進行動態幀定時，允許你連續的改進當前 幀的網格直到這幀結束。在一個高速動作游戲中，這意味著你不必花費時間進行地形分塊，相反可以先處理其他最重要的快速動作部件，而在幀時間靜止時進行地形 分塊，而在結束時進行渲染。如果一個玩家在進行交火時，地形將用一個低級細節來動態渲染以保存時間。用本文的空間來解釋幀的一致性是遠遠不夠的，但是對于 他有一些小的標題步驟：增加一個父節點指針到TriTreeNode中，建立一個不做Split()操作的Merge()函數，使用一個優先隊列或其他優 先結構來保存整個MESH中的葉節點。在分塊過程中，隨著分割這一幀中非常粗糙的節點的操作，合并所有本幀中足夠DETAIL的節點（或直到時間結束）。

4 大拓撲結構支持

本引擎是用來構造一個非常大的世界，在為每一個Landscape類進行高度圖載入和渲染每一個地形時，都沒有限制它的大小！可是還有其他限制如內存和計 算機性能。Landscape類被設計用來保存一個分頁的世界塊，連同其他Landscape類保存其他塊，每一個Landscape必須連接它的 patches到附近其他的Landscape中。這是在Patch::Reset()完成，另外設置鄰節點指針為NULL。

PS：終于翻譯完成，希望大家看到好的文章也能翻譯過來。

ROAM實時動態LOD地形渲染