我的问题很简单。我有两个四面体，每个四面体都有一个当前位置、一个空间线速度、一个角速度和一个质心（实际上是旋转中心）。
有了这些数据，我试图找到一种（快速）算法，它可以精确地确定（1）它们是否会在某个时间点发生碰撞，如果是这样，（2）在它们碰撞多长时间后和（3 ) 碰撞点。
大多数人会通过进行三角形-三角形碰撞检测来解决这个问题，但这会在冗余操作上浪费几个 CPU 周期，例如在检查不同的三角形时检查一个四面体的同一边与另一个四面体的同一边。这只是意味着我会稍微优化一下。没什么好担心的。
问题是我不知道任何考虑自旋转的公共 CCD（连续碰撞检测）三角形三角形算法。
因此，我需要一个输入以下数据的算法：
并会输出以下内容：
在此先感谢您的帮助。
常用的离散碰撞检测将在连续的离散时间点上检查每个形状的三角形是否有碰撞。虽然计算起来很简单，但由于测试的离散时间点之间发生碰撞，它可能会错过一个快速移动的物体撞到另一个物体。
连续碰撞检测将首先计算每个三角形在无限时间内追踪的体积。对于以恒定速度移动且不旋转的三角形，这个体积可能看起来像一个三棱柱。然后，CCD 将检查体积之间的碰撞，最后追溯三角形是否以及在何时实际共享相同的空间。
当引入角速度时，每个三角形所描绘的体积不再看起来像棱柱。它可能看起来更像是一个螺丝的形状，就像一条 DNA 链，或者其他一些非平凡的形状，你可以通过围绕任意轴旋转三角形同时线性拖动它来获得它。计算这种体积的形状绝非易事。
一种方法可能首先计算包含整个四面体的球体，当它以给定的角速度矢量旋转时，如果它不是线性移动的话。您可以为每个顶点计算一个旋转圆，并从中导出球体。给定一个球体，我们现在可以将挤出的 CCD 体积近似为具有球体半径并沿线速度矢量前进的圆柱体。找到这些圆柱体的碰撞可以让我们初步估计要在其中搜索碰撞的区域。
第二种补充方法可能会尝试通过将每个三角形分解成小的、几乎棱柱形的子体积来近似每个三角形所描绘的实际体积。它将以两个时间增量获取三角形位置，并添加通过在这些时刻跟踪三角形顶点生成的曲面。这是一个近似值，因为它连接的是一条直线而不是一条实际的曲线。为了避免严重错误的近似，每个连续时刻之间的持续时间需要足够短，以使三角形只完成一小部分旋转。持续时间可以从角速度得出。
第二种方法创建更多的多边形！您可以使用第一种方法来限制搜索量，然后使用第二种方法来获得更高的精度。
如果您正在为游戏引擎解决这个问题，您可能会发现以上的精度已经足够了（我仍然会为计算成本而战栗）。相反，如果您正在编写 CAD 程序或撰写论文，您可能会发现它不太令人满意。在后一种情况下，您可能希望改进第二种方法，也许通过对转动的移动三角形所占据的体积进行更好的几何描述 - 当限制为小转角时。
我花了很多时间想知道像这样的几何问题，尽管它们的陈述很简单，但似乎准确的解决方案太复杂而无法实用，即使对于类似的 2D 情况也是如此。
但直觉上，当您考虑线性平移速度和线性角速度时，我发现确实存在这样的解决方案。不要以为你会在网络或任何书中找到答案，因为我们在这里讨论的是特殊但复杂的案例。无论如何，迭代解决方案可能是您想要的——世界其他地方都对这些感到满意，那么您为什么不应该呢？
如果您试图碰撞非旋转四面体，我建议采用 Minkowski 和并执行射线检查，但这不适用于旋转。
我能想到的最好的方法是使用它们的边界球执行扫球碰撞，给你一定范围的时间来检查使用二分法或你有什么。
这是封闭式数学方法的概述。这其中的每个元素都将很容易单独表达，如果可以写出来，它们的最终组合将是一个封闭形式的表达：
1）四面体每个点的运动方程在它自己的坐标系中相当简单。质心 (CM) 的运动将沿着直线平滑移动，并且角点将围绕通过 CM 的轴旋转，此处假设为 z 轴，因此每个角点的方程（参数化为时间，t) 是p = v t + x + r(sin(wt+s) i + cos(wt + s) j )，其中v是质心的矢量速度；r 是投影到 xy 平面上的半径；i、j和k是 x、y 和 z 单位向量；和x和 s 说明 t=0 时的起始位置和旋转相位。
2) 请注意，每个对象都有自己的坐标系来轻松表示运动，但要比较它们，您需要将每个对象旋转到一个共同的坐标系中，这也可能是屏幕的坐标系。（请注意，虽然不同的坐标系在空间中是固定的，而不是与四面体一起移动。）所以确定旋转矩阵并将它们应用于每个轨迹（即每个四面体的点和 CM）。
3）现在你有一个方程，每个轨迹都在同一个坐标系内，你需要找到交叉点的时间。这可以通过测试从点到四面体的 CM 的任何线段是否与另一个三角形的任何三角形相交来找到。这也有一个封闭形式的表达式，可以在这里找到。
将这些步骤分层会产生非常难看的方程，但通过计算求解它们并不难（尽管四面体的旋转需要确保不会陷入局部最小值）。另一种选择可能是将其插入 Mathematica 之类的东西来为您启动。（并非所有问题都有简单的答案。）
您的问题可以转换为线性规划问题并准确解决。
首先，假设 (p0,p1,p2,p3) 是 t0 时刻的顶点，(q0,q1,q2,q3) 是第一个四面体在 t1 时刻的顶点，那么在 4d 时空中，它们填充以下 4d 封闭体积
V = { (r,t) | (r,t) = a0 (p0,t0) + … + a3 (p3,t0) + b0 (q0,t1) + … + b3 (q3,t1) }
这里 a0...a3 和 b0...b3 参数在区间 [0,1] 中并且总和为 1：
a0+a1+a2+a3+b0+b1+b2+b3=1
第二个四面体同样是一个凸多边形（在上面的所有内容中添加一个 ' 以定义 V' 移动四面体的 4d 体积。
现在两个凸多边形的交点就是一个凸多边形。第一次发生这种情况将满足以下线性规划问题：
如果 (p0,p1,p2,p3) 移动到 (q0,q1,q2,q3) 并且 (p0',p1',p2',p3') 移动到 (q0',q1',q2',q3')那么第一次相交发生在点/时间（r，t）：
最小化 t0*(a0+a1+a2+a3)+t1*(b0+b1+b2+b3) 服从
0 <= ak <=1, 0<=bk <=1, 0 <= ak’ <=1, 0<=bk’ <=1, k=0..4
a0*(p0,t0) + … + a3*(p3,t0) + b0*(q0,t1) + … + b3*(q3,t1)
= a0’*(p0’,t0) + … + a3’*(p3’,t0) + b0’*(q0’,t1) + … + b3’*(q3’,t1)
最后一个实际上是 4 个方程，一个对应于 (r,t) 的每个维度。这是 16 个值 ak、bk、ak' 和 bk' 的总共 20 个线性约束。如果有解决方案，那么
(r,t)= a0*(p0,t0) + … + a3*(p3,t0) + b0*(q0,t1) + … + b3*(q3,t1)
是第一个交点。否则它们不会相交。
抱歉，我不是数学爱好者，也不知道正确的术语是什么。希望我的拙劣用词不要掩饰我的意思太多。
选择一些任意时间步长。
计算每个形状在与时间步长移动的轴垂直的二维中的边界。
对于一个时间步：如果任何两个对象的这些边界的轴相交，则半个时间步并开始递归。
一种精度越来越高的二分搜索，以发现发生有限交点的点。
过去想过这个，但失去了兴趣……解决它的最好方法是抽象出一个对象。制作一个以第一个四面体为中心的坐标系（重心坐标或以一个点为原点的倾斜系统）并通过使另一个四面体围绕中心旋转来抽象出旋转。如果您将旋转时间设为时间，这应该会为您提供参数方程。将质心向第一个及其自旋的运动相加，您就有了一组相对于第一个（距离）的运动方程。求解距离为零的 t。
显然，使用这种方法，您添加的效果（如风阻）越多，方程就越混乱，但它仍然可能是最简单的（几乎所有其他碰撞技术都使用这种抽象方法）。最大的问题是，如果您添加任何具有反馈但没有解析解的效应，整个方程将变得无法解。
注意：如果您走偏斜系统的路线，请注意距离问题。你必须在正确的八分圆！这种方法有利于向量和四元数，而重心坐标有利于矩阵。因此，选择您的系统最有效使用的那个。