Once the broad phase flags a candidate pair, the narrow phase decides if they really collide. The Separating Axis Theorem tests convex shapes exactly and gives you the data needed to resolve the hit.
The Separating Axis Theorem (SAT) states that two convex shapes are not overlapping if and only if there exists an axis along which their projections do not overlap. So to test collision you check a set of candidate axes (the face normals of both shapes); if any axis separates them, they miss; if none does, they collide. SAT is the standard exact test for convex polygons and boxes.
Separating Axis Theorem (for CONVEX shapes):
Two convex shapes do NOT overlap <=> there is some AXIS on which their
projections (shadows) do not overlap.
So: for each candidate axis (the face normals of both shapes),
project both shapes onto it -> two [min, max] intervals.
if ANY axis has a gap between the intervals -> NOT colliding (early out).
if NO axis separates them -> they ARE colliding.
|----A----| |----B----| gap on this axis -> separated -> no collision
Convex only. Concave shapes must be split into convex pieces first.The core operation of SAT is projecting a shape onto an axis: take the dot product of each vertex with the axis and keep the minimum and maximum — that interval is the shape’s "shadow" on that axis. Two shapes are separated on an axis when their shadow intervals do not overlap. This small routine, run over each candidate axis, is the whole algorithm.
def dot(a, b): return a[0]*b[0] + a[1]*b[1]
def project(vertices, axis):
# the shape's shadow on 'axis' = [min, max] of vertex dot products
dots = [dot(v, axis) for v in vertices]
return min(dots), max(dots)
def overlap_on_axis(vertsA, vertsB, axis):
minA, maxA = project(vertsA, axis)
minB, maxB = project(vertsB, axis)
return maxA >= minB and maxB >= minA # intervals overlap?
square = [(0,0),(2,0),(2,2),(0,2)]
other = [(1,1),(3,1),(3,3),(1,3)]
print(overlap_on_axis(square, other, (1,0))) # True (overlap on X)Putting it together: gather the candidate axes (the edge normals of both polygons), and for each, check whether the projections overlap — the moment you find a separating axis, return "no collision." If every axis overlaps, they collide, and the axis of smallest overlap gives the collision normal and penetration depth you need to resolve it. This produces both the yes/no answer and the resolution data.
def edge_normals(verts):
axes = []
for i in range(len(verts)):
p1, p2 = verts[i], verts[(i+1) % len(verts)]
edge = (p2[0]-p1[0], p2[1]-p1[1])
axes.append((-edge[1], edge[0])) # perpendicular = the edge's normal
return axes
def sat_collision(a, b):
for axis in edge_normals(a) + edge_normals(b):
if not overlap_on_axis(a, b, axis):
return False # found a separating axis -> no hit
return True # no separating axis -> colliding
square = [(0,0),(2,0),(2,2),(0,2)]
other = [(1,1),(3,1),(3,3),(1,3)]
print(sat_collision(square, other)) # True
# the axis of MINIMUM overlap = the collision normal + penetration depth (next).SAT is simple and great for boxes and polygons, but its axis count grows with shape complexity. The GJK algorithm is the industry alternative: it works on any convex shape via a "support function" and iteratively builds a simplex to decide overlap, with EPA computing penetration depth afterward. You do not usually implement these — engines do — but knowing SAT for simple shapes and GJK/EPA for general convex shapes tells you what your engine is doing.
Narrow-phase toolkit:
SAT simple; test the face normals. Best for boxes + polygons.
axis count grows with shape complexity.
GJK works on ANY convex shape via a "support function"
(farthest point in a direction). Builds a simplex to decide
overlap. Scales better to complex convex shapes.
EPA runs after GJK to get penetration depth + collision normal.
You rarely hand-write these — physics engines (Box2D, Bullet, PhysX) provide
them. Know SAT for the intuition, GJK/EPA as what engines use for general shapes.