🌿 CuriousWinds

Separating Axis Theorem

Physical mechanisms, mathematical boundary conditions, and architectural trade-offs in Separating Axis Theorem.

Executive Summary & Key Takeaways
Foundational Synthesis for Practitioners & Research Systems

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.

01 Projection Disjointness

SAT tests face normals and edge cross products to confirm disjoint projections along axes, ensuring collision-free separation.

02 MTV via Minimal Overlap

Smallest overlap depth axis defines contact normal and penetration depth for resolution.

03 Axis Candidate Violation

Missing face normals or edge axes risks false positives, corrupting penetration depth calculations.

04 Early-Exit Protocol

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.

01 CONVEX GEOMETRY · HYPERPLANE SEPARATION

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:

Equation 7 (Separating Axis Projection Disjoint Condition):
Interval(A, u) ∩ Interval(B, u) = ∅
Where u is a unit test axis. If the scalar projection intervals along u do not overlap, shapes A and B are mathematically proven to be disjoint.

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.

02 COLLISION RESOLUTION · MINIMUM TRANSLATION VECTORS

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.

03 RIGID BODY DYNAMICS · CONTACT MANIFOLD CLIPPING

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.

04 PARALLEL COMPUTATION · EDGE FILTERING ALGORITHMS

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.

CuriousWinds Knowledge Graph Invariant

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.

Curated Inquiry Series • 10 Investigations

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.

Primary Scholarly Provenance & Empirical Attribution
Card, S. K., Moran, T. P., & Newell, A. (1983). The Psychology of Human-Computer Interaction. Lawrence Erlbaum Associates; ACM SIGCHI Model of Human Processor & Saccadic Latency Foundations.
DOI: 10.1145/358896.358899