←back to thread

A fast 3D collision detection algorithm

(cairno.substack.com)
269 points OlympicMarmoto | 1 comments | 09 Jul 25 14:12 UTC | HN request time: 0s | source

I discovered this collision detection algorithm during COVID and finally got around to writing about it.

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

Show context
reactordev ◴[09 Jul 25 16:03 UTC] No.44511689[source]▶
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.

replies(5): >>44511963 #>>44512034 #>>44512617 #>>44512959 #>>44513664 #
bruce343434 ◴[09 Jul 25 16:28 UTC] No.44511963[source]▶
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
replies(1): >>44512078 #
1. reactordev ◴[09 Jul 25 16:38 UTC] No.44512078[source]▶
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.