第二部分高級地形編程

聚焦3D地形編程第五章GeomipMapping for the CLOD

譯者: 神殺中龍 邵小寧 microsoftxiao@163.com
翻譯的爛請見諒
原著 《Focus on 3D Terrain Programming》

Woohoo!你現在將要學習地形編程的核心部分了，它們是由難以置信的復雜算法。實際上，那是謊話。本章我將解釋三個算法，因為它們的簡單和高效所以選擇了它們。And , for once in this book, 下面的列表是本章將要講述的內容:

n???????? 解釋持續層次細節的意思

n???????? geomipmapping的背后理論

n???????? 實現geomipmapping的方法

為了簡單那， 我打破了議程的三個部分。不管這些細節，本章將相當長。然而，不要讓本章的長度嚇到你。The content will be presented, as always, in a fun and simple manner. 注意，雖然我改變了一點學習風格。第5，6，7將集中在算法的解釋上相比前幾章將使用偽碼表示。在以后幾章，我將為你提供一些演示并且給出我的實現，但是實現是簡單的，并且you should use them only in conjunction with the tex. With that said, 我們開始吧。

CLOD Terrain 101?

在本書你已經聽說了術語 Continuous Level of Detail(CLOD) 持續層次細節很久了，但是現在到了我告訴你實際情況的時候了。CLOD算法， in one sentence, 是一個動態多邊形網格，通過增加額外的三角形來得到更多細節。這是個簡單的陳述，但是讀完本節你將了解更多關于CLOD的東西，并且知道本章結束。不要煩惱現在還不理解CLOD。

Why Bother with CLOD Terrain??CLOD地形為什么麻煩?

CLOD算法需要更多的研究，難于編碼，平均比brute force實現占用更多的CPU周期。在你腦中，為什么CLOD算法麻煩？它真的簡單嗎: 為了創建更真實，更多細節，更重要，更快的地形碎片。

More Detail Is Added

Where More Detail Is Needed

CLOD的基本思想是添加更多的細節(更多三角形)是必須的。舉例來說，如果我們有一個相當光滑的地形片(看圖5.1),我們將想要一個平均更少些的地形(如圖5.2)。然而，不是所有更多細節的算法都很糟糕。Geomipmapping可以似的三角形不是很分散但又擁有更多細節，但是Rottger的四叉樹算法(在第六章，攀登四叉樹)來做。因此，話說CLOD, 總體上，添加了更多細節到區域上，但并不總是這樣，但是大部分是這樣的，我徹底的把你搞暈了？

Cull Like You’ve Never Culled Before!??

另外實際的CLOD基礎算法是它們允許比brute force方法揀選更多的多邊形。這意味著這些多邊形發送給API但卻看不見。舉例來說，我們通過geomipmapping實現一系列的地形碎片。如果碎片不可見，我們排除潛在的289個被渲染的頂點(一個17x17的頂點碎片)in one fell swoop. 大量的頂點不會被加載到顯卡里，而是被CPU裁剪了。使用簡單的方法，我們滿足GPU和CPU兩者，讓你的主板同時高興。

Not Everything Is Happy

In the Land of CLOD Terrain

在CLOD地形大陸不是任何事物都是愉快的

雖盡管使用CLOD地形算法有一些缺點，Oddly enough, 世界幫助我們寫下了這一段在 Game Developer Magazine里。

主要確定是包括每幀更新多邊形網格。

當大部分這些算法還不是很流行時(geomipmapping, Rottger’s quadtree algorithm, and ROAM)被設計。這是因為該算法想要將更多的工作量放置在CPU里而且發送了一點必要的信息到了GPU。從此一直，然而，這些東西有了一丁點的變化。現在我們需要把焦點放在GPU比CPU更多些。

Wrapping Up Your Introduction to CLOD Terrain?封裝你的初級CLOD地形

明顯的，如果geomipmapping, 四叉樹，ROAM算法過時了，你將不會再讀到它們了。

這意味著某人，某地(heck, 甚至我)哪出了一些優化的，在今天的地形渲染也是最重要的優化。隨即，我將解除前面胡說的關于geomipmapping的東西。

Geomipmapping Theory for the Semi-CLOD Impaired

Geomipmapping, 是Willerm H. de Boer開發，一個友好的GPU CLOD算法。它也是轉變到CLOD大陸最完美的簡單算法。那么我們繼續前進，你也許想要查閱實際geomipmapping白皮書，我放在 CD-ROM里希望給你提供方便。(它的名字叫?/geomipmapping.pdf算法白皮書。)

