学习3D游戏编程有一段时间了,但一只以来都很少发过文章,一是觉得自己的水平太菜,二是很多想法都不是来源于自己.最近在写一个简单的游戏引擎，想把它拿出来和大家一起分享。希望高手给予指导。下面将我在游戏引擎中用到的地形生成与分割算法发表出来。与大家一起分享。
在一开始时，游戏引擎中采用了《direct9.0x3D游戏编程基础》中的地形生成算法来实现，该算法没有采用地形分割，显示64X64高度图的地形时，游戏运行得很流畅，但当地形的高度图增加256X256时，游戏的帧频下降了很多。为了提高游戏运行流畅度，我在引擎采用了基于四叉树的地形分割。
首先，我们可以选择y=0这个平面，将地形划分为等大的四个区域，然后对划分出来的四个子区域进行递归划分，每次划分都选择交于区域中心点并且互相垂直的两个平面作为划分面，直到每个子区域的大小为某个特定的值时不不规则划分。例如对于图1所示8*8大小的地形(高度图为9*9)块，经过划分之后如图2所示：
图1
图2
由图可知，只有高度图数据满足大小2n+1的正方形这个条件，我们才可能对地形进行均匀划分。我们可以把划分结果用一棵树来表述，由于每次划分之后产生四个子节点，因此这棵树叫四叉树。那么，这棵树中应该存储那些信息呢？首先对于每个节点，应该指定这个节点所代表的地形的区域范围。并不是把地形网格中实际的顶点放入树中，而是要在树中说明这个节点覆盖了地形的那些区域。因此一个子节点应该有一个边界RECT变量（包括地形的左上角点和右下角点）。另外设定一个标记，标记该子节点是否为叶子结点（m_bIsLeaves），如果不是,那么该节点拥有四个指向子节点的指针，如果是叶子结点，那么该节点有一个指向地形的指针。设定四叉树的数据结构如下
class QuadTree{ //用于管理地形的四叉树
public:
bool iSLeaf; //是否为叶子
RECT Bound; //保存的是地形边界信息
union{
QuadTree* pLeaves[4]; //四个叶子结点
CMiniTerrain* pTerrain; //地形结点,由高度图生成
} UN;
};
分割算法如下：
Void Partition(QuadTree* root)
{
if(root->Bound.left – root->m_Bound.right > Delta)//如果地形的宽度大于分割值，则分割
//新建四个叶子结点
QuadTree* pLeaves[4] = { new QuadTree,……….};
SetSubBound……//设置叶子结点的边界
for(i = 0 to 3)
setLeaves; //设置四个叶子结点
Partition(pPleaves[i]); //递归分割
else //已经分割到最小,生成地形
Set HeightMap…..
新建地形……..
}
上面仅给出了伪代码，实际在引擎中实现地形分割时，还有一些小问题，小地形小快的边缘处，还有明显的裂痕。由于代码写得太菜，暂时不想发布出来。等游戏引擎完成后，再将它一并打包发出来，与大家一起分享。