Two Different & Unknown GJK Algorithms, Visualized, Implemented, and Explained
HTML-код
- Опубликовано: 21 авг 2024
- There are actually two different GJK algorithms! You can really only find information online about one of them, which I refer to as the shortcut algorithm.
First, be sure to check out and WISHLIST my game on steam!
store.steampow...
Catch my gamedev and gamejam stream sometimes!
/ kujukuju
To see the code for both algorithms, check out my github repo.
github.com/kuj...
For more information about this shortcut algorithm, check out Casey Muratori's video. One of the best in depth explanations of this algorithm.
• Implementing GJK - 2006
There other algorithm, which relies on origin projection onto the simplex, is the more complete version of this algorithm, and contrary to Casey's video, this algorithm has divides. This algorithm also returns more information upon non-intersection such as the nearest faces and the distance between convex hulls. This information is necessary for time of impact physics engines.
For more information about the complete algorithm, check out the book "Real-Time Collision Detection" by Christer Ericson.
This is absolutely the best explanation of the GJK algorithm that I have found. Thanks!
My guy, so much appreciation for this. Recently I've been redoing my engines contact creation using Dirks GDC talk. The "shortcut" method as you describe has just been plaguing my search results
Very nice video! Please continue!
Thanks! Im trying to write my own physics engine and it helped me alot to understand gjk
you deserve at least x10'000 more subs man
Fantastic. Thanks
Is that rat-human from "From the New World" anime? That's one of my favourites anime
It's a really cool anime. I would love to see some more exploration of that world.
The ending has a huge plot hole though...
Why did she die when she killed the rat?
She wiped out an army of them earlier and it didn't bother her.
Is this algorithm fastest? I want to compare different collision algoritms.
hey, it would depend on your specific use case, but I would say GJK + EPA is more or less the industry standard for resolving overlaps. it works with any shapes, and also in 2d. (so, it's probably the fastest generic algorithm if I had to guess...)
Im trying to understand but you don’t really explain what you mean by “in the direction of the origin”. It makes sense for a point, but what do you mean when you have a line, triangle, or tetrahedron? It would also be easier to see if you moved the spheres such that the lines aren’t so close to the origin.
Without looking back at the exact context of the video, "in the direction of the origin" for a point means, as you expect, just towards the origin.
From a line probably means "in the direction of the origin" AROUND the line. So whatever perpendicular/orthogonal direction from the line is closest to the origin.
From a triangle would be whichever face normal (positive or negative) is going most towards the origin.
From a tetrahedron, typically for GJK you would find which of the normals of the 4 triangles (actually only 3 because you know the back triangle is impossible) is pointing closest to the origin. And you would replace your tetrahedron with that triangle and then repeat the triangle case above to further expand into a tetrahedron that is now closer to the origin.
For most of these non-point cases, depending on the type of GJK you're implementing, you might also need to consider every single case before it. So for a line, you need to consider the perpendicular directions AND each of the 2 vertices.
It seems pretty confusing explaining it all at a high level over text like this, so if it's still hard to follow I'd check out caseys video if you can ignore the quality.
ruclips.net/video/Qupqu1xe7Io/видео.html