碰撞检测

碰撞检测是检测两个或多个物体相交的计算问题。碰撞检测是计算几何学的一个经典问题，在各种计算领域都有应用，主要是在计算机图形学、计算机游戏、计算机模拟、机器人和计算物理学中。碰撞检测算法可以分为对2D和3D对象的操作。

物理模拟器的不同之处在于它们对碰撞的反应方式。有些使用材料的柔软度来计算力，这将在以下时间步长中解决碰撞，就像在现实中一样。由于某些材料的柔软度较低，这会占用大量CPU。一些模拟器通过线性插值估计碰撞时间，回滚模拟，并通过更抽象的守恒定律方法计算碰撞。

一些迭代线性插值（牛顿法）以比模拟的其余部分更高的精度计算碰撞时间。碰撞检测利用时间一致性来允许更精细的时间步长，而不会增加CPU需求，例如在空中交通管制中。

在非弹性碰撞之后，可能会出现滑动和静止的特殊状态，例如，开放动力学引擎使用约束来模拟它们。约束避免了惯性，从而避免了不稳定。通过场景图实现休息避免了漂移。

换句话说，物理模拟器通常以两种方式运行，其中碰撞是后验（碰撞发生后）或先验（碰撞发生前）检测到的。除了后验和先验的区别之外，几乎所有现代碰撞检测算法都分为算法层次结构。通常使用术语“离散”和“连续”而不是后验和先验。

在后验情况下，物理模拟前进一小步，然后检查是否有任何对象相交或明显被认为相交。在每个模拟步骤中，都会创建一个包含所有相交物体的列表，并且这些物体的位置和轨迹被“固定”以解决碰撞问题。这种方法被称为后验方法，因为它通常会错过碰撞的实际瞬间，并且只在碰撞实际发生后才捕获它。

在先验方法中，有一种碰撞检测算法，它将能够非常精确地预测物理物体的轨迹。碰撞的瞬间以高精度计算，并且物理身体从未真正相互渗透。这被称为先验，因为碰撞检测算法在更新物理物体的配置之前计算碰撞的瞬间。

后验方法的主要优点如下。在这种情况下，碰撞检测算法不需要知道无数的物理变量；一个简单的物理物体列表被提供给算法，程序返回一个相交物体的列表。碰撞检测算法不需要了解摩擦、弹性碰撞，或者更糟的是，非弹性碰撞和变形体。此外，后验算法实际上比先验算法简单一维。一个先验算法必须处理的时间的变量，它是从缺席的后验问题。

另一方面，后验算法会在“修复”步骤中引起问题，需要更正交叉点（物理上不正确）。此外，如果离散步长太大，碰撞可能无法检测到，如果一个物体足够快或足够小，就会导致它穿过另一个物体。

先验算法的好处是增加了保真度和稳定性。很难（但并非完全不可能）将物理模拟与碰撞检测算法分开。然而，除了最简单的情况外，提前确定两个物体何时碰撞（给定一些初始数据）的问题没有封闭形式的解决方案——通常涉及数值求根。

有些物体处于静止接触状态，即碰撞，但既不会弹开，也不会相互穿透，例如放在桌子上的花瓶。在所有情况下，静止接触都需要特殊处理：如果两个对象碰撞（后验）或滑动（先验）并且它们的相对运动低于阈值，则摩擦变为静摩擦并且两个对象都排列在场景图的同一分支中。

对多个对象进行碰撞检测的明显方法非常缓慢。对照每个其他对象检查每个对象当然是可行的，但是当对象数量非常大时，效率太低而无法使用。以明显的方式检查具有复杂几何形状的对象，通过检查每个面与彼此的面，本身非常慢。因此，已经进行了大量的研究来加速这个问题。

电子游戏必须在多个任务之间分配非常有限的计算时间。尽管存在这种资源限制，并且使用了相对原始的碰撞检测算法，但程序员已经能够创建可信的（如果不准确的话）用于游戏的系统。

长期以来，电子游戏要处理的对象数量非常有限，因此检查所有对不是问题。在二维游戏中，在某些情况下，硬件能够有效地检测和报告屏幕上精灵之间的重叠像素。在其他情况下，简单地平铺屏幕并将每个精灵绑定到它重叠的平铺中就可以提供足够的修剪，并且对于成对检查，使用称为命中框的边界矩形或圆形被认为足够准确。

三维游戏使用空间划分方法，长期以来，每个实际3D对象使用一个或几个球体进行成对检查。除了在尝试密切模拟现实的游戏中，精确检查非常罕见。即便如此，也不一定在所有情况下都使用精确检查。

因为游戏不需要模仿实际的物理，所以稳定性不是什么大问题。几乎所有游戏都使用后验碰撞检测，并且碰撞通常使用非常简单的规则来解决。例如，如果一个角色被嵌入墙壁中，他们可能会被简单地移回他们最后一个已知的好位置。有些游戏会计算角色在嵌入墙壁之前可以移动的距离，并且只允许他们移动那么远。

在许多视频游戏的情况下，通过一个点来逼近角色就足以实现与环境的碰撞检测。在这种情况下，二元空间分区树提供了一种可行、高效且简单的算法来检查一个点是否嵌入到风景中。当角色在地面上奔跑时，这样的数据结构也可以用来优雅地处理“休息位置”的情况。角色之间的碰撞，以及与射弹和危险的碰撞，是分开处理的。

一个强大的模拟器会以合理的方式对任何输入做出反应。例如，如果我们想象一个高速赛车视频游戏，从一个模拟步骤到下一个模拟步骤，可以想象汽车会沿着赛道前进很长一段距离。如果赛道上有一个较浅的障碍物（比如砖墙），赛车完全跳过它也不是完全不可能的，这是非常不可取的。在其他情况下，后验算法要求的“修复”没有正确实现，导致错误可以将角色困在墙壁中或允许他们穿过墙壁并陷入无尽的虚空，那里可能有也可能没有致命的无底洞坑，有时也称为“黑色地狱”、“蓝色地狱”或“绿色地狱”，具体取决于主要颜色。这些是碰撞检测和物理模拟系统失败的标志。BigRigs:OvertheRoadRacing是一个臭名昭著的例子，游戏的碰撞检测系统失败或可能丢失。