5 ms·

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

54 points by otikik 4y ago

Archelaos 4y ago
Interrupting a nicely crafted educational video every few seconds with a commercial is a terrible idea.
- bruce343434 4y ago
  https://ublockorigin.com/ https://ublockorigin.com/
maccard 4y 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 https://caseymuratori.com/blog_0003
- boppo1 4y 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 4y 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/ 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!)
    - boppo1 4y ago
      Thanks!
  - maccard 4y 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 4y 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 4y ago
Azrael3000 4y 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 https://www.youtube.com/watch?v=pjQTzwAqnHM
rustybolt 4y ago
How can people watch this? After 4 minutes of video I've seen 8(!) ads already.
- bruce343434 4y ago
  https://ublockorigin.com/ https://ublockorigin.com/
mbStavola 4y 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 https://youtu.be/Qupqu1xe7Io [2]: https://dyn4j.org/2010/05/epa-expanding-polytope-algorithm/ https://dyn4j.org/2010/05/epa-expanding-polytope-algorithm/

54 points by otikik 4y ago

Archelaos 4y ago

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

bruce343434 4y ago
https://ublockorigin.com/ https://ublockorigin.com/

maccard 4y 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 https://caseymuratori.com/blog_0003

boppo1 4y 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 4y 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/ 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!)
  - boppo1 4y ago
    Thanks!
- maccard 4y 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 4y 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 4y ago

Azrael3000 4y 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 https://www.youtube.com/watch?v=pjQTzwAqnHM

rustybolt 4y ago

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

bruce343434 4y ago
https://ublockorigin.com/ https://ublockorigin.com/

mbStavola 4y 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 https://youtu.be/Qupqu1xe7Io [2]: https://dyn4j.org/2010/05/epa-expanding-polytope-algorithm/ https://dyn4j.org/2010/05/epa-expanding-polytope-algorithm/