GJK Algorithm Explanation & Implementation 

Thanks!

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

Thanks, glad it helped!

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!

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!

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

Вектозавр, ты чего тут забыл?)

thought the same thing. I also think, that this is an error.

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

Thanks!

The resource you mentioned has almost 300 pages.

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?

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

Thanks from America!

Thanks glad you enjoyed it

Nice! Good to hear it helped :)

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!

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

@@fhvirus3221 C + (-B) is [0,1]. Long way. [0,3] - [0,2] = [0-0, 3-2] = [0,1]. Doesn't change if you negate and then add [0,3] + [-0,-2] = [0+-0, 3+-2] = [0,1]

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!

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

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

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 am planning to do that next, should be up in the next 2 weeks or so

Oh yea this talk is interesting, I like the bits about expanding surfaces