A fast 3D collision detection algorithm

72 OlympicMarmoto 4 7/9/2025, 2:12:16 PM cairno.substack.com ↗
I discovered this collision detection algorithm during COVID and finally got around to writing about it.

github repo: https://github.com/cairnc/sat_blog

Comments (4)

reactordev · 1h ago
This is novel indeed! What about non-spherical shapes? Do we assume a spherical bounds and just eat the cost? Either way, narrow phase gets extremely unwieldy when down to the triangle level. Easy for simple shapes but if you throw 1M vertices at it vs 1M vertices you’re going to have a bad time.

Any optimization to cut down on ray tests or clip is going to be a win.

bruce343434 · 37m ago
Most likely this can be preceded by testing branches of some spatial hierarchy datastructure, 1 million squared is a lot to compute no matter the algorithm
reactordev · 28m ago
Without optimizations of the vertices buffer, correct, it’s a 1T loop. But we can work on faces and normals so that reduces it by a factor of 3. We can octree it further as well spatially but…

There’s a really clever trick Unreal does with their decimation algorithm to produce collision shapes if you need to. I believe it requires a bake step (pre-compute offline).

I’d be fine with a bake step for this.

double051 · 1h ago
Hey that's Ascension from Halo 2. Cool test case!