最近開始抽空在看GPU Gems 3了。本來想挑幾篇全文翻譯，但是無奈自己英語水平薄弱，同時(shí)最近老板逼得緊，也沒有那么多時(shí)間，于是便準(zhǔn)備以導(dǎo)讀的形式，將文章的主干部分翻譯出來,幫助英文不好的筒子們。
導(dǎo)讀也是我自己讀書的總結(jié)。文章的核心內(nèi)容一定會(huì)提及.圖和源碼，通常我會(huì)標(biāo)注上對(duì)應(yīng)的圖書上的figure和list，各位自行參考?；揪S持原文的篇章段落，但是一般不會(huì)逐字句的考究。
至于能有多少篇，我倒是不能保證。不過我所用的電子版是那個(gè)26M的chm，我讀的時(shí)候會(huì)把它翻成PDF并加注，如果有筒子需要我注釋后的pdf，可以與我聯(lián)系：

mail： wuye9036   _AAAAATTTTT_ google _dotdotdotdotdot_com

--------------------------------------------------------------------------------

Chapter I 運(yùn)用GPU構(gòu)造復(fù)雜的過程化地形
1.1 Introduction
過程化地形的應(yīng)用已經(jīng)有不少的歷史了，Game Programming Gems 2上就已經(jīng)有了不少成熟的過程化地形的方法，比方說隨機(jī)斷層、基于噪聲的、基于分形理論的、中點(diǎn)分割加擾動(dòng)的。
不過這些算法在現(xiàn)代硬件上都時(shí)有缺陷的，特別是針對(duì)規(guī)模很大的地形，要么只能在CPU上實(shí)時(shí)生成，要么就得預(yù)存儲(chǔ)起來，但是不管怎么說都面臨著很大的資源開銷；其次這些算法都是只能生成有些起伏的平面，沒辦法表現(xiàn)山洞、巖石凸角一類的3D特征。本文運(yùn)用DX10的Geometry Shader與Stream Output，彌補(bǔ)了上述兩個(gè)缺陷。

1.2 移動(dòng)立方體與密度函數(shù)
要解決3D的地形特征，首先要解決3D地形特征的表達(dá)問題。文中將空間劃分為多個(gè)Blocks，每個(gè)Block代表了世界坐標(biāo)系中1*1*1大小的空間。每個(gè)Block由一個(gè)3D紋理來表達(dá)。由于使用了過程化的方法，每個(gè)Block可以在運(yùn)行的時(shí)候動(dòng)態(tài)生成，這樣只需要保留那些能看得見的blocks，從而解決了存儲(chǔ)問題。
概念上，一個(gè)3D的地形可以由一個(gè)密度函數(shù)來表達(dá)。對(duì)于每個(gè)空間中的點(diǎn)(x, y, z)，都有唯一對(duì)應(yīng)的密度值。我們假設(shè)，對(duì)于任意一個(gè)空間中的點(diǎn)，如果點(diǎn)在地形內(nèi)部/巖石內(nèi)部當(dāng)且僅當(dāng)點(diǎn)上的密度值大于0。那么小于0的點(diǎn)，自然就在地形之外，如在空氣中，水中等等。而巖石表面上的點(diǎn)密度剛好等于0。
那么自然，這些巖石表面上密度值等于0的點(diǎn)，就是我們要繪制的“表面”。
在將空間劃分為Block后，還要將每個(gè)block進(jìn)一步細(xì)分為多個(gè)voxel（體素）。我們假定體素內(nèi)密度變化時(shí)連續(xù)的。那么很顯然，如果一個(gè)體素的頂點(diǎn)上密度有正有負(fù)，那么必然里面會(huì)有一個(gè)（也有可能是多個(gè)）0值面。問題就轉(zhuǎn)化為，如何根據(jù)體素各個(gè)頂點(diǎn)的密度值，求出這個(gè)體素內(nèi)的0值面。如果再把這個(gè)假設(shè)限定的嚴(yán)格一點(diǎn)，如果體素內(nèi)密度變化是線性的，那么這些面可以由0-5個(gè)三角形來表示；求得這些三角形的方法，被稱為Marching Cube算法。
很顯然，有多少個(gè)三角形，每個(gè)三角形的頂點(diǎn)落在哪條邊上，是由八個(gè)頂點(diǎn)的密度的正負(fù)值所決定的，而值的相對(duì)大小則決定了三角形的頂點(diǎn)在邊上靠近那個(gè)頂點(diǎn)。那么也就是說，一個(gè)體素內(nèi)0值面的分布共有2^8中情況。如果頂點(diǎn)密度為負(fù)，那么標(biāo)記為0，頂點(diǎn)密度為正則標(biāo)記為1，則八個(gè)頂點(diǎn)的情況可以由一個(gè)Byte來表示。

圖1-3

如果這個(gè)字節(jié)的值為0或者為255，那么說明所有的頂點(diǎn)都為正或?yàn)樨?fù)，那么說明體素中并沒有地表面。Martin Frank為剩下的254中情況建立了一個(gè)查找表。其中基本的情形有14種，其余的均可由這些基本情況的對(duì)稱或旋轉(zhuǎn)求得。

圖1-4

當(dāng)確定了三角形的三個(gè)頂點(diǎn)分布于哪些邊上后，便可用插值的方法求出所在位置。頂點(diǎn)將位于0值點(diǎn)處。例如，一條邊AB上有一個(gè)0值點(diǎn)P，如果A的密度0.3，B的密度-0.1，那么PB的長度是PA長度的三倍。

1.2.2 查找表
上文已經(jīng)提到了如何通過體素角點(diǎn)的密度值，就會(huì)知道會(huì)生成哪些多邊形；這些多邊形的頂點(diǎn)落在哪些邊上。
接下來，我們將用討論這些理論如何在GPU上實(shí)現(xiàn)。
首先我們建立一張查找表
int case_to_numpolys[256];
其中每種情況能產(chǎn)生多少個(gè)三角形。
第二張查找表，
int3 edge_connect_list[256][5];
這張表保存了每種情況對(duì)應(yīng)的5個(gè)三角形。并且我們將一個(gè)體素中的12條邊按照0-11編號(hào)（圖 1-5），則查找返回的返回的int3指出了，每個(gè)三角形的三個(gè)頂點(diǎn)分別落在哪條邊上。

圖 1-5 Case 193 的0值多邊形情況

下面的例子很好的說明了這一點(diǎn)。
我們以case 193為例。193總共有3個(gè)三角形，那么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在查找了這兩張表的信息之后，并計(jì)算出頂點(diǎn)在邊上的具體位置，便會(huì)返回3個(gè)多邊形列表所需要的9個(gè)頂點(diǎn)。由于創(chuàng)建Marching Cubes查找表需要很多的計(jì)算量，因此建議預(yù)先計(jì)算好并在運(yùn)行前載入。該表在光盤上可以找到。