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