Discussion about this post

User's avatar
Sergiy Migdalskiy's avatar

Hi, I'm the author of the SAT chapter in Physics Pearls book.

Long ago (10-15 years, so my memry is fuzzy), I implemented this very idea. The scan without some O(N^2) loop is nontrivial - I used O(N+M) Bentely-Ottmann algorithm for finding all the edge-edge intersections of the gauss maps.

It has awesome theoretical properties because you're essentially just enumerating the very minimal set of axes, and you don't even have to evaluate support function for them! The perf bottleneck was the graph algorithm itself: it took ~100 vertex hull for it to start being faster than the highly SIMDizeable sweep of classic SAT (with the optimization you're mentioning here).

I implemented two variants sweeping from north to south and west to east (planar graphs of a sphere are a bit tricky), but ultimately 100 vertex hulls aren't super useful in games, so I dropped the idea.

It'd be very humbling to find out I was wrong and there is a fast algorithm to find all the intersections that makes this idea workable for smaller (~10 verts) hulls. I'd appreciate if you described the algorithm, as I can't tell what it is from skimming the code. At which point is it faster than SIMDized optimized classic SAT? I didn't try any other algorithms but BO, it's probably possible to make a practical BVH on the gauss map that works better, but I haven't tried it. BO is quite fast, but it's hard to beat the speed of a simple optimized SIMDized loop.

Expand full comment
4 more comments...