ROAM實(shí)時(shí)動(dòng)態(tài)LOD地形渲染

REALTIME DYNAMIC LOD TERRIAN RENDER WITH ROAM

作者：Bryan Turner

翻譯：Dreams Woo

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

本文的DEMO可以在這里 下載

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

在本文中我將簡(jiǎn)要的講述一下在硬件加速地形引擎中使用的技術(shù)和運(yùn)算法則。每一個(gè)法則都將被詳細(xì)的描述、討論和最終實(shí)現(xiàn)，作為一個(gè)起點(diǎn)任何人都應(yīng)該把地形加入到他的下一個(gè)項(xiàng)目中。現(xiàn)在我假設(shè)你已經(jīng)有中級(jí)的C++知識(shí)和一般的3D渲染知識(shí)，如果沒(méi)有的話建議你馬上補(bǔ)習(xí)一下。

1 引言

如果沒(méi)有接觸過(guò)涉及到細(xì)節(jié)等級(jí)（LOD）的地形生成法則，恐怕你就不能在地形可視化的世界里任意揮舞你的指揮棒 了。細(xì)節(jié)等級(jí)是一種使用了一系列啟發(fā)式的方法來(lái)決定地形的哪一部分需要看起來(lái)有更多的細(xì)節(jié)的技術(shù)。在這里，對(duì)于地形渲染的許多技術(shù)挑戰(zhàn)之一是如何存儲(chǔ)一個(gè) 地形的特征。高度圖是事實(shí)上的標(biāo)準(zhǔn)解決方案，簡(jiǎn)單的說(shuō)他們就是保存地形每點(diǎn)高度的二維數(shù)組。

2 LOD地形法則概論

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

3 ROAM執(zhí)行初步

代碼用Visual C++ 6.0來(lái)寫的，使用OPENGL來(lái)渲染。

ROAM資源說(shuō)明

讓我使用一個(gè)概述來(lái)介紹這個(gè)法則，然后討論單獨(dú)的小塊是如何相互影響的：

1高度圖文件被載入內(nèi)存并和一個(gè) Landscape類的實(shí)例相聯(lián)系，多個(gè)Landscape物體連接起來(lái)產(chǎn)生無(wú)限的地形。

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

（1）使用基于樹的結(jié)構(gòu)來(lái)控制隨著深度而呈指數(shù)增長(zhǎng)的內(nèi)存，這樣可以保持他們的深度在一個(gè)很小的有限的范圍。

（2）動(dòng)態(tài)更新高度圖需要在變更場(chǎng)景時(shí)有一個(gè)完整的變更樹從算操作。過(guò)大的Patch類物體在實(shí)時(shí)重新計(jì)算時(shí)非常慢。

3每一個(gè)Patch類物體被調(diào)用來(lái)建立一個(gè)MESH的近似值（分割成小塊）。Patch類物體使用了一個(gè)叫二元三角樹的結(jié)構(gòu)來(lái)存儲(chǔ)即將顯示在屏幕上的三角 的坐標(biāo)。這些三角形頂點(diǎn)坐標(biāo)被非常合理的存儲(chǔ)，ROAM使用36字節(jié)以上的內(nèi)存來(lái)存儲(chǔ)每 一個(gè)三角形。高效的坐標(biāo)計(jì)算也是渲染的一部分（見下）。

4在分割完高度圖后，引擎已經(jīng)建立了二元三角樹。樹的葉節(jié)點(diǎn)保存了需要進(jìn)入圖形渲染流水線的三角形。

高度圖文件格式

高度圖使用一個(gè)RAW的數(shù)據(jù)格式來(lái)保存，這個(gè)格式包含了8位的高度信息。通常高度圖必須從頭至尾保存在內(nèi)存中，在高級(jí)標(biāo)題中我將討論如何擴(kuò)展法則來(lái)呈現(xiàn)大的數(shù)據(jù)集。

二元三角樹 Binary Triangle Trees

