自从计算机游戏出现以来，程序员就不断地想办法来更精确地模拟现实世界。就拿乒乓游戏为例子（译者：Pong―被誉为电子游戏的祖先，有幸见过一次：），能见到祖先做的游戏感觉真是爽啊，想看的可以到FTP上下载“地球故事”就可以看到了：），游戏中有一个象征性的小方块（球）和两支拍子，游戏者需要在恰当的时间将拍子移动到恰当的地点，将小球反弹回去。这个基本操作的背后（以现在的标准来看）就是最原初的碰撞检测了。今天的游戏比“乒乓”要高级得多，并且基本上是基于3D的。3D游戏中的碰撞检测比“乒乓”游戏里的要更加难实现。玩一些早期模拟飞行游戏的体验向我们展现出糟糕的碰撞检测是如何毁灭一个游戏的。当穿过一座大山的尖顶的时候仍然活着，感觉很不真实。即便是现在的一些游戏也还是有碰撞上的问题，许多玩家曾经失望地看着他们喜爱的英雄或女英雄的部分身体穿进了墙里。甚至更糟的是，许多玩家都有过这样糟糕的体验，就是被那些离得很远的子弹或火箭击中。因为游戏者们要求提升真实性，我们开发者就不得不绞尽脑汁想办法让我们的游戏世界尽可能地接近现实世界。
阅读这篇文章前首先假设你对与碰撞检测相关的几何和数学知识已经有了基本的了解。在文章的最后，我将提供一些这方面的参考资料，以免你对它们感觉有点生疏。另外我还假设你已经读过 Jeff Lander 的图形专栏里关于碰撞检测文章（“Crashing into the New Year,” ; “When Two Hearts Collide,”;和 “Collision Response: Bouncy, Trouncy, Fun,”）。我将首先进行一个大概的描述，然后快速地切入到核心内容里，通过这两步从上至下地深入到碰撞检测中。我将讨论两种类型的图形引擎中的碰撞检测：基于 portal 的和基于 BSP 的。每种引擎中多边形的组织各不相同，因此在 world-object 型的碰撞检测上存在很大的差别。而object-object 型的碰撞检测绝大多数地方在上述两种引擎里的是一样的，主要看你是如何实现的了。当我们接触到多边形的碰撞检测时，我们还会实验如何将其扩展到我们学过的凸型物体上。
为了创建一个理想的碰撞检测程序，我们不得不在开发一个游戏的的图形管道的同时就开始计划并创建它的框架。在项目的最后加入碰撞检测是相当困难的。想在开发周期的末尾创建快速的碰撞检测将很有可能会使整个游戏被毁掉，因为我们不可能使它能高效地运行。在好的游戏引擎中，碰撞检测应该是精确、有效并且十分快速的。这些要求意味着碰撞检测将要与场景的多边形管理管道紧紧地联系起来。这也意味着穷举法将无法工作??今天的3D游戏中每帧处理的数据量很可能导致打格，当你还在检测一个物体的各多边形是否与场景中的其它多边形碰撞时，时间已经过去了。
让我们从基本的游戏引擎循环开始吧（列表1）。快速浏览这些代码来得到碰撞检测的相关策略。我们先假设碰撞没有发生，然后更新物体的位置，如果发现发生了碰撞，我们将把物体移回原来的位置不允许它穿越边界（或将物体销毁或执行一些预防措施）。然而，这个假设太过简单因为我们无法得知物体原来的位置是否仍然有效。你必须为这种情况设计一个方案（否则你可能会体验到坠机或被子弹击中的感觉??就是前面举的例子）。如果你是一个热心的玩家，你可能已经注意到了在一些游戏当中，当你挨着墙壁并试图穿过去的时候，摄像机就开始震动。你正经历的就是将主角移回原位的情况。震动是因为取了较大的时间片引起的。
Listing 1. Extremely Simplified Game Loop
while(1){
process_input();
update_objects();
render_world();
}
update_objects(){
for (each_object)
save_old_position();
calc new_object_position
{based on velocity accel. etc.}
if (collide_with_other_objects())
new_object_position = old_position();
{or if destroyed object remove it etc.}
Figure 1. Time gradient and collision tests.
但是我们的方法有缺陷，我们忘了在等式中加入时间。图1告诉我们时间太重要了不能忘了它。即便物体在 t1 或 t2 时刻没有发生碰撞，它仍有可能在 t 时刻穿过边界（t1
我们可以把时间看成是第四维并将所有运算在4维空间中进行。然而这可能会让运算变得十分复杂，所以我们会避开这些。我们还可以创建一个以 t1、t2时刻的物体为起始点的实心体，然后用它来与墙进行测试（见图2）
Figure 2. Solid created from the space that an object spans over a given time frame.
一个简单的方法就是创建一个凸壳来罩住两个不同时刻的物体。这种方法效率低下可能会明显地降低你的游戏速度。以其创建一个凸壳，还不如创建一个围绕实心体的包围盒。我们学习其它的技术后再回来讨论这个问题。
有另一种比较容易执行但精度较低的方法，就是把给定的时间段分为两分，然后测试时间中点的相交关系。我们还可以递归地依次测定各段的时间中点。这个方法比先前的方法要快得多，但不能保证能捕捉到所有的碰撞情况。
另一个暗藏着的问题是collide_with_other_objects()方法的实现??即判断一个物体是否与场景中的其它物体相交。如果场景中有很多的物体，这个方法可能消耗很大。如果要判断各物体与场景中其它物体是否相交，我们将不得不进行大概N选2次比较。因此比较次数会是N的平方次?（或表示成O(N2)）。但我们可以用几种方法来避免进行O(N2)对的比较。举个例子，我们可以把场景中的物体分成静态的（被撞物）和动态的（碰撞物??即使它的速度为0也行）。就好象房间中的墙壁是被撞物，而一个扔向墙壁的小球是碰撞物。我们可以创建两棵独立的树（每一棵对应一类物体），然后测试那些物体可能会碰撞的树。我们甚至可以对环境进行约定让一些碰撞物之间不发生碰撞??比如我们不需要在两颗子弹之间进行判断。现在在继续之前，（经过改进之后）我们可以说处理过程变得更加清晰了。（另一个减少场景中成对的比较的方法就是建立八叉树。这已经超出了这篇文章的范围，你可以在Spatial Data Structures: Quadtree, Octrees and Other Hierarchical Methods文章中的For Further Info一节里读到更多关于八叉的信息）。现在让我们来看一下基于 Portal 引擎，了解为什么在这类引擎中一提到碰撞检测就会那么痛苦。
Portal引擎和Object-Object型碰撞
基于 Portal 的引擎把场景或世界分割成较小的凸方形区域。凸方形区域很适合图形管道因为它们能避免重绘现象。不幸的是，对碰撞检测来说，凸方形区域会给我们带来一些困难。在我最近的一些测试中，一个引擎中平均大约有400到500个凸方形区域。当然，这个数字会随着不同的引擎而有所变化，因为不同的引擎使用不同的多边形技术。而且多边形的数目也会因场景的大小而有所不同。
判断一个物体的多边形是否穿过了场景中的多边形产生的运算量可能会很大。一个最简单的碰撞检测法就是用球形来近似地表示物体或物体的一部分，然后再判断这些包围球是否相交。这样我们仅仅需要测试两个球体中心的距离是否小于它们的半径合（这表示发生了碰撞）。如果我们是用中心点距离的平方和半径合的平方进行比较，那更好，这样我们可以在计算距离时除去拙劣的开方运算。但是，简单的运算也导致了精确度的降低（见图3）。
Figure 3. In a sphere-sphere intersection, the routine may report that collision has occurred when it really hasn’t.
但我们仅仅是将这个不太精确的方法做为我们的第一步。我们用一个大的球体代表整个对象，然后检测它是否和其它的球体相交。如果检测到发生了碰撞，那么我们就要进一步提高精度，我们可以将大的球体分割成一系列小的球体，并检查与各小球体是否发生碰撞。我们不断地分割检查直到得到满意的近似值为止。分层并分割的基本思想就是我们要尽可能达到适合需要的理想的情况。
Figure 4. Sphere subdivision.
用球体去近似地代表物体运算量很小，但在游戏中的大多数物体是方的，我们应该用方盒来代表物体。开发者一直用包围盒和这种递归的快速方法来加速光线追踪算法。在实际中，这些算法已经以八叉和AABB（axis-aligned bounding boxes）的方式出现了。图5展示了一个AABB和它里面的物体。
Figure 5. An object and its AABB.
坐标轴平行（“Axis-aligned”）不仅指盒体与世界坐标轴平行，同时也指盒体的每个面都和一条坐标轴垂直。这样一个基本信息就能减少转换盒体时操作的次数。AABBs 在当今的许多游戏中都得到了应用，开发者经常用它们作为模型的包围盒。再次指出，提高精度的同时也会降低速度。因为 AABBs 总是与坐标思平行，我们不能在旋转物体的时候简单地旋转 AABBs --- 它们应该在每一帧都重新计算过。如果我们知道每个对象的内容，这个计算就不算困难并不会降低游戏的速度。 然而，我们还面临着精度的问题。假如我们有一个3D的细长刚性直棒，并且要在每一帧动画中都重建它的AABB。我们可以看到每一帧中的包围盒的都不一样而且精度也会随之改变。
