[ Mælström ]

First-Order Collision Detection for Two Spherical Objects

From Collision.c; if you have Gnuplot, you can compile this and see,

No collision.

Collision.

This is the result of this calculation, where t, time, is normalised to go from 0 at the start, to 1 at the end (eg, of the frame.) p(t) and q(t) are the vector-valued paths of the two objects, indexed by time; p(0) = a, p(1) = b, q(0) = c, q(1) = d. Since this is a first-order method, we linearly interpolate p(t) and q(t),

t \in [0,1]
             u = b - a
             v = d - c
if(v-u ~= 0) t = doesn't matter, parallel
          p(t) = a + (b-a)t
          q(t) = c + (d-c)t
 distance(t)   = |q(t) - p(t)|
 distance^2(t) = (q(t) - p(t))^2
               = ((c+vt) - (a+ut))^2
               = ((c-a) + (v-u)t)^2
               = (v-u)*(v-u)t^2 + 2(c-a)*(v-u)t + (c-a)*(c-a)
             0 = 2(v-u)*(v-u)t_min + 2(c-a)*(v-u)
         t_min = -(c-a)*(v-u)/(v-u)*(v-u)

this is a linear optimisation; if t \notin [0,1] then pick the closest. r is one-half the sum of the two radii; if the distance of closest approach, distance^2(t_min) < r^2, then we have a collision, which happened at t0,

           r^2 = (v-u)*(v-u)t0^2 + 2(c-a)*(v-u)t0 + (c-a)*(c-a)
            t0 = [-2(c-a)*(v-u) - sqrt((2(c-a)*(v-u))^2
                 - 4((v-u)*(v-u))((c-a)*(c-a) - r^2))] / 2(v-u)*(v-u)
            t0 = [-(c-a)*(v-u) - sqrt(((c-a)*(v-u))^2
                 - ((v-u)*(v-u))((c-a)*(c-a) - r^2))] / (v-u)*(v-u)

Documents, including articles, coursework, stories, etc.

From http://neil.chaosnet.org/documents/collision/.