Speeding up the separating axis test using inscribed spheres

Separating axis tests (SAT) reliably compute contact manifolds for convex polytopes but can become costly, especially due to edge-pair checks. The presented technique uses inscribed spheres (or circles in 2D) to compute a cheap upper bound on separation along any candidate axis: for two inscribed radii rA and rB and vector d between centers, the maximum projected separation along unit axis n is bounded by n·d − (rA + rB). That bound lets many face checks be rejected with a single dot product instead of O(N) work per face; a small shrink of the combined radius guards against round-off. This preserves SAT’s global search character while trading a few inexpensive tests for large savings in projection work.

In 3D this extends to edge culling via the Gauss map: each edge produces an arc between adjacent face normals, and projecting d into that arc’s plane yields a vector w whose norm gives an upper bound on any edge-generated axis. If that bound cannot exceed the best face separation so far, the edge can be skipped before any expensive edge-pair test. Implemented carefully, this yields dramatic pruning - example hulls saw ~86% of face tests and ~98% of edge-pair tests culled, roughly doubling narrow-phase performance; slimmer shapes still benefit (e.g., ~76% edge cull), while deep overlaps naturally reduce effectiveness.