🎮 Game Dev · Physics Engines
📅 Березень 2026⏱ ≈ 12 хв читання🔴 Advanced

Collision Detection

Making objects bounce correctly requires solving two problems: which pairs of objects might be touching (broad phase), and exactly how they are touching (narrow phase). The algorithms behind AABBs, BVH trees, SAT, GJK, and EPA form the backbone of every physics engine.

1. The Two-Phase Pipeline

With N objects, naïve O(N²) pair testing is too slow. Modern engines split collision into two phases:

Phase 1
Broad Phase
Find candidate overlapping pairs using cheap bounding volumes. Output: small candidate list.
Phase 2
Narrow Phase
Test exact shape intersection for each candidate pair. Find contact points, normal, penetration depth.
Phase 3
Response
Apply impulses / position correction to resolve interpenetration and compute post-collision velocities.

2. Broad Phase — BVH and AABB Trees

Axis-Aligned Bounding Boxes (AABB)

Each shape is wrapped in a box aligned to world axes. Two AABBs overlap iff they overlap on all 3 axes simultaneously — tested with 6 comparisons.

AABB overlap test overlap = (aMin.x <= bMax.x && aMax.x >= bMin.x) && (aMin.y <= bMax.y && aMax.y >= bMin.y) && (aMin.z <= bMax.z && aMax.z >= bMin.z);

Bounding Volume Hierarchy (BVH)

A BVH is a binary tree where each node stores an AABB enclosing all its children. Construction strategy (top-down SAH):

  1. Choose split axis (longest axis of current AABB).
  2. Sort primitives along that axis.
  3. Find split position minimising Surface Area Heuristic (SAH): cost = N_left · Area_left + N_right · Area_right.
  4. Recurse on each half until leaf size ≤ threshold (~4 triangles).

Traversal: start at root. If no overlap with node AABB, prune entire subtree. Otherwise recurse into children. Average case O(log N) per query; output is O(K) candidate pairs where K is actual overlaps.

Dynamic BVH: For moving objects, rebuild nodes bottom-up or use an incremental "insert/remove" tree with AABB fattening (inflate AABBs by a velocity buffer so they don't need updating every frame). Bullet Physics and Jolt use this approach.

3. Narrow Phase — SAT

The Separating Axis Theorem states that two convex shapes are not intersecting if and only if there exists a separating axis — a direction along which their projections do not overlap.

For two convex polygons A and B, the candidate separating axes are the edge normals of both shapes. Algorithm:

  1. For each edge normal of A, project all vertices of A and B onto that axis.
  2. If the projected intervals don't overlap → shapes are separated → return false (no collision).
  3. Repeat for edge normals of B.
  4. If all axes have overlap → shapes ARE colliding. Track minimum overlap axis → penetration normal.
Projection interval project(shape, axis) → [min, max] where min = min_i(dot(vertex_i, axis)) max = max_i(dot(vertex_i, axis)) overlap = min(maxA, maxB) - max(minA, minB) separated = overlap < 0

For 3D convex polyhedra: test face normals of both shapes PLUS cross products of edge pairs (edge from A × edge from B). Total axes = F_A + F_B + E_A × E_B. Early exit on first separating axis makes this fast in practice.

SAT limitation: Works only for convex shapes. For concave meshes, decompose into convex hulls (e.g., VHACD algorithm) and test each hull pair.

4. GJK Algorithm

The Gilbert-Johnson-Keerthi algorithm is the industry standard for convex shape collision in 3D. Core insight: two convex shapes A and B are not intersecting iff the origin is not contained in the Minkowski difference A ⊕ (−B).

The Minkowski difference M = {a − b | a ∈ A, b ∈ B} is also convex. GJK finds the point in M closest to the origin using only a support function: for a direction d, return the vertex in M that goes furthest in that direction.

GJK support function support(A, B, d) = furthestPoint(A, d) − furthestPoint(B, −d) // No need to construct M explicitly

GJK builds a simplex (point → line → triangle → tetrahedron in 3D) approaching the origin. At each step it asks: does the current simplex contain the origin? If yes, collision. If no, find next search direction toward origin and add a new support point. Converges in O(1) iterations for most shapes.

Support functions are trivially fast for sphere (r·d̂), capsule, box (sign(d)·halfExtents), and convex hull (O(√N) hill climbing). This is why GJK handles arbitrary convex shapes without precomputing the Minkowski difference.

5. EPA — Contact Manifolds

GJK tells you if shapes collide, but not the penetration depth or contact normal. The Expanding Polytope Algorithm builds on the GJK simplex when a collision is detected:

  1. Start with the simplex from GJK (tetrahedron containing origin).
  2. Find the face of the polytope closest to the origin (minimum penetration direction).
  3. Expand the polytope by finding the support point in the face's outward normal direction.
  4. Replace the face with two new triangles connecting to the new point.
  5. Repeat until no new support point is further out → convergence. The closest face gives the penetration normal and depth.

With normal and depth, you can build a contact manifold: the set of contact points (for stable simulation of resting objects, especially boxes, you need 1–4 contact points, not just one). Clip against Voronoi regions of both shapes to find the contact patch.

Performance tip: GJK+EPA runs in ~microseconds for typical game objects. Warm-starting (reusing last frame's simplex) cuts iterations dramatically for slowly-moving shapes.

6. Continuous Collision Detection

Fast objects can tunnel through thin objects between frames (a bullet passing through a wall). Continuous collision detection (CCD) solves this by sweeping shapes along their trajectories.

CCD adds cost — most engines gate it: only fast/small objects (high velocity-to-size ratio) enable CCD, toggled by a "bullet" flag.

7. Implementation Notes