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