Simply the Basics 簡單的基礎

如果你熟悉mipmapping的紋理化概念，那么geomipmapping似乎是很淺顯的對你來說。概念同樣，除了處理紋理被取代，我們處理地形片上的頂點。推動geomipmapping概念的是你有一個地形片集合。為了解釋它，我有大小為5的頂點作為一片(5x5的片)。5x5的片將有一系列的等級細節，第0級是最詳細的，這樣，第2級是較詳細的。

看圖5.3如果你需要可視化解釋每個各種等級的話。在圖中，黑色頂點沒有被發送到渲染API, 但是白色被發送到了。

如果查閱了Willern de Boer的geomipmapping的白皮書，你也許注意到圖5.3和白皮書里展示的一點不同。原因是我做的改變了一點為了更清晰，但是現在，just know that I did it for a reason.

到了我們討論更多geomipmapping的時候了。我前面已經給介紹了些基礎，但是現在到了你知道所有東西的時候了….

好，幾乎所有東西。我也許會保留些信息。

[譯者注:?Mip Mapping (Mip貼圖) 這項紋理貼圖的技術，是依據不同精度的要求，而使用不同版本的材質圖樣進行貼圖。例如：當物體移近使用者時，程序會在物體表面貼上較精細、清晰度較高的材質圖案，于是讓物體呈現出更高層、更加真實的效果；而當物體遠離使用者時，程序就會貼上較單純、清晰度較低的材質圖樣，進而提升圖形處理的整體效率。LOD(細節水平)是協調紋理像素和實際像素之間關系的一個標準。一般用于中、低檔顯卡中。

注意 Mip-Mapping和三線性過濾有區別。]

[

譯者注 MipMapping 和三線性區別

Mip-Mapping

　　我第一次看到Mip-mapping技術是在游戲QUAKE里，而現在這種技術早已是隨處可見了。這種技術是由Williams在1983年發明的，“Mip”這個名稱起源于“multum in parvo”，大概就是在一小塊地方有很多東西的意思。

　　具體說來，Mip-Mapping的思想就是構建一套紋理，總共需要大約1.3倍的內存。其中，每塊子紋理是通過對父紋理過濾而得到，它的長和寬都是其父紋理的1/2，其面積為父紋理的1/4。接下來，在應用的時候，你根據距離選取最合適的一塊來進行映射，實踐證明，這種技術雖然簡單，但對提高紋理映射的質量確實非常有效。

　　通過Mip-Mapping，可以為較小的多邊形映射上面積較小的紋理，這對減少紋理的擾動大有好處。舉個例子，你有一塊256x256大小的紋理，當它開始向遠離觀察者的方向開始移動時，你會看到它開始閃爍和顫動。這種現象的出現是因為我們把一大塊紋理映射到一個很小的區域而引起的。你可能在上一幀時，畫的是紋理中(50,20)處的像素，到了下一幀，卻畫的是紋理中(60,30)處的像素。如果這兩個像素相差很大，你就會觀察到前面所說的現象了。總的來說，這種劇烈的紋理座標的變化，會損害圖像的品質，并且影響CACHE的效率，而Mip-Mapping無疑是解決這個問題的好辦法。

Tri-linear Interpolation

　　在介紹了雙線性插值和Mip-Mapping以后，該來講講三線性插值了。其實三線性插值也很簡單，它就是前兩種技術的結合。它在對Mip-Mapping的每塊紋理做雙線性插值的同時，還要對Mip-Mapping中相鄰的兩塊紋理按距離再做一次插值。既算出較大的一塊紋理上的某點雙線性插值像素值和較小的一塊紋理上的某點雙線性插值像素值，再按目標同兩塊紋理的距離做一次類似的插值。

　　使用三線性插值，可以消除Mip-Mapping里紋理切換（既上一幀時用的是某個大小的一塊紋理，而下一幀時又換了一塊的情況）時的突然變化，從而可以提供很平暢的高質圖像輸出。

　　同前兩種技術相比，三線性插值的運算量非常大，目前只能依靠硬件來實現。

原文鏈接: http://www.chinagcn.com/blog/?43/viewspace-702

]

正如我前面說的，geomipmapping與紋理的MipMapping類似除了我們使用陸地片來替代紋理片。我們需要怎么做呢，從3D空間用戶的出發點(攝影機眼睛的位置), 使所有的片的大部分細節都圍繞者攝影機因為這些片是用戶看得見的。

At a certain distance way, 我們將片切換到低的細節上。而更遠的距離，我將切換到甚至更低的細節。圖5.4是可視化解釋。

