加速球之间的碰撞检测

Question

我正在编写一个物理引擎/模拟器，其中包括三维空间飞行、行星/恒星引力、船只推力和相对论效应。到目前为止，进展非常顺利，但是我需要帮助解决的问题是碰撞检测算法的数学问题。

我使用的运动迭代模拟基本上如下：

（注意：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），并告知它们是否会发生碰撞，如果会，那么在何时发生。我需要确切的时间，以便我可以确定它是否在特定的时间增量内（因为不同的时间增量加速度也不同），同时也需要确定确切的位置（我知道如何做，只需给定时间）。

对于这个引擎，我将所有对象建模为球体，所有这个公式/算法需要做的就是找出在哪些点上：

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

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

（是的，我知道有很多其他的碰撞检测问题，然而，它们的解决方案似乎都非常特定于它们的引擎和假设，并且没有一个符合我的条件：3D、球体和在模拟增量内施加的加速度。如果我错了，请告诉我。）

---

一些澄清：

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

2）关于效率，我不需要帮助（至少目前不需要）来确定可能的碰撞候选者，我认为我已经解决了这个问题。

---

另一个经常出现的澄清：

3）我的增量运动方程（EQ.2）是一个二次方程，适用于速度和加速度：

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

在我所见过的物理引擎中（当然还包括所有我听说过的游戏引擎），只有线性方程逐步运动应用于速度，没有其他类型的方程。

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

这就是为什么我不能使用在StackOverflow、维基百科和整个互联网上普遍发布的碰撞检测解决方案，例如找到两条直线段的交点/最近接触点。我的模拟涉及基本结果的可变加速度，因此我需要找到两个抛物线段的交点/最近接触点。

- RBarryYoung

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)，那么可以忽略它（即无碰撞）。然而，如果距离更小，这意味着球体在此之前发生了碰撞。然后，您可以使用迭代搜索来测试较早时间的距离。也可能通过另一个（甚至更复杂的）派生解决方案来考虑大小，或者可能找到其他分析解决方案，而不必求解迭代。 编辑：由于高阶，方程的一些解实际上是 最远分离时刻。我认为在所有情况下，3个解中的1个或2个解将是最远分离的时间。您可以通过在找到使第一导数为零的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时，距离处于最小值而不是最大值。

- tcovo

---

谢谢tcovo，这是我需要的好的开始。您有没有想过如何将维基百科上的三次方程解法扩展到向量系数？ - RBarryYoung

我在一些简单的情况下测试了数学问题，并发现（1）有一个打字错误，（2）求导方程的解可能会找到最远分离的时间，这不是我们要寻找的（这并不奇怪，因为将导数设置为零通常会找到极值）。我编辑了我的回答。 - tcovo

考虑使用不等式来保守地消除常见情况：如果 |p1-p0| - |v1-v0|t - |a1-a0|t^2/2 > r1+r2，则不存在碰撞风险。 - comingstorm

回复：最远分离：是的，我知道这一点。还需要检查的其他事项包括(t)解在当前时间增量范围之外，以及它在碰撞状态下开始（或结束）(即边界/初始条件)。 - RBarryYoung

comingstorm: 这是一个很好的例子，但我希望有一个测试可以避免距离（“| 向量 |”）计算中的 SquareRoot()。也就是说，基于 Distance^2 的一些方法。 - RBarryYoung

Answer 2

在每个球的起始位置和结束位置之间画一条线。如果结果的线段相交，则这些球体肯定在某个时间点发生了碰撞，而一些巧妙的数学方法可以找到碰撞发生的时间。还要确保检查线段之间的最小距离（如果它们不相交）是否小于2倍半径。这也表示有碰撞发生。

从那里开始，您可以回溯您的delta时间，让它恰好在碰撞时发生，以便正确计算力。

您是否考虑过使用已经完成此工作的物理库？许多库使用更先进和更稳定（更好的积分器）的系统来解决您正在处理的方程组。 Bullet Physics 是一个不错的选择。

- basszero

---

再次强调，“线段”假设我的增量运动方程是：（obj.POS = obj.POS （obj.VEL * dT）}，这是线性的。我的增量运动方程是二次的*，需要解决“抛物线段”的最小分离距离。这需要完全不同（并且更困难）的公式。 - RBarryYoung

我不考虑使用别人的物理库，因为我的主要目标之一就是自己实现。此外，在我对开源物理引擎进行的简要调查中，并没有发现任何一个能够充分处理具有与距离的平方反比变化的对象加速度（即行星引力，它们都假定恒定加速度，最多只是大致近似），或者具有速度限制的效果和可见性传播（即光速/相对论），也没有合理的方法来添加它们。这两点对于我的模拟是必要的。 - RBarryYoung

我不知道你想要多准确...如果 dt 足够小，你可以把 delta 位置看作线段吗？ - basszero

Answer 3

op要求碰撞时间。稍微不同的方法可以精确计算...

记住位置投影方程：

NEW_POS = POS + VEL * t + (ACC * t ^ 2) / 2

如果我们将POS替换为D_POS = POS_A-POS_B，VEL替换为D_VEL = VEL_A-VEL_B，并且对于物体A和B，ACC=ACC_A-ACC_B，则会得到：

