Predicting trajectory collisions for multiple moving objects [duplicate]

Very simply, if you define the minimum distance between two moving bounding volumes as a function of time, D(t), then the roots (a.k.a. zeros) of that function are obviously the set of times, {t₁, t₂, ... t_n}, when the distance between the volumes is exactly zero, D(t₁)=0, D(t₂)=0, ... D(t_n)=0. If the volumes collide at some time in past or future, then one or more of those roots will be real. The smallest real root that is greater than or equal to the current time can usually be described as the time of the initial collision between the two volumes. If the volumes never collide in the past or future, then D(t) will have no real roots, because it is never equal to zero anywhere at any time, in which case it will only have imaginary roots. So, simply by examining the presence or lack of real roots in the distance function, you can determine if a collision occurs or not.

Polynomial functions up to degree 3 (i.e. "cubic"; ax³+bx²+cx+d) have well-defined roots that can be derived algebraically very easily. Polynomials of degree 4 (a.k.a. quartic) also have a relatively straight forward solution for their roots which was provided by Lodovico Ferrari, so it is sometimes called Ferrari's Method. For functions that are more complex than that, you can use Newton's method to systematically find roots between some t_min and t_max. Newton's method actually is somewhat ideal for collision detection, since we are usually only concerned with finding collisions between some known time interval. There's almost never any need to hunt down all of the roots for this application. Furthermore, the precision that we require for collision events often isn't very high. The precision of the root being computed can be tuned in Newton's method by simply increasing or decreasing the number of iterations spent in its loop.