最近開始抽空在看GPU Gems 3了。本來想挑幾篇全文翻譯，但是無奈自己英語水平薄弱，同時最近老板逼得緊，也沒有那么多時間，于是便準備以導讀的形式，將文章的主干部分翻譯出來,幫助英文不好的筒子們。
導讀也是我自己讀書的總結(jié)。文章的核心內(nèi)容一定會提及.圖和源碼，通常我會標注上對應的圖書上的figure和list，各位自行參考。基本維持原文的篇章段落，但是一般不會逐字句的考究。
至于能有多少篇，我倒是不能保證。不過我所用的電子版是那個26M的chm，我讀的時候會把它翻成PDF并加注，如果有筒子需要我注釋后的pdf，可以與我聯(lián)系：
mail： wuye9036 _AAAAATTTTT_ google _dotdotdotdotdot_com
--------------------------------------------------------------------------------
Chapter I 運用GPU構造復雜的過程化地形
1.1 Introduction
過程化地形的應用已經(jīng)有不少的歷史了，Game Programming Gems 2上就已經(jīng)有了不少成熟的過程化地形的方法，比方說隨機斷層、基于噪聲的、基于分形理論的、中點分割加擾動的。
不過這些算法在現(xiàn)代硬件上都時有缺陷的，特別是針對規(guī)模很大的地形，要么只能在CPU上實時生成，要么就得預存儲起來，但是不管怎么說都面臨著很大的資源開銷；其次這些算法都是只能生成有些起伏的平面，沒辦法表現(xiàn)山洞、巖石凸角一類的3D特征。本文運用DX10的Geometry Shader與Stream Output，彌補了上述兩個缺陷。
1.2 移動立方體與密度函數(shù)
要解決3D的地形特征，首先要解決3D地形特征的表達問題。文中將空間劃分為多個Blocks，每個Block代表了世界坐標系中1*1*1大小的空間。每個Block由一個3D紋理來表達。由于使用了過程化的方法，每個Block可以在運行的時候動態(tài)生成，這樣只需要保留那些能看得見的blocks，從而解決了存儲問題。
概念上，一個3D的地形可以由一個密度函數(shù)來表達。對于每個空間中的點(x, y, z)，都有唯一對應的密度值。我們假設，對于任意一個空間中的點，如果點在地形內(nèi)部/巖石內(nèi)部當且僅當點上的密度值大于0。那么小于0的點，自然就在地形之外，如在空氣中，水中等等。而巖石表面上的點密度剛好等于0。
那么自然，這些巖石表面上密度值等于0的點，就是我們要繪制的“表面”。
在將空間劃分為Block后，還要將每個block進一步細分為多個voxel（體素）。我們假定體素內(nèi)密度變化時連續(xù)的。那么很顯然，如果一個體素的頂點上密度有正有負，那么必然里面會有一個（也有可能是多個）0值面。問題就轉(zhuǎn)化為，如何根據(jù)體素各個頂點的密度值，求出這個體素內(nèi)的0值面。如果再把這個假設限定的嚴格一點，如果體素內(nèi)密度變化是線性的，那么這些面可以由0-5個三角形來表示；求得這些三角形的方法，被稱為Marching Cube算法。
很顯然，有多少個三角形，每個三角形的頂點落在哪條邊上，是由八個頂點的密度的正負值所決定的，而值的相對大小則決定了三角形的頂點在邊上靠近那個頂點。那么也就是說，一個體素內(nèi)0值面的分布共有2^8中情況。如果頂點密度為負，那么標記為0，頂點密度為正則標記為1，則八個頂點的情況可以由一個Byte來表示。
圖1-3
如果這個字節(jié)的值為0或者為255，那么說明所有的頂點都為正或為負，那么說明體素中并沒有地表面。Martin Frank為剩下的254中情況建立了一個查找表。其中基本的情形有14種，其余的均可由這些基本情況的對稱或旋轉(zhuǎn)求得。
圖1-4
當確定了三角形的三個頂點分布于哪些邊上后，便可用插值的方法求出所在位置。頂點將位于0值點處。例如，一條邊AB上有一個0值點P，如果A的密度0.3，B的密度-0.1，那么PB的長度是PA長度的三倍。
1.2.2 查找表
上文已經(jīng)提到了如何通過體素角點的密度值，就會知道會生成哪些多邊形；這些多邊形的頂點落在哪些邊上。
接下來，我們將用討論這些理論如何在GPU上實現(xiàn)。
首先我們建立一張查找表
int case_to_numpolys[256];
其中每種情況能產(chǎn)生多少個三角形。
第二張查找表，
int3 edge_connect_list[256][5];
這張表保存了每種情況對應的5個三角形。并且我們將一個體素中的12條邊按照0-11編號（圖 1-5），則查找返回的返回的int3指出了，每個三角形的三個頂點分別落在哪條邊上。
圖 1-5 Case 193 的0值多邊形情況
下面的例子很好的說明了這一點。
我們以case 193為例。193總共有3個三角形，那么case_to_numploys[193] = 3，其次，edge_connect_list[193][]返回這樣的結(jié)果：
int3 edge_connect_list[193][0]: 11 5 10
int3 edge_connect_list[193][1]: 11 7 5
int3 edge_connect_list[193][2]: 8 3 0
int3 edge_connect_list[193][3]: -1 -1 -1
int3 edge_connect_list[193][4]: -1 -1 -1
Geometry Shader在查找了這兩張表的信息之后，并計算出頂點在邊上的具體位置，便會返回3個多邊形列表所需要的9個頂點。由于創(chuàng)建Marching Cubes查找表需要很多的計算量，因此建議預先計算好并在運行前載入。該表在光盤上可以找到。