Contents

Collision detection is fundamental to physics engines, robotics, and contact mechanics. Three algorithms cover most practical cases: AABB (axis-aligned bounding box) for fast broad-phase filtering, SAT (Separating Axis Theorem) for exact convex polygon tests, and GJK (Gilbert-Johnson-Keerthi) for general convex shapes. This post covers the formulas and a 2D interactive demo.

AABB overlap

Two axis-aligned rectangles overlap if and only if their projections overlap on all coordinate axes. For boxes $A$ and $B$ with centers $(c^A_x, c^A_y)$ and half-extents $(h^A_x, h^A_y)$:

\[|c^A_x - c^B_x| \leq h^A_x + h^B_x \quad \text{and} \quad |c^A_y - c^B_y| \leq h^A_y + h^B_y \tag{1}\]

This is an O(1) test — used as a broad-phase filter before running exact geometry.

Separating Axis Theorem (SAT)

Two convex shapes do not overlap if and only if there exists an axis $\hat{\mathbf{n}}$ such that their projections on $\hat{\mathbf{n}}$ are disjoint. For convex polygons in 2D, it suffices to test the face normals of both shapes.

For shape $A$ with vertices ${v_i^A}$ and shape $B$ with vertices ${v_j^B}$:

\[\text{overlap on axis } \hat{\mathbf{n}}: \quad \max_i(v_i^A \cdot \hat{\mathbf{n}}) \geq \min_j(v_j^B \cdot \hat{\mathbf{n}}) \quad \text{and vice versa} \tag{2}\]

If any tested axis yields a gap, the shapes are separated. The minimum translation vector (MTV) is the axis with the smallest overlap — the minimum push to separate them:

\[\text{MTV} = \hat{\mathbf{n}}_{\rm min} \cdot d_{\rm min} \tag{3}\]

GJK — the Minkowski difference

The GJK algorithm tests if the origin lies inside the Minkowski difference $A \ominus B = {a - b : a \in A, b \in B}$. The support function in direction $\hat{\mathbf{d}}$ is:

\[h_{A \ominus B}(\hat{\mathbf{d}}) = h_A(\hat{\mathbf{d}}) - h_B(-\hat{\mathbf{d}}) \tag{4}\]

For a convex polygon, the support function returns the vertex with the maximum dot product with $\hat{\mathbf{d}}$:

\[h_A(\hat{\mathbf{d}}) = \underset{v \in V_A}{\arg\max}\, v \cdot \hat{\mathbf{d}} \tag{5}\]

GJK iteratively builds a simplex (triangle in 2D) in the Minkowski difference space, shrinking it toward the origin. If the origin is enclosed, the shapes overlap; otherwise the closest point on the simplex to the origin determines the next search direction.

Interactive 2D demo

Move shapes by adjusting center coordinates and rotation. The chart shows both polygons colored green (separated) or red (overlapping). When separated, the separating axis is drawn as a dashed line. The output line reports AABB and SAT results plus the MTV when overlapping.

—

Python

import numpy as np

def support(verts, d):
    """Vertex of convex polygon furthest in direction d."""
    return verts[np.argmax(verts @ d)]

def project_polygon(verts, axis):
    projections = verts @ axis
    return projections.min(), projections.max()

def sat_2d(poly_a, poly_b):
    """SAT test for 2D convex polygons. Returns (overlap, mtv)."""
    def get_axes(verts):
        n = len(verts)
        edges = np.roll(verts, -1, axis=0) - verts
        norms = np.linalg.norm(edges, axis=1, keepdims=True)
        return np.column_stack([-edges[:, 1], edges[:, 0]]) / norms

    axes = np.vstack([get_axes(poly_a), get_axes(poly_b)])
    min_overlap, min_axis = np.inf, None

    for axis in axes:
        lo_a, hi_a = project_polygon(poly_a, axis)
        lo_b, hi_b = project_polygon(poly_b, axis)
        overlap = min(hi_a, hi_b) - max(lo_a, lo_b)
        if overlap < 0:
            return False, None
        if overlap < min_overlap:
            min_overlap = overlap
            min_axis = axis

    return True, min_axis * min_overlap


# Example
triangle = np.array([[0, 1.2], [-1.04, -0.6], [1.04, -0.6]])
pentagon = np.array([[0, 1.2], [1.14, 0.37], [0.70, -0.97],
                     [-0.70, -0.97], [-1.14, 0.37]])

# Shift pentagon to the right
pent_shifted = pentagon + np.array([2.5, 0])

hit, mtv = sat_2d(triangle, pent_shifted)
print(f"Overlap: {hit},  MTV: {mtv}")

References

Gilbert, E. G., Johnson, D. W., & Keerthi, S. S. (1988). A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Journal of Robotics and Automation, 4(2), 193–203.

Gottschalk, S., Lin, M. C., & Manocha, D. (1996). OBBTree: A hierarchical structure for rapid interference detection. Proceedings of SIGGRAPH, 171–180.

Ericson, C. (2005). Real-Time Collision Detection. Morgan Kaufmann.

In practice, broad-phase AABB filtering eliminates most pairs early. SAT is then used for exact tests between the remaining candidates. GJK extends naturally to 3D and handles smooth shapes (capsules, convex hulls) via the same support-function interface.