Speeding up the separating axis test using inscribed spheres
2 days ago
- The Separating Axis Test (SAT) is robust for computing contact manifolds between convex hulls, working well even when shapes overlap unlike GJK.
- SAT can be computationally expensive (O(N^3) in vertices), but optimizations like Gauss maps, SIMD, caching, and contact recycling help mitigate this.
- Using inscribed spheres provides an upper bound on separation for any candidate axis, allowing early culling of non-promising faces and edges.
- For faces, if the bound n·d - r (d is vector between sphere centers, r sum of radii) is less than the current maximum separation, the face test is skipped, replacing N dot products with one.
- For edges, a bound using the Gauss map arc determines if the edge can beat the best face separation, culling many edge-edge pair tests.
- Benchmarks show dramatic speedups: up to 98% edge pairs culled, 62% reduction in collide stage time, and 51% total time reduction in the Convex Pile benchmark.
- This technique makes SAT competitive with GJK without sacrificing global optimality or requiring fallbacks, and it is straightforward to implement.