The idea: look for a gap
A game must know, every frame, which objects touch. It does not ask "do they overlap?" directly. It asks the easier question: is there a direction in which they are apart? Shine a light across the scene and look at the two shadows on a line. If the shadows have a gap, the shapes cannot touch. This page runs that test on boxes, circles and convex polygons, and shows what goes wrong with a very fast object.
The shadow of a shape on an axis with unit direction n is an interval. For a polygon, take every corner p and compute the dot product p·n; the shadow runs from the smallest to the largest value. For a circle it is centre·n − r to centre·n + r. How dot products project points is shown on 2D Vectors and the Dot Product.
On each axis the page computes the overlap depth, min(maxA − minB, maxB − minA). A positive depth is an overlap, 0 is touching, a negative depth is a gap.
Two boxes (AABB)
An axis-aligned bounding box (AABB) has its sides along x and y. Its shadows are simply its x range and its y range, so two boxes overlap exactly when their x ranges overlap and their y ranges overlap. That is two comparisons per axis and no multiplication, which is why games use boxes everywhere.
Box A is x 3 to 9, y 4 to 8; box B is x 7 to 12, y 7 to 11. On x the depth is min(9 − 7, 12 − 3) = 2, on y it is min(8 − 7, 11 − 4) = 1. Both overlap: a hit (Demo 1: two boxes).
Two circles
Two circles overlap when the distance d between their centres is less than r₁ + r₂. Comparing squares avoids the square root: d² < (r₁ + r₂)². With centres (6, 6) and (10, 9) and radius 3 each, d² = 4² + 3² = 25 and (3 + 3)² = 36, so they overlap, by 6 − 5 = 1 (Demo 2: two circles). In the language of shadows this is one axis, the line through the centres.
The separating axis theorem
The separating axis theorem (SAT) says: two convex shapes do not overlap if and only if some axis shows a gap between their shadows. For two convex polygons you do not have to try every direction. It is enough to try the normal of every edge of both polygons (the direction at a right angle to the edge). Parallel edges give the same axis, so it is tried once.
- For each axis: project both polygons, compare the two intervals.
- As soon as one axis shows a gap, stop: no collision. This early exit makes most tests short.
- If every axis overlaps, the polygons collide.
The triangle (3, 3), (9, 3), (5, 9) gives the axes A1, A2, A3. The diamond has four edges but only two directions, B1 and B2: 5 axes in all. With the diamond centred at (8, 7) every axis overlaps: depths 5, 1.11, 5.06, 5.66 and 1.41 (Demo 3). With the diamond at (10, 8), axis A1 overlaps by 4, then axis A2, the normal of the slanted edge, shows a gap of 1.11 and the test stops after 2 axes (Demo 4).
For a concave shape a gap may not show on any edge normal even when the shapes are apart. Games split a concave shape into convex pieces and test the pieces.
The minimum translation vector
When the shapes do collide, the game also needs to separate them. Every axis gives a depth: how far A must move along that axis to end the overlap. The smallest depth wins. That axis and depth form the minimum translation vector (MTV), the shortest move that pulls A out of B. Its direction is chosen to point from B toward A.
| pair | smallest overlap | Push Apart moves A by |
|---|---|---|
| two boxes (Demo 1) | y: 1 (x was 2) | (0, −1) |
| two circles (Demo 2) | centre line: 1 | (−0.8, −0.6): A's centre goes to (5.2, 5.4) |
| triangle + diamond (Demo 3) | A2: 1.11 | 1.11 along −(0.83, 0.55) = (−0.92, −0.62) |
After the push, the depth on that axis is exactly 0: the shapes touch but no longer overlap. A physics engine then works out the bounce from the contact normal, which is the MTV direction; that part is on Collisions in 2-D.
Broad phase, then narrow phase
A game with n objects has about n²/2 pairs. Running SAT on all of them is too slow. So engines first run a cheap broad phase: compare bounding boxes, often with a grid, a quadtree or a sorted list of x ranges, to throw away far pairs. Only the pairs whose boxes overlap go to the exact narrow phase. A box overlap is only a "maybe": in Demo 4 the bounding boxes overlap, yet SAT finds a gap. In Demo 5 A moves 2 units right and now all 5 axes overlap.
For the spatial indexes a broad phase can use, see Quadtree vs Geohash and KD-Tree vs R-Tree.
Tunnelling and swept tests
A game tests once per frame, at the positions of that frame. An object that moves far between frames can be on one side of a wall in one frame and on the other side in the next. No frame shows an overlap, so the hit is missed: this is tunnelling.
The bullet on this page is a 1 × 1 box and the wall is 1 wide. If the bullet moves less than 1 + 1 = 2 per frame, some frame must land inside the wall. At 1.5 per frame from x = 4 it is caught at frame 4 with an overlap of 0.5 (Demo 6). At 6 per frame from x = 2 the frames show gaps of 7.5, 1.5 and then 2.5 on the far side (Demo 7).
The fix is a swept test (continuous collision detection): test the box that covers the whole move of a frame. From frame 1 to frame 2 the bullet sweeps x 7.5 to 14.5, which overlaps the wall. The time of impact is t = (wall left − bullet right) / speed = (10 − 8.5) / 6 = 0.25: the bullet touches the wall a quarter of the way through that frame, at x = 9.5. Engines also use smaller time steps for fast objects, or cast a ray along the path.
See also Convex Hull: Graham Scan vs Gift Wrapping, which builds the convex outline that SAT needs from a cloud of points.
See also The Game Loop: Variable Delta Time vs a Fixed Timestep, where one long frame with variable dt makes the ball jump through a wall and a fixed timestep catches it.
What the page leaves out
Real engines rotate shapes, so boxes become oriented boxes (OBB) with their own two axes; circle against polygon needs one extra axis, from the circle's centre to the nearest corner. In 3-D, SAT also tests the cross products of edge pairs. Engines keep contact points and contact manifolds, not just the MTV, and often use GJK and EPA instead of SAT for general convex shapes. The page also skips swept tests for rotating objects, ray casts, and how the broad phase is kept up to date as objects move.