如圖所示，這些片是攝影機位置處的細節層次(LOD)為0，以為這這些片是最高等級的細節。這些片一旦拉遠，細節將調整到1，是第二高的細節。如果距離攝影機更遠的話，片將降低到等級2，是圖中最低的細節。

Triangle Arrangement Made Easy

前面，你也許注意到5.3排列出的三角形不同于我提供給你的geomipmapping paper中的排列。這種情況你不需要立刻訪問白皮書，看圖5.5看，論文的建議三角形這么排列。

這個排列也許像更好的想法，and it is for the most part. (警告: I’m going to get slightly sidetracked right here.)三角形帶如果你計劃使用頂點緩沖渲染片的話，這是我給你的建議。然而，因為使用頂點緩沖區進行渲染輝高度依賴API，我選擇使用直接渲染模式因為它更容易轉換到其他API語法。使用頂點緩沖區渲染對地形實現來說更高速因為它的函數當你發送每個頂點，紋理坐標，顏色等到API時是單獨的。另外，大部分圖形卡更喜歡每個頂點信息被發送到頂點緩沖的形式。最后，我推薦你使用頂點緩沖區渲染地形。你將獲得極大的速度，完成這個是相當有價值的。如果你喜歡看一個Direct3D頂點緩沖區實現geomipmapping-esque的例子，可以看“Simplified Terrain Using Interlocking Tiles”在 Game Programming Gems, 卷2里。

總之，該回到前面的話題了。如圖5.3是我們將要渲染好的排列好的片。這個排列對我們來說是非常有益的：它允許我們更容易的跳過被渲染的頂點當我們需要時，which is quite often. 接著下一個話題。

Hacks and Cracks, But Mostly Just Cracks?? 砍，爆裂，砍，更多爆裂

常常當你處理CLOD地形算法時，你必須處理裂縫的問題。裂縫出現，在geomipmapping出現這種情況，當高細節挨著低細節時(看圖5.6)。

正如你看到的圖，片左邊比右邊細節高。我們的問題位于點A和B。問題是當A點比B細節高時，這意味著左邊的精確度高于A點，但是右邊的片剛剛是從那個高度平均過來的位于高度之下。這個破裂的東西也許不像個大問題，但是圖5.7所示，展示了我的geomipmapping 實現沒有裂縫嗎？

這不是一個平滑的地形，是吧？這是所有洞穴的景色。我們來解決它！

Crack-Proofing Your Geomipmapping Engine?你的Geomipmapping引擎裂縫實驗

裂縫穿透你的geomipmapping地形是比聽著來的容易。你添加些有意的東西(that would be me)解釋這個概念給你，整個處理過程是容易的… 好，好像是容易的。

我有兩個可能的解決裂縫問題的方法。一個方法是在低細節地方添加頂點片以至于這個片區域將達到和高細節區同樣的細節等級。這個解決方法是丑陋的，可是，它意味著我們必須對片進行重排列(添加其他的三角形扇)。

另外的方法是從更多細節片內刪掉頂點。這個方法更有效一些。看圖5.8看刪掉頂點多么容易解決裂縫。

Where Art Thou Crack??你在哪里裂縫了？

你知道怎么導致裂縫和怎樣解決它們。真正的問題是: 你如何確定它們？基本上，當你當前渲染片，你需要測試片周圍(看圖5.9)看是否有低細節。如果它們是，你知道你需要忽略一些頂點了。

測試每個片不困難。你將需要實現一系列的簡單的if-else語句。(Pseudo-code如下).

If LeftPath.LOD is less than CurrentPath.LOD

?????? RenderLeftVertex = true;

Else

?????? RenderLeftVertex = false;

If RightPath.LOD is less than CurrentPath.LOD

?????? RenderRightVertex = true

Else

?????? RenderRightVertex = false;

If UpperPath.LOD is less than CurrentPath.LOD

?????? RenderUpperVertex = true;

Else

?????? RenderUpperVertex = false;

If LowerPath.LOD is less than CurrentPath.LOD

?????? RenderLowerVertex = true;

Else

?????? RenderLowerVertex = false;

看多么簡單啊？之后測試，渲染你的三角形扇，你跳過粗糙片的方向頂點。例如，右邊片是低級等級的，那么你的當前片是高等級細節(行列翻倍被渲染), 那么你僅僅想要跳過這些頂點到遠處的片（看圖5.10）。

警告：

注意你省略的僅僅是必須的頂點。否則，你將結束整個片而不意味著省略。例如，圖5.10, 片由多行多列組成的三角形扇。你不想省略右邊的頂點；你僅僅想省略右邊的頂點在最右列。

