c++ - 线性插值和对象碰撞

Question

我有一个使用 AABB 测试来检测对象碰撞的物理引擎和一个不使用线性插值的动画系统。正因为如此，我的碰撞有时会出现不规律的行为，尤其是在高速时。这是我系统中一个明显的问题......

为了演示，假设我们的动画系统中的一帧持续 1 秒，我们在第 0 帧给出以下场景。

在第 1 帧，将不会检测到对象的碰撞，因为 c1 将在下一次平局时经过 c2。

虽然我没有使用它，但我对线性插值的工作原理有一点了解，因为我在这个项目中在不同的上下文中使用了线性外插。我想知道线性插值是否可以解决我遇到的问题，或者我是否还需要其他方法。

我的一部分人对如何在动画上下文中使用线性插值感到困惑。这个想法是我们可以在低帧率下实现流畅的动画。在上述场景中，我们不能简单地将 c1 设置为在第 1 帧中以 x=3 为中心。实际上，它们会在第 0 帧和第 1 帧之间发生碰撞。线性插值是否会自动处理这一点并允许精确的 AABB测试？如果没有，它将解决什么问题以及我应该研究哪些其他方法来实现平滑和精确的碰撞检测和动画？

标签： c++animationmfcgame-physicslinear-interpolation

Answer 1

您遇到的现象称为隧道效应，是离散碰撞检测架构固有的问题。您认为线性插值可能与解决方案有关是正确的，因为它可以让您在误差范围内（通常）预测帧之间对象的路径，但这只是其中的一部分更大的解决方案。我见过的与这些类型的解决方案相关的术语是“连续碰撞检测”。这个话题很大而且很复杂，有一些书讨论它，比如实时碰撞检测和其他在线资源。

所以回答你的问题：不，线性插值本身并不能解决你的问题*。除非你只处理圆圈或球体。

开始思考什么

解决方案的外观和行为方式取决于您的设计决策，并且通常很大。所以只是指向解的方向，连续碰撞检测的基本思想是弄清楚：碰撞发生在早帧和晚帧之间的距离，以及此时的两个物体在什么位置和旋转观点。然后，您必须计算对象在稍后的帧时间将处于的配置以响应此。除了二维圆之外，解决这些问题的事情变得非常有趣。

我还没有实现这一点，但我已经看到描述了一个解决方案，您可以在帧之间向前移动两个候选者，通过线性插值推进它们的位置，通过球面线性插值推进它们的方向，并使用离散算法检查它们是否相交（吉尔伯特-Johnson-Keerthi 算法）。从这里您继续应用离散算法来获得最小的穿透深度（扩展多面体算法）并将该深度和帧之间的剩余时间传递给求解器，以获取对象在以后的帧时间中的外观。这没有给出分析答案，但我不知道广义 2 或 3D 案例的分析答案。

如果您不想走这条路，那么与复杂性作斗争的最佳武器就是假设：如果您可以假设您的高速物体可以表示为一个点，那么事情会变得更容易，如果您可以假设物体的方向没关系（圆圈，球体）事情变得更容易，而且它一直在进行。这个话题非常有趣，我仍在学习它，但它提供了我编程期间最令人满意的一些时刻。我希望这些想法也能让你走上这条道路。

编辑：由于您指定您正在玩台球游戏。

首先，我们将检查是否需要离散或连续

• 在这个游戏中可以接受任何数量的隧道吗？不是在台球没有。
• 我们将看到隧道的速度是多少？使用 0.0285m 的球半径（标准美式）和 0.01s 的物理步长，我们得到 2.85m/s 作为碰撞开始产生不良响应的最小速度。我不熟悉台球的速度，但感觉这个数字太低了。

因此，仅检查每一帧是否有两个球相交是不够的，但我们不需要完全连续。如果我们使用插值细分每一帧，我们可以增加创建错误行为所需的速度：使用 2 个细分，我们得到 5.7m/s，这仍然很低；3 细分给我们 8.55m/s，这似乎是合理的；4 给我们 11.4m/s 的速度，感觉比我想象的台球移动要高。那么我们如何做到这一点呢？

使用线性插值进行帧细分的离散碰撞

使用细分很昂贵，因此值得花时间进行候选检测，以便仅在需要时使用它。这是一堆有趣的解决方案的另一个问题，不幸的是超出了问题的范围。

所以你有两个候选圆圈，它们很可能会在当前帧和下一帧之间发生碰撞。所以在伪代码中，算法看起来像：

dt = 0.01
subdivisions = 4
circle1.next_position = circle1.position + (circle1.velocity * dt)
circle2.next_position = circle2.position + (circle2.velocity * dt)
for i from 0 to subdivisions:
   temp_c1.position = interpolate(circle1.position, circle1.next_position, (i + 1) / subdivisions)
   temp_c2.position = interpolate(circle2.position, circle2.next_position, (i + 1) / subdivisions)
   if intersecting(temp_c1, temp_c2):
      intersection confirmed
no intersection

插值签名在哪里interpolate(start, end, alpha)

所以在这里你有插值被用来沿着他们在当前帧和下一帧之间的路径“移动”圆圈。在确定的交叉点上，您可以获得穿透深度并将增量时间（dt / 细分）、两个圆、穿透深度和碰撞点传递给确定它们应如何响应碰撞的分辨率步骤。