翻譯的爛，請見諒，期望深刻理解還請閱讀原著，本譯文僅供參考。
譯:microsoftxiao@163.com 邵小寧 神殺中龍
好，在這里——你將進入3D地形編程的世界！本章將包括地形渲染的所有方面，在你開始有趣的紋理化/光照化技術之前，你需要知道這些，各種各樣的硬編碼地形算法。在本章，你將學習到下面的關鍵概念:
n 什么是高度圖，怎樣創建它，并且怎樣加載它。
n 怎樣使用burte force算法渲染地形
n 怎樣使用fault formation和midpoint displacement產生不規則地形。
那么，讓我們開始吧!
Heightmaps – 高度圖
假設你有一個規則的多邊形格子沿X和Z軸展開。這種情況下你不知道我要談論什么，如圖2.1可以更新你的內存。
現在那是一張漂亮但有令人討厭的圖像！我們怎樣可以正確的制作它呢，好，terrain-ish? 答案是使用高度圖。高度圖，在我們這兒，是一系列unsigned char變量(讓我們把值取在0-255, 這樣在灰度圖上產生一系列漸變灰度值)我們將實時創建且在繪圖程序內。高度圖為我們的地形提供高度值，所以如果我們沿著X和Z軸展開的話，高度圖定義的值將沿著Y軸展開?？炫e個例子， 看如圖2.2。 之后我們加載它并且把它運用到我們的地形中，在格子2.1的格子中將變換出美麗地形(雖然它非常的缺乏顏色和光照)你看如圖2.3。
必須承認，圖2.3的地形開起來即漂亮又討厭，沒有非常酷的紋理和光照，但是我們需要從某處開始!同樣我剛剛解釋了，高度圖給我們的格子的頂點提高到一個宏偉的風景，增添了力量。問題是，嚴密的說什么是高度圖？通常，一個高度圖是一個每像素描繪的灰度值。(在這里，高度范圍從0-255, 一系列漸變的灰度圖。)暗色描繪低海拔，那么亮色描繪高海拔。再看如圖2.2和2.3; notice how the 3D terrain(Figure 2.3) corresponds exactly to the heightmap in Figure 2.2, 從山頂任何一點，到山谷，是平滑的顏色么？那么我們想要我們高度圖做什么呢：作為我們地形頂點的模型。
在這里，我們高度圖的格式將是RAW格式。(雖然大部分demos動態創建高度圖，我包含了加載和保存RAW格式的選項。) 我選擇這個格式因為它難以置信的簡單容易使用。另外，因為RAW格式僅僅包含純數據，它更容易加載高度圖。（我們也要加載灰度的RAW圖，更容易制作。）在我們加載RAW圖像前，我們需要幾個東西。首先，我們需要創建一個簡單的可以描繪高度圖的數據結構。我們這個結構是一個unsigned char類型的緩沖區(我們需要可以動態分配內存)并且變量可以存儲高度圖的大小。這足夠了么， 恩？好，這里:
struct SHEIGHT_DATA
{
unsigned char* m_pucData; // the height data
int m_iSize; // the height size(power of 2)
};
創建地形基礎類 The Creation of a Base Terrain Class
我們需要從所有特定的地形引擎中(brute force, geomipmapping等)創建基礎類將被繼承。我們不希望用戶創建這類的實例；我們僅僅想讓這個類成為我們今后開發特定實現的父類。看圖2.4在我們頭腦獲得一個可視化概念。
圖2.4 CTERRAIN和四個地形實現類的關系
注意: CTERRAIN類是我們C++內的一種抽象類。抽象類是給所有它的子類提供公共的接口。用途是: 一個目前有紅色頭發但是性格另人討厭。雖然所有它的孩子繼承了母親的紅色頭發，但每個有獨特的性格。同樣一個抽象類；雖然一個抽象類令人討厭，its traits carry on to its children, 并且那些孩子可以被定義更多它們自己的另人激動的行為。(即通過覆寫虛函數)
至此我們的類需要三個變量: 一個SHEIGHT_DATA的實例，一個高度縮放比列變量(將讓我們可以為地形動態縮放高度), 和一個大小變量(可以存儲SHEIGHT_DATA的大小)。至于函數，我們需要一些操作高度圖的函數和設置高度縮放變量的函數。這里我們展示出:
class CTERRAIN
{
protected:
SHEIGHT_DATA m_heightData; // the height data
Float m_fHeightScale; // scaling variable
public:
int m_iSize; // must be a power of two
virtual void Render(void) = 0;
bool LoadHeightMap(char* szFilename, int iSize);
bool SaveHeightMap(char* szFilename);
bool UnloadHeightMap(void);
//-------------------------------------------------------------------------------------
// Name: SetHeightScale – public
// Description: Set the height scaling variable
// Arguments: -fScale: how much to scale the terrain
// Return Value: None
//---------------------------------------------------------------------------------------
inline void SetHeightScale(float fScale)
{ m_fHeightScale = fScale; }
//------------------------------------------------------------------------------------------
// Name: SetHeightAtPoint – public
// Description: Set the true height value at the given point
// Arguments: -unHeight: the new height value for the point
// -iX, iZ: which height value to retrieve
// Return Value: None
//-------------------------------------------------------------------------------------------
inline void SetHeightAtPoint(unsigned char ucHeight, int iX, int iZ)
{ m_heightData.m_pucData[( iZ*m_iSize )+iX] = ucHeight; }
//---------------------------------------------------------------------------------------------
// Name: GetTrueHeightAtPoint – public
// Description: A function to get the true height value(0-255) at a point
// Arguments: -iX, iZ: which height value to retrieve
// Returen Value: An unsigned char value: the true height at
// the given point
//----------------------------------------------------------------------------------------------
inline unsigned char GetTrueHeightAtPoint(int iX, int iZ)
{ return ( m_heightData.m_pucData[( iZ*m_iSize )+iX ]; }
//-------------------------------------------------------------------------------------------------
// Name: GetScaledHeightAtPoint – public
// Description: Retrieve the scaled height at a given point
// Arguments: -iX, iZ: which height value to retrieve
// Return Value: A float value: the scaled height at the given point
//--------------------------------------------------------------------------------------------------
inline float GetScaledHeightAtPoint( int iX, int iZ )
{ return ( ( m_heightData.m_pucData[( iZ*m_iSize )+iX])*m_fHeightScale); }
CTERRAIN(void)
{ }
~CTERRAIN(void)
{ }
};
Not too shabby if I do say so myself! 好那是我們的地形父類!每個我們開發的其他實現從這個類派生。我為用戶添加了兩個容易使用的操作高度圖的函數。然而我們，作為開發者，將使用true函數，用戶將使用被縮放了的函數來執行碰撞檢測(我們將在第八章做, “封裝它: 特效和其他”)
加載和卸載高度圖 Loading and Unloading a Heightmap
我已經談論了這些例程，并且我們最后要使用它們。這些例程是簡單的，所以對比他們沒有任何難度。我們僅僅使用一些C風格的文件I/O來做。
注意: 我趨向于使用嚴格的C風格I/O因為它比C++風格的更容易閱讀。如果你已經是真正的C++死忠，并且完全厭惡C做事的方式，那么可以自由改變例程為C++式的。另一方面，我確實喜歡C++風格的內存操作，所以，如果你是C死忠，那么你就那么做。
我需要談論怎樣加載，保存和卸載高度圖。最好的地方是在開始時加載例程因為你不能在沒有加載前卸載任何事物。我們需要兩個參數：文件名和地圖大小。在函數內，我們想創建FILE的實例來加載高度圖。那么我們想確認高度圖類的實例是否已經加載了信息；如果是這樣，那么我們需要調用卸載例程并繼續我們操作。我們討論的代碼像這樣:
bool CTERRAIN::LoadHeightMap(char* szFilename, int iSize)
{
FILE* pFile;
//check to see if the data has been set
if( m_heightData.m_pucData)
UnloadHeightMap();
}
其次, 我們需要打開文件并為我們的高度圖實例數據緩沖區分配內存(m_heightData.m_pucData)。我們需要確認內存是否被正確的分配，是否沒有發生可怕的錯誤。
// allocate the memory for our height data
m_heightData.m_pucData = new unsigned char [ iSize*iSize];
// check to see wether the memory was successfully allocated
if (m_heightData.m_pucData == NULL)
{
// the memory could not bel allocated
// something is seriously wrong here
printf(“Could not allocate memory for%s"n”, szFilename);
return false;
}
我們的加載過程繼續，我們將加載實際的數據把它們放置在高度圖實例的數據緩沖區內。然后我們將關閉文件，設置一些類成員變量，然后輸出成功消息。
// read the heightmap into context
fread(m_heightData.m_pucDat, 1, iSize*iSize, pFile);
// close the file
fclose(pFile);
// set the size data
m_heightData.m_iSize = iSize;
m_iSize = m_heightData.m_iSize;
// Yahoo! The height has been successfully loaded!
Printf(“Loaded %s"n”, szFilename);
Return true;
}
注意: 高度圖保存例程幾乎是和加載同樣的東西。基本上，我們僅僅需要替換fread為fwrite。That’s all there is to it!
那就是加載例程。讓我們在我們注意力被分散前轉到卸載例程。卸載程序是簡單的。我們僅僅必須檢查內存是否已經被分配，然后如果分配了，我們需要刪除它。
bool CTERRAIN::UnloadHeightMap(void)
{
// check to see if the data has been set
if(m_heightData.m_pucData)
{
// delete the data
delete[] m_heightData.m_pucData;
// reset the map dimensions, also
m_heightData.m_iSize = 0;
}
// the heightmap has been unloaded
printf(“Successfully unloaded the heightmap"n”);
return true;
}
我真的不需要檢查數據緩沖是一個NULL指針(指針是否為NULL在中心會檢查) , 所有我的檢查有點是多余的。這個檢查已經成為了習慣，然而，這本書就是這么做的。你可以不檢查是否為NULL指針就刪除它?，F在我將展示給你我們已經討論的渲染方法。
The Brute Force of the Matter 硬渲染
渲染地形使用brute force算法直接而簡單，而且它提供了最大化的細節。不幸的是，它是這本書里講的最慢的算法。基本上，如果你有一個64x64像素的高度圖，那么地形，當使用brute force渲染時，由64x64個頂點組成，規則的重復模式。如圖(2.5)
這種情況下你不能立即重新組織它，我們將每行的頂點作為三角形帶渲染因為這是大部分渲染頂點的方式。你不能單獨的渲染一個三角形或使用像圖2.5那樣的方式渲染三角扇形，would you?
這章的demo, 我留著它作為一種簡單的可能。頂點的顏色基于它的高度，所以所有頂點將利用灰色著色。并且所有這些都使用brute force渲染地形。這里快速的摘錄一小片OpenGL來展示怎樣渲染地形:
void CBRUTE_FORCE::Render(void)
{
unsigned char unColor;
int iZ;
int iX;
// loop throught the Z axis of the terrain
for (iZ = 0; iZ<m_iSize-1; iZ++)
{
// begin a new triangle strip
glBegin(GL_TRIANGLE_STRIP);
//loop through the X axis of the terrain
//this is where the triangle strip is constructed
for(iX=0; iX<m_iSize-1;iX++)
{
//Use height-based coloring. (High-points are
//light, and low points are dark.)
ucColor = GetTrueHeightAtPoint(iX, iZ);
// set the color with OpenGL, and reader the point
glColor3ub(ucColor, ucColor, ucColor);
glVertex3f(iX, GetScaledHeightAtPoint(iX, iZ), iZ);
// Use height-based coloring. (High-points are
// light, and low points are dark.)
ucColor = GetTrueHeightAtPoint(iX, iZ+1);
// set the color with OpenGL, and render the point
glColor3ub(ucColor, ucColor, ucColor);
glVertex3f(iX,
GetScaledHeightAtPoint(iX, iZ+1),
iZ+1);
}
// end the triangle strip
glEnd();
}
}
現在到了創建實際demo的時候了!拿出在CD上的demo2_1。到Cod"Chapter 2"demo2_1, 用Microsoft Visual C++打開工作區， 然后開始娛樂！這個demo展示了我們剛剛討論的梭魚東西。如圖2.6展示了demo的截圖，如表2.1提供了控制demo的描述。移動你的視點，僅僅可以使鼠標向左，右和拖拽。
Woohoo!現在，我說過我們將創建大量我們的動態高度圖。你也許會問你自己，我該怎樣做? 好的，我很高興回答你。(甚至如果你不問，我仍然要解釋它!)現在我們將學習怎樣以程序的方式使用兩種不規則地形產生技術生成高度圖。準備!
Fractal Terrain Generatoin 不規則地形生成
Fractal terrain generation被用來產生地形的算法， 雖然這里，我們將高度圖作為我們地形的藍圖。但是我們將通過這里的兩個算法，第一個是fault formation和第二個midpoint displacement。我們將自始至終的使用fault formation算法在本書因為它不會被地點尺寸所限制，(如果用一般高度圖將限制在0-255的高度)， 而midpoint displacement需要2的N次方才可以。(尺寸也必須是相等的，所以你可以產生1024x1024的高度圖，你不能產生產生一個512x1024的高度圖。)所以，不要再耽擱了，讓我們從不規則地形生成算法開始!
Fault Formation缺點形成算法
一種不規則地形生成算法叫做fault formation. Fault formation是在生成地形過程中”faults”; 大部分時，它產生比較平滑的地形?；旧希形覀冏龅碾S機線在blank高度區域， 而且然后我們添加隨機高到一邊?？磮D2.7如果你討厭可視化或者如果你剛剛想要證實你腦中的圖(或者， 如果你喜歡， 注意你的頭腦 – 我很奇怪)是正確的。
圖 原版 43頁 fault-formation algorithm
這是整個過程的第一步，當然。在你提高到高級階段之前，這里還有一些你需要知道的算法。首先，更早時我談論過需要減少每次反復。你也許會問為什么？好，如果你不減少每個高度，你最后使用的高度將像2.8?？?/span>2.9的高度圖。
注意， 在圖2.8, 亮/暗斑點是多么的不和諧就是這個原因；他們僅僅在所有地方被展開。這就好像一個混亂的地形，但是我們像創建一個平滑的，起伏的小山。不要擔心；解決這個問題相當簡單。我們想用線性遞減高度值沒有在0結束。這么做，我們將使用下面的等式(拿出demo2_2):
iHeight = iMaxDelta – ((iMaxDelta-iMinDelta)*iCurrentIteration)/iIterations;
iMinDelta, iMaxDelta, 和iIterations作為函數參數提供。 iMinDelta和iMaxDelta描繪了最低值和最高值，你想要當新faults時的高度。我趨向于嚴格的一個0作為iMinDelta和255作為iMaxDelta。iIterations， 我之前說過，描繪fault passes一系列過程(多么不同的時間被劃分)。最后，but certainly not least, iCurrentIteration描繪了當前iteration值。
我早說過，我們就年斤毫年 想提升一邊，然后我們想升起每個邊線點的高度值。因此，我們將循環處理整個高度圖的所有高度。所有這些容易實現；它僅僅是解決一個簡單的數學問題。我有一個vector在我們線的方向上(我們之前創建了兩個隨機點，那么它的方向被存儲在(iDirX1, iDirZ1)。下一個vector我們想創建一個從最初隨機點(iRandX1, iRandZ1)到當前循環點(x, z)。 之后完成，我們需要找到Z分量的叉乘， 然后如果它比0大，那么我們需要增加當前點。所有之前的解釋都將從這的代碼展示出來。
// iDirX1, iDirZ1 is a vector going the same direction as the line
iDirX1 = iRandX2 – iRandX1;
iDirZ1 = iRandZ2 – iRandZ1;
for(x = 0; x<m_iSize;x++)
{
for(z=0; z<m_iSize; z++)
{
// iDirX2, iDirZ2 is a vector from iRandX1, iRandZ1 to the
// current point (in the loop).
iDirX2 = x-iRandX1;
iDirZ2 = z-iRandZ1;
// if the result of (iDirX2*iDirZ1 – iDirX1*iDirZ2) is “up”
//(above 0), then raise this point by iHeight
if((iDirX2*iDirZ1 – iDirX1*iDirZ2) > 0)
fTempBuffer[( z*m_iSize)+x]+=(float)iHeight;
}
}
注意: 在demo2_2這兩段你看到了fault formation和midpoint displacement代碼在demo2_2內的兩個片段，你也許注意到我怎樣創建臨時緩沖區，fTempBuffer, 所有的高度值嚴格用浮點表示。如果你記得，雖然，我談論過我們的高度圖是一個unsigned char類型的數組。為什么我在這種情形使用浮點變量？我這么做是因為算法需要比我們的默認unsigned char高度緩沖區有更高的精確性。之后我們創建整個高度圖并規格化，我從fTempBuffer傳送所有信息到CTERRAIN類內的高度緩沖區， m_heightData。
檢查圖2.9看一些使用fault formation產生的高度圖，和各種fault-line iterations. 緊接著， 我們也還沒有完成這個算法！萬一你沒注意， 地圖看起來像之前的圖(非-terrainish)(新世界)。我們需要經過一個腐蝕(erosion)過濾器來過濾整個地圖直到我們形成一個新的平滑的值的。這個過程非常好， 如果不精確， 像經過污點過濾器通過你喜歡的繪圖程序來處理下。 如果它幫助你理解了下面的解釋， 正好是這樣的理解。
我們將要應用一個簡單的FIR過濾器， 作為Jason Shankel的建議。 這個過濾器意味著模擬地形侵蝕(erosion)，就像自然界頻繁發生的那種。你曾經在自然界里看到過的一系列的高山看起來如圖2.9?) 我們將獲得波形(bands)數據，勝于立刻過濾整個高度圖。過濾函數看起來像這樣:
void CTERRAIN::FilterHeightBand( float* fpBand, int iStride, int iCount, float fFilter)
{
float v = ucpBand[0];
int j = iStride;
int i;
// Go through the height band and apply the ersion filter
for(i = 0; i < iCount-1; i++ )
{
ucpBand[j] = fFilter*v + (1-fFilter)*ucpBand[j];
v = ucpBand[j];
j+= iStride;
}
}
這個函數獲取高度值的單個邊并且goes through them value by value, 通過iStride規定在每次循環內的向前的值日。iStride也規定出我們過濾整個高度圖從上到下的方向，從下到上，從坐到右，從右到左。整個函數最重要的是這行:
ucpBand[j] = fFilter*v + (1-fFilter)*ucpBand[j];
這行是涂污/侵蝕。 各種各樣的值為了fFilter影響模糊。0.0f是根本不模糊， 1.0f是最模糊。通常，我們想要值在0.3f到0.6f之間，這依賴于你想要地形的平滑程度。現在，例如， 我們說出過濾器的值0.25f, 且當前邊值為0.9f。前一個等式看起來像這樣:
ucpBand[j] = 0.25f*v + (1-0.25f)*0.9f;
之后我們執行初始化計算， 之前的等式將簡單化為這樣:
ucpBand[j] = 0.25f*v + 0.675f;
0.675f是高度圖像素被模糊的新值， 但是現在它需要被和之前的像素值進行插值。(我們將給出像素值為0.87f)。我們應用0.25模糊過濾器到該像素且加上非插值的像素值到此像素，以致于我們有這樣的計算。
ucpBand[j] = 0.25f*0.87f + 0.675f;
執行最后的計算， 我們得到0.8925f的最終值。 所以，你看， 所有我們真實的行動這里混合成了當前像素到前一像素間的值。拿出圖2.10看我們之前討論的每像素過濾看起來是非常大攀登。
玩弄下demo2_2. 我為高度圖操作制作了菜單， 并且現在你可以動態創建新的高度圖。如果你找到了，僅僅選擇保存當前選項， 那么高度圖將被保存到程序目錄下。當你選擇Fault Formation選項時，彈出一個對話框你可以輸入細節值。這個值是一個整數，取值范圍為1-100?，F在該介紹些有趣的midpoint displacement(中點位移)的時候了。
Midpoint Displacement 中點位移算法
Fault formation在一些小場景組成一些小山工作的非常好，但是如果你想產生一些比這混亂的，甚至像山脈那樣的地貌, Fault formation就不行了。好，繼續看。Midpoint displacement將可以滿足你的期待！這個算法也被認為是plasma fractal和diamond-square算法。然而，midpoint displacement發出的聲音更酷，并且它提供給讀者(就是你)一個繼續整個過程更好的觀點，所以我將堅持大部分時間使用這一術語。
注意: 重要的是注意midpoint displacement算法有一個輕微的缺點: 算法僅可以生成方形的高度圖，并且尺寸必須似乎2的N次方。這不像fault formation算法，你可以指定任何你想要的尺寸。
我們將完成這個算法，本質上，它是對單條邊的中點進行位移。讓我給你一個一維空間的概念。如果我們有一條線，像如圖2.11 AB， 我們找到它的重點，標記出來為C。并且移動它?，F在，我們將位移線中點的高度值，我們叫fHeight吧。(看圖2.12)。我們將使得產生的兩條線相等，并且我們將在-fHeight/2到fHeight/2到范圍內位移中點。(我們想要每次細分出(subdivide)兩條線，而且我們將要將其位移到線的某個高度在一定范圍內。
之后我們需要遞減fHeight的直到我們期望的粗糙程度。就這么做，我們簡單的用2-fRoughness來進行乘法, fRoughness是未加工地形的一個常量值。用戶將指定該值存儲到fRoughtness內，所以你需要知道一點關于你可以設置各種值的信息。這個值是可以的，從技術上講，任何可以是你任何期望的浮點值，但是最好的結果應該是0.25f到1.5f。看圖2.13，可視化的指示出各種可以達到的粗糙程度的情形。
正如你看到的，這個值即fRoughness對高度圖的影響相當大。值小于1.0f將創建一個無序地形，值正好為1.0將是平行的，大于1.0f將創建一個平滑的地形?，F在讓我們繼續深入解釋二維的情形。
1D的解釋留在你的大腦中，我們將改變到2D因為你剛剛學習了單條線的相關概念。有個例外是這樣的，代替單線的中點計算，我們現在必須計算四條不同邊的中點，平均它們，然后為正方形的中心的高度值增加這個值。如圖2.14所示的正方形(ABCD)開始。
像我之前說的第二點，我們必須計算所有四邊的中點(AB, BD, DC, CA)。結果點為E, 將直接在正方形的中心。然后位移E用ABCD高度值的平均值，并加上在-fHeight/2到fHeight/2范圍內的隨機值。結果將如圖2.15所示。
這還僅僅是第一次位移的一半階段。現在我們必須計算出每個中點的高度值，是我們先前找到的那個。跟我們之前做的是相似的，；我們僅僅平均圍繞頂點的高度值并加上-fHeight/2到fHeight/2范圍內隨機值日。最后將如圖2.6所示。
然后你可以繼續找到下一個矩形執行同樣的處理。如果你理解了1D解釋，然而，你確定理解了2D解釋并實習那代碼，demo2_2, 找到CD內Code"Chapter 2"demo2_2。
編譯信息，照常，提供了文本文件在demo的目錄下。去查看這個demo。控制與最后一次的(表2.1提示)的相同，但是這次，當你點下細節區域的重點時，你想要的值范圍為0(真是無序的地形)到150(簡單地形 ). 真有趣。
摘要
本章，你收到了進入地形編程的入門級訓練。你學到了所有關于高度圖的信息: 它們是，怎樣產生它們，還有怎樣加載/卸載它們。然后你學習了怎樣使用burte force渲染那些高度圖，是市面上最簡單的地形渲染算法。最后，你學習兩種程序式產生高度圖的算法。下兩章，我們將學習所有和地形的紋理化和光照化的有趣技術。
參考
1 Shankel, Jason, “Fractal Terrain Generation – Fault Formation. “
Game Programming Gems. Rockland, Massachusetss: Charles River Media, 2000. 499-502.
2. Shankel, Jason. “Fractal Terrain Generation – Midpoint Displacement. “ Game Programming Gems. Rockland, Massachusetts:
Charles River Media, 2000. 503-507.