這是你簡單的geomipmapping理論！現在到我們實現我們學過所有東西的時候了。

Implementing Geomipmapping for the Very Slightly CLOD Impaired 實現Geomipmapping CLOD

你了解了geomiapping背后的基礎，但是現在我們需要實現它。這將使你的大腦負擔太重。做完它將是最難的部分，照常，我們將每次做一步。來點咖啡，鎖好你的們，然后來點好聽的音樂！

Path It Up?拼湊

由于geomipmapping是由一系列碎片組成的，大概可以從一個好的想法出發，創建一個patch數據結構。這個結構不需要包含太多信息，而且我們至少需要包含，最好。實際上，這將是從本書里你見過的最小的結構。不要太習慣漂亮的大小！

所有的patch結構真的只需要兩個變量。一個變量將記錄當前細節等級，另一個變量存儲從patch到攝影機的位置的距離。保持頭腦正常！整個patch數據結構。在這里，代碼:

struct SGEOMM_PATTH

{

?????? float m_fDistance;

?????? int?m_iLOD;

};

它也許是微笑結構，但是記住: 大東西將由小東西組成。雖然小，我們將經常使用它，所以確認你已經花了幾小時記住它的成員。

Creating the Basic Geomipmapping Implementation?創建基本的Geomimapping實現

Yeah, 兩個成員的數據結構不要哭哭啼啼的。現在我們將開始geomipmapping引擎的重負荷工作——geomimapping類。開始，我們需要獲得我們的patch信息指針，我們將動態的分配一些指針在我們的demo內。繼續，我們需要計算出patch大小(頂點數)和地形的邊需要多少個patchs。

警告

geomipmmaping實現是基于2的N次方+1個像素塊高度圖。這意味著你不能使用midpoint displacement不規則高度圖產生高度圖。所有你的高度圖只能使用fault formation產生。

Patch的大小由用戶來指定，所以我們可以讓它指定patch大小當它初始化類時。(我趨向于嚴格的大約17x17頂點提供一個漂亮的細節和速度。本章將解釋為什么采取這么大。)

Geomipmapping Initialization Geomipmapping初始化

為了初始化geomipmapping系統，我們需要用戶指定他們的patch大小。(我將恢復我的建議17x17的頂點。)After we have that, 我們初始化系統。

首先我們許喲啊計算地形每個邊的片。我們描繪出高度圖和劃分出獨立的patch, 如圖5.11。

P描繪一系列的每個邊， h描繪出高度圖的大小， s描繪出單獨patch的大小。使用一個等式，看圖5.12我們將在之后插入一個等式。

之后我們計算每個邊的patch，我們需要為每個片分配正方形的緩沖區。(這個值我們僅僅完成這個計算。)

m_pPatches = new SGEOMM_PATH[SQUARE(m_iNumPathcesPerSide)];

繼續，雖然它不是初始化必要的部分，我想計算出這個片可以達到的最大細節等級。注意最大等級是最小細節等級，最大細節等級是0。如果等級增加，細節減少。這的計算:

iDivisor = m_iPatchSize – 1;

while(iDivisor > 2)

{

?????? iDivisor = iDivisor >> 1;

?????? iLOD++;

}

所有我們做的許喲啊多少個循環獲得iDivisor下至2。當iDivisor到達2時，我們不會繼續減，并且我們計算一些我們處理的細節。例如17x17片大小，我們的最大細節為3，意味著我們有四個不同的細節等級(0, 1, 2, 3)從任何單個片選擇。初始化吧！現在我們將移動到可怕的下一節。

Geomipmapping Shutdown 清理Geomipmapping

關閉geomipmapping系統是簡單的。我們需要釋放我們為patch緩沖分配的所有內存和讓類成員變量都休息。

Geomipmapping Maintenance Geomipmapping維護

不像我們前三章的地形， CLOD地形算法需要在每幀更新(這也是為什么叫做Continuous Level of Detail的原因)。大部分基于CLOD的算法需要在更新階段進行一些維護工作，但是geomipmapping不那么做。這個工作我們必須在更新函數徹底到最小限度時處理；它簡單由我們的patch來計算得到。

為了實現我們的geomipmapping更新函數，我們需要為每個patch進行更新; 因此，我們需要制作一個雙循環:

for(z = 0; z<m_iNumPatchesPerSide; z++)

{

?????? for(x = 0; x<m_iNumPatchesPerSide; x++)

?????? {

?????? }

}

