翻译的烂，请见谅，期望深刻理解还请阅读原著，本译文仅供参考。
译: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轴展开。快举个例子， 看如图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指针就删除它。现在我将展示给你我们已经讨论的渲染方法。
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”; 大部分时，它产生比较平滑的地形。基本上，所有我们做的随机线在blank高度区域， 而且然后我们添加随机高到一边。看图2.7如果你讨厌可视化或者如果你刚刚想要证实你脑中的图(或者， 如果你喜欢， 注意你的头脑 – 我很奇怪)是正确的。
图 原版 43页 fault-formation algorithm
这是整个过程的第一步，当然。在你提高到高级阶段之前，这里还有一些你需要知道的算法。首先，更早时我谈论过需要减少每次反复。你也许会问为什么？好，如果你不减少每个高度，你最后使用的高度将像2.8。看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。现在该介绍些有趣的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。并且移动它。现在，我们将位移线中点的高度值，我们叫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将创建一个平滑的地形。现在让我们继续深入解释二维的情形。
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.