加速球体之间的碰撞检测 [英] Collision Detection between Accelerating Spheres

问题描述

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

I am writing a physics engine/simulator which incorporates 3D space flight, planetary/stellar gravitation, ship thrust and relativistic effects. So far, it is going very well, however, one thing that I need help with is the math of the collision detection algorithm.

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

The iterative simulation of movement that I am using is basically as follows:

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

(Note: 3D Vectors are ALL CAPS.)

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) 找到一些有效的公式，并判断它们是否发生碰撞，如果发生碰撞，在什么时候.我需要确切的时间，以便我可以确定它是否在这个特定的时间增量中(因为加速度在不同的时间增量下会有所不同)，并且还可以定位准确的位置(我知道如何做，鉴于时间)

What I basically need to do is to find some efficient formula that derives from (EQ.2) above for two objects (obj1, obj2) and tell if they ever collide, and if so, at what time. I need the exact time both so that I can determine if it is in this particular time increment (because acceleration will be different at different time increments) and also so that I can locate the exact position (which I know how to do, given the time)

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

For this engine, I am modelling all objects as spheres, all this formula/algorithm needs to do is to figure out at what points:

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

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

where .Distance is a positive scalar value. (You can also square both sides if this is easier, to avoid the square root function implicit in the .Distance calculation).

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

(yes, I am aware of many, many other collision detection questions, however, their solutions all seem to be very particular to their engine and assumptions, and none appear to match my conditions: 3D, spheres, and acceleration applied within the simulation increments. Let me know if I am wrong.)

一些说明:

1) 在时间增量前后检查两个球体的 Intersection 对我来说是不够的.在许多情况下，它们的速度和位置变化将远远超过它们的半径.

1) It is not sufficient for me to check for Intersection of the two spheres before and after the time increment. In many cases their velocities and position changes will far exceed their radii.

2) RE:效率，我不需要帮助(无论如何在这一点上)确定可能的碰撞候选者，我想我已经涵盖了.

2) RE: efficiency, I do not need help (at this point anyway) with respect to determine likely candidates for collisions, I think that I have that covered.

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

Another clarification, which seems to be coming up a lot:

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

3) My equation (EQ.2) of incremental movement is a quadratic equation that applies both Velocity and Acceleration:

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

在我见过的物理引擎(当然还有我听说过的每个游戏引擎)中，只有线性增量运动方程仅应用速度:

In the physics engines that I have seen, (and certainly every game engine that I ever heard of) only linear equations of incremental movement that apply only Velocity:

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

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

This is why I cannot use the commonly published solutions for collision detection found on StackOverflow, on Wikipedia and all over the Web, such as finding the intersection/closest approach of two line segments. My simulation deals with variable accelerations that are fundamental to the results, so what I need is the intersection/closest approach of two parabolic segments.

推荐答案

在 AShelley 引用的网页上，最近点方法是针对两个物体匀速运动的情况开发的.但是，我相信相同的向量演算方法可以用于在两个物体都以恒定的非零加速度(二次时间相关)移动的情况下推导出结果.

On the webpage AShelley referred to, the Closest Point of Approach method is developed for the case of two objects moving at constant velocity. However, I believe the same vector-calculus method can be used to derive a result in the case of two objects both moving with constant non-zero acceleration (quadratic time dependence).

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

In this case, the time derivative of the distance-squared function is 3rd order (cubic) instead of 1st order. Therefore there will be 3 solutions to the Time of Closest Approach, which is not surprising since the path of both objects is curved so multiple intersections are possible. For this application, you would probably want to use the earliest value of t which is within the interval defined by the current simulation step (if such a time exists).

我计算出应该给出最接近方法的时间的导数方程:

I worked out the derivative equation which should give the times of closest approach:

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 * 点(D_POS，D_VEL)

哪里:

D_ACC = ob1.ACC-obj2.ACC

D_VEL = ob1.VEL-obj2.VEL(更新前)

D_POS = ob1.POS-obj2.POS(也在更新前)

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

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

(Note that the square of the magnitude |A|^2 can be computed using dot(A, A))

要为 t 解决这个问题，您可能需要使用类似 在维基百科上找到.

To solve this for t, you'll probably need to use formulas like the ones found on Wikipedia.

当然，这只会给您最接近的时刻.此时您需要测试距离(使用类似 Eq. 2 的方法).如果大于(obj1.Radius + obj2.Radius)，则可以忽略(即无碰撞).但是，如果距离更小，则意味着球体在这一刻之前发生了碰撞.然后，您可以使用迭代搜索在更早的时间测试距离.也可能想出另一个(甚至更复杂)的推导，将大小考虑在内，或者可能找到其他一些解析解，而无需求助于迭代求解.

Of course, this will only give you the moment of closest approach. You will need to test the distance at this moment (using something like Eq. 2). If it is greater than (obj1.Radius + obj2.Radius), it can be disregarded (i.e. no collision). However, if the distance is less, that means the spheres collide before this moment. You could then use an iterative search to test the distance at earlier times. It might also be possible to come up with another (even more complicated) derivation which takes the size into account, or possible to find some other analytic solution, without resorting to iterative solving.

编辑:由于阶数更高，方程的一些解实际上是最远分离的时刻.我相信在所有情况下，3 种解决方案中的一种或 3 种解决方案中的 2 种将是分离最远的时间.您可以通过评估相对于时间的二阶导数(通过将一阶导数设置为零而找到的 t 值)来分析测试您是处于最小值还是最大值:

Edit: because of the higher order, some of the solutions to the equation are actually moments of farthest separation. I believe in all cases either 1 of the 3 solutions or 2 of the 3 solutions will be a time of farthest separation. You can test analytically whether you're at a min or a max by evaluating the second derivative with respect to time (at the values of t which you found by setting the first derivative to zero):

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 内是最小值，而不是最大值.

If the second derivative evaluates to a positive number, then you know the distance is at a minimum, not a maximum, for the given time t.

这篇关于加速球体之间的碰撞检测的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！