线性插值和物体碰撞
Linear Interpolation and Object Collision
我有一个使用 AABB 测试来检测对象碰撞的物理引擎和一个不使用线性插值的动画系统。因此，我的碰撞有时会不稳定，尤其是在高速行驶时。这是我系统中一个非常明显的问题...
为了演示，假设我们的动画系统中的一帧持续 1 秒，我们在第 0 帧处给出以下场景。
在第 1 帧，不会检测到对象的碰撞，因为 c1 将在下一次绘制时经过 c2。
虽然我没有使用它，但我对线性插值的工作原理有了一些了解，因为我在这个项目中在不同的上下文中使用了线性外推。我想知道线性插值是否可以解决我遇到的问题，或者我是否还需要其他方法。
我有一部分人对如何在动画上下文中使用线性插值感到困惑。这个想法是我们可以在低帧率下实现流畅的动画。在上面的场景中，我们不能简单地将 c1 设置为以第 1 帧中的 x=3 为中心。实际上，它们会在第 0 帧和第 1 帧之间的某个地方发生碰撞。线性插值是否会自动处理这个问题并允许精确的 AABB测试？如果不是，它会解决什么问题，我应该研究哪些其他方法来实现流畅和精确的碰撞检测和动画？
您遇到的现象称为隧道，是离散碰撞检测架构固有的问题。您认为线性插值可能与解决方案有关是正确的，因为它可以让您在误差范围内（通常）预测帧之间对象的路径，但这只是其中的一部分更大的解决方案。我见过的与这些类型的解决方案相关的术语是 "Continuous Collision Detection"。这个话题很大而且很复杂，有讨论它的书籍，例如 Real Time Collision Detection 和其他在线资源。
所以回答你的问题：不，线性插值本身不能解决你的问题*。除非你只处理圆或球。
开始考虑什么
解决方案的外观和行为方式取决于您的设计决策并且通常很大。所以只是为了指出解决的方向，连续碰撞检测的基本思想是弄清楚：前一帧和后一帧之间发生碰撞的距离是多少，这两个物体在什么位置和旋转观点。然后您必须计算对象在稍后的帧时间将处于的配置以响应此。对于除二维圆以外的任何事物，解决这些问题会变得非常有趣。
我还没有实现这个，但我看到描述了一个解决方案，你可以在帧之间向前移动两个候选人，用线性插值推进他们的位置，用球面线性插值推进他们的方向，并用离散算法检查他们是否'相交（Gilbert-Johnson-Keerthi 算法）。从这里开始，您继续应用离散算法以获得最小的穿透深度（扩展多面体算法）并将该深度和帧之间的剩余时间传递给求解器，以获取对象在您以后的帧时间中的外观。这没有给出分析答案，但我不知道广义 2 或 3D 案例的分析答案。
如果你不想沿着这条路走下去，那么你对抗复杂性的最好武器就是假设：如果你可以假设你的高速物体可以表示为一个点，那么事情就会变得更容易，如果你可以假设物体的方向并不重要（圆圈、球体），事情变得更容易，而且它会一直持续下去。这个主题非常有趣，我仍在学习它的道路上，但它提供了我编程期间最令人满意的一些时刻。我希望这些想法也能让你走上这条路。
编辑： 由于您指定您正在开发台球游戏。
首先我们将检查是否需要离散或连续
- 这款游戏可以接受任何数量的隧道吗？不在台球
没有。
- 我们将看到隧道的速度是多少？使用 0.0285m
球的半径（标准美式）和 0.01 秒的物理步长，我们
获得 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)
所以这里你有插值用于 "move" 圆圈沿着它们在当前帧和下一帧之间将采用的路径。在确认的交叉点上，您可以获得穿透深度并传递增量时间（dt / 细分）、两个圆、穿透深度和碰撞点，以决定它们应如何响应碰撞的解决步骤。
我有一个使用 AABB 测试来检测对象碰撞的物理引擎和一个不使用线性插值的动画系统。因此，我的碰撞有时会不稳定，尤其是在高速行驶时。这是我系统中一个非常明显的问题...
为了演示，假设我们的动画系统中的一帧持续 1 秒，我们在第 0 帧处给出以下场景。
在第 1 帧，不会检测到对象的碰撞，因为 c1 将在下一次绘制时经过 c2。
虽然我没有使用它，但我对线性插值的工作原理有了一些了解，因为我在这个项目中在不同的上下文中使用了线性外推。我想知道线性插值是否可以解决我遇到的问题，或者我是否还需要其他方法。
我有一部分人对如何在动画上下文中使用线性插值感到困惑。这个想法是我们可以在低帧率下实现流畅的动画。在上面的场景中，我们不能简单地将 c1 设置为以第 1 帧中的 x=3 为中心。实际上，它们会在第 0 帧和第 1 帧之间的某个地方发生碰撞。线性插值是否会自动处理这个问题并允许精确的 AABB测试？如果不是，它会解决什么问题，我应该研究哪些其他方法来实现流畅和精确的碰撞检测和动画？
您遇到的现象称为隧道，是离散碰撞检测架构固有的问题。您认为线性插值可能与解决方案有关是正确的，因为它可以让您在误差范围内（通常）预测帧之间对象的路径，但这只是其中的一部分更大的解决方案。我见过的与这些类型的解决方案相关的术语是 "Continuous Collision Detection"。这个话题很大而且很复杂，有讨论它的书籍，例如 Real Time Collision Detection 和其他在线资源。
所以回答你的问题：不，线性插值本身不能解决你的问题*。除非你只处理圆或球。
开始考虑什么
解决方案的外观和行为方式取决于您的设计决策并且通常很大。所以只是为了指出解决的方向，连续碰撞检测的基本思想是弄清楚：前一帧和后一帧之间发生碰撞的距离是多少，这两个物体在什么位置和旋转观点。然后您必须计算对象在稍后的帧时间将处于的配置以响应此。对于除二维圆以外的任何事物，解决这些问题会变得非常有趣。
我还没有实现这个，但我看到描述了一个解决方案，你可以在帧之间向前移动两个候选人，用线性插值推进他们的位置，用球面线性插值推进他们的方向，并用离散算法检查他们是否'相交（Gilbert-Johnson-Keerthi 算法）。从这里开始，您继续应用离散算法以获得最小的穿透深度（扩展多面体算法）并将该深度和帧之间的剩余时间传递给求解器，以获取对象在您以后的帧时间中的外观。这没有给出分析答案，但我不知道广义 2 或 3D 案例的分析答案。
如果你不想沿着这条路走下去，那么你对抗复杂性的最好武器就是假设：如果你可以假设你的高速物体可以表示为一个点，那么事情就会变得更容易，如果你可以假设物体的方向并不重要（圆圈、球体），事情变得更容易，而且它会一直持续下去。这个主题非常有趣，我仍在学习它的道路上，但它提供了我编程期间最令人满意的一些时刻。我希望这些想法也能让你走上这条路。
编辑： 由于您指定您正在开发台球游戏。
首先我们将检查是否需要离散或连续
- 这款游戏可以接受任何数量的隧道吗？不在台球 没有。
- 我们将看到隧道的速度是多少？使用 0.0285m 球的半径（标准美式）和 0.01 秒的物理步长，我们 获得 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)
所以这里你有插值用于 "move" 圆圈沿着它们在当前帧和下一帧之间将采用的路径。在确认的交叉点上，您可以获得穿透深度并传递增量时间（dt / 细分）、两个圆、穿透深度和碰撞点，以决定它们应如何响应碰撞的解决步骤。