1. The Intuition: The Flashlight and Shadow Test

1.1 The Shadow Projection Analogy

Imagine placing two solid cardboard geometric shapes—such as a rotated rectangle and a pentagon—on a table. Now, imagine shining a bright flashlight on the two shapes from different angles around the perimeter of the table, casting their 1D linear shadows onto a wall behind them.

If you discover even one single flashlight angle where the 1D shadow of Shape A and the 1D shadow of Shape B do not overlap, you have absolute mathematical proof that the two 3D shapes are NOT colliding! Conversely, if you test every possible unique surface normal angle and their 1D shadows overlap in every single test, the two shapes MUST be intersecting. This shadow projection test is the core intuition powering the **Separating Axis Theorem (SAT)**.

Diagram: The SAT pipeline evaluating edge normals to detect 2D convex polygon collisions.

1.2 Convex Geometry vs Concave Decomposition

A polygon is defined as **convex** if any line segment drawn between any two interior points lies entirely inside the shape. Mathematically, for all adjacent edges, the cross product $\vec{e}_i \times \vec{e}_{i+1} \ge 0$ maintains a constant sign.

When a game artist imports complex concave sprite collision meshes (such as an L-shaped building or a crescent moon), physics engines perform **Concave Polygon Decomposition** (e.g. Hertel-Mehlhorn algorithm or Ear Clipping). The engine decomposes the concave mesh into $k$ convex sub-polygons $P_1, P_2, \dots, P_k$. During gameplay, SAT evaluates collisions against the individual convex components, preserving 100% mathematical accuracy without sacrificing performance.

Pitfall — Applying SAT to Concave Polygons: The Separating Axis Theorem applies EXCLUSIVELY to convex polygons (where all interior angles are $\le 180^\circ$). If you pass a concave polygon (e.g. a star shape or L-shape) into SAT, the algorithm will generate false positive collisions! Concave polygons must first be decomposed into a set of convex polygons using algorithms like Ear Clipping or Convex Hull Triangulation.

2. Vector Mathematics & Projections of Convex Polygons

2.1 Edge Vector and Perpendicular Normal Calculation

Given a polygon defined by an ordered list of 2D vertices $V = [\vec{v}_0, \vec{v}_1, \dots, \vec{v}_{n-1}]$, an edge vector $\vec{e}_i$ connecting vertex $\vec{v}_i$ to $\vec{v}_{i+1}$ is computed as:

The perpendicular surface normal vector $\vec{n}_i$ is obtained by swapping components and negating one axis (yielding a 90-degree counter-clockwise rotation):

2.2 Scalar Dot Product Projections

To project a 2D vertex $\vec{v} = (x, y)$ onto a normalized axis $\hat{n} = (n_x, n_y)$, we compute the vector dot product scalar projection $p$:

By projecting all vertices of Polygon A onto axis $\hat{n}$, we find its 1D projection interval $[\min_A, \max_A]$. Similarly, projecting Polygon B yields $[\min_B, \max_B]$. The 1D overlap distance $d_{\text{overlap}}$ is:

If $d_{\text{overlap}} \le 0$ on ANY tested axis, the polygons are separated and execution terminates immediately!

2.3 Polygon Area & Center of Mass (Shoelace Formula)

To determine polygon mass $m = \text{Area} \cdot \text{density}$ and center of mass $\vec{C}$, physics engines compute **Gauss's Area Formula (Shoelace Algorithm)** across vertices $V = [\vec{v}_0, \vec{v}_1, \dots, \vec{v}_{n-1}]$:

The centroid coordinates $(C_x, C_y)$ are calculated as:

3. Minimum Translation Vector (MTV) & Penetration Resolution

3.1 Calculating the Minimum Translation Vector (MTV)

When SAT confirms that ALL candidate axes overlap, the polygons are colliding. To prevent objects from sinking into one another (positional penetration), the physics engine must push them apart along the axis of smallest overlap.

The **Minimum Translation Vector (MTV)** is defined by the smallest overlap distance $d_{\text{min}}$ among all tested axes, multiplied by the corresponding normalized axis direction $\hat{n}_{\text{min}}$:

Pitfall — Object Tunneling at High Velocities: If a fast-moving bullet or character travels at 1000 pixels/frame, it can pass completely through a thin wall in a single frame. Because SAT evaluates static geometry per frame, it fails to detect the collision! High-speed objects require Continuous Collision Detection (CCD) or swept-volume raycasting.

4. Linear Impulse Physics: Newton's Law of Restitution

4.1 Relative Normal Velocity & Impulse Scalar $J$

Once positional overlap is resolved via MTV, the physics engine updates linear velocities using Newton's Law of Restitution. The relative velocity $\vec{v}_{\text{rel}}$ of Body A relative to Body B is:

The normal velocity component $v_{\text{normal}} = \vec{v}_{\text{rel}} \cdot \hat{n}$ determines if the bodies are moving toward each other ($v_{\text{normal}} < 0$). If $v_{\text{normal}} \ge 0$, they are separating, and no impulse is applied. The impulse magnitude $J$ is calculated as:

