Collision Detection with SAT (Math for Game Developers)

Рет қаралды 25,900

pikuma

Күн бұрын

Пікірлер: 60

@Jaqopx 3 жыл бұрын

As always, I learn great knowledge every time I watch a new Gustavo video :)

@dinosoeren 10 ай бұрын

Some key comprehension points that I think were left out of or understated in this video: 1. This algorithm _uses_ SAT but is not the same thing as SAT itself. To find the separating line S between two convex polygons P1 and P2, requires picking a common projection axis A (often confusingly referred to as the "separating axis") on which to project the vertices v1,i of P1 and the vertices v2,j of P2. In effect of this projection, each polygon becomes a flat line interval across axis A. If the projected intervals don't overlap on the axis A, then the SAT theorem states you can draw a separating line S perpendicular to the axis A inside the gap between the intervals. 2. Anytime you hear him say "projecting (pairs of) normal vectors" shouldn't be taken literally, b/c "projecting a normal vector" onto another vector is actually a singular operation - what he really means is *_selecting the projection/separating axis A_* using the direction of the normal vector n1,i associated with edge e1,i of P1 (or the direction of the normal vector n1,j associated with edge e2,j of P2). Then, regardless of the chosen edge, *_all vertices_* of P1 and *_all vertices_* of P2 are projected onto axis A. Mathematically, we only care about the max and min components of the projection, since those form the interval. 3. The reason *_why it even makes sense_* to consider the normal vectors perpendicular to the edges of polygons P1 and P2 as candidates for the projection axis A, is b/c if any separating line S exists between P1 and P2, then it's possible to rotate S to be parallel to some edge e1,i of P1 or some edge e2,j of P2. This can be proven by contradiction, since if S cannot be rotated to be parallel to some edge e1,i of P1 or e2,j of P2, then it's possible to find an overlapping projection of vertices of P1 and P2 onto S's perpendicular projection axis A, which contradicts the SAT. Therefore a correct choice for A is guaranteed to be perpendicular to some edge e1,i of P1 or e2,j of P2. 4. If you're confused why this code implementation uses the normal of the *_vertex_* instead of the normal of the *_edge_* - remember that each vertex is a point on 2 edges of the polygon, so the vertex normal _is_ the normal of one of the edges. As long as the edge for each vertex is chosen consistently, the validity of the algorithm isn't impacted by which edge you pick. 5. Taking advantage of SAT theorem can produce a more efficient implementation, because for the purpose of detecting collisions (not overlap distance), once you've found _any_ axis of separation, it's safe to break out of the vertex loop and return false. Regardless, you may want to check the size of the gap is >0 before returning, since otherwise this naïve algorithm won't detect a collision when the polygons are simply touching and not overlapping.

@Killerkraft975 Жыл бұрын

Great video but had problems understanding at the end. When using the code, it would be great if you did a step by step process + diagram to show how each part of the code works together with the dot products + minSep

@mithogui 2 жыл бұрын

This channel is a hidden gem!

@4T4T. Ай бұрын

Hey Gustavo just a moment ago i succesfully implemented SAT the funny part about it was that i was not getting the correct vertice positons so i had to rewrite my code over 4 times 🤣 love your tutorials!

@ManWithoutSoup_ 2 жыл бұрын

I've watched many different videos about the SAT, this is the best. Very clear and understandable with illustrations. It was very easy for me to understand how to write AABB and quite difficult to understand how to write OBB. thank!

@sleepnaught 2 жыл бұрын

Fascinating stuff. I'm too far behind in math to implement something like this, but I'm working my way up. These algorithms are really neat.

@tinydoggames7443 3 жыл бұрын

Nice one Gustavo! Keep up the good work Amigo.

@firaoldereje415 Жыл бұрын

You are the best man, Really great video with clear explanation.

@ignacioja 7 ай бұрын

Hi! Great tutorial! but I've some questions 1 - The values of vertices is one number or two? for example va = 1 or va = (x,y)? I guess the second option because you store the result in a vector (Vec2) 2- How can I calculate the Perpendicular value for va? (then you store this as normal) or maybe you can show one example? I try to replicate this code in JS. I understand that is the projection where you after do the comparative between both vertices to find the gap.

@RelativeResonance 5 ай бұрын

I think we could reduce calculations by prioritising the normals, that are similar in direction to the vector that goes from object A to B

@nguyenoanthanhcao8857 Жыл бұрын

it's very helpful for me, thanks for the clear explanation

@oolong4700 2 ай бұрын

Amazing video. Thanks you a lot.

@danielsharp2402 3 жыл бұрын

One question thats been bugging me is is it possible that we do have to test the second set of normals as well, meaning the first set is inconclusive. I have never found such configuration.

@rautamies2305 Жыл бұрын

As a 3D implementation where you have 2 tetrahedrons, could you define 3 planes with the faces of the triangles and simply check the signed distance of the other triangles points to those planes? That way if you found a set of vertices that all have a positive signed distance, you know the tetrahedrons are separated.

@firstacc5442 3 жыл бұрын

Hello sir First of all this is amazing tutorial I ever found on internet I implemented SAT for polygons and seperating them normally using projection resolution (like position correction) Now I would like to implement ANGULAR IMPULSE RESOLUTION for that I need POINT OF CONTACT (main folds) I kindly request you to make a tutorial on how to find contact points of collision for SAT Thank you sir, Have a nice day 😄

@pikuma 3 жыл бұрын

Hello! The answer to your question and the explanation+code will be in my new video book on 2D game physics. It will be up live next week on pikuma.com. Sign up to receive news. :)

