zerO

想想顺便连地形一起放上来吧。由于时间比较赶，目前Alchemy3D的地形引擎是基于三角形网格的。

HeightMap简介

现实中的地形是真实的，不是由三角平面模拟的，但是3D图形图像处理中常常使用三角形来代替地形的表面，每个三角形的顶点高度在山脉到山谷之间转换，模拟自然地形，如图所示。在这个过程中，还将应用纹理展示沙滩、丘陵和雪山。

HeightMap技术的灵感来源于等高地图的绘制，如图所示，是一幅等高地图，它通常用来描绘高低起伏比较大的地形。

例如，飞行员必须了解哪里有高海拔的障碍物、山川、湍流的方向等，以便安全地飞行。从空中往下看，陆地上可能很平坦，但事实上等高线是展开的，没有相当的理解力和想象力，许多人并不能很好地领会地图实际提供的信息。

高度从平面图上无法立体地显现，所以用有规律的间隔来表示海拔，通常根据测量方法的不同一般间隔为50英尺或10m，同等位置的点被连成线，即等高线。

许多情况下这些等高线聚在图上形成封闭的环线，有些部分为不规则的心形，不时会凸出来一点。如果它们突然中断与其他线相冲突，则表示有高度的突然变化，事实上为悬崖或很深的落瀑。

自然界中能看到的惟一等高线只有沿着海岸的水平线（由于海潮的变化，事实上那也不是完全意义上的等高线），但可以把等高线想象成如同水平桌面的边线，如果把衣物或其他东西堆在桌面上，就如同小山峰或其他形状。

在这些等高线之间具体地形如何，都没有表示出来。等高线之间也不一定就是斜坡，可能是洞穴、凸起的岩石，以及其他各种高度变化在10m之内的地势。从等高线的相应位置，可以简单地猜测出地表大概会是如何变化的。

等高线地图可以形象地反映山体的情况，如图所示是实际山体与等高线地图的对应表示。等高线地图在军事、旅游、探矿中有着广泛的应用。

等高线之间的间隔只是表明同一理论高度下地平线上点之间的距离，并非是地面山坡上点间的实际距离，它们只是用来表明相应的位置，并非根据地平面的比例。

常见的一种错误想法是，一群等高线是按地图绘制比例缩小的地面高度——要知道典型的旅行地图比例是1∶50000，10m在图上只有0.02mm。图上间距5mm的等高线在地表面的距离为250m，而不是实际代表的10m落差，差距是1∶25。

理解等高线，就可以说掌握了一半的HeightMap技术。在3D地形渲染中，采用数组的形式来保存高度信息（数组内容可以通过高度图读取，图片上的一个像素或者一个区域代表同一高度），根据高度信息在不同的位置绘制多边形，从而通过2D图像展示出3D地形场景。

高度图可以使用画图板或者图像编辑器Adobe Photoshop产生。使用图像编辑器可能更容易，它能够帮助创建想要的交互地形，另外也可以通过图形编辑特性，例如过滤，创建有趣的高度图。

海岛地图的原理

从上面对等高图的阐述，可以知道，地形是真实世界的一个模型，有平原、山脉、河流、悬崖和丘陵等。以抽象角度来看，可以简单地认为地形仅仅是高度上的变化。

例如，一个草原就是一个高度基本为常数的地形（除了可能有一些起伏和山丘外）；一个山区或者鸿沟是高低落差比较大的地形；一条河流就是由一个高地势平原和穿过它的曲线组成，这个曲线比它周围的地形高度稍低。

如图所示，是一系列的高度地图，简单来看，它是一个像素的集合，每个像素都是在灰度上0～255之间变化，0是黑色，255是全白，读者也可以自己绘制高度地图。可以判断，明暗反差越大，地势高低起伏也越大。

在Alchemy3D中，如果不使用高程图，将自动使用PerLin噪音进行高程图进行计算生成。

地图元素图元

要将高度地图转换为场景，只需要读取图片的像素，然后根据像素的值设置平面的高度，最常用的平面是四边形。因为四边形是规则的，可以采用数组方便地统一创建和管理（并且能实现地图的无缝）。四边形由两个三角形组成，多个四边形组成了场景地图。

这里说明一下Alchemy3D地形引擎并不是采用元素图元，而是单个三角形组成网格的形式，做到更精确化的地形坡度。

地形跟踪技术

地形跟踪技术有很多种方法，目前Alchemy3D集成了2种测试方法，1种精确方法。

下面先介绍当前流行的四元平面算法（转自小祥的BLOG http://xfxsworld.cnblogs.com ）：

