Narrow Phase: SAT

For convex shapes: Separating Axis Theorem.

Two convex shapes don't intersect iff there's an axis along which their projections don't overlap.

Algorithm:

1. For each edge of each shape, compute its normal axis.
2. Project both shapes onto the axis (compute min, max).
3. Check if projections overlap.
4. If any axis: NO overlap.
5. If all axes overlap: COLLIDES, smallest overlap is the contact axis.

For 2D polygons: number of axes = sum of edges. For two boxes: 4 axes (4 edge normals + 0 if axis-aligned).

GJK (Gilbert-Johnson-Keerthi) is an alternative for general convex shapes:

• Uses Minkowski difference.
• Iterative: check if origin is in difference.
• Handles arbitrary convex shapes (point clouds).
• Used by Bullet, PhysX.

EPA (Expanding Polytope Algorithm):

• Companion to GJK.
• Computes penetration depth + contact normal.

Manifold:

• For impulse-based response, need:
  • Contact normal (which way to push).
  • Penetration depth.
  • Contact points (where on each body).

Generated by SAT/GJK + EPA.

For our toy: implement SAT for boxes + circles. Skip GJK (more complex).

Special cases:

• Point in polygon (ray casting).
• Polygon in polygon (subset check).
• Closest point computation.

Real engines have hand-tuned narrow-phase per shape combination:

• Box-box (SAT optimized).
• Sphere-sphere (distance check).
• Capsule-capsule.
• Triangle mesh (BVH traversal).