$D_NEW_POS=D_POS+D_VEL*t+(D_ACC*t^2)/2

这是对象之间的向量距离公式。为了得到它们之间的平方标量距离，我们可以取这个方程的平方，展开后看起来像：

distsq(t) = D_POS^2+2*dot(D_POS,D_VEL)*t + (dot(D_POS, D_ACC)+D_VEL^2)*t^2 + dot(D_VEL,D_ACC)*t^3 + D_ACC^2*t^4/4

为了找到碰撞发生的时间，我们可以将方程设置为半径和的平方和，并解出t：

0 = D_POS^2-(r_A+r_B)^2 + 2*dot(D_POS,D_VEL)*t + (dot(D_POS, D_ACC)+D_VEL^2)*t^2 + dot(D_VEL,D_ACC)*t^3 + D_ACC^2*t^4/4

现在，我们可以使用四次方程公式解出这个方程。

四次方程公式将得到4个根，但我们只对实数根感兴趣。如果有一个双重实根，则两个对象在正好一个时间点触碰边缘。如果有两个实根，则对象在根1和根2之间持续重叠（即根1是碰撞开始的时间，根2是碰撞停止的时间）。四个实根意味着物体相互碰撞了两次，在根对1、2和3、4之间持续不断。

在R中，我使用polyroot()来解决问题，如下所示：

# initial positions
POS_A=matrix(c(0,0),2,1)
POS_B=matrix(c(2,0),2,1)
# initial velocities
VEL_A=matrix(c(sqrt(2)/2,sqrt(2)/2),2,1)
VEL_B=matrix(c(-sqrt(2)/2,sqrt(2)/2),2,1)
# acceleration
ACC_A=matrix(c(sqrt(2)/2,sqrt(2)/2),2,1)
ACC_B=matrix(c(0,0),2,1)
# radii
r_A=.25
r_B=.25
# deltas
D_POS=POS_B-POS_A
D_VEL=VEL_B-VEL_A
D_ACC=ACC_B-ACC_A


# quartic coefficients
z=c(t(D_POS)%*%D_POS-r*r, 2*t(D_POS)%*%D_VEL, t(D_VEL)%*%D_VEL+t(D_POS)%*%D_ACC, t(D_ACC)%*%D_VEL, .25*(t(D_ACC)%*%D_ACC))
# get roots
roots=polyroot(z)
# In this case there are only two real roots...
root1=as.numeric(roots[1])
root2=as.numeric(roots[2])

# trajectory over time
pos=function(p,v,a,t){
  T=t(matrix(t,length(t),2))
  return(t(matrix(p,2,length(t))+matrix(v,2,length(t))*T+.5*matrix(a,2,length(t))*T*T))
}

# plot A in red and B in blue
t=seq(0,2,by=.1) # from 0 to 2 seconds.
a1=pos(POS_A,VEL_A,ACC_A,t)
a2=pos(POS_B,VEL_B,ACC_B,t)
plot(a1,type='o',col='red')
lines(a2,type='o',col='blue')

# points of a circle with center 'p' and radius 'r'
circle=function(p,r,s=36){
  e=matrix(0,s+1,2)
  for(i in 1:s){
    e[i,1]=cos(2*pi*(1/s)*i)*r+p[1]
    e[i,2]=sin(2*pi*(1/s)*i)*r+p[2]
  }
  e[s+1,]=e[1,]
  return(e)
}

# plot circles with radius r_A and r_B at time of collision start in black
lines(circle(pos(POS_A,VEL_A,ACC_A,root1),r_A))
lines(circle(pos(POS_B,VEL_B,ACC_B,root1),r_B))
# plot circles with radius r_A and r_B at time of collision stop in gray
lines(circle(pos(POS_A,VEL_A,ACC_A,root2),r_A),col='gray')
lines(circle(pos(POS_B,VEL_B,ACC_B,root2),r_B),col='gray')

物体A从左下角沿红色轨迹向右上方移动，物体B从右下角沿蓝色轨迹向左上方移动。两个物体在时间 0.9194381 到时间 1.167549 之间持续碰撞。两个黑色圆圈刚好接触，表示重叠的开始 - 重叠在时间上持续到物体到达灰色圆圈位置为止。

- thayne

Answer 4

看起来你想要最接近点 (CPA)。如果它小于半径之和，那么就会发生碰撞。链接中有示例代码。您可以使用当前速度计算每个帧，并检查CPA时间是否小于您的tick大小。您甚至可以缓存cpa时间，并且只在任一项应用加速度时更新。

- AShelly

---

是的，我知道这个方法。不幸的是，据我所知，它不能解决我的方程2（即带有加速度的方程），它只能解决对物体进行速度增量应用的问题。我的引擎使用速度和加速度的增量应用于物体，因此需要一个不同的（高阶）公式来解决它。 - RBarryYoung

你的时间间隔（dT）是多长？对于我看过的大多数模拟，它足够小，以至于(obj.ACC * dT^2)/2这个术语在任何单个tick中都可以忽略不计，至少对于碰撞检测来说是这样。 - AShelly

目前每个刻度是1/10秒，但这是可参数化的，可能会改变。更糟糕的是，加速度可以超过100 G，并且有时很可能发生。 - RBarryYoung