加速球体之间的碰撞检测

Question

我正在编写一个物理引擎/模拟器,它结合了3D太空飞行,行星/恒星引力,船舶推力和相对论效应.到目前为止,它的进展非常顺利,但是,我需要帮助的一件事是碰撞检测算法的数学计算.

我正在使用的运动的迭代模拟基本如下:

(注意:3D矢量是全部大写.)

For each obj

    obj.ACC = Sum(all acceleration influences)

    obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2     (*EQ.2*)

    obj.VEL = obj.VEL + (obj.ACC * dT)

Next

哪里:

obj.ACC is the acceleration vector of the object
obj.POS is the position or location vector of the object
obj.VEL is the velocity vector of the object

obj.Radius is the radius (scalar) of the object

dT is the time delta or increment

我基本上需要做的是找到一个有效的公式,从上面的(EQ.2)派生出两个对象(obj1,obj2),并告诉他们是否碰撞,如果碰到,在什么时候.我需要确切的时间,以便我可以确定它是否在这个特定的时间增量(因为加速器在不同的时间增量会有所不同),并且还可以找到确切的位置(我知道该怎么做,给定时间)

对于这个引擎,我将所有对象建模为球体,所有这些公式/ algortithim需要做的是弄清楚在哪些点:

(obj1.POS - obj2.POS).Distance = (obj1.Radius + obj2.Radius)

其中.Distance是一个正标量值.(如果这更容易,您也可以将两边平方,以避免.Distance计算中隐含的平方根函数).

(是的,我知道许多其他碰撞检测问题,但是,他们的解决方案似乎都非常特别适合他们的引擎和假设,并且似乎没有一个符合我的条件:在模拟增量中应用的3D,球体和加速度如果我错了,请告诉我.)

---

一些澄清:

1)在时间增量之前和之后检查两个球体的*交点*是不够的.在许多情况下,它们的速度和位置变化将远远超过它们的半径.

2)RE:效率,我不需要帮助(此时无论如何)确定可能的碰撞候选人,我认为我已经涵盖了这一点.

---

另一个澄清,似乎出现了很多:

3)我的增量运动方程(EQ.2)是一个应用速度和加速度的二次方程:

obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2

物理引擎,我所看到的,(当然,我听说过的每一个游戏引擎)只线性适用增量运动方程只有速度:

obj.POS = obj.POS + (obj.VEL * dT)

这就是为什么我不能使用在StackOverflow,维基百科和整个网络上找到的常见发布的碰撞检测解决方案,例如找到两个线段的交点/最接近的方法.我的模拟处理的是可变加速度,这是结果的基础,所以我需要的是两个抛物线段的交点/最近逼近.

Answer 1

在提到的AShelley网页上，针对两个物体以恒定速度运动的情况开发了“最接近点”方法。但是，我相信在两个对象都以恒定的非零加速度（二次时间依赖性）运动的情况下，可以使用相同的矢量演算方法来得出结果。

在这种情况下，距离平方函数的时间导数是3阶（三次）而不是1阶。因此，“最接近时间”将有3种解决方案，这并不奇怪，因为两个对象的路径都是弯曲的，因此可能有多个相交。对于此应用程序，您可能希望使用t的最早值，该值在当前模拟步骤定义的间隔内（如果存在这样的时间）。

我算出了应该给出最接近时间的导数方程：

0 = |D_ACC|^2 * t^3 + 3 * dot(D_ACC, D_VEL) * t^2 + 2 * [ |D_VEL|^2 + dot(D_POS, D_ACC) ] * t + 2 * dot(D_POS, D_VEL)

哪里：

D_ACC = ob1.ACC-obj2.ACC

D_VEL = ob1.VEL-obj2.VEL （更新之前）

D_POS = ob1.POS-obj2.POS （同样在更新之前）

和 dot(A, B) = A.x*B.x + A.y*B.y + A.z*B.z

（请注意，|A|^2可以使用来计算幅度的平方dot(A, A)）

为了解决这个问题的牛逼，你可能需要用的公式，如那些在维基百科上找到。

当然，这只会给您最接近的机会。您此时需要测试距离（使用等式2）。如果大于(obj1.Radius + obj2.Radius)，则可以忽略（即无碰撞）。但是，如果距离较小，则意味着球在此刻之前发生碰撞。然后，您可以使用迭代搜索来更早地测试距离。也有可能提出另一种（甚至更复杂的）推导，该推导考虑了大小，或者有可能找到其他解析解，而无需求助于迭代求解。

编辑：由于高阶，方程的一些解实际上是距离最远的时刻。我相信，在所有情况下，三种解决方案中的一种或三种解决方案中的两种将是最遥远的时间。您可以通过评估相对于时间的二阶导数（通过将一阶导数设置为零而找到的t值）来分析性地测试您是处于最小值还是最大值。

D''(t) = 3 * |D_ACC|^2 * t^2 + 6 * dot(D_ACC, D_VEL) * t + 2 * [ |D_VEL|^2 + dot(D_POS, D_ACC) ]

如果二阶导数计算为正数，则您知道在给定的时间t内，距离是最小而不是最大。