@firstacc5442 3 жыл бұрын

Wow thank you very much sir, I would love to buy this "2d game physics" course....thank you again for making this uncovered tutorials sir!

@alessiostefanelli5663 2 жыл бұрын

Hello! Thank you for the great content! I'm a little bit confused about two points: 1) It seems like you compute the normal of the vertices and not the edges (Perpendicular(va), C++ code), does it lead to the same result? 2) Is it correct to say that FindMinSeparation computes the minimum distance between the vertices of the first polygon a and the contour of polygon b? that's why you make the double check in IsCollidingPlygonPolygon? Thank you very much.

@dinosoeren 10 ай бұрын

It's important to remember that each vertex is a point on 2 edges of the polygon, so the vertex normal _is_ the normal of one of the edges. As long as the edge for each vertex is chosen consistently, the validity of the algorithm isn't impacted by which edge you pick.

@BingusBongusMan Жыл бұрын

Wouldn't this lose the efficiency of the separating axis theorem, since normally you would return early as soon as you find the first axis where there is no overlap? This seems to require calculating every vertex against every vertex since you never evaluate 1 axis fully at a time. i.e. a scene with sparsely laid out convex polygons would normally be very fast, since most axis will have no intersection. But with this, even if they were spaced a mile apart you would need to evaluate every vertex. I know this is a contrived scenario, and you'd probably have spatial partitioning or something which would make this notably faster, but it still feels like I'm missing something.

@honkhonk8009 Жыл бұрын

Hes Gus Fring. Dw abt it

@myelinsheathxd 3 жыл бұрын

Thank you! I was able to create my own 2d Physics Engine!

@pikuma 3 жыл бұрын

Great!!! What language did you use to write your physics engine, Myelin?

@keresztesjonatan5015 2 ай бұрын

Can you please explain how does the Dot function works? I understand everything else. So we make a vector from vb-va and rotate it so it will be paralel with the normal vector? and than what? I don't get it :(

@duketwo22 2 жыл бұрын

thank you. very well explained.

@Bopek Жыл бұрын

Amazing. Thank you.

@Sam-im6lk 3 ай бұрын

if you're using a square, wouldn't the normal of a side be in the exact same direction (but opposite magnitude) as the normal on the oposite side of the square? you only have to do 2 calculations for squares instead 4 if i undserstand this correctly.

@faizanahmed9304 3 жыл бұрын

Great video brother

@JacobElliottSermons 3 ай бұрын

How can this transfer to, say, 3 dimensions, instead of 2D, for cases of working with a 3D OpenGL/C++ engine?

@Sam-im6lk 3 ай бұрын

i would guess you try to find a plane in the same way as this.

@cursedfox4942 Жыл бұрын

the thing no one shows is how to project the points i guess you compare amax and a min and bmax b min point amax(x,y) amin(xy) and bmax(xy) bmin(xy )

@mohsinmd2662 3 жыл бұрын

Hi Prof Gustavo, I sense a new course on game physics coming up? So when will it to be released :D

@pikuma 3 жыл бұрын

Hello! If everything goes well, in about two weeks. 🤞

@mohsinmd2662 3 жыл бұрын

@@pikuma cant wait, looking forward to enroll into it :)

@paralol_ 2 жыл бұрын

Hello! Thank you very much for this video, it really helped me to understand OBB and has led me to try to implement it myself. I am having some trouble in my algorithm, but, I can't pinpoint exactly where the error is. Could you please share the code or just explain what exactly is the Perpendicular method in PolygonShape doing? Is it just a regular cross product or is some other mathematical function? Again, thank you for your time!

@pikuma 2 жыл бұрын

Hello! Sure. The Perpendicular method is actually very simple: Vec2 Vec2::Perpendicular() const { return Vec2(y, -x).Normalize(); } Where Normalize is the simple vector normalization function, which I assume you are familiar with. I hope this helps.

@paralol_ 2 жыл бұрын

@@pikuma Oh wow, that was fast! Thank you very much!

@ScrewY0UguyS 15 күн бұрын

@@pikuma I mean. Isn't it a normal vector of a point and not the edge? If you imagine axis aligned box and a point (1,1) , than your normal is (-1, 1) - which is basically diagonal line. While all the normals of the edges of a box are aligned with axis. SO, whatever your algorithm is, it's not what you're showing in your video. Am I right?

@harywhiteproductions Жыл бұрын

Thank you!

@razorblade413 Жыл бұрын

why do we need to check the vertices of b if we checking only the vertices of a we could be sure that there is no collision at all?

@gmdrandom6287 Жыл бұрын

What do you mean? To get the separating axes we need to check both polygons and to check if two polygons are colliding we need to project the polygons and to do that we must project and check both polygon A and B

@danyfour7754 3 жыл бұрын

Nice video bro

@ToothbrushMan 8 ай бұрын

GJK only works with convex hulls too.

@pikuma 8 ай бұрын

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

@ToothbrushMan 8 ай бұрын

@pikuma This is indeed the case with GJK. GJK tells you if two convex hulls overlap and the result is a triangle/tetrahedron that encloses the origin. Because the Minkowski difference encloses the triangle/tetrahedron, the origin must, therefore, be inside the Minkowski difference, and the two hulls must intersect. At this point, the EPA can start expanding the triangle/tetrahedron to determine the point on the Minkowski difference that is closest to the origin. This point maps onto two points on each convex hull and a normal vector that will tell you the minimum displacement that is required to separate the two convex hulls. However, the GJK will also only work on convex hulls, Also, the EPA does not use the Minkowski sum. It uses the Minkowski difference of the two convex hulls.