Predictive Collision Detection

The Problem

On certain applications, specially games, it is often necessary to determine if two moving objects collide. The standard approach is to check for overlap after each step of the animation. While this approach may be sufficiently accurate for some applications, sometimes you need to determine the exact point of collision so that you can apply collision forces or handle the situation more accurately. Also, if objects are moving too fast the overlap approach may miss the collision entirely.

Here we will have a look at a predictive, or a priori, technique specially suited for particles or small objects. It detects collisions even if the bodies are moving fast and it's pretty accurate at determining the collision point.

Line Segment Intersection

Suppose you have two particles. In a particular simulation step of size Δt, one particle goes from p0 to pf while the other goes from q0 to qf. We assume that the particles follow a straight line during this step. If the step size is small, and it should be, then this is a good approximation even if the particles are not traveling at constant velocity.

We want to find the point c where the two line segments intersect, if it exists. For this we parametrize the line segments:
p(t) = p0 + t(pf - p0)
q(s) = q0 + s(qf - q0)
where the parameters t and s go between 0 and 1. p(0) is the point of the first particle at the start of the step and p(1) is the point at the end of the step.

Now we need to find the values of s and t such that p(t) = q(s). To do this we start by equating the parametric equations:
p0 + t(pf - p0) = q0 + s(qf - q0)

To simplify, lets define Δp = pf - p0 and Δq = qf - q0. Rearranging, we get tΔp - sΔq = q0 - p0. In two dimensions this is a linear matrix equation where we can apply Cramer's rule. The solution is
t = [Δqy(q0x-p0x) - Δqx(q0y-p0y)] / d
s = [Δpx(q0y-p0y) - Δpy(q0x-p0x)] / d
where d = ΔpxΔqy - ΔpyΔqx.

If d is zero it means the line segments are parallel, either there cannot be a collision or the segments collide at an infinite number of points. If the values we get for t and s lie outside the range [0, 1] it means that there was no collision within the step's duration. If we find that both t and s lie in the range we can apply the parametric equation to find the point of collision.

In three dimensions you solve the 2D system on an arbitrary plane (e.g. using only the x and y components) and then add an extra check to see if the third component matches.

Here is the code:

bool intersection(const Point& p0, const Point& pf, const Point& q0, const Point& qf, Point& col_point) {
  float Dpx = pf.x - p0.x;
  float Dpy = pf.y - p0.y;
  float Dqx = qf.x - q0.x;
  float Dqy = qf.y - q0.y;
  float d = Dpx*Dqy - Dpy*Dqx;
  if (d == 0.f)
    return false;

  float t = (Dqy*(q0.x - p0.x) - Dqx*(q0.y - p0.y)) / d;
  float s = (Dpx*(q0.y - p0.y) - Dpy*(q0.x - p0.x)) / d;
  if (t < 0.f || t > 1.f || s < 0.f || s > 1.f)
    return false;

  col_point.x = p0.x + t * (pf.x - p0.x);
  col_point.y = p0.y + t * (pf.y - p0.y);

#ifdef THREE_D
  col_point.z = p0.z + t * (pf.z - p0.z);
  float alt_z = q0.z + s * (qf.z - q0.z);
  return std::abs(alt_z - z) < EPSILON;
#else
  return true;
#endif
}

Spheres

The previous method has two noticeable problems: first it assumes that the bodies have no extension, second it doesn't take into account the time it takes a body to move from the origin to the destination. The fact that the trajectories intersect not necessarily means that the objects collided because they may have gone through that point at different times.

To address these problems we will use the same technique as before but with a couple of modifications. First we will take into account the size of the bodies, assuming they are spheres of radii r1 and r2. Second we will require the parameters s and t to be equal. This improved method has a lot in common with the previous but the math is a bit more involved so I will skip over some of the more involved details.

The equation we will try to solve now is |p(t) - q(t)|2 = (r1+r2)2. What this says is that the distance between the bodies at time t should be equal to the sum of their radii. Here again the parameter t goes between 0 and 1, and can be seen as a normalized time.

To solve this we expand the squares, do some magic, and arrive to
t2|Δq-Δp|2 + 2t(q0-p0)•(Δq-Δp) + |q0-p0|2 = (r1+r2)2
This is a quadratic equation whose solutions are given by the quadratic formula: t = [-b ± (b2-4ac)½] / 2a. In this case
a = |Δq-Δp|2
b = 2(q0-p0)•(Δq-Δp)
c = |q0-p0|2 - (r1+r2)2

There might be more that one solution with a value of t between 0 and 1, in that case you should choose the solution with the smallest value of t, that will be the first contact point. If we inject t back into the parametric equations it will give us back the collision point for each body. You can also find the absolute collision time: col_time = sim_time + t Δt, where sim_time is the simulation time before the current step and Δt is your step size.

Conclusion

The method presented may be more expensive than doing a simple overlap check but it is also much more accurate. It also gives precise information about the collision point and time. The biggest drawback is that it assumes spherical objects. A possible extension to general polygons is to run the algorithm for each vertex, but that may be too computationally intensive.