转地形编程（一）

地形在三维中的地位是毋庸置疑的，最近在看《Focus On 3D Terrain Programming》这本书，做一下简单的笔记.

本书的第二章主要解决了三个问题：

• 什么是高度图？怎么创建高度图？如何载入高度图？
• 如何使用直接的方法渲染地形？(how to render terrain using a brute force algorithm?)
• 如何使用fault formation与mid displacement算法动态生成高度图，然后生成地形。

高度图就是一个灰度图片，每一个像素代表了一个高度。通常情况下黑色的像素点代表了地形低洼的地带，白色的像素点代表了地形高的像素点。读入高度图后可以通过OpenGL直接将绘制出来。

地形生成算法（Fractal Terrain Generation）：

1：Fault Formation

     此算法的主要思想：对于想要生成的m*n维高度图，在此高度图上随机取一条直线，直线将高度图一份为二，然后在其中的一边（被直线分成的两部分中的一部分）加上一个随机的高度。此算法过程中，每次迭代都需要一个平滑滤波对其进行做一定的修改，不然得出的高度图会非常的尖锐。如图所示：

在生成fault formation的时候，进行改变的一边是用过向量的叉乘得来的，在确定直线的两点A（iRandX1， iRandX1)、B（iRandX2， iRandX2）。通过这两点可以确定直线的方向向量，然后再在高度图上另取一点C（x， z)，此时通过向量AC叉乘向量AB，通过叉乘法则（右手法则）就可以确定直线的一边，然后对其进行变换。变换代码如下：

for(i = 0; i < m_iSize * m_iSize; i++)
    fTempBuffer[i] = 0;

for(iCurrentIteration = 0; iCurrentIteration < iIterations; iCurrentIteration++)
{
    // calculate the height range (linear interpolation from iMaxDelta to iMinDelta
    // for this fault-pass
    iHeight = iMaxDelta - ((iMaxDelta - iMinDelta) * iCurrentIteration) / iIterations;

    // pick two points at random from the entire height map
    iRandX1 = rand() % m_iSize;
    iRandZ1 = rand() % m_iSize;

    // check to make sure that the points are not the same
    do
    {
        iRandX2 = rand() % m_iSize;
        iRandZ2 = rand() % m_iSize;
    }while(iRandX1 == iRandX2 && iRandZ2 == iRandZ1);

    // iDirX1, iDirZ1 is a vector going the same direction as the line
    iDirX1 = iRandX2 - iRandX1;
    iDirZ1 = iRandZ2 - iRandZ1;

    for(z = 0; z < m_iSize; z++)
    {
        for(x = 0; x < m_iSize; x++)
        {
            // iDirX2, iDirZ2 is a vector  from iRandX1, iRandZ1 to the current point
            iDirX2 = x - iRandX1;
            iDirZ2 = z - iRandZ1;

            // if the result of(iDirX2 * iDirZ1 - iDirX1 * iDirZ2) is "up"
            // then raise this point by iHeight
            if(iDirX2 * iDirZ1 - iDirX1 * iDirZ2 > 0)
                fTempBuffer[(z*m_iSize) + x] += (float)iHeight;

        }
    }

经过这些变换之后，得到的高度图并不能得到非常平滑的地形，因此需要一个滤波变换（erosion filter）本文中使用的是FIR滤波器，在对高度图进行处理的时候分别从左到右、从右到左、从上到下、从下到上进行处理。最后得出高度图，如图所示：

2:Midpoint Displacement(plasma fractal/diamond-square)

优点：对于fault formation来说生成小地形（小的山丘等）完全可以胜任，但是如果地形如果有很多山脉，fault DIsplacement就有点儿不行了，此时就需要使用midpoint displacement算法了。

缺点：只能生成一个正方形的高度图，并且维度为2的n次方。

中点偏移算法（我自己翻译的，如有不对还望告知）算法思想非常简单，对于一维的(一条直线）而言取其中点，然后对重点进行一定范围的位移，这个范围是[-fHeight/2, fHeight/2]，其中fHeight=length。经过一次迭代后，此时变换的高度要乘以一个缩放系数，2^-Roughness，其中Roughness是地形的粗糙度。这样变换是为了能够在接下来的迭代过程中能够得到非常好的地形。

对于二维情况，中点是由其上下左右四个点共同决定的，废话少说，代码说明问题：

     // being the displacement process
     while(iRectSize > 0)
     {
         for(i = 0; i < m_iSize; i += iRectSize)
         {
             for(j = 0; j < m_iSize; j += iRectSize)
             {
                 ni = (i + iRectSize) % m_iSize;
                 nj = (j + iRectSize) % m_iSize;

                 mi = (i + iRectSize / 2 );
                 mj = ( j + iRectSize / 2);

                 fTempBuffer[mi + mj * m_iSize] = (float)((fTempBuffer[i + j*m_iSize] + fTempBuffer[ni + j*m_iSize]
                                                    + fTempBuffer[i + nj*m_iSize] + fTempBuffer[ni + nj*m_iSize]) / 4 + RangedRandom( -fHeight/2, fHeight/2 ));
             }
         }


         for(i = 0; i < m_iSize; i += iRectSize)
         {
             for(j = 0; j < m_iSize; j += iRectSize)
             {
                 ni = (i + iRectSize) % m_iSize;
                 nj = (j + iRectSize) % m_iSize;

                 mi = (i + iRectSize / 2);
                 mj = (j + iRectSize / 2);

                 pmi = (i - iRectSize / 2 + m_iSize) % m_iSize;
                 pmj = (j - iRectSize / 2 + m_iSize) % m_iSize;

                 //Calculate the square value for the top side of the rectangle
                 fTempBuffer[mi+j*m_iSize]= ( float )( ( fTempBuffer[i+j*m_iSize]      +
                     fTempBuffer[ni+j*m_iSize]      +
                     fTempBuffer[mi+pmj*m_iSize]      +
                     fTempBuffer[mi+mj*m_iSize] )/4+
                     RangedRandom( -fHeight/2, fHeight/2 ) );

                 //Calculate the square value for the left side of the rectangle
                 fTempBuffer[i+mj*m_iSize]= ( float )( ( fTempBuffer[i+j*m_iSize]      +
                     fTempBuffer[i+nj*m_iSize]      +
                     fTempBuffer[pmi+mj*m_iSize]      +
                     fTempBuffer[mi+mj*m_iSize] )/4+
                     RangedRandom( -fHeight/2, fHeight/2 ) );
             }
         }

         // reduce the rectangle size by two prepare for the next
         // displacement stage
         iRectSize /= 2;

         // reduce  the height by height reducer
         fHeight *= fHeightReducer;
     }

     // normalize the terrain for our purposes
     NormalizeTerrain(fTempBuffer);

     // transfer the terrain into our class's unsigned char height buffer
     for(z = 0; z < m_iSize; z++)
     {
         for(x = 0; x < m_iSize; x ++)
             SetHeightAtPoint((unsigned char) fTempBuffer[(z * m_iSize) + x], x, z);
     }

运行结果如下：

两种方法，各有所长。