Circle Collision Detection - Non-Linear Trajectories

Last week I promised we'd take a quick look at collisions between two circles or spheres traveling on non-linear trajectories. So, today we're going to derive the time of collision of two circles moving on parabolic (i.e. quadratic) trajectories.

This is probably one of the most difficult problems that you can solve algebraically. When we start talking about collisions between moving parametric geometry, such as two moving lines and planes, then we'll have to resort to other methods, such as iterative solvers, because the distance equations just become too complex to work with directly. In fact, I'm not even going to go through the entire derivation of this parabolic trajectory problem with you here, since that would just take too much time.

Diagram 1: Two circles on parabolic trajectories collide at some point in the future.

We'll set up the problem exactly the same way as we set up the linear-trajectory problem, except this time we will introduce an acceleration term into the trajectory equations. The circle's (or sphere's) initial positions are Pa and Pb, their velocity vectors are Va and Vb, and now their acceleration vectors are Aa and Ab. Once again, the parametric variable, t, represents time in this problem.

The distance between the two trajectory curves is given by the same equation that we used in the linear-trajectory problem:

But, when we expand this out, the equation is not a nice quadratic equation (i.e. a 2nd degree polynomial). Instead, what we get is a nasty quartic equation (i.e. a 4th degree polynomial), the roots of which are infinitely more difficult to compute.

When we set d(t) to zero and expand, here is what we get:

It's easier to see the quartic equation after we collapse the coefficients into single variables. Here is the equation we need to solve:

I'm not going to go through the derivation of the quartic roots, because it's not easy, and it's also a bit beyond the scope of this discussion anyway. The roots of the quartic equation were first derived by an Italian mathematician named Lodovico Ferrari back in the mid 16th century. The expanded solution is pretty hairy (courtesy of Mathematica)...

t = -(b/(4 a))-1/2 Sqrt(b^2/(4 a^2)-(2 c)/(3 a)+(2^(1/3) (c^2-3 b d+12 a e))/(3 a (2 c^3-9 b c d+27 a

d^2+27 b^2 e-72 a c e+Sqrt(-4 (c^2-3 b d+12 a e)^3+(2 c^3-9 b c d+27 a d^2+27 b^2 e-72

a c e)^2))^(1/3))+(1/(3 2^(1/3) a))((2 c^3-9 b c d+27 a d^2+27 b^2 e-72 a c e+Sqrt(-4 (c^

2-3 b d+12 a e)^3+(2 c^3-9 b c d+27 a d^2+27 b^2 e-72 a c e)^2))^(1/3)))-1/2 Sqrt(b

^2/(2 a^2)-(4 c)/(3 a)-(2^(1/3) (c^2-3 b d+12 a e))/(3 a (2 c^3-9 b c d+27 a d^2+27 b^2 e-72 a c e+Sqrt(

-4 (c^2-3 b d+12 a e)^3+(2 c^3-9 b c d+27 a d^2+27 b^2 e-72 a c e)^2))^(1/3))-(1/(3 2^(1/3) a))((2 c

^3-9 b c d+27 a d^2+27 b^2 e-72 a c e+Sqrt(-4 (c^2-3 b d+12 a e)^3+(2 c^3-9 b c d+27 a d^2+

27 b^2 e-72 a c e)^2))^(1/3))-(-(b^3/a^3)+(4 b c)/a^2-(8 d)/a)/(4 Sqrt(b^2/(4 a^2)-(2 c)/(3 a)+(2^(1/3) (c^2-3 b d+12

a e))/(3 a (2 c^3-9 b c d+27 a d^2+27 b^2 e-72 a c e+Sqrt(-4 (c^2-3 b d+12 a e)^3+(2 c^3-9 b c d+27 a d^2+

27 b^2 e-72 a c e)^2))^(1/3))+(1/(3 2^(1/3) a))((2 c^3-9 b c d+27 a d^2+27 b^2 e-72 a c e+Sqrt(-4 (

c^2-3 b d+ 12 a e)^3+(2 c^3-9 b c d+27 a d^2+27 b^2 e-72 a c e)^2))^(1/3)))))

(if you can read this you need your eyes examined)

And that's just one of four possible roots. But, it's not as bad as it looks. Ferrari realised that he could use the same trick that Nicolo Fontana Tartaglia used to find the roots of a general cubic polynomial, by converting the quartic equation into a depressed form to reduce the number of roots and then converting that into a series of nested cubic and quadratic polynomials which have much simpler roots. It's definitely not as easy as it sounds, but, if you have a few brain cells and a couple hours to kill, Ferrari's solution is a very interesting problem to work through. It is published in dozens of texts and on the web. I just pulled the solution off of Wikipedia... it might actually be the only formula on Wikipedia that is actually correct.

Here is Ferrari's solution:

The next value, y, has a conditional statement that arises due to a singularity. If U is zero, or really, really close to zero, then variable y has a solution that avoids the division-by-zero in the (P / 3U) term.

Finally, the four possible roots of the quartic equation are given by the following four equations:

The time of the initial impact, if there is one, is one of these four roots. Since we're only interested in the initial time of impact, all we need to do is find the smallest, real, root that is greater than or equal to zero. And, that's all there is to it.

Conclusion

I've coded this solution into a demo. The demo is coded, once again, in C#.NET using the XNA framwork to render the graphics. The demo lets you play around with the quartic solver in a neat little GUI. The full source code and Visual Studio C# Express project are available here:

http://code.google.com/p/xna-circle-collision-detection/downloads/list

Diagram 2: The parabolic trajectory solution is a generalization of the linear trajectory solution.
Simply set the length of the acceleration vectors to zero.

Circle Collision Detection - Linear Trajectories

Calculating the time of impact or time of closest approach of two moving circles or spheres is a common problem in game physics. The solution to this problem can be used to solve the collisions of billiard balls on a pool table, the collision of a bullet fired with high velocity at a target in the distance, or a number of other common game scenarios in which the exact time and location of impact must be known with a high degree of accuracy.

It's a simple enough problem to solve as long as we enforce a couple key constraints. First, we assume that the circles or spheres will be moving at some constant linear velocity. Secondly, we assume that they don't change size; their radius remains constant. In the future, I'll talk about how to solve collisions between circles or spheres with non-linear trajectories and variable radii. But, for now, let's set up the problem with these constraints in mind.

Diagram 1: Two moving circles collide at some point in the future.

The first step to solving this problem is to write down the functions that describe the linear trajectories of the objects. If we let Pa and Pb be the initial positions of two circles or spheres, A and B, and let Va and Vb be the linear velocity of A and B, then their position at any time, t, are the linear parametric functions A(t) and B(t):

Next, we need the function that describes the distance between the two trajectories at any time, t. That function is simply the Euclidean distance between A(t) and B(t) minus the sum of the circle's radii, Ra and Rb.
The goal is to find time, t, where d(t) = 0. In other words, we need to find the roots of d(t). As it turns out, d(t) is quadratic, so the roots will be easy to find. We can simply expand the equation, find the quadratic terms, and then use the quadratic formula to find the roots.

We start the expansion by setting d(t) to zero and replacing the straight bracket term with the Euclidean formula.
The first step we're forced to make is to move the (Ra + Rb) term to the left side and then square both sides to eliminate the square root.
Next, we'll substitute in the equations for A(t) and B(t), combine like terms, and then collapse the position and velocity terms into single variables. This will give us a very simple equation that we can easily expand into a quadratic form.
Now we can expand the right-hand side without it being too gnarly. We'll also move the (Ra+Rb) term back to the right side. An important thing to remember here is that Pab and Vab are vector terms, so when we expand the square we use the Dot Product instead of multiplication. This is perfectly valid for two reasons: First, the dot product of a vector dotted with itself is the length of the vector squared (i.e. a.a = |a|*|a|). Second, the dot product operation is distributive (i.e. a.(b+c) = a.b + a.c). So, when we expand the right-hand side, here is what we get:

It's a nice, neat quadratic equation with simple terms. We can now pump the terms into the quadratic formula and find the roots.
There are three cases that arise from the quadratic formula. The first case is where there are no real roots. The second case is when there is exactly one real root. And the third, and final, case is where there are exactly two real roots. These cases are decided by the value of the quadratic discriminant.
Case #1: Discriminant is negative.
If the discriminant is negative, then d(t) has no real roots. The circles do not intersect at any time in the past or future. They either pass each other or are traveling with parallel trajectories. In this case, two imaginary roots are created. These complex roots are conjugates of each other. In the special case of quadratic functions, they are always precisely the same distance away from the critical point that marks the time where the distance function is minimized. Therefore, the time of closest approach is literally the average of these two imaginary roots.

However, a better way to get the location of the critical point is to take the first-derivative of the function, set it equal to zero, and solve for t. Either way, we'll get the same answer in this case.
Time, t, in this case is the time of closest approach of the two circles or spheres.

Diagram 2: The circles never intersect.

Case #2: Discriminant is zero.
If the discriminant is zero, then there is exactly one real root. That means that the circles or spheres just barely graze each other at a single point. In this case, everything under the square root in the quadratic formula goes away, and you're left with the same answer as in case #1.
But, the meaning of this time is different than in the first case. In this case, t is the exact time of the collision event.

Diagram 3: The circles graze each other.

Case #3: Discriminant is positive.
If the discriminant is positive, then there are exactly two real roots. That means that the circles or spheres pass through each other at some point in the past or future. The roots are the times when the distance between the object's surfaces equals zero. The root that produces the smallest time is the initial impact.
Time, t, in this case is the time of the initial impact.

Diagram 4: The circles hit head-on and will pass through each other.

Conclusion
In all three cases, it's worth noting that the time that is calculated can be negative, which means that the event occurred in the past. But, because most games are only concerned with future collision events, you may want to include a conditional statement in your program that returns a "no collision" response in that case.

I would like to start a series of posts describing in detail the time of closest approach of other primitives, including cones and planes. I may write a few articles on difficult collision detection problems solved via Lagrangian methods and iterative optimization techniques.

Please feel free to e-mail me or post a comment here in this blog if you find any errors or have any concerns with the material presented here. I always try to be accurate with everything I say, but I'm not a mathematician. Sometimes I end up being right, but for the wrong reasons. And, sometimes, I'm just totally wrong. :)

Demo
I created an interactable demonstration program coded in C# for Microsoft's XNA framework. You can download that demo from the Google Code archive here:
http://code.google.com/p/xna-circle-collision-detection/downloads/list


Thank you for reading. I hope you've found this information useful. :)

My Blog and Me

Programming is the science of making statistically random binary digits generate money for large corporations.

Welcome to my coder blog. I don't have a schedule or vector for this thing, so I'll be using it to post random thoughts of madness from time-to-time. Any time that I have an idea or a project that can be made public, I'll try to toss it up here.

Please don't hesitate to leave comments or send me an e-mail if you have any questions or problems with anything on this blog. As usual, I'm always happy to lend a hand or give out free advice.

-- Brian Stone