Comment by maccard | Hacker News Reader

Comment by maccard | Hacker News Reader

This brings back a lot of memories. I wrote a 3d physics engine about 10 years ago and implemented GJK. Despite how simple this video may make it look, it's an absolute minefield of a problem (and for a 3d physics engine, only 1/4 of the problem you need to solve for). GJK only tells you if two convex hulls are overlapping, it doesn't give you information about how they're overlapping. For that you need to use something like the Expanding polytope algorithm (which is very similar to GJK but uses minkowski sum instead of differences). Both of these algorithms are sensitive to numerical precision issues (and were responsible for me learning far more about floating point numbers than I ever wanted to know), and a lot of the resolutions to the numerical precision issues are not scientific, they involve fudging for "feel" (at least with single precision floats!)

Despite it being a "fast" algorithm, it's actually fairly slow. The performance is based on the performance of your support function, and in practice, heavy caching of results is required to get very good results out of it!

It also only operates on a pair, meaning you need a higher level algorithm to cull down pairs to check (commonly referred to as a "broad phase" step). Again, a good broadphase relies heavily on caching and pre-existing state!

For extra fun, here's another video[0] from much longer ago by Casey Muratori, known for the Handmade Hero and other handmade style creations. [0] https://caseymuratori.com/blog_0003

Can you recommend a good resource for learning these types of geometrical algorithms? Is there a collection somewhere? I'm trying to get into graphics programming.

Depends how deep you want to go. But I'd personally suggest going through past courses from someone in the field. For example:

https://igl.ethz.ch/teaching/shape-modeling/sm2022/

is a course that Olga Sorkine-Hornung taught in the Spring. Seems to have some decent course titles, but apparently the course slides are only available at ETH itself... (anyway, find some other course and dig in!)

Thanks!

The nitty gritty math of convex shape overlap tests is super interesting but unlikely to help if you're interested in Graphics programming (for the most part). Theres a few books on game development from the late 2000's like Real Time Collision Detection that cover them, for example.

If you're interested in Graphics programming it's probably the wrong path to go down, and I don't have any resources I can provide there sorry. I'm not a graphics programmer at heart, unless it needs to be done!

Oh man I spent months in highschool thinking about that algorithm. I remember reading some paper on it and being confused by notation and then I found Casey's video and it was so simple to understand. It made me think what was the point of papers when they make such trivial things so hard to understand.

Never really got EPA working correctly, was too OCD to finish stuff like that back then.

Did you ever consider using the Separating Axis theorem? It's fairly simple and also only works for convex shapes. The math can be implemented quite fast - lots of dot products. It also works in 3d where there are more candidate axis to consider but the test is the same.

I did! I actually wrote a couple of methods and tried them out (including V-clip, a patented algorithm). From what I recall, I ended up sticking with GJK because of how it interacted with EPA (which you need to figure out the actual result of the collision). It's been a few years though so it could have also just been a bad implementation on my part. That code lives in multiple shipped games though, which is cool!

Reply on news.ycombinator.com