我的问题非常简单。我有两个四面体，每个都有当前位置，空间线速度，角速度和质心（实际上是旋转中心）。我试图找到一个（快速）算法，它将精确确定（1）他们是否会在某个时间点发生碰撞，如果是这种情况，（2）他们在多长时间后碰撞和（3）碰撞点。大多数人会通过做三角形 - 三角形碰撞检测来解决这个问题，但是这会浪费几个CPU周期来处理冗余操作，比如在检查不同三角形时检查一个四面体的同一边缘与另一个四面体的同一边缘。这只意味着我会优化一些东西。完全不用担心。两个移动四面体之间的连续碰撞检测
的问题是，我不知道任何公开的CCD（连续碰撞检测）三角形三角算法这需要自转在帐户的。
因此，我需要这将被输入下面的数据的算法：
而且会输出以下内容：
在此先感谢您的帮助。
常用的离散的碰撞检测将检查每个形状的三角形碰撞，在连续的离散时间点的。虽然计算简单，但由于测试的离散时间点之间发生碰撞，它可能会错过一个快速移动的物体撞击另一个物体。
连续碰撞检测将首先计算由每个三角形随时间的无边跟踪的卷。对于一个以恒定速度运动且不旋转的三角形，这个体积可能看起来像一个三角棱镜。然后CCD将检查这些体积之间的碰撞，并最终追溯三角形实际共享相同空间的时间和时间。
当引入角速度，由每个三角形描绘的体积不再看起来像的棱镜。它可能看起来更像是一个螺丝的形状，就像一串DNA，或者是一些其他非平凡的形状，可以通过围绕某个任意轴旋转一个三角形，同时将其线性拖动。计算这种音量的形状并非易事。
一种方法可能首先计算当它旋转以给定的角速度矢量，如果它不是直线移动一个包含整个四面体球体。您可以计算每个顶点的旋转圆，并从中得出球体。给定一个球体，我们现在可以将挤出的CCD体积近似为一个具有球体半径的圆柱体，并沿线速度矢量进行。寻找这些圆柱体的碰撞使我们能够首先近似找到一个区域来寻找碰撞。
第二个补充方法可能会尝试将每个三角形追踪的实际体积近似为几乎棱柱形的小体积。它需要两次增量的三角形位置，并在这些时刻添加通过追踪三角形顶点生成的曲面。这是一个近似值，因为它连接了一条直线而不是实际的曲线。对于避免粗差的逼近，每个连续时刻之间的持续时间需要足够短，以使三角形只完成一小部分旋转。持续时间可以从角速度得出。
第二种方法创建更多的多边形！您可以使用第一种方法来限制搜索量，然后使用第二种方法获得更高的精度。
如果你正在为游戏引擎解决这个问题，你可能会发现上面的精度已经足够了（我仍然会对计算成本感到不寒而栗）。相反，如果您正在编写CAD程序或正在撰写论文，您可能会发现它并不令人满意。在后一种情况下，您可能需要改进第二种方法，可能是通过对转动的三角形所占据的体积进行更好的几何描述 - 当转动角度很小时。
OP在这里。感谢您的贡献。我正在考虑对问题采取更精确的*和*快速方法。如果我想要一些近似的东西，我会简单地用非常小的时间步长来使用离散碰撞检测。如果我不在乎时间，我会使用类似二分法的方法来查找碰撞前的确切点，最多可达小数位数。 – x26 2009-07-11 09:55:11
我会做两个球碰撞，因为在3D中一个圆柱体/圆柱体的碰撞速度非常快（它基本上只是检查两条线之间的最小距离）。所以首先你看看气缸是否碰撞，然后你看看球是否碰撞（同时在碰撞体积内）。然后在离散时间做三角形检查。角速度会把你在这个阶段通常拥有的大多数快捷键搞砸。 – Nosredna 2009-07-11 22:27:31
我花了相当多的时间来思考像这样的几何问题，尽管它们很简单，但似乎精确的解决方案太复杂了，实际上也是如此，即使是类似的2D情况。
但直观地看到，当您考虑线性平移速度和线性角速度时，这样的解决方案确实存在。不要以为你会在网上或任何书中找到答案，因为我们在这里讨论的是特殊而复杂的案例。无论如何，迭代解决方案可能就是你想要的 - 世界其他地方都对这些满意，所以你为什么不去？
如果你试图碰撞非旋转的四面体，我建议采取闵可夫斯基和进行射线检查，但是这对旋转不起作用。
我能想出的最好的方法是使用它们的边界球执行扫掠球碰撞，给你一个时间范围来检查使用平分或你有什么。
对不起，我不是一个数学boff，不知道什么是正确的术语。希望我可怜的条款不会隐藏我的意思太多。
选择一些任意的时间步。
计算每个形状的垂直于它在时间步上移动的轴的两个维度的边界。
对于一个时间步长： 如果这些界限的任意两个物体轴相交，半时间步长和在开始递归
一类二进制搜索的越来越细的精度来发现的点上有限的交叉点发生。
下面是封闭式数学方法的概述。每个元素都可以很容易地单独表达，如果有人能写出它们，它们的最终组合将是一个封闭的表达式：
1）四面体每个点的运动方程相当简单在它自己的坐标系中。质心（CM）的运动将沿着一条直线平滑移动，并且角点将围绕通过CM的轴旋转，假定为此处的z轴，因此每个角点的方程式（参数化为时间，t）为p = v吨+ X + R（SIN（重量+ S）我 + COS（重量+ S）Ĵ），其中v是的矢量速度质量中心; r是投影到x-y平面上的半径; i,j和k是x，y和z单位向量;和x和s说明t = 0时的起始位置和旋转相位。 2）请注意，每个物体都有自己的坐标系来轻松地表示运动，但为了比较它们，您需要将每个物体旋转到一个公共坐标系中，这也可能是屏幕的坐标系。 （注意不同的坐标系固定在空间中，不与四面体一起行进）。因此，确定旋转矩阵并将它们应用到每个轨迹（，即各个四面体的点和CM）。
3）现在，您可以在同一坐标系中获得每个轨迹的方程，并且需要查找交点的时间。这可以通过测试从四面体的点到CM的任何线段是否与另一个三角形的任何三角形相交来找到。这也有一个封闭的表达式，可以发现here。
分层这些步骤会造成非常丑陋的方程，但它不会很难通过计算来解决它们（尽管随着四面体的旋转，您需要确保不会陷入局部最小值）。另一种选择可能是将它插入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'为该四面体移动的四维体积。
现在两个凸多边形的交集是一个凸多边形。第一次发生这将满足下面的线性规划问题：
如果（p0，p1，p2，p3）移动到（q0，q1，q2，q3） 和（p0'，p1'，p2' （r，t）：
最小化t0 *（a0 + a1 + a2 + p3'）移动到（q0'，q1'，q2'，q3'） 然后第一次交点发生在点/ 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。
显然用这种方法效果更为你添加（如风阻）的混乱的公式得到的击打其仍然可能是最简单的（几乎所有其他碰撞技术使用抽象这种方法）。最大的问题是，如果添加任何反馈而没有解析解的效应，则整个方程将无法解决。
注意：如果您走偏斜系统的路线，请留意距离有缺陷的地方。你必须在正确的八分之一！尽管这种方法有利于矢量和四元数，而重心坐标则偏向于矩阵。所以选择你的系统最有效的使用。
+1只是因为标题太酷了 - 如果你正在尝试，你不会做得更好！）。 （对不起，我没有足够的三维计算几何专业知识来真正帮助这里）。 – 2009-07-11 01:34:47
是的，这是一个很酷的标题。我不记得有足够的数学来解决这个问题，但我相信你会想要求解一个微分参数方程来模拟当前位置（x，y，z）=（f（t），g（t），h（t ））为每个对象。您可以通过首先查找它们是否足够接近以使其成为基于每个对象的最小球体的碰撞来优化它。如果不是，它们不会相互碰撞。如果是，那么你可以做复杂的计算。 – cletus 2009-07-11 01:39:29
OP在这里。我可能会使用其他技术来过滤实际需要测试碰撞的对象（有些称它为宽相）。如果没有人提出任何实际的方程或更好的方法来做到这一点，我会把所有的东西都放在一个距离方程中（就时间而言），并写出一个算法，试图找到一个解决方案。说实话，我真的不想这样做，特别是如果它已经完成。 – x26 2009-07-11 02:11:26