Monday, April 26, 2010

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:

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

3 comments:

DrJBN said...

Hello Mr Stone,
Very interesting blog topic you have going. Perhaps you can help me with a problem for which I have no clean solution.

An object (A) is pointing in an initial direction (Cur_dir) but will be moving toward another object (B) by lerping between its present direction and the present direction to B and moving in the new direction. Cur_dir, dir_AB, and A thus update each frame. B is static.


Dir_AB = normalize(b-a)
cur_dir = lerp(cur_dir,dir_AB,amt)
A += cur_dir * speed;

How can one determine how close A will come to another point D in its path to B?

If there is a solveable equation for that, I would be most appreciative!

Best,
Byron (DrJBN on the forums)
drJBN@hotmail.com

Brian Stone said...

Byron,

Thank you very much. I've been a bit distracted with other projects, but hopefully I'll be adding some more here soon.

The problem you've described is a really interesting one. If I'm reading the problem correctly, it's possible for point A to spiral into B potentially producing multiple solutions. It may even be indeterminate. The speed of the particle and the rate of interpolation will affect the solution set.

I can tell you pretty confidently that it won't likely have a closed-form solution. But, that's not to say we can't find an approximate solution, or a really fast iterative solution.

I'll have to mull this one over. You've given me a interesting problem to think about. I'll let you know if I come up with anything. :)

-Brian

DrJBN said...

I presently iterate through the path, but would like a more elegant solution.

The problem presented itself with spaceships that navigate using the algo described. Sometimes a ship would fly through the camera on its path to its target, even though the camera was not between the starting position and the target the lerp path took it through it anyway. So, I presently choose a target, run through the path, and choose a new target if the ship smacks the camera in the path. For one or two ships I have had no problems thus far.

One edit to the algo though,
A += normailze(cur_dir)*speed;

Best,
Byron

If you find a bug or a mistake in any of my posts or projects, please e-mail me and I'll do my best to correct them. :)

Copyright © 2010 Brian Stone
All Rights Reserved