首先的東西我們需要在循環內計算從攝影機位置到當前片中心的距離。這個計算將是你在高校熟悉的數學，他們操練一個距離公式在你的大腦里。這種情況你可以像我一樣所有課在睡覺，這里重復。

Dist = sqrt((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2);?3D距離公式

帶著這個燈市，看圖5.13變量將被插入到等式中。

這是距離計算的代碼;

m_pPatches[iPatch].m_fDistance = sqrtf(

???????????????????????????????????????????????? SQUARE( ( fX-camera.m_vecEyePos[0] ) )+

???????????????????????????????????????????????? SQUARE( ( fY –camera.m_vecEyePos[1]) )+

???????????????????????????????????????????????? SQUARE( ( fZ –camera.m_vecEyePos[2] ) ) );

之后我們從攝影機開始計算距離，我們可以計算出該片的細節等級。代碼，我計算出硬編碼的距離。(我的代碼僅僅有一點是這樣的；你也許想撇去這樣的代碼)。對于你的引擎，雖然，你想要更多嚴格的方式計算出細節等級。例如，在geomipmapping白皮書內， Willem de Boer描述了屏幕像素決定算法以至于當片改變登記，too mch popping won’t be present.

Popping是當多邊形改變到不同的細節去出現的。這個改變也許或不會很明顯。例如，從1改變到0沒有引起popping因為1 等級片仍然是端正的細節(是17x17，至少) 。然而，從3級改變到2導致一點popping因為你從8個三角形到了32。雖然那些同樣比率的三角形被在第一個片添加了，在3到2級是明顯的。CLOD算法一個主要的目標是減少甚至完全消除popping。我將在稍后部分講述它。

總之，這本書要實現我的geomipmapping，我簡單硬編碼遠離了LOD。(我想排除和你的經驗差距，更容易理解。是的，我知道我是個和藹的家伙。) 這是改變的LOD代碼小片:

if(m_pPatches[iPath].m_fDistance < 500)

?????? m_pPatches[iPath].m_iLOD = 0;

else if(m_pPathes[iPatch].m_fDistance<1000 )

?????? m_pPatches[iPatch].m_iLOD = 1;

else if(m_pPatches[iPatch].m_fDistance<2500)

?????? m_pPatches[iPatch].m_iLOD = 2;

else if(m_pPatches[iPatch].m_fDistance>=2500)

?????? m_pPatches[iPatch].m_iLOD = 3;

這些距離有效的速度整合和細節。如果demo有點在你的視頻卡遲緩，你也許需要改變下這些距離。之后的章節我們將優化下速度，所以不要失望！那么更新所有geomipmapping片吧… 現在，至少。現在到了地形實現最有趣的部分了：渲染它！

Geomipmapping Rendering 渲染Geomipmapping

這可能是本章你遇到的最難的部分了，但也沒那么壞。它偶爾變得復雜些，但是我帶領你搞定它。

Splitting Things Up a Bit?劈開東西

最容易的方式是我們把要渲染的東西分離開以使得代碼不是太膨脹。這也許增加了函數調用，但是我們做的只能些，它不是很壞。

我描繪它， geomipmapping類將是高級渲染函數，另外有一些低級的， in succession. 例如，最高級的渲染函數是Render。比Render更低的是RenderPath和RenderFan。 RenderVertex將是最低級的。使用這些函數，我們增加了一點函數調用開銷，但是我們減少我們代碼的丑陋。這種交易是值得的。如果你已經抓住設計的低級部分，如圖5.14。作為實現我們的渲染系統，讓我們從低和是高級的部分開始呢？

The RenderVertex Function

這個系統的頂點渲染函數不是特定的，但是公平起見，它是個小函數。我們將經常調用它，是個完美的inline函數。 RenderVertex設置頂點的顏色，并從光照圖和分別乘以光顏色的RGB值以著色。然后RenderVertex發送紋理坐標到渲染API(為細節映射, 如果需要，顏色紋理) 。之后，一簡單的需要發送縮放后的頂點坐標到渲染API。 That’s it!

Render->RenderPath->RenderFan->RenderVertex

The RenderFan Function

每個geomipmapping patch是在一些三角形扇處停止，不管它們是1 patch或者256 patch。使用這個函數在RenderPatch內整理代碼，在下一節進行討論。

所有渲染patch的函數都渲染單個的三角形扇。因此，函數需要允許扇形中心作為一個扇形的邊傳送到函數并渲染它。RenderFan也需要包含臨近的patch信息。好，排序。臨近的信息是獨立的扇形。如果patch需要省略應得的頂點到海岸的patch在它的正確的一邊，但是當扇形在patch的中間時，那么臨近的結構顯示出所有為真。(僅扇形在patch需要的右邊時在大約頂點省略。) 如果扇形被渲染，然而，頂點需要被省略。例如，如果扇形在右邊的一邊，那么扇形將在LOD滑坡的一邊，那么當前扇形需要省略右邊的頂點。

The RenderPat Function

Patch-rendering函數是整個渲染系統是重要的因為不渲染patch, 你不會看見地形。大部分裂縫都發生在這個函數，使用休息發生在RenderFan函數。

記得我展示給你的偽代碼了么？ Where Art Thou Crack? 好，這里我們將實現它。我們需要填充臨近的結構，這是一個簡單那的數據結構四個布爾值標志提供給臨近的patch(左，右，上和下patch)是高等級細節多于當前的。如果臨近的標記為真，那么我們可以正常渲染在patch邊上的因為我們不需要特殊的預防裂縫。如果標記為false, 那么我們需要指定特殊的量。

注意:

當我們談論關于“高級細節”時候，我們以為這” 低級細節.”這因為我們的等級系統從高(低值)到更高，而0是最多細節的。千萬不要搞亂了當我們說高/低細節時。

之后裂縫預防步驟，我們需要計算出起始渲染三角形是怎樣的。它也許稍微變得復雜了些。最難的部分是計算三角扇的中心的距離。之后再完成， we’re good as gold!

我們怎樣計算出每個扇形間的距離呢？好，我要著手做了，雖然它看起來是不固定的，以獨立的patch大小開始并且試著計算它并在每個扇形中心來劃分。我計算出每個片大小的約數，然后while循環計算出被多個總的patch劃分。例如，如果patch是0等級，我們用patch自己去劃分，我們渲染它直到產生一個1的長度。(我們做但不想縮放頂點知道我們執行了RenderVertex函數。)如果patch等級為1， 每個扇形距離將是2單位， 等級為2將為8個單位等。之前的計算代碼像這樣:

fDivisor = (float)m_iPatchSize;

fSize?? = (float)m_iPatchSize;

iLOD?? = m_pPatches[iPath].m_iLOD;

// find out how many fan divisions we are going to have

while (iLOD >= 0)

?????? iDivisor = fDivisor/2.0f;

// the size between the center of each triangle fan

fSize /= fDivisor;

盡管計算結果不完全是正確的；當我們使用它們，他們產生圖5.15的地形。

這些計算做錯了？ 好， 我們犯了一個簡單的錯誤。 我們想要分割變量， fDivisor, 作2的N次方。記得當patch大小和divisor相等時， 在扇形等級0和1直接有1個單位？ 好的，從中心到中心， 我們需要至少兩個獨立的單位(看圖5.16。)。你看到如圖5.16成對的扇形彼此交叉(產生了相當難看的結果) with a one-unit interval and how the two fans on bottom fit together perfectly with the two-unit interval? 好的， 我們需要改變前一個扇形中心間隔計算所以在patch間的最小間隔為兩個單位。How de we do this, 你問？這相當簡單。我們剛剛設置了初始除數變量為patch大小減1， 總是2的平方的約數， 因此我們已經解決了前面的所有問題。檢查新代碼。(fDivisor變成iDivisor以致于我們加速了一點計算。)

fSize = (float)m_iPathSize;

iDivisor = m_iPathSize – 1;

iLOD = m_pPatches[iPatch].m_iLOD;

// find out how many fan divisions we are going to have

while(iLOD >= 0)

?????? iDivisor = iDivisor >>1;

// the size between the center of each triangle fan

fSize /= iDivisor;

完成之后， 渲染了patch的三角形扇形就變得微不足道了。你僅僅需要確定你開始渲染fSize的一半因為第一個扇形的中心。我們需要檢查每個邊是否省略了頂點。這意味著我們需要使用patch相臨結構的信息，that we filled out earlier并應用它到每個片的被渲染的邊，如下演示:

// if this fan is in the left row, we might need to

// adjust its rendering to prevent cracks

if( x==fHalfSize)

?????? fanNeighbor.m_bLeft = patchNeighbor.m_bLeft;

else

?????? fanNeighbor.m_bLeft = true;

// if this fan is in the bottom row, we might need to

// adjust its rendering to prevent cracks

if(z == fHalfSize)

?????? fanNeighbor.m_bDown = patchNeighbor.m_bDown;

else

?????? fanNeighbor.m_bDown = true;

// is this fan is in the right row, we might need to

// adjust its rendering to prevent cracks

if(x>=(m_iPatchSize – fHalfSize))

?????? fanNeighbor.m_bRight = patchNeighbor.m_bRight;

else

?????? fanNeightbor.m_bRight = true;

// if this fan is in the top row, we might need to

// adjust its rendering to prevent cracks

if(z>=(m_iPatchSize-fHalfSize))

?????? fanNeighbor.m_bUp = patchNeighbor.m_bUp;

else

?????? fanNeightbor.m_bUp = true;

// render the triangle fan

RenderFan((PX*m_iPatchSize)+x, (PZ*m_iPatchSize)+z, fSize, fanNeighbor, bMultiTex, bDetail);

填充分離的扇形到相鄰結構， 我們必須重新計算patch的相臨結構。扇形結構被發送到渲染扇形的函數里，習慣于找出無論任何頂點需要從渲染時被省略掉。那是因為所有的低級渲染函數。現在我們需要簡要的討論高級渲染函數，因為用戶將要使用。 我們可以釋放demo5_1到世界中了！

The Render Function 渲染函數

好，我們剛剛完成了我們的簡單geomipmapping實現。你激動嗎？我知道我很激動！

在高級渲染函數里，我們需要循環遍歷所有的patchs并調用RenderPatch函數，但是我們將有三個不同的渲染patch循環。還記得我們的brute force實現么？我們僅僅需要成為循環體的一體如果擁護開起多紋理的話；然而，如果用戶沒有開啟多紋理，我們也許需要制作紋理貼圖通道還有細節貼圖通道。兩個不同的渲染通道不是好東西，可是，所以一個選項是如果用戶不支持多紋理就不進行細節映射。如果你已經閱讀了從開始到現在的章你將很熟悉這個概念。唯一的東西是你必須循環遍歷所有的patch和使用RenderPatch函數來渲染它們。

That’s it! 我們完成了接納的geomipmapping實現。看demo5_1(位于CD盤的Code"Chatper5"demo5_1)并且看圖5_17的截圖。左邊展示了紋理/細節貼圖右邊是線框情形下的圖。注意在線框模式下離近距離你可以看到更多細節比遠處。這真是一個漂亮的CLOD算法！

Problems Exist to Be Fixed 存在的問題被解決

Yeah, yeah, 我知道。我僅僅完成了geomipmapping的一部分問題。例如，除非你有非常高級的卡，你可能經歷了可怕的前一個demo的幀速率。(我在GeForce 4 TI4600，在我寫本書時時常上最好的卡，并且穩定在45-50幀每秒) 這個demo也會遭受當地形改變的他們低級細節時的裂縫問題。我們將解決所有上述章節的問題，所以不要擔心！

Adding a Bit of Juice to the Engine?? 給引擎來點果汁

首先，我認為我們將加速我們的實現。加速是容易的。使用一些簡單的視錐裁剪，因為我們的地形被分割成了多個patch, 我們最好只裁剪視錐外的patch，這意味著不需要多少測試。

Cull Like You’ve Never Culled Before… Again

我們將完成基本的視錐裁減。我添加了一些視錐計算函數到CCAMERA類基于 Mark Morley的文章 “Frustum Culling in OpenGL, “ 我認為最好的視錐裁剪的文章在互聯網上。(你可以從這里找到: http://www.markmorley.com/opengl/frustrumculling.html.) 是的，我承認，我的數學知識不太性(注意遍及這本書的數學變復雜!), 但是那可能是個好東西——除非你的數學癮君子， in which case, 我大概除了不喜歡郵件外。

總之，這里是我們將要使用的基礎。我將再次使用視錐對patch進行裁剪(如圖5.18你需要一個可視化的更新)以排除不必要的對CPU/GPU的周期的浪費。(如果觀察者不能看到它，將不會被渲染/更新。)

我們需要再次利用視錐來對地形片進行測試。To do this, 我們制作了一個Axis-Aligned Bouding Box(AABB)包圍住patch.(實際上， we make more along the lines of a cube.)那么我們想再測試視錐呢。為了計算patch的尺寸，我們在中心并縮放了變量的大小。(看圖5.19).

因為我們僅僅處理patch中心，你需要一般的大小作為函數參數(Cube 和視錐相交)并計算出正方體的角度。我們也獲得了更精確的盒子，但是在我的裁剪實現下，其余的空間緩存是必要的以為了視錐不能看見地形而矛盾（像patch輕微的可見 but ends up getting culled anyway）.

現在你知道更多關于揀選和它的實際是如何用于地形的了吧，檢測demo5_2(在CD上Code"Charpter5"demo5_2)并且作為你獲得更快的證據。例如，在圖5.20上，用910個patch制成，?我們僅僅369。而demo，我穩定工作在(80-120幀), 并且高度圖使用了2倍大的在demo5_1上。還不算太破！

Pop Today, Gone Tomorrow?今天破裂，明天死掉

下個問題是解決之前的問題。我們的目標四簡化或者——甚至更好——略過裂縫。

有一系列的方式關于這一點，我將描述它們背后的兩種原理。而實際實現你自己來做。

Morph It! And Morph It Good!?它的變體，變體更好。

首先的解決方案叫geomorphing，幾何變形。雖然名字聽起來像一個巨大的網格，它絕對沒有龐大的機器人。Gomorphing實際過程是是逐漸的變形多邊形的頂點(像我們的geomipmapping patch一樣)改變他們的等級細節。我個人認為這些mesh將更有趣，但是實際意味著幾何變形更有用。

為什么是有用的，你會問？這相當簡單，實際上。你看，當一個patch低級時，大約高度為這個區域(圖5.21)。并且，在圖中，patch接近黑點的標記出來的值。

你看在低的patch上有多少個黑點？好，接近低細節patch有多高的值。這個近似值接近于實際的值，但是不會等于實際值。因此，當從等級3細分為等級2patch(or vice-versa), 裂縫發生；那是因為那些值被實際的值替換了(或者真實的值被接近的值替換了。)

Geomorphing解決這個問題計算出從實際值到遠處接近的值并從超過大于255的范圍內進行插值。(Or vice versa…again.好的，從這外面，我將假設我們細分了patch. 如果你合并了patch, 就推翻了所有的計算。)為了計算一串你需要移動每步的單位，就用這個等式：

Geo = (to-from) / numSteps

在等式內， “to”是你要用的實際值， “from”是要用的近似值，而”numSteps”是你想要記性geomorphing替換的步長，我建議設置為255。整個過程使用圖5.23解釋。

好，that’s it. Geomorphing是簡單的概念，并且你可以用不同的方式實現。（我不想限制你的想象力，這就是為什么我沒有實現的原因）。Go have some func with it, 但是要確認你記得并讀了下節，幫助你減少裂縫甚至更多。

Should Lights Make a Popping Noise??光制作裂縫燥聲？

答案是不，盡管這不重要。重要的是減少我們地形實現里的裂縫。現在，可是多半裂縫戶出現等改變LOD等級使用geomorphing, 另外問題是，我們使用了goraud光照對每頂點！雖然聽起來不是太大的處理。使用LOD切換，光照被應用到了多或少的細節patch上，那么將發生。幸運的是解決這個問題是微不足道的，并且你可以用不同的方式處理。

一種方式解決這問題是結合地形光照圖使用地形的紋理圖。這允許你執行光照和紋理的渲染通道。不幸的是，這意味著你不得不制作你的光照圖和紋理圖用同樣的分辨率并優化結果。因此，如果你動態改變光照，你也動態改變了紋理映射，代價相當昂貴。另外解決的方式是光照圖紋理通道分離。這視為光照圖作為紋理，忽略每頂點光照，允許你動態更新而不必煩惱紋理圖。不幸的是，這意味著用戶需要至少3層多紋理單位來接近效率。而且，甚至用戶有兩個紋理單位，執行2次渲染通道不是個好思想。多通道渲染不擅長處理小模型，但是巨大多邊形集數據，像地形Mesh, 它擅長。

這個解決方案你伴隨你完成。如果你不需要做動態斜坡光照或光照圖的話就接近完成了，而第二個方法如果你知道你的用戶圖形卡支持3層或更多紋理單位的話就加上。請小心的使用額外的紋理單位。

Summary 摘要

好，真是夠長的一章，但是你達到目標了。祝賀你！本章你全面的學習了CLOD地形，但是你也了解了geomipmapping CLOD地形算法。你學會了怎樣加速geomipampping和怎樣減少LOD產生的裂縫。所有這些都將應用到下一章。你要支撐住: 四叉樹結構是基于CLOD算法的。

References 參考

1 de Boer, Willem H. “Fast Terrain Rendering Using Geometrical Mipmapping. “ October 2000. http://www.flipcode.com/tutorials/geomipmaps.pdf

轉載于:https://www.cnblogs.com/microsoftxiao/archive/2008/07/09/1238558.html

總結

以上是生活随笔為你收集整理的聚焦3D地形编程第五章GeomipMapping for the CLOD的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。