一：
《Introduction to 3D Game Programming With Directx 9.0》这本书里介绍的，利用向量来算。

 

 1 float  Terrain::GetHeight( float  x,  float  z)
 2 {
 3    //  Translate on xz-plane by the transformation that takes
 4   //  the terrain START point to the origin.
 5  x  =  (( float )_width  /   2.0f )  +  x;
 6  z  =  (( float )_depth  /   2.0f )  -  z;
 7   //  Scale down by the transformation that makes the 
 8   //  cellspacing equal to one.  This is given by 
 9   //  1 / cellspacing since; cellspacing * 1 / cellspacing = 1.
10  x  /=  ( float )_CellSpacing;
11  z  /=  ( float )_CellSpacing;
12   //  From now on, we will interpret our positive z-axis as
13   //  going in the 'down' direction, rather than the 'up' direction.
14   //  This allows to extract the row and column simply by 'flooring'
15   //  x and z:
16   float  col  =  ::floorf(x);
17   float  row  =  ::floorf(z);
18   //  get the heights of the quad we're in:
19   //  
20      //   A   B
21      //   *---*
22      //     | / |
23      //   *---*  
24      //   C   D
25   float  A  =  GetHeightMapEntry(row,   col);
26   float  B  =  GetHeightMapEntry(row,   col + 1 );
27   float  C  =  GetHeightMapEntry(row + 1 , col);
28   float  D  =  GetHeightMapEntry(row + 1 , col + 1 );
29   //
30   //  Find the triangle we are in:
31   //
32   //  Translate by the transformation that takes the upper-left
33   //  corner of the cell we are in to the origin.  Recall that our 
34   //  cellspacing was nomalized to 1.  Thus we have a unit square
35   //  at the origin of our +x -> 'right' and +z -> 'down' system.
36   float  dx  =  x  -  col;
37   float  dz  =  z  -  row;
38   //  Note the below compuations of u and v are unneccessary, we really
39   //  only need the height, but we compute the entire vector to emphasis
40   //  the books discussion.
41   float  height  =   0.0f ;
42   if (dz  <   1.0f   -  dx)   //  upper triangle ABC
43   {
44    float  uy  =  B  -  A;  //  A->B
45    float  vy  =  C  -  A;  //  A->C
46    //  Linearly interpolate on each vector.  The height is the vertex
47    //  height the vectors u and v originate from {A}, plus the heights
48    //  found by interpolating on each vector u and v.
49   height  =  A  +  Lerp( 0.0f , uy, dx)  +  Lerp( 0.0f , vy, dz);
50  }
51   else   //  lower triangle DCB
52   {
53    float  uy  =  C  -  D;  //  D->C
54    float  vy  =  B  -  D;  //  D->B
55    //  Linearly interpolate on each vector.  The height is the vertex
56    //  height the vectors u and v originate from {D}, plus the heights
57    //  found by interpolating on each vector u and v.
58   height  =  D  +  Lerp( 0.0f , uy,  1.0f   -  dx)  +  Lerp( 0.0f , vy,  1.0f   -  dz);
59  }
60   return  height;
61 }
62

 
用到的2个函数

1float Terrain::Lerp(float a, float b, float t)     //一个插值函数
2{
3 return (a - (a*t) + (b*t));
4}
5
6int Terrain::GetHeightMapEntry(int row, int col)         //读取高度函数
7{
8 return _heightmap[row * _numVertsPerRow + col];   // 高度图数据存在_heightmap里
9}

二：
网上找的一个方法
假设你的地形为terrain[][];用下面的函数求出地形上点(x,z);的y值,将人物的高度加上这个y值即可.

 1float GetHeight(GLfloat x, GLfloat z)
 2{ 
 3float h=0;
 4float Xb,Yb;
 5int Xa,Ya;
 6Xa=(int)x;
 7Ya=(int)z;
 8Xb=x-Xa;
 9Yb=z-Ya;
10float a=terrain[Xa][Ya].y;
11float b=terrain[Xa+1][Ya].y;
12float c=terrain[Xa][Ya+1].y;
13float d=terrain[Xa+1][Ya+1].y;
14h=(a*(1-Xb)+b*Xb)*(1-Yb)+(c*(1-Xb)+d*Xb)*Yb;
15return h;
16} 
17

下面是Alchemy3D的算法：

我们知道 ,每个三角形决定一个面,而每个面的多项式是:

ax+by+cz+d=0

其中a,b,c是平面的法向量x,y,z,d为平面的法向量与三角形第一个向量的点积的负数形式.

我们的目的就是求出a,b,c,d,然后把当前x,z代入多项式即可求出高度y.

而要求a,b,c,d关键需要知道平面的法向量,但是三角形我们已经知道,由此我们就很轻易得得到了y值.

这里还有一个问题,如图所示:

高度我们有了,但是方向却不知道,怎么办呢?

其实很简单,只要一步

entity.lookAt( entity.position, normal )