代码之家 › 专栏 › 技术社区 › RBarryYoung

加速球碰撞检测

collision-detection physics simulation 3d math

RBarryYoung · 技术社区 · 15 年前

我正在写一个包含三维空间飞行、行星/恒星引力、船舶推力和相对论效应的物理引擎/模拟器。到目前为止,它进展得很顺利,但是,有一件事我需要帮助,那就是碰撞检测算法的数学。

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

(注:三维矢量都是大写的。)

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

我基本上需要做的是找到一个有效的公式( 情商2 )上面是两个物体(obj1,obj2)的图,告诉他们是否曾经碰撞过,如果碰撞过,在什么时候。我需要准确的时间,这样我就可以确定它是否在这个特定的时间增量中(因为加速度在不同的时间增量中会不同),也可以确定准确的位置(我知道如何做,给定时间)

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

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

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

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

一些澄清:

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

2)回复:效率,我不需要帮助(无论如何,在这一点上)来确定可能的碰撞候选,我认为我已经涵盖了这一点。

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

3)我的方程式( 情商2 )增量运动是一个二次方程,适用于两种速度和加速度:

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

我见过的物理引擎(当然还有我听说过的所有游戏引擎)都是 线性的 应用的增量运动方程只有速度:

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

这就是为什么我不能使用在stackoverflow、wikipedia和整个网络上常见的冲突检测解决方案的原因,例如查找两个线段的交叉点/最近的接近点。我的模拟处理对结果至关重要的可变加速度,所以我需要的是交叉口/最近的两个 抛物线的 部分。

4 回复 | 直到 6 年前

tcovo 15 年前

在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) )

为了解决这个问题 T ,您可能需要使用类似的公式 found on Wikipedia .

当然,这只会给你 最近进近 .此时您需要测试距离(使用公式2)。如果大于 (obj1.Radius + obj2.Radius) 可以忽略(即没有碰撞)。但是,如果距离较小,这意味着球体在此时刻之前发生碰撞。然后您可以使用迭代搜索在早期测试距离。它也可能会提出另一个(甚至更复杂的)推导,考虑到规模,或可能找到一些其他的分析解决方案,而不诉诸于迭代求解。

编辑 :由于高阶,方程的一些解实际上是 最远间隔 . 我相信在所有情况下,3种溶液中的1种或3种溶液中的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内,距离是最小的,而不是最大的。

basszero 15 年前

在每个球体的开始位置和结束位置之间画一条线。如果得到的直线段与球体相交,那么球体肯定会在某个点上发生碰撞,并且可以通过一些巧妙的数学方法找到碰撞发生的时间。还要确保检查段之间的最小距离(如果它们不相交)是否始终小于2*半径。这也表明发生了碰撞。

从那里你可以倒退三角洲时间,使之恰好在碰撞时发生,这样你就可以正确地计算力了。

你有没有考虑过使用一个已经起作用的物理图书馆?许多库使用更高级、更稳定(更好的积分器)的系统来求解您正在使用的方程组。 Bullet Physics 浮现在脑海中。

AShelly 15 年前

似乎你想要 Closest Point of Approach (CPA) . 如果它小于半径之和,就会发生碰撞。链接中有示例代码。您可以用当前速度计算每个帧,并检查CPA时间是否小于您的刻度线大小。您甚至可以缓存CPA时间,并且仅当加速应用于任一项时才进行更新。

thayne 6 年前

OP要求碰撞时间。一个稍微不同的方法将精确计算它…

记住位置投影方程是:

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

如果我们替换 POS 具有 D_POS=POS_A-POS_B , VEL 具有 D_VEL=VEL_A-VEL_B 和 ACC=ACC_A-ACC_B 对于对象 A 和 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

现在,我们可以用 quartic formula .

四次公式将产生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')

对象 一 沿着红色轨迹从左下到右上。对象 乙 沿着蓝色轨迹从右下到左上。两个物体在时间0.9194381和时间1.167549之间不断碰撞。这两个黑色圆圈刚好接触,显示重叠的开始-和重叠的时间继续,直到对象到达灰色圆圈的位置。