GJK Algorithm Explanation & Implementation
Vložit
- čas přidán 5. 08. 2024
- Spheres are nice and all, but there comes a time when more complex shapes are needed. One popular algorithm for testing collisions is the Gilbert-Johnson-Keerthi algorithm, or GJK for short. With it we can detect collisions between any two convex polygons.
Check out the full article: blog.winter.dev/2020/gjk-algo...
Intro- 0:00
Sphere vs Polygons: 0:17
Supporting Points: 1:20
GJK: 3:20 - Věda a technologie
The best explanation of GJK that i have ever seen in my life
Thanks!
Great video! It just felt a bit too quick on the last section (gjk itself). I’m surprised you only have about 90 subs! Keep up the good work.
Thanks! Pacing is something I still need to pin down... I write articles to go along with the videos so it's a tricky decision
Where were you back in 2013 when I was writing my Terraria world analysis software that depended on computing biome extents using these algorithms...
Thank you for such a clear explanation. This is amazingly informative and very useful.
You are a real talented teacher. Well done!
Just wanna say, the first time I saw this I really appreciated it but didn't truly understand it. Months later, after reading various articles and the like, I understood the theoretical aspect but was hella worried about implementation.
Then I found this vid again and god DAMN it was a life savor
You a life savor
Thanks a ton for saving me a whoooole lotta implementation headache
Thanks! I made this to be sorta like a tutorial if you already knew 50% of it. I’m glad to hear that’s how it worked out for you!
Great explanation! The one slide in my robotics script was nowhere near enough to understand this :D
Thanks, glad it helped!
I'm actually quite impressed with the quality of the videos; visual, simple, and concise. Keep up the great work! P.S. You've earned a new sub :)
This is an awesome explanation
Nice visualizations. I really like the Minkowski Sum one.
It's complicated math but when you simplify it and write the code for it it's actually much faster than you expect
Wow!! Thank you for the easy explanation.!!!
Maybe a small or better implementation is to make the first GJK support to be in the direction of the relative positions of the shapes. That way, you already get an extreme point, using, for instance, the center of mass of both objects 'direction = colliderB->getCenterOfMass() - colliderA->getCenterOfMass()'. Amazing video!!!
I’ve seen some people do that and I think you could shave off some iterations but I was going for extra small code so I didn’t. Thanks!
One word - Superb!
Amazing Explanation!
Thanks glad you enjoyed it
When you say that you iterate the direction D. How you do that? How many directions you use? Which values?
awesome video!! I was reading about gjk on the allen chou game physics blog and just didn't get it. the visualizations made it click immediately
That was quick. The hard part is not copy'n paste that algorithm but understanding why the orientations are correct.
great video ! Unfortunatly the full article is down :c
damn, really nice explanation and visualization
Thanks!
In my implementation I'm never getting support.dot(direction)
I’d start by putting a cap on the number of iterations and see if you’re getting a correct answer. Then I’d log the simplex points and direction to make sure they’re right. If you’re in 2d, you could check out the website winter.dev/lilapps/gjk and put the same points in your code as those and step though each to spot a difference. Good luck! :)
you dropped the best video series ever just to disappear :(
How to find direction in supporting point?
It's needed to know the vertex to compute the algorithm? Some convex sets are given by equations, like c(x)
If you can get a support function then yes. If you look at how the sphere works it generates a point based on the direction and the center point/radius. I think that this also isn’t very good with those types of shapes however because it loops forever unless you put a max step count in. I wonder if there is a version specifically for these types of functions/shapes?
5:57 in the Line case, I found that the AB not pointing towards AO never happening in practice, and if you consider the operation, it go as follows: the same direction check is basically testing the dot product, consider 2d case, ABx * AOx + ABy * AOy > 0, if you substitute the values and re-arrange you get: Ax^2 + Ay^2 > Ax*Bx + Ay*By , wich is basically saying geomretrically: A dot A > A dot B, if A and B are unit vectors and A != B, then this is always true.
Maybe I'm wrong but also if the A point isn't past the origin it wouldn't also be dropped on the main gjk loop with the dir check?
So the Line function doesn't need the false block of if(SameDirection(ab,ao)) because it never will be executed based on my tests, the maths and the logic.
EDIT: ok realised your code uses the Line function on the triangle and tetrahedron, so it's more general, that is why it is possible.
Aa ok this is code that I wrote months ago so I takes a little bit to go back and look. This vid was supposed to be a super condensed version of the one that Casey did, so he came up with the if flow. Glad I got you interested in this algo I appreciate the scrutiny cus I learn more from these comment that I did making the vid in the first place! Thinking about it you’re right for the line case because there can be a further point that A cus that’s the by def what the support point is, but it allows the code to be nice and condensed for the later checks where it could be on either side of A. Thanks for the comment :)
I implemented this in unity and then compared the results with unity's physics engine and with 36 of these mesh colliders the frame rate dropped to 80fps. but with unity's mesh collider it stayed at 280fps. So I would like to know how can I optimize this type of mesh collider?
How are you checking them? Brute force, or some kind of tree algorithm? There's probably a couple of other optimisations that unity is using, but that's one of the big ones I can think of
@@compositeembryo7186 Currently I only have one optimization that is using aabb trees
@@bluedev6304 I don't know if this will help because I am nowhere near the skill of the people who develop unity itself, but maybe give a kd or quadtree a try
my guess is that if unity is using physx then it’s prob more paralleled on the gpu
4:52 - why did you chose -support for the new direction?
And also why did't you normalize this vector? As I got from your explanation vector D should be normalized (2:12)
At 2:21 all the points get scaled by D's length, so you don't need to normalize. And at 4:52 it's slightly confusing but we want the direction to the origin at (0, 0) so you take (0, 0) - support = -support
@@Winterdev thank's a lot for your videos and answer!
p/s: I am writing 3d engine by my own to make a video on my channel about it :)
@@vectozavr Sounds cool, good luck with it! I've got the engine, now I got to make the videos :)
Вектозавр, ты чего тут забыл?)
Pretty sure there is an error in formula @2:20. We want max(D*A - D*B) => max(D*A) - min(D*B) => max(D*A) - (-max(-D*B)) => max(D*A) + max(-D*B). This is using the identity that min(f(x)) = -max(-f(x)). I think you just merged the minus signs on accident. What are your thoughts? Am I missing something?
thought the same thing. I also think, that this is an error.
Not to be a jerk but I think it would be valuable to clarify that this is really the sub-variant of the traditional GJK algorithm (GJK-SAT). As well as this, the number of cases in three dimensional space actually expands to considering all regions rather than just the faces of the simplex. I hate to be rude but I spent way too long figuring this out when attempting to implement this myself. Gino van den Bergen's 'Colllsion Detection in Interactive 3D Environments' documents the GJK as well as Gino's EPA rather extensively, and I think the full distance minimization implementation is insightful for those just figuring this stuff out. Either way, this video does a fantastic job explaining the essence of the support function and the configuration space obstacle. I can't wait to see what else you're up to!
The resource you mentioned has almost 300 pages.
The best tutorial that i have ever seen! Thanks!
I've been struggling with my own implementation for a few days and this really helped, however I'm sometimes getting false positives with an analytical cylinder support when rotation for one or both of the objects is zero, which is strange. I'm not sure if this is fault of the core gjk or the support function though.
Thanks for the comment! I’m gonna need a drawing lol I don’t really know what you mean. Are you saying that when you have two objects, 0 angle, I’m assuming in 2d, the line case fails?
@@Winterdev Thanks for the reply.
When i have two 3d cylinders with an analytically computed support (instead of using a mesh and looping over the vertices) and the rotation is zero in all axes, the algorithm detects a collision where there is none in some cases, even when the objects are really far from each other. I'm not exactly sure where it fails because there doesn't seem to be a pattern, however the core algorithm works 100% of the time when using mesh supports.
Here's the actual function, sorry if it gets mangled by youtube formatting.
vec3 cylinder_support(vec3 dir, float radius, float high_y, float low_y) {
vec3 xz = normalize(vec3(dir.x, 0, dir.z)) * radius;
xz.y = (dir.y < 0) ? low_y : high_y;
return xz;
}
It seems to return almost the same exact points as when using an equivalent cylinder mesh, so I'm not sure where the issue could come from, in my mind it ought to return a marginally different collision when the shapes are really close, not complete nonsense.
And also a screenshot, although you can't tell much from it. i.imgur.com/MR5Knp5.png, the wireframes are green for collision. (ignore the z-fighting on the lower cylinder)
@@chyza2012 Interesting... False positives were a common issue when I was making the original version, but I use the analytical support for the sphere v mesh collisions. I don't see why that would be any different. I'll have to make a cylinder collider and test it in my version. I'll let you know what I find
@@Winterdev
I've resolved this a while ago, but it didn't occur to me to update this comment chain.
In the end it was a dumb division by zero issue in the support function.
if the direction was purely in the y direction, the normalize in the line
vec3 xz = normalize(vec3(dir.x, 0, dir.z)) * radius;
would divide by zero (since the vector would end up being {0, 0, 0}) and result in all nans, these would mess up the rest of the algorithm, apparently this degenerate case happened often enough with perfectly axis aligned cylinders to be an issue.
To fix it i simply added a check
vec3 cylinder_support(vec3 dir, float radius, float high_y, float low_y) {
vec3 xz = vec3(0);
if (dir.x != 0 && dir.y != 0) {
xz = normalize(vec3(dir.x, 0, dir.z)) * radius;
}
xz.y = (dir.y < 0) ? low_y : high_y;
return xz;
}
Might not be the most elegant but it works.
aa that makes sense. I had put your code in, but never got around to making a mesh for it so I couldn't tell if it was correct. Glad you found a solution :)
I don't understand why "support.dot(direction)
I remember changing that to stop an infinite loop if the origin lies directly on the simplex. I think that you're correct in wanting 0 distance collisions, I was only thinking about position, but if you're working with forces, then friction for example would be more accurate with 0 distance collisions. I played around with the code and it seems like that the anomaly caused by
@@Winterdev In 2D, I found a case where a real collision (where they actually collide deeper than just with the border) occur but is not detected by taking 2 same square that are exactly in the same y position and overlap on the x axis. In this case, the first support point is exactly along the x axis. Then, the second support point is also exactly along the x axis in the other direction. In this situation, the Line function will set the direction with the 0 vector. And then, if the direction is the 0 vector, it will verify "support.dot(direction)
@@sebastientaymans Yeah I was playing around with a similar edge case in the little tool, it seems like removing '=' results in the same behavior though. The order of vertices shouldn't matter, it seems like if the direction from the simple is 0, then something has gone wrong so it should just exit, you could put code that checks for this, but in practice it this case never comes up. Maybe there is a stronger way to find the direction, this is a simplified version specifically for games, the people who do CAD need much higher fidelity version that you can read whitepapers about, but they are wordy. dl.acm.org/doi/abs/10.1145/3072959.3083724 this has a cool video
Hello!
It seems like the description and figure for Minkowski difference is wrong. According to the link provided below (and the link in the linked page), the Minkowski difference of A and B should be C s.t. the Minkowski sum of B and C is equal to A. The polygon shown in the video is the Minkowski sum of A and -B rather than their difference. Given that, the algorithm does not produce Minkowski difference, but it's still correct.
Aa good point I was trying to simplify the terms cus everyone talks about a sum but then subtracts, what makes this different than normal addition and subtraction that we can’t flip the terms like I did?
@@Winterdev For example, in 1D world, the sum of A [0, 1] and B [0, 2] would be C [0, 3]. If we use C + (-B), we will get [-2, 3], but if we use C - B, we should get A (meaning undoing the addition operation).
can you do one for EPA?
I am planning to do that next, should be up in the next 2 weeks or so
Amazing content. Hello from Russia.
Thanks from America!
This helped me out so much! So clearly explained! Thank you :)
Nice! Good to hear it helped :)
Your variant breaks down if the origin is contained in one of the edges or faces.
Yeah someone else brought up the >= too. I did that but because it seemed to decrease the number of iterations in some cases without changing how the tests worked. Maybe that has more of an effect than I realized though. You don’t get 0 distance collisions, but those would have no effect so I dropped them, maybe for rotational that is a problem though. I need to see an example of it breaking to put this to rest!
it's a great video! but it's too fast... if you want to reach people who do not already know what you know, give them some time to think about what you're trying to tell them...
Yeah haha that was the goal when I made these vids a year ago. I was thinking that if you wanted to code along, instead of sifting through an hour it would be easier to sift through a condensed 5-10mim cus you need to watch more than once. Looking back now though if you’re not specifically looking for this exactly it’s a tense watch. There are articles to read if the vids too fast was my thought. When I make more tutorial like vids I think I am going to aim for that zen feel. Thanks for the comment!
It might not be stable, floating point comparisons
It seems like you miss a few edge-case checks:
1. For the line simplex: what if the origin is on the line?
2. For the tetrahedron: what if the origin is in a region between two triangular faces? (i.e. sameDirection could return true for two faces of the tetrahedron, if the origin is in the right spot)
Also the animation at 5:35 doesn't represent a possible scenario, if I'm understanding correctly. If you start with point B and search towards the origin, and A is the furthest support point you can find in that direction, no collision occurred because A does not pass the origin in the direction BO.
A solid theoretical intro on GJK in case it helps anyone:
czcams.com/video/SDS5gLSiLg0/video.html
That vid plus this vid saved my life
Oh yea this talk is interesting, I like the bits about expanding surfaces
Ugh. Too. Much. Math. I think i’ll just stick to iterating over my edges to find an overlap