Separating axis theorem

Deep dive

How it works

In: two convex polygons or polyhedra (or two oriented boxes) · Out: a separating axis (no contact), or the contact normal, depth and a manifold of up to 2 points in 2D or 4 in 3D · State: none; a cached last separating axis per pair is optional · Cost: O(n·m) naive in 2D, 15 closed-form axes for two oriented boxes

1. Axes. 2D: outward unit normal of every edge of A and B. 3D polytopes: face normals of A, face normals of B, and normalize(eA × eB) for every edge pair (skip near-zero crosses of parallel edges).
2. Separation per axis. For a face normal n of A at vertex p: s = min over vertices v of B of n·(v − p). If s > 0, n separates. This "support point" form measures the signed gap directly and is the robust way for polytopes. For OBBs, use the closed form: project half-extents, compare with the projected center distance.
3. Choose the contact axis. If no axis separates, take the axis of largest (least negative) separation. Use a tolerance that prefers A's faces and face axes over edge axes, so the choice doesn't flip between frames.
4. Manifold (face contact). Reference face = the chosen face on one shape. Incident face = the face on the other shape whose normal is most anti-parallel to the reference normal. Clip the incident face polygon against the side planes of the reference face (Sutherland–Hodgman), keep clipped points below the reference face; depth = distance below it.
5. Edge contact (3D). If an edge-edge axis wins, the contact is the closest point pair of the two edges: one point.

     reference face (A)          side planes clip the incident
   ─┼━━━━━━━━━━━━━━━━━┼─         edge to the reference extent;
    │  ●───────────●  │  ← B      points below the face become
    │ incident face    │          contacts with depth = gap

Code

#[derive(Clone, Copy, Debug, PartialEq)]
pub struct V2 { pub x: f32, pub y: f32 }
fn v(x: f32, y: f32) -> V2 { V2 { x, y } }
fn sub(a: V2, b: V2) -> V2 { v(a.x - b.x, a.y - b.y) }
fn add(a: V2, b: V2) -> V2 { v(a.x + b.x, a.y + b.y) }
fn mul(a: V2, s: f32) -> V2 { v(a.x * s, a.y * s) }
fn dot(a: V2, b: V2) -> f32 { a.x * b.x + a.y * b.y }

/// Convex polygon in world space, counter-clockwise; normals[i] is the outward
/// unit normal of edge (verts[i], verts[i+1]).
pub struct Poly { pub verts: Vec<V2>, pub normals: Vec<V2> }

impl Poly {
    pub fn new(verts: Vec<V2>) -> Poly {
        let n = verts.len();
        let normals = (0..n).map(|i| {
            let e = sub(verts[(i + 1) % n], verts[i]);
            let len = dot(e, e).sqrt();
            v(e.y / len, -e.x / len) // CCW winding: (y, -x) points outward
        }).collect();
        Poly { verts, normals }
    }
}

/// Max over a's edge normals of the min signed distance of b's vertices to that edge.
/// > 0 means that normal is a separating axis.
fn max_separation(a: &Poly, b: &Poly) -> (usize, f32) {
    let mut best = (0, f32::NEG_INFINITY);
    for (i, &n) in a.normals.iter().enumerate() {
        let s = b.verts.iter().map(|&p| dot(n, sub(p, a.verts[i]))).fold(f32::INFINITY, f32::min);
        if s > best.1 { best = (i, s); }
    }
    best
}

pub struct Contact { pub point: V2, pub depth: f32 }

/// SAT test plus reference/incident face clipping. Returns the normal (pointing from
/// a to b) and up to 2 contact points, or None if a separating axis exists.
pub fn collide(a: &Poly, b: &Poly) -> Option<(V2, Vec<Contact>)> {
    let (ea, sa) = max_separation(a, b);
    if sa > 0.0 { return None; }
    let (eb, sb) = max_separation(b, a);
    if sb > 0.0 { return None; }
    // Prefer a's face unless b's is clearly better: stops the reference face from
    // flip-flopping between frames when the two separations are nearly equal.
    const REL_TOL: f32 = 0.98; const ABS_TOL: f32 = 0.001;
    let (rf, inc, edge, flip) =
        if sb > REL_TOL * sa + ABS_TOL { (b, a, eb, true) } else { (a, b, ea, false) };
    let n = rf.normals[edge];
    // Incident edge: the one on the other polygon most anti-parallel to n.
    let ie = (0..inc.normals.len())
        .min_by(|&i, &j| dot(inc.normals[i], n).total_cmp(&dot(inc.normals[j], n))).unwrap();
    let mut pts = [inc.verts[ie], inc.verts[(ie + 1) % inc.verts.len()]];
    // Clip the incident segment against the two side planes of the reference edge.
    let (r0, r1) = (rf.verts[edge], rf.verts[(edge + 1) % rf.verts.len()]);
    let t = mul(sub(r1, r0), 1.0 / dot(sub(r1, r0), sub(r1, r0)).sqrt()); // edge tangent
    for (plane_n, offset) in [(mul(t, -1.0), -dot(t, r0)), (t, dot(t, r1))] {
        let d0 = dot(plane_n, pts[0]) - offset;
        let d1 = dot(plane_n, pts[1]) - offset;
        if d0 > 0.0 && d1 > 0.0 { return None; } // numerically degenerate
        if d0 * d1 < 0.0 {                        // segment crosses the plane: cut it
            let cut = add(pts[0], mul(sub(pts[1], pts[0]), d0 / (d0 - d1)));
            if d0 > 0.0 { pts[0] = cut } else { pts[1] = cut }
        }
    }
    // Keep points below the reference face; depth = penetration along n.
    let contacts = pts.iter().filter_map(|&p| {
        let sep = dot(n, sub(p, r0));
        (sep <= 0.0).then(|| Contact { point: p, depth: -sep })
    }).collect();
    Some((if flip { mul(n, -1.0) } else { n }, contacts))
}

