几乎所有的3D游戏都离不开碰撞检测――无论是各物体之间的碰撞检测，还是物体与场景之间的碰撞检测。在真实世界中，你是很自然地不能穿墙而过的，所以很多人在玩各种3D游戏的时候自然而然的忽视了碰撞检测这一过程的存在。然而，碰撞检测的过程是重要的。如果没有它，你在CS中就会毫无遮拦的飞来飞去――如果考虑重力的话，则会一直不停地往下掉，直到符点数溢出（或你受不了这一漫长的过程而离开游戏）为止。碰撞检测是在编程时实现的。不要以为碰撞检测是在显示3D图像的同时由显卡完成的――这是幼稚的看法――现在没有什么硬件能支持碰撞检测。
看了这些后你可能对碰撞检测产生了兴趣，或者你作为一个3D编程爱好者正在寻找碰撞检测的原理和方法，或者已经找了很长时间还没找到（我是不是有点贫:P），那么，就让我们一起来看一种十分有效而又易于理解的算法吧。
这个算法是针对物体与场景之间的碰撞检测的。它要求你的场景是以很多的三角形组成的。目前几乎所有的3D程序的场景或者物体都是由许多三角形组成的，所以这一点不成问题。另外，你需要记录物体在上一帧的位置和当前帧的位置。这也很容易办到。除了这些，就每什么其他的要求了。那么我们来看一下它的原理。
一、原理
首先，根据物体的运动规律或用户的输入计算物体在即将渲染的一帧（当前帧）时的位置（这时还不用考虑碰撞检测的问题）然后，循环遍历场景中每一个三角形。在循环过程中，作如下操作：
1、找到当前三角形所在的平面，我们暂且称之为平面S。沿平面法线方向对它做一个平移d，表示物体和平面之间所能接近的距离。
2、判断物体在上一帧和当前帧时的位置OldPosition、NewPosition与平面S的关系：如果上一帧在平面前，而当前帧在平面后，如下图所示：
则进一步做3。
否则，跳过3、4，做5。
3、因为前后两帧物体在平面的异侧，说明物体穿过了平面S。但这时还不能说物体与三角形发生了碰撞，因为平面是无边界的,还需进一步判断物体是否在三角形三条边范围之内穿过平面S。过三角形的三边，做垂直于三角形的平面PS1,PS2,PS3。并且令它们的法线指向三角形的内部，如下图所示：
为了体现物体和三角形所能接近的最短距离，这三个平面也需要做一个平移L，只不过是沿着其法线负方向：
我们将依靠这三个平面来判断物体是否是在三角形三边所界定的范围之内穿过平面S的。但是，如果三角形有很尖利的锐角，就会使其界定的区域过大，如figure4中所示。所以我们需要另外三个与它们平行的平面PS4,PS5,PS6 来削去产生的锐角(figure5)。产生这三个平面很容易，只需将PS1、PS2、PS3分别向它们的法线正方向平移到与之相对的顶点，再加上L。
现在，判断物体位置是否在这六个平面之内，如果是，则做4，否则，做5。
4、我们已经能够确定物体与当前的三角形发生了碰撞，这时，修正当前帧的位置NewPosition，使物体的运动沿着与平面S平行的方向。
5、我们已经能够确定物体与当前三角形没有发生碰撞。使下一三角形成为当前三角形，回到1。
当所有的三角形都遍历了一次之后，物体的位置NewPosition就是经过碰撞检测并修正了之后的。以该位置渲染物体和场景，并在下一帧之前，更新旧的位置为当前帧的位置（OldPosition = NewPosition）。
总之，该算法的原理就是：给出一个三角形――判断物体是否穿过了三角形所在的面――再判断物体是否是在三角型内部穿过的。下面我们来看一看它的具体实现。
二、具体实现
在具体的实现中，我们可能会遇到下面这些问题。
首先，如何得到三角形所在的平面呢？一个平面可以由法向量和它与原点的距离来表示，假设我们有一个三角形ABC，其所在平面为 S ，如下图所示：
其顶点位置为三个三维向量a,b,c。我们首先得到三角形的法向量 N：(下面的vector 表示三维向量，float表示浮点型标量)
vector v1 = b - a '由 a 指向 b 的边向量
vector v2 = c - a '由 a 指向 c 的边向量。
vector N = Normalize(v1 X v2) ' X代表叉乘，注意叉乘是有顺序的，如果v1和v2互换，结果向量将会反向。Normalize表示将所得结果单位化。所得的N就是三角形的法向量
vector S.N = N '三角形的法向量也就是平面 S 的法向量
然后，我们计算该平面与原点的距离 S.D：
float S.D = N * a ' *代表点乘，计算结果为三角形顶点a到法线S.N上的投影的长度，即距离S.D，为一标量。
有了法向量和距离，就可以表示一个平面了。如果想要对平面进行平移，只需修改 S.D 的值。
那么，怎样判断物体在平面的那一边呢？只需要比较物体位置在平面法向量上的投影长度和平面的 D 值就行了。假定我们的物体位置用3维向量 p 表示
float dp = S.N * p '点乘，dp为物体位置在平面 S 法线 N 上的投影长度，为一标量。
if (dp - S.D)0 ，在平面 S 正面。
if (dp - S.D)
还有一个问题，就是怎样得到上文中提到的平面PS1,PS2和PS3。这个其实也不难，可以由下面的方法得到（以PS1为例）：
vector PS1.N = Normalize(S.N X v1) '平面 S 法向 N 与 三角形边向量v1叉积并单位化，结果为PS1.N代表PS1的法向量。
float PS1.D = PS1.N * a - L'三角形顶点 a 在PS1的法向量上的投影长度，再减去 L
与之对应的平面PS4可以随之求得：
vector PS4.N = -PS1.N '两个平面的法向相对
float PS4.D = PS1.N * c - L '用顶点c点乘PS4的法向量，再减去 L
（#_# 这些公式真是令人头痛，我已经尽力想把它们说得清楚一些了。）
下面让我们进入实质性的阶段――代码的编写。
三、编写代码
还记得前不久在本站出现的一篇有关DirectX Mesh优化的文章吗？那里用到了一个非常简陋的所谓的“第一人称射击”游戏――“没有碰撞检测，没有光照，没有LightMap，没有BSP树，没有敌人（也就没有AI），没有武器：天那，什么也没有！”好吧，现在就让我们来给它加上碰撞检测。
下面是我后来向该程序中加入的三个自定义函数：Collision()、PreCheckCollision()和CheckCollision()。其中，Collision()函数完成整个的碰撞检测过程。在其内部调用了另外两个函数。PreCheckCollision()主要判断物体位置（在该程序中就是玩家的位置）是否穿过了某个平面。CheckCollision()函数进一步判断穿过位置是否在三角形内部。
//=====================================================
// 函数名称:Collision()
// 函数功能: 完成碰撞检测
// 备注:使用优化后的场景网格模型
// 参数说明：
// Player_State * lpPs:Player_State是代表玩家状态的
//
自定义结构。其中的vnewPos、
//
vOldPos成员变量将被用于碰撞检测。
//
函数接受该结构的一个指针lpPs。
// LevelMap * lpMap
:LevelMap是代表场景的自定义结构。
//
其中的m_pMesh成员变量是一个
//
ID3DXMESH接口指针，保存地图的网
//
格信息。
//-----------------------------------------------------
HRESULT Collision(Player_State * lpPs,LevelMap * lpMap)
{
WORD * pIndexData;
CustomVertex * pVertexData;
D3DXVECTOR3 vNormal,vP1,vP2,vP3;
FLOAT fdistance;
if(lpMap == NULL)
return E_FAIL;
if(lpMap-m_pMesh == NULL)
return E_FAIL;
if(lpPs == NULL)
return E_FAIL;
if(lpMap-m_dwNumIndices == 0)
return E_FAIL;
if(lpMap-m_dwNumVertices == 0)
return E_FAIL;
在DirectX 8 Graphics中，场景的网格模型顶点缓冲和索引缓冲组成。顶点缓冲保存了所有的顶点的信息，而索引缓冲中的每三个元素代表一个三角形，这些元素的值是该三角形的三个顶点在顶点缓冲中的索引号。我们可以由此获得三角形的三个顶点的位置。下面的代码锁定网格模型中的顶点和索引缓冲，并得到指向它们的指针。
lpMap-m_pMesh-LockIndexBuffer(D3DLOCK_READONLY,(BYTE**)&pIndexData);
lpMap-m_pMesh-LockVertexBuffer(D3DLOCK_READONLY,(BYTE**)&pVertexData);
然后，遍历网格的每一个三角形：
for(WORD i = 0;i m_dwNumIndices; i+=3)
{
WORD a = pIndexData[i+0]; //a:三角形的第一个顶点的索引
WORD b = pIndexData[i+1]; //b:三角形的第二个顶点的索引
WORD c = pIndexData[i+2]; //c:三角形的第三个顶点的索引
D3DXVECTOR3 v1 = pVertexData[b].p - pVertexData[a].p;
//v1:边
