Collision Detection

A game and physics engine asks one question thousands of times per frame: are these two shapes touching, and if so, where? For convex primitives — spheres, boxes, cylinders — the answer is pure computational geometry: distances, closest points, projection intervals. Let me introduce that to you.

The pieces

A collision detector takes two shapes and returns a contact manifold: the normal between them, the penetration depth, and one or more contact points. In practice the work is split in two: a cheap reject that discards pairs which are far apart, and the exact primitive test. Chapters 1–6 below are the exact tests; chapter 7 builds the cheap reject out of bounding boxes. What happens after a contact is produced (impulses, friction, resting stacks) is collision resolution, and deliberately out of scope on this page.

  • sphere — a center point and a radius.
  • box — half extents and an orientation.
  • cylinder — a radius, a height, and an axis orientation.

I will use some common notation through out the article. A point is (or for center), radius is , distance is , penetration depth is , the contact normal is , half extents are , and a box orientation is .

1 Sphere vs sphere

Given two spheres and with centers , and radii , , they overlap exactly when the distance between their centers is no more than the sum of their radii. The contact normal is the unit vector between the centers, and the penetration depth is how much the two radii overlap along that line:

a. The distance test

You can drag the circles.

JS 
import { vsub, vadd, vscale, vlen } from "./sat.js";

export function circleCircle(a, b) {
  const delta = vsub(b.center, a.center);
  const dist = vlen(delta);
  const radiusSum = a.radius + b.radius;
  if (dist > radiusSum) {
    return { hit: false, normal: null, penetration: 0, point: null };
  }
  const normal = dist > 1e-6 ? vscale(delta, 1 / dist) : [0, 1];
  const penetration = radiusSum - dist;
  const point = vadd(a.center, vscale(normal, a.radius - penetration * 0.5));
  return { hit: true, normal, penetration, point };
}

2 Sphere vs box

