This article will assume some familiarity with narrow phase collision detection methods and associated geometric concepts such as the Minkowski sum.
A few years ago I was watching Dirk’s great presentation, The Separating Axis Test between Convex Polyhedra (video, slides). Around the 18 minute mark (slide 29) he starts talking about overlaying Gauss maps of convex polyhedra to find the faces of their Minkowski difference.
Figure 1: A gauss map for two convex hulls
The upshot is that all faces of the minkowski difference are either:
A face of shape A A face of shape B A cross product of an edge from A and an edge from B
And most importantly, you can avoid a costly full support function evaluation in case #3 because you know a vertex that lies on the face. After letting that fact sink, I wondered — why can’t we skip the support function evaluation for all the points on the Gauss map? Turns out you can, the result is a version of the separating axis test that requires only one full support function evaluation as opposed to FaceCountA+FaceCountB. Before we get to the details, let’s back up a bit.
TLDR: Github repo
Collision Detection Formalization
Let A and B be two bounded convex sets in R³. There are two scenarios:
No overlap — We want the closest point between the two sets. Overlap — We want to find the minimum translation we can apply to separate the shapes.
... continue reading