ROAM使用了二元三角樹來(lái)保持三角坐標(biāo)而不是存儲(chǔ)一個(gè)巨大的三角形坐標(biāo)數(shù)組來(lái)描繪地形。這個(gè)結(jié)構(gòu)可以看作是一個(gè) 測(cè)量員把地形切斷為一個(gè)一個(gè)小三角塊的結(jié)果。這些三角塊邏輯上看就象一組相連的鄰居一樣（左右鄰居）。同樣的當(dāng)一個(gè)三角塊把土地當(dāng)作遺產(chǎn)時(shí)，他需要平等的 分給兩個(gè)兒子。

用這樣進(jìn)行擴(kuò)展，這個(gè)三角塊就是二元三角樹的根節(jié)點(diǎn)，其他三角塊也是他們各自樹的根節(jié)點(diǎn)。 Landscape類如同一個(gè)局域的土地注冊(cè)表，保存所有三角塊的索引，同時(shí)也保存他們之間的層次關(guān)系。由于大量子三角塊的產(chǎn)生，分割土地也成為一個(gè)沉重的負(fù)擔(dān)，但是大量的細(xì)節(jié)可以被需要更好模擬的區(qū)域的種群'population'來(lái)簡(jiǎn)單的處理。看圖一：

圖一 二元三角樹結(jié)構(gòu)等級(jí)0-3

二元三角樹被TriTreeNode結(jié)構(gòu)保存，同時(shí)他還保存ROAM需要的五個(gè)最基本的數(shù)據(jù)，參考圖二。

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

圖二 基本的二元三角樹的子和鄰節(jié)點(diǎn)

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

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

4 Landscape類的詳解

Landscape 類對(duì)地形的細(xì)節(jié)渲染進(jìn)行了高級(jí)的封裝，通過(guò)一些簡(jiǎn)單的函數(shù)調(diào)用我們可以在屏幕緩沖中 進(jìn)行從簡(jiǎn)單的點(diǎn)的顯示到復(fù)雜的地形渲染工作。這里是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 類管理了一個(gè)大的正三角塊，同時(shí)可以和其他Landscape物體一起工作。在初始化過(guò)程中，高度圖被分割成大量的可管理的小塊，同時(shí)把他和一個(gè)新的 Patch物體聯(lián)系起來(lái)。Patch類及其它的方法我們將在下面花費(fèi)更多的時(shí)間講解。注意這些函數(shù)的簡(jiǎn)單性， Landscape物體本身是設(shè)計(jì)用于一個(gè)簡(jiǎn)單的渲染流水線的，尤其是在可以免費(fèi)使用Z緩沖的今天。

5 Patch類詳解

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

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
...

在上面的代碼中，下面要解釋的基本函數(shù)被每一個(gè)PATCH物體所調(diào)用，PATCH類的方法名類似于調(diào)用他們的 Landscape類的方法，這些方法或許太單純化這里需要詳細(xì)的解釋一下：

Init() 函數(shù)需要高度圖和世界坐標(biāo)的偏移值，他們用來(lái)對(duì)地形進(jìn)行縮放，指向高度圖的指針已經(jīng)經(jīng)過(guò)調(diào)整，指向了這個(gè)PATCH物體所需要數(shù)據(jù)的第一個(gè)字節(jié)。

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

Tessellate()函數(shù)簡(jiǎn)單的傳遞適當(dāng)?shù)母呒?jí)三角形參數(shù)（每一個(gè)PATCH物體的兩個(gè)根節(jié)點(diǎn)）給一個(gè)遞歸版本的函數(shù)，函數(shù)Render()和ComputeVariance()也是這樣。

6 ROAM精華

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

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

但是等等，我們不能僅僅計(jì)算每一個(gè)PATCH物體的兩個(gè)二元三角樹Variance值，因?yàn)檫@樣計(jì)算帶來(lái)的誤差太大了。因此還應(yīng)該計(jì)算樹的深度，在本DEMO中計(jì)算的深度可以在編譯時(shí)指定。通常， Variance計(jì)算每一幀都需要進(jìn)行，除非高度區(qū)域發(fā)生變化，他一般不會(huì)發(fā)生變化。因此我們提出一個(gè)和二元三角樹一起工作的 Variance樹，一個(gè)Variance樹是一個(gè)填充高度值的二元樹，用一個(gè)連續(xù)的數(shù)組來(lái)表示。一些簡(jiǎn)單的宏可以讓我們有效的操縱這個(gè)樹，我們填充到里面的數(shù)據(jù)是每個(gè)不同節(jié)點(diǎn)的單字節(jié)值。如果你沒(méi)有遇到過(guò)這個(gè)結(jié)構(gòu)可以參考以下圖四，兩個(gè) Variance樹被存儲(chǔ)在PATCH類中，分為左右兩個(gè)。

