分类： C/C++
2008-02-20 13:06:19
使用Managed DirectX创建三维地形
作者：clayman
转载请注明作者，商业使用请联系我^_^
使用Height Map作为输入
首先，什么是高度图（Height Map）呢？所谓高度图实际上就是一个2维数组。创建地形为什么需要高度图呢？我们这样考虑，地形实际上就是一系列高度不同的网格而已，这样数组中每个元素的索引值刚好可以用来定位不用的网格（x,y），而所储存的值就是网格的高度（z）。正是由于这个简单的映射关系，最常见的地形生成方法都使用高度图作为输入数据。同时，为了减小数组的尺寸，通常使用Byte类型来保存高度值，因此，地形中最低点将用0表示，而最高点使用255表示（当然，这样做可能会出现一些问题，比如，地形中大部分区域的高度差别都不大，但是有少数地方高度差特别大时，不过大多数情况下这个系统都能运行的很好）。使用2D Byte数组的另一个好处就是我们高度图刚好可以用一张灰度位图（grayscale bitmap） 来表示。对于位图中的每个像素来说，同样使用0~~255之间的值来表示一个灰度。这样，我们又能把不同的灰度映射为高度，并且用像素索引表示不同网格。
那么如何来创建高度图呢？有两种方法：直接使用程序创建2D数组或者使用其他绘图软件创建灰度位图。先来看看两种方法的优缺点。直接创建数组，通过特定算法填充每个元素的值（只为每个元素赋随即值是不可行，这样会导致你的地面看起来极度不真实，不连续的高度值可能创建出很扭曲的地形。），你不需要任何额外的工具就能创建地形。但是，通过这种方法创建的地形基本是随机的，虽然可以通过调节算法的参数控制大概的地形形状，却不能精确控制每个点应该凹下还是凸起。而使用灰度图，你不必掌握复杂的地形生成算法，可以把3维软件建好的地形模型渲染为灰度图，也可以使用通过卫星采样的图片作为灰度图。我们的示例程序将使用后一种方法，不过首先，我们还是来看看完全使用程序生成地形的算法。
使用Midpoint Displacement方法生成高度图
这里我们介绍一种比较常用，也比较简单的地形生成算法，称为Midpoint Displacement中点偏移算法。使用这个方法，我们先创建一张平坦的高度图，然后再来升高或降低不同的网格创建随机地形。为了避免生成的值是完全没有规则的，我们先把整个平面分为4个正方形区域，接下来重复对这四个正方形进行同样的分割，同时，调整每个正方形顶点的高度。随着细份层次的增加，相应减少顶点高度调整的幅度。
使用[0，255]之间的浮点值来进行调整，以保证最后能用8位的灰度值来表示所有高度。每一步，都在一个确定范围内产生一个随机值来作为顶点偏移值。对于第一步来说，随机值将在[-128,128]之间（为了方便说明，我们把这个随机值范围记为[-delta，delta]产生，并且赋给上图左边的A,B,C,D四个顶点。接下来，用虚线把它分为4个小区域，这将创建5个新的顶点。计算每个新顶点所在边两个顶点高度的平均值作为这个点的基准值（比如 把点A和B的高度平均值作为点1的基准值），其中，点5的基准值是由四个顶点A，B，C，D的平均值来决定的。再计算[-delta，delta]之间的一个随机值，对基准值进行偏移，作为这个点的最终值。5个点的值都计算完毕之后，我就调到下一阶段，使用同样的方法，计算个顶点值，如上图右边所示。
为了引导地形的产生，再把delta和一个缩放因子相乘。我们把这个因子称为roughness，它是一个1~0之间的值，这样，每个阶段都会减小delta的值。
delta = delta * roughness
roughness的值越大，地形起伏就越明显，而越小，相应的地形也就越平坦。
使用Perlin Noise生成高度图
任何没有讨论噪声函数的程序地形算法都是不完整的。最重要的噪声函数就是Perlin Noise。他几乎是现代图形软件包生成各种火焰,云彩,奇形怪状的岩石,以及树木和大理石表面等许多应用的基础。这里不对Perlin Noise的理论做详细介绍，我们主要看看如何使用它为我们的地形添加噪声。
Perlin噪声可以适用于任何维度的空间，但这里我们只讨论二维的情况。本质上，2D Perlin噪音就是对每个网格顶点法线的一种插值，来仔细看看这个技术吧。
首先，使用网格把整个图片划分为几个不同部分。如上图所示，我们使用了一个4X4的网格来划分整个图片。这里，网格的多少控制着噪声的复杂性。网格越多，噪声越密集（tiger），类似于电视没有信号时显示出的雪花点；而网格越少，噪声的波形就越明显，类似于云朵的效果。
对于每个网格顶点我们都分配一个随机法线（normal vector）。这些法线实际上就是一些指向不同方向的单位矢量而已。这里，常见的方法是创建一张有256个指向不同方向（形成一个圆周）的向量查找表。然后为每个网格随机分配一个向量，如上图所示。
对于图片中的每个像素来说，我们先找到包含它的网格单元。然后，再创建4个从网格顶点指向所要计算的像素的方向矢量，如下图所示。现在，每个网格顶点有2个向量：一个随机的单位向量以及一个指向像素的方向向量。计算每对向量的点积，把它作为每个网格顶点的梯度高度值（scalar height value）。接下来，混合这4个值决定所计算像素的高度。这里，不同的混合方法可以产生不同效果，最常见的就方法就是通过目标像素与每个顶点位置的权重来计算。
我们将执行3次混合操作。首先需要计算混合权重。使用如下公式：
W = 6t^5 – 15t^4 + 10t^3 (^符号表示幂运算)
其中w表示权重，t根据需要替换为x或y值。这个方法与最早Perlin提出的公式（w = 3t^2 – 2t^3）有些区别。它虽然计算起来比较慢，但效果要好得多。
首先，计算x方向上的权重，使用公式：
V = Ca(w) + Cb(1-w)
混合网格上边的两个顶点。其中Ca和Cb分别为上面两个顶点的梯度高度值，w是上一个公式计算出的权重值。然后，使用同样的方法混合下面两个顶点。最后，使用前两部混合的结果，以及y方向上的权重再进行一次混合。最后为这个像素计算出的高度值位于[0，1]之间，我们再把它缩放为相应的灰度值。
举个例子，假如网格上边两个顶点的坐标分别为Ca[2,0]和Cb[8,0]，梯度高度值分别为h0和h1，所求像素位置为[4，2]，那么两个顶点指向这个像素的矢量就是
Vector2 d0(4 -2,2-0)
Vector2 d1(4-8,2-0);
X轴方向的权重就为
S = 6*d0.x^5 – 15d0.x^4 + 10d0.x^3
相应的插值就为
avgX0 = h0*Sx + h1(1 –Sx)
如果下面两个顶点的插值为avgX1，则最后的插值就是：
Result = avgX0 * Sy + avg2(1- Sy)
通常情况下，为了获得真实的地形，会选取不同网格粒度，分别对图像进行多次Perlin噪音处理，最后把这些处理过的图加到一起，获得最终结果。
生成地形
现在来看看如何把高度图转变为为多边形网格。一开始就说过，把高度图中像素的x，y值转换为顶点的x，y值，把像素的颜色值转换为顶点高度。我们可以把这些值缩放为所需要的尺寸。
每2X2个像素就对应着2X2个顶点，同时可以组成2个三角形。可以把把顶点数据储存为一个简单的（x,y,z）列表，三角形数据储存为三个索引值一组的顶点列表。这两个列表之后就转变为顶点缓冲和索引缓冲。
public class Terrain
{
private Device device;
private VertexBuffer vb;
private IndexBuffer ib;
private int numVertices, numIndices, numTriangles;
//保存从高度图中提取的数据
float[,] heights;
//地形大小
private float terrainSize;
public unsafe Terrain(Device d,float Min, float Max,float terrainSize)
{
device = d;
//加载高度图
Bitmap heightMap = new Bitmap(@"..\..\heightmap.bmp");
//根据位图大小创建数组
heights = new float[heightMap.Width,heightMap.Height];
//锁定数据
BitmapData data = heightMap.LockBits(new Rectangle(0,0,heightMap.Width,heightMap.Height),ImageLockMode.ReadOnly,PixelFormat.Format24bppRgb);
//获得位图中第一个像素的地址
byte* p = (byte*) data.Scan0;
//遍历位图，获得最高和最低点的灰度值
byte lowest = 255;
byte hightest = 0;
for(int i=0;i
{
for(int j=0;j
{
if ( *p < lowest)
lowest = *p;
if( *p > hightest)
hightest = *p;
//由于每个像素是24位，而指针是8位，所以+3指向下一个像素
p += 3;
}
}
//填充数组，max表示地形最高点的位置，min标志最低点。
p = (byte*) data.Scan0;
for(int i=0;i< heightMap.Width;i++)
{
for(int j=0; j< heightMap.Height; j++)
{
heights[i,j] = (float)(*p - lowest) / (float)(hightest - lowest) * (Max - Min) + Min;
p += 3;
}
}
heightMap.UnlockBits(data);
//计算顶点，索引，三角形数量
numVertices = heightMap.Width * heightMap.Height;
numIndices = 6 * (heightMap.Width - 1) * (heightMap.Height - 1);
numTriangles = 2 * (heightMap.Width - 1) * (heightMap.Height - 1);
//创建顶点数组
Vector3[] verts = new Vector3[numVertices];
int[] index = new int[numIndices];
int x = 0;
int n = 0;
float dx = terrainSize / (float) heightMap.Height;
float dy = terrainSize / (float) heightMap.Width;
//填充顶点数组
for ( int i = 0; i < heightMap.Height; i ++)
{
for ( int j = 0; j < heightMap.Width; j ++)
{
verts[i*heightMap.Width+j] = new Vector3((float)j*dx -terrainSize/
}
}
//填充索引数组
for ( int i = 0; i < heightMap.Width-1; i ++)
{
for ( int j = 0; j < heightMap.Height-1; j ++)
{
x = i * heightMap.Width + j;
index[n++] = x;
index[n++] = x+1;
index[n++] = x+heightMap.Width+1;
index[n++] = x;
index[n++] = x+heightMap.Width;
index[n++] = x+heightMap.Width+1;
}
}
//设置顶点以及索引缓冲
vb = new VertexBuffer(typeof(Vector3),numVertices,device,Usage.None,VertexFormats.Position,Pool.Default);
vb.SetData(verts,0,0);
ib = new IndexBuffer(typeof(int),numIndices,device,Usage.None,Pool.Default);
ib.SetData(index,0,0);
}
public void DrawTerrain()
{
device.VertexFormat = VertexFormats.Position;
device.SetStreamSource(0,vb,0);
device.Indices = ib;
device.Transform.World = Matrix.Translation(0,0,0);
device.DrawIndexedPrimitives(PrimitiveType.TriangleList,0,0,numVertices,0,numTriangles);
}
}
好了，看看我们的工作成果吧，还不错把。源码中我们使用了一张位图作为高度图。
当然，这只是初级的地形技术而已，我们没有为地形贴纹理，顶点没有法线信息，以至于不能使用灯光照亮他，另外，也没有进行任何LOD处理。下一次，我们将仔细讨论这些问题。
