Narrow Phase: SAT

The broad phase hands you pairs that might touch. The narrow phase answers exactly: do these two shapes overlap, and if so, which way and how far must one move to separate them? After this lesson your program will answer that for any two convex polygons using the separating axis test.

The idea: look for a gap

Shine a light along a line and look at the shadow each polygon casts on it. If the two shadows (intervals) do not overlap, the polygons cannot overlap either: that line is a separating axis. The Separating Axis Theorem says that for two convex shapes the reverse also holds: if no separating axis exists, they overlap. Convexity is load-bearing. Two interlocking C shapes are disjoint yet have no separating line, which is why engines split concave geometry into convex pieces first.

You cannot try infinitely many directions, but for polygons you do not need to. A gap, if there is one, shows up on the direction perpendicular to one of the polygons' edges. So the candidate axes are the edge normals of both polygons.

Step by step

1. For each edge of A and then each edge of B, take the edge vector (ex, ey) and rotate it a quarter turn to get a direction (ey, -ex). Divide by its length to make it a unit axis. Skip a zero-length edge.
2. Project every vertex of A onto the axis (dot product) and keep the smallest and largest value: A's interval. Do the same for B.
3. If the intervals do not overlap, stop: the answer is "no contact".
4. Otherwise measure how far B would have to move to escape along this axis:
   • along +axis: the top of A minus the bottom of B,
   • along -axis: the top of B minus the bottom of A. The smaller of the two is the depth on this axis, and the direction is the matching sign.
5. After all axes, the axis with the smallest depth gives the contact: normal (pointing from A toward B) and depth.

Why measure the push rather than the interval overlap min(tops) - max(bottoms)? Because when one polygon sits inside the other, the interval overlap is just the size of the smaller shadow, which is not enough to get it out. The push distances handle containment correctly.

Worked trace

A is the rectangle (0,0) (6,0) (6,3) (0,3); B is the triangle (5,1) (9,1) (5,6).

axis          A interval     B interval     push +   push -
(0,-1)        [-3, 0]        [-6, -1]        6        2
(1,0)         [0, 6]         [5, 9]          1        9
(0,1)         [0, 3]         [1, 6]          2        6
(-1,0)        [-6, 0]        [-9, -5]        9        1
(0.78,0.63)   [0, 6.56]      [4.53, 7.65]    2.03     7.65     (B's slanted edge)

Every axis has overlapping intervals, so the shapes touch. The smallest depth is 1, found on the x axis, with B on the positive side: normal (1, 0), depth 1. Moving B left by 1 separates them.

Contact manifold

The solver needs more than a yes or no. A contact manifold carries the normal, the depth and one or two contact points. Normal and depth come from SAT; contact points come from clipping the two touching edges against each other. A flat box lying on the ground needs two points or it rocks.

GJK

SAT needs a finite list of edge normals. GJK only needs a support function (the farthest point in a given direction), so it also handles circles, capsules and any convex shape; its companion EPA recovers normal and depth. For two boxes a tuned SAT is usually faster.

Common mistakes

• Using only A's edge normals. A gap can lie on a normal of B.
• Forgetting to normalize the axis. The projections are then scaled and the depth is wrong.
• Using the interval overlap for depth; containment is under-reported.
• Returning the first axis that overlaps instead of the one with the smallest depth.
• Getting the normal's sign from a guess. The sign comes from which push (+ or -) was smaller.

Your exercise

The starter reads the polygons and the commands and prints the answers; you write project and sat. The most likely mistake is skipping B's edge normals.