圖四 二元樹結(jié)構(gòu)

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

圖五 地形顯示 低級(jí)，優(yōu)化和高Variance設(shè)置

這還是有一點(diǎn)復(fù)雜，當(dāng)分割在地形上相鄰的二元三角樹時(shí)，在網(wǎng)格里經(jīng)常出現(xiàn)裂縫，這個(gè)裂縫是由于不連續(xù)的分割穿過(guò)PATCH邊界的樹造成的。這個(gè)問(wèn)題如圖六。

圖六 網(wǎng)格上的裂縫

為了解決這個(gè)問(wèn)題，ROAM使用了網(wǎng)格本身關(guān)于鄰節(jié)點(diǎn)的一個(gè)有趣規(guī)律：一個(gè)細(xì)節(jié)節(jié)點(diǎn)和它的鄰節(jié)點(diǎn)只存在兩種關(guān)系： 共直角邊關(guān)系（如左右鄰節(jié)點(diǎn)）和共斜邊關(guān)系（如下鄰節(jié)點(diǎn)）[可參考圖一的等級(jí)三]，我們可以應(yīng)用這個(gè)原理到建立網(wǎng)格上以保持相鄰的樹與我們同步。下面看一 下如何使用這個(gè)規(guī)則：對(duì)于一個(gè)節(jié)點(diǎn)，我們只在它與它的下鄰節(jié)點(diǎn)呈相互下鄰關(guān)系時(shí)才進(jìn)行分割（如圖七），這個(gè)關(guān)系可以把它當(dāng)作一個(gè)鉆石來(lái)看，這樣形容是因?yàn)?在鉆石上分割一個(gè)節(jié)點(diǎn)可以很容易的鏡象到其他節(jié)點(diǎn)，因此在網(wǎng)格上不會(huì)出現(xiàn)裂縫。

圖七 在一個(gè)鉆石上進(jìn)行分割操作

當(dāng)分割一個(gè)節(jié)點(diǎn)時(shí)存在三種可能：

1 節(jié)點(diǎn)是鉆石的一部分---分割它和它的下鄰節(jié)點(diǎn)。

2 節(jié)點(diǎn)是網(wǎng)格的邊---只分割這個(gè)節(jié)點(diǎn)。

3 節(jié)點(diǎn)不是鉆石的一部分---強(qiáng)制分割下鄰節(jié)點(diǎn)。

強(qiáng)制分割指的是遞歸的遍歷整個(gè)網(wǎng)格直到發(fā)現(xiàn)鉆石樣的節(jié)點(diǎn)或網(wǎng)格邊。這里是它的工作流程：當(dāng)分割一個(gè)節(jié)點(diǎn)時(shí)，首先看 是不是鉆石的一部分，如果不是，然后在下鄰節(jié)點(diǎn)上調(diào)用第二個(gè)分割操作建立一個(gè)鉆石，然后繼續(xù)最初的分割。第二個(gè)分割操作將做同樣的工作，重復(fù)處理下一個(gè)節(jié) 點(diǎn)，一旦一個(gè)節(jié)點(diǎn)被發(fā)現(xiàn)可以遞歸的分割，就一直分割下去，看一下圖八：

圖八 強(qiáng)制分割操作

現(xiàn)在讓我們重新看一下，給出一個(gè)PATCH物體建立兩個(gè)包含高度區(qū)域細(xì)節(jié)的二元三角樹，我們將進(jìn)行下列操作：

1 計(jì)算Variance樹----為每一個(gè)二元三角樹建立包含Variance數(shù)據(jù)的二元樹，Variance是一個(gè)我們用來(lái)決定模擬是否足夠逼真的數(shù)值，它是直角三角形斜邊中點(diǎn)與斜邊兩端點(diǎn)高度經(jīng)過(guò)插值產(chǎn)生的不同高度取樣。

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