Given a sphere with center and radius , and a box with center , half extents , and orientation (whose columns are the box's face axes), the sphere hits the box when the closest point on the box is within . In the box's local frame that closest point is a componentwise clamp:

a. Closest point on a box

You can drag the sphere or the box.

JS 
import { vsub, vadd, vscale, vdot, vlen, clamp } from "./sat.js";

export function closestPointOnBox(box, p) {
  const d = vsub(p, box.center);
  const lx = clamp(vdot(d, box.axes[0]), -box.half[0], box.half[0]);
  const ly = clamp(vdot(d, box.axes[1]), -box.half[1], box.half[1]);
  return vadd(vadd(box.center, vscale(box.axes[0], lx)), vscale(box.axes[1], ly));
}

export function circleBox(circle, box) {
  const closest = closestPointOnBox(box, circle.center);
  const delta = vsub(circle.center, closest);
  const dist = vlen(delta);
  if (dist > circle.radius) {
    return { hit: false, closest, normal: null, penetration: 0 };
  }
  const normal = dist > 1e-6 ? vscale(delta, -1 / dist) : [0, 1];
  return { hit: true, closest, normal, penetration: circle.radius - dist };
}

3 Sphere vs cylinder

Seen from the side a cylinder is a capsule: an axis segment inflated by the radius. The test finds the closest point on that axis, then asks which region the sphere center falls in — past an end cap, or alongside the curved wall. The region decides the surface normal. Given a sphere with center and radius , and a cylinder with axis endpoints , and radius , the closest point on the segment is a clamped projection:

The parameter is the region classifier: or puts the closest point on an end cap, while puts it on the curved wall. Either way, the sphere overlaps the cylinder when the distance is no more than the radius sum .

a. Caps, rims, and walls

You can drag the sphere or the cylinder.

JS 
import { vsub, vadd, vscale, vdot, vlen, clamp } from "./sat.js";

export function closestPointOnSegment(p, a, b) {
  const ab = vsub(b, a);
  const len2 = vdot(ab, ab);
  let t = 0;
  if (len2 > 1e-12) t = clamp(vdot(vsub(p, a), ab) / len2, 0, 1);
  return { point: vadd(a, vscale(ab, t)), t };
}

export function circleCapsule(circle, cap) {
  const axis = closestPointOnSegment(circle.center, cap.a, cap.b);
  const delta = vsub(circle.center, axis.point);
  const dist = vlen(delta);
  const region = axis.t > 1e-3 && axis.t < 1 - 1e-3 ? "side" : "cap";
  if (dist > circle.radius + cap.radius) {
    return { hit: false, axis: axis.point, region, normal: null, penetration: 0 };
  }
  const normal = dist > 1e-6 ? vscale(delta, -1 / dist) : [0, 1];
  const surface = vadd(axis.point, vscale(normal, cap.radius));
  const penetration = circle.radius + cap.radius - dist;
  const point = vadd(surface, vscale(normal, penetration * 0.5));
  return { hit: true, axis: axis.point, region, normal, penetration, point, surface };
}

4 Box vs box — the Separating Axis Theorem

Two convex shapes do not overlap exactly when you can draw a straight line between them. Project both shapes onto that line's direction: their projections are two intervals, and if those intervals don't touch, the line is a separating axis. For two boxes the only directions that can separate them are their face normals (in 2D, four of them; in 3D, six faces plus nine edge cross-products). So the infinite question collapses to a handful of dot products. Given a box with center , half extents , and unit face axes , projecting it onto a unit axis gives an interval centered at whose half-width is the projection radius :

a. Casting a shadow

Turn the axis and reshape the box. The green bar is the box's projection.

b. Watch it run

For two boxes and with centers and projection radii (from part a), each candidate axis turns both into intervals on that line. The gap between the two interval centers is , so the intervals overlap by . A negative means the two shadows have a gap — a separating line:

You can drag and rotate the boxes. When the boxes overlap, the green edge is the reference face, the purple edge is the opposing incident face, the green dots are the contact points, and the green arrow is the minimum translation that separates them.

  1. For each face normal, project both boxes and compute the overlap of the two intervals.
  2. If any overlap is negative, that axis separates → the boxes are apart.
  3. Otherwise the axis with the smallest overlap is the contact normal, and its overlap is the penetration depth.
  4. Clip the opposing face against the reference face's sides; what survives is the contact region.
JS 
const vdot = (a, b) => a[0] * b[0] + a[1] * b[1];

export function boxFrame(center, half, angle) {
  const c = Math.cos(angle), s = Math.sin(angle);
  return {
    center, half, angle,
    axes: [[c, s], [-s, c]],
  };
}

export function projectBox(f, n) {
  const ext =
    f.half[0] * Math.abs(vdot(f.axes[0], n)) +
    f.half[1] * Math.abs(vdot(f.axes[1], n));
  const c = vdot(f.center, n);
  return { min: c - ext, max: c + ext, ext };
}

export function satTest(fa, fb) {
  const d = [fb.center[0] - fa.center[0], fb.center[1] - fa.center[1]];
  const axes = [
    { n0: fa.axes[0], owner: 0, face: 0, label: "A.x" },
    { n0: fa.axes[1], owner: 0, face: 1, label: "A.y" },
    { n0: fb.axes[0], owner: 1, face: 0, label: "B.x" },
    { n0: fb.axes[1], owner: 1, face: 1, label: "B.y" },
  ];

  const results = axes.map(({ n0, owner, face, label }) => {
    const axis = vdot(d, n0) >= 0 ? n0 : [-n0[0], -n0[1]];
    const pa = projectBox(fa, axis);
    const pb = projectBox(fb, axis);
    const overlap = Math.min(pa.max, pb.max) - Math.max(pa.min, pb.min);
    return { axis, owner, face, label, pa, pb, overlap };
  });

  let min = results[0], minIndex = 0;
  results.forEach((r, i) => {
    if (r.overlap < min.overlap) { min = r; minIndex = i; }
  });

  const hit = results.every((r) => r.overlap >= 0);
  return {
    hit,
    results,
    min, minIndex,
    normal: hit ? min.axis : null,
    penetration: hit ? min.overlap : 0,
  };
}

5 Cylinder vs cylinder

In side view a cylinder is a capsule, so two cylinders are two capsule cores: the closest points between their axis segments, compared against the radius sum. Given cylinder with axis and radius , and cylinder with axis and radius , the test is just the distance between the two segments:

The minimizer is the standard segment-to-segment closest-point solve (see the JS below). When the axes are nearly parallel that solve degenerates, so the test switches to a circle check: confirm the two axis intervals overlap along , then compare the perpendicular distance between the axes:

a. Closest points between axes

You can play drag and tilt the cylinders

JS 
import { vsub, vadd, vscale, vdot, clamp } from "./sat.js";

export function closestPointSegmentSegment(p0, p1, q0, q1) {
  const d1 = vsub(p1, p0);
  const d2 = vsub(q1, q0);
  const r  = vsub(p0, q0);
  const a = vdot(d1, d1);
  const e = vdot(d2, d2);
  const f = vdot(d2, r);

  let s = 0, t = 0;
  if (a <= 1e-12 && e <= 1e-12) {
    s = 0; t = 0;
  } else if (a <= 1e-12) {
    s = 0; t = clamp(f / e, 0, 1);
  } else {
    const c = vdot(d1, r);
    if (e <= 1e-12) {
      t = 0; s = clamp(-c / a, 0, 1);
    } else {
      const b = vdot(d1, d2);
      const denom = a * e - b * b;
      s = denom !== 0 ? clamp((b * f - c * e) / denom, 0, 1) : 0;
      t = (b * s + f) / e;
      if (t < 0)      { t = 0; s = clamp(-c / a, 0, 1); }
      else if (t > 1) { t = 1; s = clamp((b - c) / a, 0, 1); }
    }
  }

  return {
    p: vadd(p0, vscale(d1, s)),
    q: vadd(q0, vscale(d2, t)),
    s, t,
  };
}

6 Box vs cylinder

A box and a cylinder meet through the cylinder's axis. The distance from a convex box to that axis is the minimum of four segment-to-edge distances, so the test takes the closest points between the axis and each box edge and keeps the nearest pair. That distance is compared against the cylinder radius. With the axis segment and box corners :

Each is the segment-to-segment distance from chapter 5. With the cylinder radius, the winning pair also gives the contact normal , pointing from the box toward the axis.

a. Axis against box edges

Drag the box or the cylinder. The green dot is the closest point on the box, the amber dot is the closest point on the cylinder axis, and the dashed line between them is the distance compared against the cylinder radius.

JS 
import { vsub, vscale, vdot, vlen } from "./sat.js";

export function boxCapsule(box, cap) {
  const corners = boxCorners(box);
  let best = null;
  for (let i = 0; i < 4; i++) {
    const ea = corners[i];
    const eb = corners[(i + 1) % 4];
    const seg = closestPointSegmentSegment(cap.a, cap.b, ea, eb);
    const delta = vsub(seg.p, seg.q);
    const dSq = vdot(delta, delta);
    if (!best || dSq < best.dSq) best = { dSq, axis: seg.p, boxPoint: seg.q };
  }

  const delta = vsub(best.axis, best.boxPoint);
  const dist = vlen(delta);
  if (dist > cap.radius) {
    return { hit: false, axis: best.axis, boxPoint: best.boxPoint, dist, normal: null, penetration: 0 };
  }
  const normal = dist > 1e-6 ? vscale(delta, 1 / dist) : [0, 1];
  return { hit: true, axis: best.axis, boxPoint: best.boxPoint, dist, normal, penetration: cap.radius - dist };
}

7 Bounding volume hierarchies

The tests in chapters 1–6 are exact but not free. With hundreds of shapes, testing every pair is — and nearly all of those pairs are nowhere near each other. A bounding volume hierarchy avoids that in three steps: wrap each shape in a box, merge nearby boxes into bigger boxes recursively, then query the tree and only test the leaves that survive. The node of choice is the axis-aligned box (AABB) — it is the cheapest volume to build, merge, and test.

a. A box around every shape

You can drag the boxes.

JS 
export function aabbOverlap(a, b) {
  return a.min[0] <= b.max[0] && a.max[0] >= b.min[0] &&
         a.min[1] <= b.max[1] && a.max[1] >= b.min[1];
}

export function aabbMerge(a, b) {
  return {
    min: [Math.min(a.min[0], b.min[0]), Math.min(a.min[1], b.min[1])],
    max: [Math.max(a.max[0], b.max[0]), Math.max(a.max[1], b.max[1])],
  };
}

export function aabbOfBox(c, h) {
  return { min: [c[0] - h[0], c[1] - h[1]], max: [c[0] + h[0], c[1] + h[1]] };
}

b. Group and merge

You can step through the tree levels.

JS 
export function buildBVH(objects) {
  const items = objects.map((o) => ({ object: o, aabb: aabbOfShape(o) }));

  function build(list, depth) {
    const aabb = list.slice(1)
      .reduce((acc, it) => aabbMerge(acc, it.aabb), list[0].aabb);
    if (list.length === 1) {
      return { aabb, depth, leaf: list[0].object, left: null, right: null };
    }

    const wide = aabb.max[0] - aabb.min[0] >= aabb.max[1] - aabb.min[1] ? 0 : 1;
    const sorted = list.slice().sort((a, b) => {
      const ca = (a.aabb.min[wide] + a.aabb.max[wide]) / 2;
      const cb = (b.aabb.min[wide] + b.aabb.max[wide]) / 2;
      return ca - cb;
    });
    const mid = Math.floor(sorted.length / 2);
    return {
      aabb, depth, leaf: null,
      left: build(sorted.slice(0, mid), depth + 1),
      right: build(sorted.slice(mid), depth + 1),
    };
  }

  return build(items, 0);
}

c. Query the tree

You can drag the query box and resize it. See how the tree answer your query.

JS 
export function queryBVH(node, query) {
  const pruned = [];
  const candidates = [];

  function walk(n) {
    if (!aabbOverlap(n.aabb, query)) { pruned.push(n); return; }
    if (n.leaf) { candidates.push(n.leaf); }
    else { walk(n.left); walk(n.right); }
  }
  walk(node);
  return { pruned, candidates };
}
  1. Wrap each shape in an axis-aligned box — the cheapest volume to build and test.
  2. Recursively merge nearby boxes (median split along the widest axis) until one root box holds everything.
  3. To query, test the root box; recurse only into boxes that overlap; every surviving leaf is a candidate to test.

And that was an introduction to collision detection. Hope you find this interesting as I do! Happy learning.