physics - 两个移动四面体之间的连续碰撞检测

Question

我的问题很简单。我有两个四面体，每个四面体都有一个当前位置、一个空间线速度、一个角速度和一个质心(实际上是旋转中心)。

有了这些数据，我试图找到一个(快速)算法，它可以精确地确定(1)它们是否会在某个时间点发生碰撞，如果是这样，(2)在它们碰撞多长时间后和(3 ) 碰撞点。

大多数人会通过进行三角形-三角形碰撞检测来解决这个问题，但这会在冗余操作上浪费几个 CPU 周期，例如在检查不同的三角形时检查一个四面体的同一边与另一个四面体的同一边。这只是意味着我会稍微优化一下。没什么可担心的。

问题是我不知道任何考虑自旋转的公共(public) CCD(连续碰撞检测)三角形三角形算法。

因此，我需要一个输入以下数据的算法:

三个三角形的顶点数据

位置和旋转中心/质量

线速度和角速度

并会输出以下内容:

是否有碰撞

碰撞发生多长时间后

碰撞发生在空间的哪个点

在此先感谢您的帮助。

Answer 1

常用的离散碰撞检测将在连续的离散时间点检查每个形状的三角形是否有碰撞。虽然计算起来很简单，但由于测试的离散时间点之间发生碰撞，它可能会错过一个快速移动的物体撞到另一个物体。

连续碰撞检测将首先计算每个三角形在无限时间内追踪的体积。对于以恒定速度移动且不旋转的三角形，这个体积可能看起来像一个三棱柱。然后 CCD 将检查体积之间的碰撞，最后追溯三角形是否以及在何时实际共享相同的空间。

当引入角速度时，每个三角形所描绘的体积不再看起来像棱柱。它可能看起来更像是一个螺丝的形状，就像一条 DNA 链，或者其他一些非平凡的形状，你可以通过围绕任意轴旋转三角形同时线性拖动它来获得它。计算这种体积的形状绝非易事。

一种方法可能首先计算包含整个四面体的球体，当它以给定的角速度矢量旋转时，如果它不是线性移动的话。您可以为每个顶点计算一个旋转圆，并从中导出球体。给定一个球体，我们现在可以将挤出的 CCD 体积近似为具有球体半径并沿线速度矢量前进的圆柱体。找到这些圆柱体的碰撞可以让我们初步估计要在其中搜索碰撞的区域。

第二种补充方法可能会尝试通过将每个三角形分解成小的、几乎棱柱形的子体积来近似每个三角形所描绘的实际体积。它将以两个时间增量获取三角形位置，并添加通过在这些时刻跟踪三角形顶点生成的曲面。这是一个近似值，因为它连接的是一条直线而不是一条实际的曲线。为了避免严重错误的近似值，每个连续时刻之间的持续时间需要足够短，以使三角形只完成一小部分旋转。持续时间可以从角速度得出。

第二种方法创建更多的多边形!您可以使用第一种方法来限制搜索量，然后使用第二种方法来获得更高的精度。

如果您正在为游戏引擎解决这个问题，您可能会发现以上的精度已经足够了(我仍然会为计算成本而战栗)。相反，如果您正在编写 CAD 程序或撰写论文，您可能会发现它不太令人满意。在后一种情况下，您可能希望改进第二种方法，也许通过更好地描述转动的移动三角形所占据的体积 - 当限制为小转角时。