碰撞检测加速球面间 [英] Collision Detection between Accelerating Spheres
问题描述
我写一个物理引擎/仿真器，其采用了三维空间飞行，行星/恒星的引力，船舶推力和相对论效应。到目前为止，这是进行得非常顺利，然而，一件事，我需要帮助的碰撞检测algorithim的数学。
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 algorithim.
迭代模拟，我使用的运动基本上是如下：
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
我基本上需要做的是找到一些有效的公式，源自（式（2）的），上面的两个对象（OBJ1，OBJ2），并告诉我们，如果他们曾经发生碰撞，如果是这样，在什么时候。我需要的确切时间既让我能确定它是否是在这个特定的时间增量（因为accelleratons会在不同的时间增量不同），也让我能找到确切的位置（我知道该怎么做，考虑到时间）
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 accelleratons 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)
有关这款发动机，我模拟的所有对象的领域，这一切的公式/ algortithim需要做的是找出在什么点：
For this engine, I am modelling all objects as spheres, all this formula/algortithim 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），这是不够的，我检查*前的时间增量后路口的两个球体*。在许多情况下，他们的速度和位置的变化会远远超过他们的半径。
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）我的公式（式（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
这是我所见过的物理引擎，（当然，我听说过的每一个游戏引擎）只的线性的适用增量运动方程的只有的速度：
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解决方案，以最接近的方法，这并不奇怪，因为这两个对象的路径是弯曲的，以便多个交叉点是可能的时间。对于这种应用中，可能会希望使用吨的其是由当前的仿真步骤中定义的时间间隔内的最早值（如果这样的时间存在的话）。
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 *点（D_ACC，D_VEL）* T ^ 2 + 2 * [| D_VEL | ^ 2 +点（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 （也更新之前）
和点（A，B）=斧* Bx的+好哦*通过+了Az * BZ
（注意幅度的平方 | A | ^ 2 可以使用计算点（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.
当然，这样只会给你的最接近的那一刻的。您将需要（使用类似公式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.
修改：由于高阶，一些解决方案，以公式实际上是最远的分离的时刻。相信在所有情况下是1的3溶液或2的3解决方案将分离最远的一个时间。可以解析是否是在一分钟或一最大通过评估所述第二导数相对于时间（在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 *点（D_ACC，D_VEL）* T + 2 * [| D_VEL | ^ 2 +点（ 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屋！
