Detecting Polygon Collisions Using SAT

Detecting and resolving collisions between point-mass particles is pretty straightforward. See the previous post on "Simulating Lift: Particle-Particle Collisions". But how does one detect collisions between particles and a 2D polygon, e.g., an airfoil shape?

Overview

The Separating Axis Theorem (SAT) offers a way to detect collisions between polygons. I like to think of it as shining a light from various directions on the polygons of interest, and checking whether any lighting angle results in multiple shadows.

Before reading further you may want to read "N Tutorial A - Collision Detection and Response". That's where I learned about the Separating Axis Theorem, aka the Hyperplane separation theorem.

Perspective

If two shapes are not colliding, i.e., they are not overlapping, then there must be a lighting angle that projects distinct shadows for the two shapes. In other words there must be an angle at which their projected extrema do not overlap.

(There is an obvious exception to this. See below.)

True Collision

No matter the lighting angle, you won't see any daylight between two shapes that overlap each other. They will always project a single shadow.

Limitations

If one shape is nestled in a hollow of another, concave, shape, then even if the two shapes are not in contact, they may project a single shadow. This is true regardless of lighting angle. SAT doesn't work reliably with concave shapes.

Algorithm Details

Here's a procedure for implementing an SAT polygon overlap test.

Angles to Check

The interactive figures may give the impression that it's necessary to analyze the polygons from every possible angle, but it's enough to use the normal to each polygon edge as the separating axis. In other words, it suffices to project along the direction of each polygon edge. Again, see Wikipedia.

Finding "Shadow" Boundaries

For each angle, consider each edge \(e\) of each polygon in turn.

Find \(e\)'s normal vector, \(n\). This is analogous to the wall onto which any shadows will be projected.

Then, for each polygon \(p\), and for each vertex \(v\) of \(p\), find the projection of \(v\) onto \(n\): that is, find \(v \cdot n\). In effect, this is where the shadow of \(v\) lies on the normal vector "wall".

Checking for Overlap

The extent of the "shadow" of a polygon \(p\) is given by the minimum and maximum projections of its vertices onto \(n\).

If, for any edge normal \(n\), the polygon extrema do not overlap, then the polygons themselves do not overlap. Otherwise - assuming neither polygon is concave - the polygons do overlap.

Summary

Here's the algorithm expressed in Python-like pseudocode.

def projected_extrema(poly, normal):
    projections = [v.dot(normal) for v in poly.vertices()]
    return (min(projections), max(projections))


def extrema_overlap(e1, e2):
    for v in e1:
        if (e2[0] <= v < e2[1]):
            return True
    return False


def polygons_overlap(poly1, poly2):
    for edge in chain(poly1.edges(), poly2.edges()):
        n = edge.normal().unit()

        extrema = [projected_extrema(poly, n) for poly in [poly1, poly2]]
        if not extrema_overlap(*extrema):
            return False
    return True

Circles

It's easier to calculate projected extrema for circles than for polygons. First find the projection of the center of the circle, as if it were a polygon vertex. Then add and subtract the radius to find the projected extrema.

Extra Information

The algorithm above is adequate for detecting collisions between two polygons, but more info is needed in order to actually resolve collisions. That's a subject for another post.

In the particle-based simulation, most of the collisions involving polygons occur between point-mass particles and polygons, rather than between pairs of polygons. In some particle-polygon collisions the particle impinges, not on an edge, but on a polygon vertex. Detecting and resolving a particle-vertex collision is also a matter for another post.