The GJK Algorithm for intersecting shapes (2021) [video]

https://www.youtube.com/watch?v=ajv46BSqcK4

by otikik • 4 years ago

54 14 4 years ago

youtube.com

Archelaos• 4 years ago

Interrupting a nicely crafted educational video every few seconds with a commercial is a terrible idea.

bruce3434342• 4 years ago

https://ublockorigin.com/

maccard3• 4 years ago

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

boppo12• 4 years ago

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.

boulos• 4 years ago

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!)

maccard3• 4 years ago

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!

moonchrome• 4 years ago

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.

phkahler• 4 years ago

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.

maccard3• 4 years ago

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!

Azrael3000• 4 years ago

The big issue with intersections of convex objects is that there might be infinitely many intersection points (two cubes lying on top of each other). This creates a multitude of numerical issues. I worked on this topic extensively for a DEM software where you need to calculate a lot of these interactions with extremely high precision (overlaps between objects are usually < 1% of the bounding radius) and since it's not computer graphics but engineering you really need stability and performance. That was a real tough challenge involving lots of identifying limiting scenarios during large simulations but it works quite nicely now [0].

[0] https://www.youtube.com/watch?v=pjQTzwAqnHM

rustybolt• 4 years ago

How can people watch this? After 4 minutes of video I've seen 8(!) ads already.

bruce3434342• 4 years ago

https://ublockorigin.com/

mbStavola• 4 years ago

I've implemented GJK after watching Casey Muratori's video on the subject. It was surprisingly straightforward and I was able to bang it out in a day or two for the game I was working on a few years ago.

But GJK only gives you part of the story. The fun bit comes after with EPA[2], which gives you more actionable information for your collision detection routines. It took me a bit longer to grok EPA than it did GJK; I probably spent a week or so fixing bugs and handling edge-cases before I had something that worked consistently. However, the fact that you can just use the last simplex you calculated from GJK to continue with EPA was a very nice property to have.

[1] https://youtu.be/Qupqu1xe7Io [2]: https://dyn4j.org/2010/05/epa-expanding-polytope-algorithm/

The GJK Algorithm for intersecting shapes (2021) [video]

Related Stories