Take the 2-minute tour ×

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:

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



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

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)

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)

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

(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.)

Some Clarifications:

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: 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) My equation (EQ.2) of incremental movement is a quadratic equation that applies both Velocity and Acceleration:


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)

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.

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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

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 * dot(D_POS, D_VEL)


D_ACC = ob1.ACC-obj2.ACC

D_VEL = ob1.VEL-obj2.VEL (before update)

D_POS = ob1.POS-obj2.POS (also before update)

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

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

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

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.

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

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.

share|improve this answer
thanks tcovo, this is a good start on exactly what I need. Any idea how to extend the cubic equation solution at Wikipedia to vector coefficients? –  RBarryYoung Dec 16 '09 at 20:49
The cubic equation I wrote has scalar coefficients: the dot product of two vectors is a scalar, and the square of the magnitude is also a scalar. I edited my response to elaborate on those. –  tcovo Dec 17 '09 at 0:07
Ah, great! Thanks... –  RBarryYoung Dec 17 '09 at 0:29
I tested the math on some simple cases and found (1) a typo and (2) that the solution to the derivative equation might find the times of farthest separation, which is not what we're looking for (not surprising, since setting the derivative to zero finds extrema, in general). I edited my response. –  tcovo Dec 17 '09 at 1:50
Consider using inequalities to conservatively eliminate the common case: if |p1-p0| - |v1-v0|t - |a1-a0|t^2/2 > r1+r2 then there is no risk of collision. –  comingstorm Dec 17 '09 at 3:22

Draw a line between the start location and end location of each sphere. If the resulting line segments intersect the spheres definitely collided at some point and some clever math can find at what time the collision occurred. Also make sure to check if the minimum distance between the segments (if they don't intersect) is ever less than 2*radius. This will also indicate a collision.

From there you can backstep your delta time to happen exactly at collision so you can correctly calculate the forces.

Have you considered using a physics library which already does this work? Many libraries use far more advanced and more stable (better integrators) systems for solving the systems of equations you're working with. Bullet Physics comes to mind.

share|improve this answer
Again, "Line Segments" assumes that my equation of incremental movement is: ( obj.POS = obj.POS * (obj.VEL * dT) }, which is Linear. My incremental movement equation is Quadratic, which requires solving for the minimum separation of "Parabolic Segments". It requires a completely different (and more difficult) formula. –  RBarryYoung Dec 16 '09 at 18:07
I am not considering using someone else's physics library because one of my main goals is to do this myself. Additionally, my brief survey of Open Source physics engines did not turn up any that adequately dealt with either object accelerations that varied with the inverse square of their distance (i.e., planetary Gravity, they all assume constant acceleration, at best) or with speed-limited effects and visibility propagation (i.e., the speed of light/relativity), nor any reasonable way too add them on. Both of these are necessary for my simulation. –  RBarryYoung Dec 16 '09 at 18:16
I don't know how accurate you're trying to be ... for a small enough dt can you treat the delta position as line segment? –  basszero Dec 16 '09 at 19:18

Seems like you want the Closest Point of Approach (CPA). If it is less than the sum of the radiuses, you have a collision. There is example code in the link. You can calculate each frame with the current velocity, and check if the CPA time is less than your tick size. You could even cache the cpa time, and only update when acceleration was applied to either item.

share|improve this answer
Yes, I know this method. Unfortunately, AFAIK it does NOT solve for my equation 2 (i.e., with acceleration), it only solves for the incremental application of Velocity to the objects. My engine uses the incremental application of Velocity AND Acceleration to the objects and thus requires a different (higher-order) formula to solve it. –  RBarryYoung Dec 16 '09 at 17:56
How long is your tick (dT)? For most simulations I've seen, it's small enough that the (obj.ACC * dT^2)/2 term is negligable for any single tick, at least for the purposes of collision detection. –  AShelly Dec 16 '09 at 18:33
The ticks are 1/10th second right now, but that's parameterizable and could change. Worse is the fact that accelerations of over 100 G's are both possible and at times likely. –  RBarryYoung Dec 16 '09 at 19:00

Your Answer


