标签: C++, 代码, 实例, 游戏编程, 碰撞检测, 3D
几乎所有的3D游戏都离不开碰撞检测——无论是各物体之间的碰撞检测，还是物体与场景之间的碰撞检测。在真实世界中，你是很自然地不能穿墙而过的，所以很多人在玩各种3D游戏的时候自然而然的忽视了碰撞检测这一过程的存在。然而，碰撞检测的过程是重要的。如果没有它，你在CS中就会毫无遮拦的飞来飞去——如果考虑重力的话，则会一直不停地往下掉，直到符点数溢出（或你受不了这一漫长的过程而离开游戏）为止。碰撞检测是在编程时实现的。不要以为碰撞检测是在显示3D图像的同时由显卡完成的——这是幼稚的看法——现在没有什么硬件能支持碰撞检测。
看了这些后你可能对碰撞检测产生了兴趣，或者你作为一个3D编程爱好者正在寻找碰撞检测的原理和方法，或者已经找了很长时间还没找到（我是不是有点贫:P），那么，就让我们一起来看一种十分有效而又易于理解的算法吧。
这个算法是针对物体与场景之间的碰撞检测的。它要求你的场景是以很多的三角形组成的。目前几乎所有的3D程序的场景或者物体都是由许多三角形组成的，所以这一点不成问题。另外，你需要记录物体在上一帧的位置和当前帧的位置。这也很容易办到。除了这些，就每什么其他的要求了。那么我们来看一下它的原理。
一、原理
首先，根据物体的运动规律或用户的输入计算物体在即将渲染的一帧（当前帧）时的位置（这时还不用考虑碰撞检测的问题）然后，循环遍历场景中每一个三角形。在循环过程中，作如下操作：
1、找到当前三角形所在的平面，我们暂且称之为平面S。沿平面法线方向对它做一个平移d，表示物体和平面之间所能接近的距离。
2、判断物体在上一帧和当前帧时的位置OldPosition、NewPosition与平面S的关系：如果上一帧在平面前，而当前帧在平面后，如下图所示：
null
则进一步做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）。
总之，该算法的原理就是：给出一个三角形——判断物体是否穿过了三角形所在的面——再判断物体是否是在三角型内部穿过的。下面我们来看一看它的具体实现。