where $e \in [0, 1]$ is the coefficient of restitution ($e = 1$ is perfectly elastic bounce, $e = 0$ is completely inelastic stick), and $m_A, m_B$ are object masses.

4.2 Velocity Post-Collision State Update

Applying impulse vector $\vec{J} = J \cdot \hat{n}$ updates object velocities instantaneously:

4.3 Positional Correction & Baumgarte Stabilization

Floating-point numerical integration errors cause resting objects (such as a stack of boxes) to sink slightly into one another over consecutive frames. Applying velocity impulse alone cannot fix static overlap penetration, leading to visible jittering.

To solve static sinking, engines apply **Linear Projection Positional Correction** (also known as Baumgarte Stabilization). Objects are directly translated apart proportionally to their inverse mass, incorporating a small slop tolerance threshold ($slop \approx 0.01 \text{ px}$) to prevent jitter:

Position vectors update directly: $\vec{p}_A' = \vec{p}_A + \frac{1}{m_A} \vec{\text{PosCorrection}}$ and $\vec{p}_B' = \vec{p}_B - \frac{1}{m_B} \vec{\text{PosCorrection}}$, eliminating object sinking in multi-body stacks.

5. Step-by-Step C++ / Python Physics Engine Implementation

5.1 Complete Object-Oriented SAT & Impulse Engine

Below is a complete, production-ready Python 2D physics engine class implementing SAT polygon projection, MTV calculation, and impulse velocity updates:

5.2 Coulomb Friction Model & Tangential Impulse

To simulate real-world surface traction (such as a car tires skidding or a crate sliding to a stop), physics engines apply **Tangential Friction Impulses** alongside normal restitution impulses:

The tangential unit vector $\hat{t}$ is extracted from the relative velocity vector $\vec{v}_{\text{rel}}$:

The raw friction impulse magnitude $J_t$ is computed as $J_t = \frac{-(\vec{v}_{\text{rel}} \cdot \hat{t})}{\frac{1}{m_A} + \frac{1}{m_B}}$. Under **Coulomb's Law of Friction**, if $|J_t| \le J \cdot \mu_s$ (where $\mu_s$ is static friction), the surfaces stick (static friction holds). Otherwise, tangential impulse is clamped to $J_t = -J \cdot \mu_k$ (where $\mu_k$ is kinetic friction).

6. Advanced: Rotational Dynamics & Moment of Inertia

6.1 Angular Impulse Formulation

In realistic 2D games, off-center polygon collisions induce rotational spin (angular velocity $\omega$). The moment of inertia $I$ represents an object's resistance to rotational acceleration.

Given collision contact point $\vec{P}$, vector offset $\vec{r}_A = \vec{P} - \text{Center}_A$, and angular impulse denominator, the complete 2D rotational impulse equation is:

Applying angular impulse updates angular velocity: $\omega_A' = \omega_A + \frac{\vec{r}_A \times (J \cdot \hat{n})}{I_A}$.

6.2 Moment of Inertia Formulas for 2D Primitives

Game physics engines pre-compute the scalar moment of inertia $I$ based on geometry shape and total mass $m$:

• Solid Circle (Radius $R$): $I = \frac{1}{2} \, m \, R^2$
• Box / Rectangle (Width $W$, Height $H$): $I = \frac{1}{12} \, m \, (W^2 + H^2)$
• Regular $N$-gon (Radius $R$): $I = \frac{1}{6} \, m \, R^2 \, \left(1 + 2 \cos^2\frac{\pi}{N}\right)$

7. Advanced: Broadphase Spatial Partitioning & Quadtrees

7.1 Scaling Collision Checks from $O(N^2)$ to $O(N \log N)$

Testing every polygon against every other polygon in a scene with $N = 10,000$ game objects requires $\frac{N(N-1)}{2} \approx 50,000,000$ SAT pair evaluations per frame (causing massive FPS drops!).

Diagram: Two-phase collision architecture separating broadphase spatial filtering from narrowphase SAT math.

By inserting objects into a **Quadtree** or **Spatial Hash Grid**, the engine quickly filters out distant objects using fast AABB bounding boxes, passing only nearby candidate pairs to the narrowphase SAT engine.

7.2 Quadtree Spatial Partitioning Implementation

Below is a recursive Quadtree implementation partitioning 2D game space into 4 quadrants when node capacity exceeds 8 objects:

8. Game Collision Algorithm Comparison Matrix

The table below compares 2D collision detection algorithms across complexity and geometry support:

9. Interactive: SAT Projection & Impulse Physics Simulator

Click "Step Collision Test" to simulate SAT edge projections, MTV overlap evaluation, and physical impulse bounce:

10. Collision Detection Performance Benchmarks

The chart below compares execution time per frame (in milliseconds) across spatial indexing architectures:

11. Frequently Asked Questions