3 強(qiáng)制分割---如果我們分割的節(jié)點(diǎn)不是鉆石的一部分，就調(diào)用強(qiáng)制分割，它將給我們一個(gè)能進(jìn)行基本分割操作的完整鉆石。

4 重復(fù)---在子節(jié)點(diǎn)上重復(fù)對(duì)分塊操作直到在二元三角樹的所有的三角形達(dá)到當(dāng)前幀的Variance值或者我們分割的節(jié)點(diǎn)溢出我們的靜態(tài)內(nèi)存池。

7 重新討論P(yáng)ATCH

現(xiàn)在我們已經(jīng)明白R(shí)OAM的所有細(xì)節(jié)了，讓我們重新完成我們的PATCH類吧。所有的遞歸函數(shù)（分割函數(shù)除外）都 需要從即將渲染的三角形中獲得坐標(biāo)數(shù)據(jù)，這些坐標(biāo)需要在棧中進(jìn)行計(jì)算并傳送到下一級(jí)運(yùn)算，或通過(guò)OPENGL進(jìn)行渲染。在二元三角樹的最深級(jí)別，在棧內(nèi)運(yùn) 算的三角形不會(huì)超過(guò)十三個(gè)。下面的函數(shù)使用了最基本的遞歸運(yùn)算：

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()函數(shù)進(jìn)行了包含強(qiáng)制分割處理的ROAM分割。它的功能包括選擇合適的鉆石，分配子節(jié)點(diǎn)，連接他們到網(wǎng)格和調(diào)用我們需要的其他分割操作。

RecurseComputeVariance()函數(shù)用于獲得當(dāng)前三角形的所有坐標(biāo)設(shè)置和我們保存在棧內(nèi)的一部 分?jǐn)U展信息。三角的Variance值是和它的子三角一起合并計(jì)算的。我選擇通過(guò)傳送每一個(gè)點(diǎn)的X和Y坐標(biāo)而不是每點(diǎn)的高度值來(lái)減少在高度圖數(shù)據(jù)數(shù)組的內(nèi) 存采樣。

RecurseTessellate()完成LOD功能。在計(jì)算完到CAMERA的距離后，它調(diào)整當(dāng)前節(jié)點(diǎn)的 Variance值，以便于適應(yīng)距離的變化。它也可以讓一個(gè)閉合的節(jié)點(diǎn)有一個(gè)比較大的Variance值。調(diào)整后的MESH將在近處使用比較多的三角形而 在遠(yuǎn)處使用較少的三角形。距離的計(jì)算使用了一個(gè)簡(jiǎn)單的平方根計(jì)算（他比較慢，我將用一個(gè)較快的方法來(lái)替換它）。

RecurseRender()這個(gè)函數(shù)非常的簡(jiǎn)單，但是你必須看一下在下面高級(jí)話題中的三角形排列優(yōu)化技術(shù)。簡(jiǎn) 單的說(shuō)來(lái)就是如果當(dāng)前的三角形不是一個(gè)葉節(jié)點(diǎn)那么就把它重新并入到子節(jié)點(diǎn)中。另外輸出一個(gè)三角形使用了OPENGL，注意OPENGL渲染并沒(méi)有被優(yōu)化， 這是為了使代碼容易閱讀。現(xiàn)在所有的都完成了，你需要做的是去理解代碼，接下來(lái)將介紹一些高級(jí)話題了。

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值的注意事項(xiàng)：Variance值在本引擎中是一個(gè)非常重要的變量，它被用在整個(gè)框架內(nèi)。試著更改一下用于Variance樹的計(jì)算方法，或樹的深度。例如設(shè)置深度值為非常小的值如3，再試一個(gè)比較大的數(shù)如13，注意一下渲染性能的差異。

9 高級(jí)話題

作為一個(gè)承諾，這里有一些關(guān)于引擎優(yōu)化和高級(jí)特性的暗示和秘密。他們中的每一個(gè)都可以論述成一篇論文，因此在每一個(gè)標(biāo)題中我都盡可能的用最少的段落來(lái)描述最重要的內(nèi)容。

1三角形排列

