The separating axis theorem (SAT) mathematically proves convex polyhedron collision via axis projections, unlike flawed proximity checks. Its hyperplane separation guarantees real-time accuracy for physics engines and simulations.
SAT tests face normals and edge cross products to confirm disjoint projections along axes, ensuring collision-free separation.
Smallest overlap depth axis defines contact normal and penetration depth for resolution.
Missing face normals or edge axes risks false positives, corrupting penetration depth calculations.
Test face normals first, terminate on disjoint projection to optimize O(n + m) runtime.
Separating axis theorem (SAT) algorithms constitute the geometric engine powering narrowphase collision detection and contact manifold generation across physical simulation frameworks. While broadphase hierarchical acceleration structures successfully prune distant objects, the simulation must ultimately determine whether two intersecting convex polyhedra are in physical contact, compute their exact penetration depth vector, and calculate contact points to generate physical reaction impulses. The separating axis theorem states that two convex shapes do not overlap if and only if there exists a single axis along which the projections of the two shapes are disjoint. In this monograph, we examine polyhedral projection mathematics, analyze the minimum translation vector (MTV), and detail how SAT delivers high-speed contact manifolds in real-time game physics.
The Geometric Invariant of Separating Hyperplanes
The mathematical foundation of SAT is the Hyperplane Separation Theorem in convex geometry. For two non-intersecting convex sets A and B in 3D Euclidean space, there exists a separating plane P such that set A lies entirely on one side of P and set B lies on the other:
Interval(A, u) ∩ Interval(B, u) = ∅
For arbitrary 3D convex polyhedra with face sets F_A, F_B and edge sets E_A, E_B, the complete set of candidate separating axes that must be tested is finite: 1. The face normal vectors of Polyhedron A (F_A). 2. The face normal vectors of Polyhedron B (F_B). 3. The cross products of every edge in A with every edge in B (E_A × E_B). If any candidate axis yields a non-overlapping projection interval, the separating axis theorem algorithm terminates immediately with an early-exit rejection.
Computing the Minimum Translation Vector (MTV)
When all candidate axes exhibit overlapping projection intervals, the two polyhedra are in physical collision. To resolve the collision, the physics solver must separate the objects along the path of least resistance.
By recording the overlap depth along each candidate axis during traversal, the separating axis theorem identifies the axis with the minimal positive overlap. This axis represents the contact normal, and the magnitude of the minimal overlap defines the penetration depth. Multiplying the normal by the penetration depth produces the Minimum Translation Vector (MTV) required to push the bodies apart.
Contact Manifold Generation via Polygon Clipping
Resolving rigid body physics requires more than a single penetration vector; it requires a stable contact manifold consisting of contact points, friction tangents, and impulse levers.
Once SAT identifies the collision normal, the engine identifies the reference face and incident face on the colliding bodies. The incident face polygon is then clipped against the side planes of the reference face using Sutherland-Hodgman polygon clipping. The resulting contact polygon vertices are passed directly to sequential impulse constraint solvers, enabling stable stacking of resting physical objects.
SIMD Optimization and Fast Edge Filtering
The primary computational bottleneck in 3D SAT testing is the edge-edge cross product combination (|E_A| × |E_B|), which can generate dozens of redundant axes. High-performance game engines prune edge pairs using Gauss Map analysis: only edge pairs whose arcs on the unit sphere intersect can form a valid separating plane.
Furthermore, vertex projections along candidate axes are vectorized using AVX-512 or ARM Neon dot products. By executing projection interval tests in parallel across four axes simultaneously, modern separating axis theorem narrowphase routines resolve complex polyhedral collisions in less than two microseconds per contact pair.
Continue Curriculum: Spatial Partitioning BVH Collision: 5 Empirical Rules for Games
This inquiry is directly integrated into the parent monograph hub. Next in the curriculum is Part 8: GPU Parallel BVH: Radix Tree Construction in Modern Compute Shaders, examining linear bvh (lbvh), karras prefix trees, & workgroup parallelism.
Spatial Partitioning BVH Collision: 5 Empirical Rules for Games
An empirical exploration through the foundational dynamics, systemic trade-offs, and practical architecture of spatial partitioning bvh collision: 5 empirical rules for games.