我的问题是相当简单的。 我有两个四面体，每一个的当前位置，在空间中的线性速度，角速度和质量中心（旋转中心，实际上）。
有了这个数据，我想找到一个（快速）算法，这将精确地确定（1）他们是否会在某个时间点发生碰撞，如果是的话，（2）后多少时间，他们相撞（3 ）碰撞点。
大多数人会做三角三角形碰撞检测解决这个问题，但是这会浪费多余的操作，比如检查，对其他的四面体的同一边缘一个四面体在检查了不同的三角形同一边缘的几个CPU周期。 这不仅意味着我将优化的东西一点。 没什么好担心的。
问题是，我不知道任何公开的CCD（连续碰撞检测）三角三角算法采用自转的账户。
因此，我需要这将是输入以下数据的算法：
并且将输出以下内容：
在此先感谢您的帮助。
常用的离散的碰撞检测将检查每个形状的三角形碰撞，在连续的离散时间点的。 虽然简单的计算，它可能会错过一个快速移动的物体击中一个又一个，因碰撞测试中离散的时间点之间发生的事情。
连续碰撞检测将首先计算由每个三角形随时间的无边跟踪的卷。 对于一个三角形以恒定速度和无旋转移动，该体积可能看起来像一个三角棱镜。 然后CCD将检查各卷之间的碰撞，最后追溯是否以及在什么时候三角形居然有着相同的空间。
当引入角速度，由每个三角形描绘的体积不再看起来像的棱镜。 它看起来更像是一个螺丝钉的形状，像一个DNA链，或者你可能被周围的一些任意旋转轴的三角形，而线性拖动它得到一些其他的非平凡的形状。 计算这样的体积的形状并非易事。
一种方法可能首先计算当它旋转以给定的角速度矢量，如果它不是直线移动一个包含整个四面体球体。 你可以计算旋转圆环每个顶点，并从中导出球体。 给定的球体，我们现在可以近似挤出CCD体积与球的半径的圆柱体，并沿线速度矢量取得进展。 找到这样的缸碰撞得到我们的区域来搜索碰撞的第一近似值。
第二，互补的做法可能会试图通过它分解成小的，几乎棱柱子体积近似由每个三角形跟踪的实际体积。 这将需要的三角形的位置在时间的两个增量，并添加通过在那些时刻跟踪三角形顶点生成的表面。 这是一个近似值，因为它连接一条直线，而不是实际的曲线。 对于近似，以避免严重的错误，每个相继的时刻之间的持续时间必须足够，使得三角形只完成一个旋转的一小部分短。 持续时间可以从角速度来导出。
第二种方法创造了许多更多的多边形！ 您可以使用第一种方法来限制搜索量，然后用第二个获得更高的精度。
如果您正在解决这一个游戏引擎，你会发现上面足够的精度（我仍心有余悸计算成本）。 如果，相反，你正在写一个CAD程序或在你的论文的工作，你会发现它比满意更小。 在后一种情况下，你可能要细化第二种方法，或许可以通过转动所占的体积更好的几何描述，移动三角 - 仅限于小转角时。
我花了相当多的时间琢磨一下这样一个几何问题，这似乎是准确的解决方案，尽管他们的简单语句，实在是太复杂，是可行的，即使是类似2D的情况。
但直觉我看到，当你考虑线性平移速度和线性角速度确实存在这样的解决方案。 不要以为你会发现在网络上或任何一本书的答案，因为我们在这里讨论的是什么特别的，但复杂的案件。 迭代求解可能是你想要的要多 - 在世界其他地方是满意的，那么你为什么不现在呢？
如果你试图冲撞非旋转四面体，我建议一个走的是闵可夫斯基之和进行射线检查，但不会使用轮流工作。
我能想出的最好的是用他们的包围球给你的时间范围内进行扫频球体碰撞使用二分法或什么都有，你要检查。
这里有一个封闭形式的数学方法的轮廓。 这每一个元素会很容易单独表达，而这些最终的组合将是一个解析解，如果人能写出来：
1）为四面体的每个点的运动方程是在它自己的坐标系中非常简单。 质量（CM）的中心的运动将只平滑地移动沿着直线和角点将围绕通过CM的轴线旋转，假定为z轴在这里，所以对于每个角点的方程（由参数时间，t）是p = v T + X + R（SIN（重量+ S）1 + COS（重量+ S）j），其中v是质量中心的向量速度; r是投影到XY平面上的半径; I，J，和k是在x，y和z的单位矢量; 并且x和s帐户在t = 0的起始位置和旋转相位。
2）请注意，每个对象都有它自己的坐标系，以轻松代表议案，但对它们进行比较，你需要给每个旋转成一个共同的坐标系，它也可以被坐标屏幕系统。 （不过要注意的是，不同的坐标系在空间中固定，而不是与四面体旅行。）所以确定旋转矩阵，并把它们应用到每个轨迹（ 即点和CM每个四面体的）。
3）现在，你必须为每个轨道内的所有相同的坐标系的方程，你需要找到交叉的时间。 这可通过测试是否有任何从点到四面体的CM的线段的相交的任意的另一个三角形的找到。 这也有一个封闭的形式表达，如能找到这里 。
分层这些步骤将使可怕丑陋公式，但它不会是很难解决他们的计算（虽然与四面体的旋转，你需要确保不陷入局部最小值）。 另一种选择可能是将其插入像数学为你做的发动。 （并非所有的问题都有简单的答案。）
对不起，我不是一个数学B关，而且不知道正确的术语是什么。 希望我的可怜的方面丝毫不掩饰我的意思太多了。
挑选一些任意时间步长。
计算各形状的边界在垂直于它是在移动的时间步长的轴的两个维度。
对于时间步：如果这些界限的任何两个物体的轴相交，一半时间步长和开始递归。
一类二进制搜索的越来越细的精度来发现在其中有限交发生的点。
你的问题可以转换成线性规划问题，准确地得到解决。
首先，假设（P0，P1，P2，P3）是在时刻t0的顶点，和（Q0，Q1，Q2，Q3）是在用于第一四面体时间t1的顶点，然后在四维空间 - 时间，它们填充以下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
第二四面体是类似的凸多边形（添加a“到一切上述定义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个值的20个线性约束AK，BK，AK“和BK”。 如果有一个解决方案，然后
(r,t)= a0*(p0,t0) + … + a3*(p3,t0) + b0*(q0,t1) + … + b3*(q3,t1)
首先是一个交点。 否则，他们不相交。
想到这点，在过去，但失去了兴趣......去着手解决这将是抽象出一个物体的最佳方式。 做一个坐标系，其中第一四面体是中心（重心COORDS或一个点为原点偏态系统），通过使其他四面体绕中心旋转和抽象出来的旋转。 如果你做的旋转时间时这应该给你参数方程。 添加大容量的向第一和它的旋转中心的运动，你有相对于第一（距离）的运动方程组。 求解T，其中距离等于零。
显然，用这种方法效果更为你添加（如风阻）的混乱的公式得到的击打其仍然可能是最简单的（几乎所有其他碰撞技术使用抽象这种方法）。 最大的问题是，如果你添加有没有解析解整方程变成无法解决的反馈任何影响。
注意：如果你去的偏斜系统的路径注意随距离的陷阱。 你必须在正确的八分！ 这种方法有利于载体和四元数虽然，而重心COORDS利于矩阵。 所以，无论选择哪种系统使用最有效的。
