Fast, Accurate Collision Detection for Arbitrary Triangle Meshes

January 8, 2013 General News 10 Comments

This is probably the single most exciting post in my three years of blogging. It's definitely what I feel to be the biggest technical achievement, in terms of what people usually think of as being technical achievements. At first I wrote an exceedingly long post and a mini-history of my experiences with collision detection, and the development of this new algorithm. But it was too long and boring, so I'm just going to get to the facts.

Tonight, frustrated by the poor performance of Bullet's concave-concave solver (GIMPACT), I've developed a general-purpose intersection algorithm that works for any kind of mesh (convex, concave, degenerate, ... pretty much whatever you want), allows any kind of world transform (including scaling, shearing, ... pretty much whatever you want), and is remarkably fast. Maybe it's not that great, maybe everyone already knows about it...but I feel like I would have heard about it by now. I mean, it takes less than 200 lines to implement this incredibly simple, powerful algorithm that blows GIMPACT out of the water. Am I missing something?? Maybe so. I need to do some more tests to make sure I'm not being premature, but initial tests show that it takes an absurdly small amount of time, even for insane meshes. For example, I tried checking two full-quality asteroids against one another...a test that should be prohibitively expensive (they're concave and roughly 50000 polys)...and it takes almost no time at all (concrete numbers to come in the future). Wow. I can run full physics on my full meshes now...! And best of all, I can quit worrying about this convexity nonsense, and also drop all the hacks that I had to use to get other physics engines to cooperate with scaling.

I've never been more excited about an algorithm than I am tonight. This may mean ditching the 3rd-party physics library entirely, which would be a dream come true!!! After three years, I've finally gotten collision detection right. I hope to write something on this algorithm soon, so that I can get it out there, and people can tell me whether it's actually novel or not.

If this algorithm is really as good as initial tests show it to be, my belief that everything is fundamentally simple with the right insights...will just be cemented into my mind beyond any shadow of a doubt. If concave-concave collision detection is actually trivial...then can there be anything that isn't?!?