如何插值多个高速多边形碰撞（2D）？

Question

上下文

我需要在物理模拟中检测高速物体的碰撞。由于网格中数字的截断和对象的数字表示，快速移动的对象很有可能相互穿过或错过。我试图通过模拟“模拟”或现实生活中的运动属性来执行插值碰撞，在这些运动中，物体会通过每一点移动。（现实世界中的物体通常不会在宏观层面上传送到下一个点）

研究和预见我们能够找到投影物体的最终和初始点，时间和速度的位移。我使用每像素碰撞来获得像素映射，所以我们有一个像素簇。目前我解决这个问题的方法是使用牛顿方法来计算线性交点。

问题是：如何像计算“单个像素”或“法线”线那样计算像素簇的交点。

额外好处：非线性运动（速度加加速度）或计算插值中的多次碰撞会怎样（弹性碰撞会使一个碰撞对象与另一个附加对象发生碰撞，否则该附加对象会靠近初始碰撞，但会丢失初始碰撞。这最好都在插值计算范围内。）

Answer 1

一年后，我没有答案，所以我想我应该用自己的知识尽可能地回答自己的问题。

似乎很多游戏都不关心这种特殊情况，不幸的是，这种情况经常被观察到。游戏中的许多高速物体有时会因为缺乏捕捉这些物体的机制而出故障。实现一些东西来捕获高速对象需要插值演算，这将不可避免地导致游戏的更高开销。

增加开销的概念在这里很清楚，如果你真的想要最准确的物理模拟，你会引入越来越多的计算，对于一个游戏来说，这将有效地使它越来越难以保持模拟的平稳播放，特别是如果有要签入的对象数量更多。例如，比较完美的每像素交叉点和不太完美的轴对齐边界盒交叉点的性能开销。如果你有一场乒乓球或雅达利风格的突破比赛，AABB将是完全可以接受的，唯一的接球是球正好在拐角处击中另一个矩形。与此同时，也没有足够的对象让每像素交叉点变得可怕（尤其是如果你只考虑交叉点相对于其他对象的球）。

当一个人在游戏中处理复杂的交叉点时，作弊和使用近似来掩盖平淡的物理计算是关键。以我们前面的每像素相交为例，这次使用类似于马里奥游戏的东西。我们不能只计算马里奥的交叉点，因为他还可以投掷需要碰撞检测的火球，或者与其他敌人互动的敌人。在这种情况下，您可以使用类似于四叉树的东西，它会不断地将更多的碰撞细化为包含预定密度的对象碰撞的碰撞区域。现在重新考虑一下我们的pong例子，比如在混音中再加入4个球。一个真正狡猾的程序员可以首先使用四叉树将交叉点放入区域，然后在确定与每像素交叉点的精确碰撞（如果形状被标记为复杂）之前，与AABB进行初步交叉。

像Minkowski Portal Refineration或它的近亲GJK距离算法这样的算法，它给出了凸集之间的最短距离，可能是我能给出的最接近的解决方案。我个人对这些算法没有太多经验，但这是我能推荐的最佳答案。这些算法非常先进，绝对超越了初级中级程序员。

关于子弹碰撞的补充说明

如果你来这里是因为你在想射击游戏，我还有一颗宝石给你。我不建议真的制造子弹“可碰撞”的物体（也许是移动较慢的导弹）。相反，你可以保持枪口闪光，但把视觉子弹变成效果。现在要计算子弹是否击中，你可以使用从枪口延伸出的对齐圆锥体来计算。圆锥半径从尖端到无限底部的变化可以从精度统计中确定为常数，也可以根据连续火灾进行扩展。然后你考虑到，一个百分比，多少目标被圆锥相交，乘以RNG概率，决定子弹是否被击中。因此，我们将子弹交互简化为锥体与物体碰撞，并简单地将其余部分留给随机数生成。因此，获得了精确的物理仿真假象。想象一下现在实现迷你枪有多容易，这将在我们的非RNG示例中产生大量的子弹延迟。