三角形排列是當(dāng)所有的三角形都共享一個(gè)中心點(diǎn)時(shí)你才可以使用的一項(xiàng)優(yōu)化技術(shù)（也就是三角形是按扇形排列的）。它允許你對(duì)相同數(shù)目的三角形指定一些頂點(diǎn)，并 進(jìn)行改進(jìn)處理。在OPENGL中三角形排列對(duì)每個(gè)三角形的點(diǎn)進(jìn)行處理時(shí)是按照順時(shí)針進(jìn)行的，因此你將不得不去轉(zhuǎn)換待處理三角形所面對(duì)的方向否則 OPENGL將剔除所有的三角形。為了獲得正確的三角形輸出，三角形排列將幫助用于改變?cè)诿恳患?jí)別（LOD級(jí)別）的渲染過(guò)程中遍歷子節(jié)點(diǎn)的順序。也就是說(shuō) 如果我們?cè)诩?jí)別1上首先遍歷左子節(jié)點(diǎn)，那么在級(jí)別2中必須首先遍歷右子節(jié)點(diǎn)，而級(jí)別3又首先是遍歷左子節(jié)點(diǎn)。

在這里頂點(diǎn)的順序是非常重要的，第一個(gè)被指定的頂點(diǎn)必須是圍繞其他三角形“扇形擴(kuò)展”方向的中心點(diǎn)。這樣做是通過(guò) 傳送一個(gè)參考值給來(lái)做為“最佳中心點(diǎn)（BEST CENTER POINT）”一個(gè)三角形頂點(diǎn)。在每一個(gè)級(jí)別上，這個(gè)值都被改變?yōu)橹赶蛞粋€(gè)新的每級(jí)“最佳中心點(diǎn)”。當(dāng)一個(gè)葉節(jié)點(diǎn)被發(fā)現(xiàn)時(shí)，它被添加到一個(gè)很小的頂點(diǎn)緩沖 中，這個(gè)緩沖是以一個(gè)“最佳中心點(diǎn)”開始，其他頂點(diǎn)以順時(shí)針?lè)较蚺帕小Ｔ谙乱粋€(gè)子節(jié)點(diǎn)中，我們只需要把“最佳中心點(diǎn)”和緩沖中的第一個(gè)頂點(diǎn)進(jìn)行比較，如果 他們不相等，把扇形輸出到OPENGL中并終止。無(wú)論如何，如果兩個(gè)頂點(diǎn)相等的話，那么測(cè)試緩沖中最后一個(gè)頂點(diǎn)是否等于三角形中按順時(shí)針?lè)较虻南乱粋€(gè)頂 點(diǎn)，如果他們不相等，那么輸出扇形到OPENGL并終止。另外要注意添加三角形的最后一個(gè)頂點(diǎn)到頂點(diǎn)緩沖的結(jié)尾部分。在這個(gè)方法中扇形的長(zhǎng)度不能超過(guò)8個(gè) 三角形，而平均長(zhǎng)度應(yīng)該為每一個(gè)扇形不超過(guò)3-4個(gè)三角形。

2 GeoMorphing

使用動(dòng)態(tài)LOD進(jìn)行渲染的一個(gè)不好的邊緣效果是當(dāng)三角形從MESH中插入或移出時(shí)會(huì)產(chǎn)生突然的看的見的裂縫，這個(gè)現(xiàn)象可以被頂點(diǎn)變形體 （MORPHING）簡(jiǎn)化為忽略不計(jì)，也叫幾何變形體（GEOMORPHING）。它是指一個(gè)頂點(diǎn)在幾幀的過(guò)程中隨著從不分割點(diǎn)位置到它的新分割點(diǎn)位置而 他的高度隨著逐漸升高或降低。

幾何變形體并不難，但他也有一些棘手的地方。在分塊過(guò)程中TriTreeNode結(jié)構(gòu)或許保存有一個(gè)等于這個(gè)三角形的“MORPH”的值，這個(gè)“MORPH”值將被保持在0.0-1.0的范圍。在渲染過(guò)程中，把插值高度值改變?yōu)閷?shí)際的高度區(qū)域值需要使用下面的函數(shù)：

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

3 幀的一致性

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

4 大拓?fù)浣Y(jié)構(gòu)支持

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

PS：終于翻譯完成，希望大家看到好的文章也能翻譯過(guò)來(lái)。

ROAM實(shí)時(shí)動(dòng)態(tài)LOD地形渲染