几乎所有的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，只不过是沿着其法线负方向：