3D游戏如何检测碰撞？
为了创建一个理想的碰撞检测程序，我们必须开始规划和创建它的框架，同时为游戏开发图形管道。在项目的最后添加碰撞检测是相当困难的。试图在开发周期结束时创建一个快速的碰撞检测可能会毁了整个游戏，因为我们无法让它高效地运行。在一个好的游戏引擎中，碰撞检测应该是准确、有效和非常快的。这些要求意味着碰撞检测将与场景的多边形管理管道密切相关。这是否也意味着穷举法行不通？在当今的3D游戏中，每帧处理的数据量可能会导致网格断裂。当你还在检测一个物体的每个多边形是否与场景中的其他多边形发生碰撞的时候，时间已经过去了。
先说基本的游戏引擎循环(清单1)。快速浏览这些代码，获得碰撞检测的相关策略。我们假设碰撞没有发生，然后更新物体的位置。如果发现有碰撞，我们会把物体移回到原来的位置，不允许它越界(或者破坏物体或者采取一些预防措施)。但是，这个假设太简单了，因为我们无法知道物体的原始位置是否仍然有效。你必须为这种情况设计一个方案(否则你可能会体验到崩溃或者被子弹击中的感觉？就是上面给的例子)。如果你是一个热情的玩家，你可能已经注意到，在一些游戏中，当你靠近墙壁并试图穿过它时，相机开始抖动。你正在经历的是把主角搬回原来位置的情况。振动是由于取了较大的时间片而引起的。
清单1。极度简化的游戏循环
while(1){
process_input()。
update _ objects()；
render _ world()；
}
update_objects(){
对于(每个对象)
save_old_position()。
计算新对象位置
{基于速度加速度。等等。}
if (collide_with_other_objects())
new_object_position =旧_ position()；
{或者，如果被破坏的对象移除它，等等。}
图1。时间梯度和碰撞测试。
但是我们的方法是有缺陷的，我们忘记了在等式中加入时间。图1告诉我们，时间太重要了，不能忘记。即使物体在t1或t2处没有碰撞，它仍可能在T (t1)处越过边界
我们可以把时间看作第四维，在四维空间中进行一切操作。不过这可能会让操作变得非常复杂，所以我们会避开这些。我们还可以从t1和t2处的对象开始创建一个实体，然后用它与墙进行测试(见图2)。
一个简单的方法是创建一个凸包来覆盖不同时间的两个对象。这种方法的低效可能会明显降低你的游戏速度。要创建凸壳，最好在实体周围创建一个边界框。我们会在学习完其他技术后再回来讨论这个问题。
另一种更容易实现但不太精确的方法是将给定的时间段分成两部分，然后测试时间点之间的相交关系。我们也可以依次递归确定每个段落的时间中点。这种方法比前一种方法快得多，但不能保证所有碰撞都能被捕获。
另一个隐藏的问题是如何实现collide_with_other_objects()的方法？即判断一个物体是否与场景中的其他物体相交。如果场景中有许多对象，这种方法可能会非常昂贵。如果我们要判断场景中的每个对象是否与其他对象相交，我们将不得不进行两次左右的比较。所以比较的次数会是n的平方？(或表示为O(N2))。但是我们可以用几种方法避免比较O(N2)对。比如我们可以把场景中的物体分为静态(撞击物体)和动态(碰撞物体？即使其速度为0)。就好像房间里的墙是碰撞物体，扔向墙的小球就是碰撞物体。我们可以创建两个独立的树(每种类型的对象一个),然后测试对象可能发生碰撞的那些树。我们甚至可以对环境做个约定，让一些碰撞的物体不碰撞？例如，我们不需要在两颗子弹之间进行判断。现在，在我们继续之前，我们可以说这个过程已经变得更加清晰了。另一种减少场景中成对比较的方法是构建八叉树。这超出了本文的范围。你可以在空间数据结构:四叉树，八叉树和其他层次方法的更多信息部分阅读更多关于八叉树的信息。现在让我们来看看基于门户的引擎，以理解为什么在这种引擎中提到碰撞检测是如此痛苦。
门户引擎和对象-对象碰撞
基于门户的引擎将场景或世界分成更小的凸方形区域。凸方形区域适用于图形管道，因为它们可以避免重绘。不幸的是，对于碰撞检测，凸正方形区域会给我们带来一些困难。在我最近的一些测试中，一台发动机平均有大约400到500个凸方形区域。当然，这个数字会随着不同的引擎而变化，因为不同的引擎使用不同的多边形技术。多边形的数量会随着场景的大小而变化。
判断一个物体的多边形是否穿过场景中的多边形，可能会导致计算量很大。最简单的碰撞检测方法之一是用球体近似表示一个物体或物体的一部分，然后判断这些包围球是否相交。这样，我们只需要测试两个球体的中心之间的距离是否小于它们的半径(这意味着碰撞)。如果比较中心点距离的平方和半径的平方就更好了，这样在计算距离的时候就可以排除平方根运算差的情况。然而，简单的操作也会导致精度下降(见图3)。
图3。在球体与球体相交的情况下，例程可能会报告碰撞已经发生，而实际上并没有发生。
但我们只是把这种不精确的方法作为我们的第一步。我们用一个大球体来代表整个物体，然后检查它是否与其他球体相交。如果检测到碰撞，那么我们需要进一步提高精确度。我们可以把一个大球体分成一系列小球体，检查每个小球体是否有碰撞。我们不断地划分和检查，直到得到满意的近似值。分层和划分的基本思想是，要尽力达到适合自己需求的理想状况。
图4。球体细分。
用一个球体来近似表示一个物体，需要的计算量很小，但是游戏中的大部分物体都是方形的，所以我们要用一个方形的盒子来表示物体。开发人员一直在使用包围盒和这种递归的快速方法来加速光线跟踪算法。？补习学校？你在做什么?一瞬间，ABB(轴对齐边界框)出现了。图5显示了一个AABB及其对象。图5。一个对象及其AABB。
轴对齐不仅意味着长方体平行于世界坐标轴，还意味着长方体的每个面都垂直于坐标轴。这样的基本信息可以减少换箱时的操作次数。AABBs在当今很多游戏中都有应用，开发者经常把它作为模型的包围盒。再次指出，提高精度也会降低速度。因为AABBs永远是平行于坐标思维的，所以旋转物体的时候不能简单的旋转AABBs——每一帧都要重新计算。如果知道每个对象的内容，这个计算并不难，也不会拖慢游戏。然而，我们仍然面临着准确性的问题。假设我们有一个三维细长刚性直杆，我们想在动画的每一帧重建它的AABB。我们可以看到，每一帧中的包围盒是不同的，精度也会相应变化。