The Separating Axis Theorem

Closest-point queries tell you how far apart two shapes are. Often you need the blunter yes/no: do they overlap? For two convex shapes there is an exact, embarrassingly cheap answer — the separating axis theorem (SAT) — and its whole engine is a single operation you already own, the dot product.

The idea is a sleight of dimension. Instead of comparing two 2-D (or 3-D) shapes directly, you crush each one down onto a line — a 1-D shadow — and ask whether the two shadows overlap. A shadow is just an interval [\min, \max], and two intervals on a line either overlap or they don't. The miracle is that for convex shapes, checking the right finite set of lines settles the whole question.

The theorem, line by line

Step 1 — projecting a shape onto an axis is one dot product. Pick a direction \hat{n} (a unit vector). The projection of a point \vec{p} onto that axis is the signed shadow length \vec{p}\cdot\hat{n}. A whole shape projects to the interval spanned by its extreme points:

\operatorname{proj}_{\hat n}(S) = \big[\ \min_{\vec p\in S}\ \vec p\cdot\hat n,\ \ \max_{\vec p\in S}\ \vec p\cdot\hat n\ \big].

For a polygon you only need its vertices: the min and max over the corners is the min and max over the whole shape (convexity again).

Step 2 — a gap on one axis proves separation. Suppose for some \hat{n} the two intervals don't touch — say shape A's max is below shape B's min:

\max_{\vec a\in A}\ \vec a\cdot\hat n \ <\ \min_{\vec b\in B}\ \vec b\cdot\hat n.

Then every point of A has a smaller shadow than every point of B. No point of A can equal a point of B — if it did, their shadows would be equal too — so the shapes are disjoint. We call such an \hat{n} a separating axis: a single gap is a certificate of non-collision.

Step 3 — convexity makes the converse true. The deep half of the theorem is that if the shapes don't overlap, a separating axis is guaranteed to exist. Two disjoint convex sets can always be cleanly split by a hyperplane (the separating-hyperplane theorem); the normal of that plane is the axis on which their shadows part. So for convex shapes the test is exact, not merely conservative:

A\cap B=\varnothing\ \iff\ \exists\,\hat n:\ \operatorname{proj}_{\hat n}(A)\ \text{and}\ \operatorname{proj}_{\hat n}(B)\ \text{are disjoint}.

Step 4 — only finitely many axes can matter. There are infinitely many directions, but a separating plane for two polytopes can always be slid until it lies flush against a face of one of them. So you need only test a small candidate set:

in 2-D: each edge normal of A and of B;
in 3-D: each face normal of both, plus the cross products \vec e_A\times\vec e_B of every pair of edge directions (these catch edge-on-edge separations no face normal sees).

A box-versus-box test in 3-D is thus 3+3+9=15 axes — a fixed, tiny number.

Step 5 — the algorithm, and its early-out. Loop the candidate axes; on each, project both shapes and compare intervals. The instant you find a gap, stop — you've proved they're apart, no further axes needed. This early-out is why SAT is so fast on the common case of objects not colliding: most pairs separate on the first axis or two.

Step 6 — if no axis separates them, they intersect — and you get the push-out for free. Should every axis show overlap, the shapes collide. Track the smallest overlap depth across all axes; that axis is the minimum translation vector (MTV) — the shortest shove that pulls the shapes apart. The penetration depth is the overlap amount, and the direction is that axis. One pass gives you both the boolean and the collision response.

Let A,B be convex shapes. Then:

Exact test — A and B are disjoint if and only if there exists a separating axis \hat n on which their projections do not overlap.
Project with the dot product — a shape's shadow on \hat n is the interval [\min\vec p\cdot\hat n,\ \max\vec p\cdot\hat n] over its vertices.
Finite candidate set — test each shape's face normals (edge normals in 2-D), and in 3-D also the cross products of edge pairs.
Any gap ⇒ no collision — one separating axis is a certificate; stop early.
No gap ⇒ collision — and the axis of minimum overlap is the push-out (minimum translation vector) for the response.

SAT is one of two algorithms every physics engine ships for convex-convex collision. The other is GJK (Gilbert–Johnson–Keerthi), which attacks the same question from the opposite end. Instead of testing separating axes, GJK works in the Minkowski difference A\ominus B=\{\vec a-\vec b\}: the two shapes intersect exactly when this difference contains the origin. GJK marches a small simplex (a triangle/tetrahedron) toward the origin using only a support function (“farthest point in direction \hat d”), so it never enumerates faces and handles smooth shapes — spheres, capsules — that have no flat faces for SAT to use.

The trade-offs split cleanly. SAT is simplest for boxes and low-poly polytopes and hands you the penetration axis directly; its axis count grows with the face count, so it gets pricey for detailed meshes. GJK scales to arbitrary convex hulls and is fast, but on its own only answers are they touching? — recovering penetration depth needs its companion EPA (expanding polytope algorithm). Engines mix and match: SAT for the ubiquitous box pairs, GJK+EPA for the general case.