A box of half-size 0.5 sunk 0.1 into a ground box returns normal (0, 1) and two contacts at the box's bottom corners with depth 0.1.

Complexity and constants

• 2D, naive: (n + m) axes × O(m or n) projections = O(n·m). For boxes and the typical ≤ 8-vertex polygons this is a few dozen dot products, order of 100 ns.
• Support-point hill climbing over the vertex adjacency turns each projection into O(log n)-ish walks for large hulls.
• 3D hulls: F1 + F2 face axes plus E1·E2 edge axes, each needing a projection. A 20-edge hull pair has 400 edge axes; Gauss-map pruning keeps only edge pairs that form a face of the Minkowski difference, usually a small fraction.
• OBB vs OBB: 15 axes, closed form, no vertex loops; one rotation matrix and its absolute value are shared by all axes.

Efficiency

• Cost: two 2D boxes need 4 axes and two oriented 3D boxes 15 closed-form axes; two 2D polygons need n + m axes of O(m or n) dot products each, order of 100 ns for polygons of at most 8 vertices (order of, not measured here). The bound is arithmetic on a few vertices, with branches that exit early.
• Levers:
  • cache the last separating axis — most non-colliding pairs then need one test (this page) — coherent scenes
  • work in A's local frame — A's normals become constants, axis-aligned for boxes — box pairs
  • Gauss-map pruning — only edge pairs that form a face of the Minkowski difference, usually a small fraction of E1·E2 (Gregorius 2013) — 3D hulls with dozens of faces
  • support-point hill climbing — each projection becomes a short walk instead of a loop over all vertices — large hulls
  • prefer face axes by a tolerance — avoids reference-face flipping that breaks warm starting — stacked contacts
• Naive → standard → state of the art:
  • project every vertex on every candidate axis, no early exit · O((F1+F2+E1·E2)·(n+m)) for hulls
  • early exit on the first gap, cached axis, closed-form OBB test · 1 to 15 axes per pair
  • Gauss-map pruned edge pairs with hill-climbed supports · F1+F2 face axes plus the few edge pairs that can separate

Implementation notes

• Work in A's local frame: transform B into A's frame once; A's normals become constants (axis-aligned for boxes).
• Separating-axis cache: store the last separating axis (or the reference face id) per pair; test it first next frame. Coherent scenes mostly exit after one axis.
• Feature ids: tag each clipped contact with (reference edge, incident edge, vertex) ids so the solver can match contacts across frames for warm starting (sequential impulse solver).
• Speculative contacts: keep points with separation up to a small positive margin (Box2D v3: 4× the linear slop) so the solver prevents contacts from opening a gap or tunnelling within one step.
• Polygon radius / skin: give polygons a small rounding radius; SAT works on the core shape and the radius is subtracted from the separation. Gives smooth normals and stable stacking.
• 3D manifolds: clip the incident face polygon against all side planes of the reference face, then reduce to at most 4 points (deepest point plus the points maximising manifold area).

Pitfalls

• Edge-edge axes from nearly parallel edges: eA × eB ≈ 0, normalising it amplifies noise into a bogus axis. Skip crosses with tiny length; for OBBs add an epsilon to the absolute rotation matrix (Ericson's fix).
• Comparing separations along unnormalised axes: depths are scaled by axis length and the minimum is wrong.
• No tolerance in reference-face selection: contact points jump between faces every frame, stacks jitter and warm starting breaks.
• Concave shapes: SAT is only valid for convex sets. Decompose into convex pieces.
• Clockwise polygon input with code that assumes CCW: all normals point inward and everything "collides".

Variants and alternatives

In production

Games, VR and effects: Box2D (b2CollidePolygons: reference/incident face clipping), Bullet (btPolyhedralContactClipping for convex hulls); the Rust parry library exposes SAT routines for cuboids and segments (query::sat). Large-model interference detection: the oriented-box test inside OBB-tree libraries such as RAPID (Gottschalk 1996).

Implementations

Sources

• Stefan Gottschalk, Ming C. Lin, Dinesh Manocha, OBBTree: A Hierarchical Structure for Rapid Interference Detection, SIGGRAPH 1996. paper
• Christer Ericson, Real-Time Collision Detection, Morgan Kaufmann, 2005 (OBB-OBB test, ch. 4).
• Dirk Gregorius, The Separating Axis Test between Convex Polyhedra, GDC 2013.
• Erin Catto, Contact Manifolds, GDC 2007.