Exact (integer arithmetic only) capsule intersection test

The capsule (also called a “pill”) is one of a few common types of shape used for collision detection in games and other applications. A 3-D capsule is a cylinder capped by hemispheres. The 2-D equivalent, a rectangle capped by semicircles, is technically called a stadium, but they are commonly just called capsules as well.

Capsules used for collision detection in Super Smash Bros. Melee.
Capsules used for collision detection in Super Smash Bros. Melee. From here.

Capsules are nice because they can form both spherical and elongated shapes in any direction. The animation above shows how Super Smash Bros. Melee uses spherical hitboxes that are “stretched” across frames into capsules to prevent fast-moving attacks from going through opponents without hitting them. (Marvel vs. Capcom 3 uses the same trick.) What really makes capsules useful is that they have a very simple mathematical description: a capsule is the set of all points less than a certain radius from a line segment. This means you can check whether two capsules intersect each other by just finding the shortest distance between the two line segments and checking whether it is less than the sum of the radii.

Calculating the distance between two line segments is a well-known problem. This StackOverflow answer gives the code to do that with floating-point arithmetic. Sometimes, though, approximating the correct answer with floating-point isn’t good enough. What if we want an exact intersection test for capsules using only integer arithmetic?

I’ll be giving code examples in Haskell. The code will be for 2-D capsules, but the 3-D case is not too different. Let’s start with some basic definitions using the vector-space package. Since we’re using integer arithmetic, all of our vectors and radii should have integer values only.

The first step of the line segment distance computation is to test whether the line segments intersect. The test shown in the StackOverflow answer doesn’t work for our purposes because it uses floating-point division and because it treats parallel segments as never intersecting. Instead, we can use the exact test from this page.

Now here’s the tricky bit. If the segments do not intersect, we can’t simply find the distance between them to check against the radii, because the shortest distance may not be an integer. The standard trick of doing all comparisons on squared distance values to avoid square root operations doesn’t completely solve the problem either, because the closest point on one segment to the other may not even have integer coordinates.

If we were using imprecise floating-point arithmetic, the test would look like this:

Since we’re using integer arithmetic, though, the (/) operator is banned. The trick to pulling this off with integers only is to scale both sides of the third inequality by segLenSq^2. This will cancel the denominator so that we don’t have to do any division. We can use primed variables to denote “multiplied by a factor of segLenSq“. The exact capsule intersection is then:

Notice also that we don’t have to check segLenSq == 0 anymore, because the t' <= 0 case implicitly covers that.

Yay, math!