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.
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!
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!
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
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.
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 😄
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. :)
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.
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.
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.
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.
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.
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 :(
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.
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!
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.
@@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?
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
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).
@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.
![BLACK BAG - Official Trailer [HD] - Only in Theaters March 14](http://i.ytimg.com/vi/Du0Xp8WX_7I/mqdefault.jpg)
As always, I learn great knowledge every time I watch a new Gustavo video :)
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.
This channel is a hidden gem!
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!
You are the best man, Really great video with clear explanation.
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.
Nice one Gustavo! Keep up the good work Amigo.
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!
it's very helpful for me, thanks for the clear explanation
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
Thank you! I was able to create my own 2d Physics Engine!
Great!!! What language did you use to write your physics engine, Myelin?
Amazing video. Thanks you a lot.
thank you. very well explained.
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.
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 😄
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. :)
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!
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.
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.
Hes Gus Fring. Dw abt it
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.
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.
Great video brother
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.
Amazing. Thank you.
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
Hi Prof Gustavo, I sense a new course on game physics coming up? So when will it to be released :D
Hello! If everything goes well, in about two weeks. 🤞
@@pikuma cant wait, looking forward to enroll into it :)
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 :(
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.
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!
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.
@@pikuma Oh wow, that was fast! Thank you very much!
@@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?
How can this transfer to, say, 3 dimensions, instead of 2D, for cases of working with a 3D OpenGL/C++ engine?
i would guess you try to find a plane in the same way as this.
Nice video bro
Boa Gustavo, tu é foda
Grande!
Thank you!
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?
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
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 )
GJK only works with convex hulls too.
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).
@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.
I run your code but don't work😢
This guys name and accent litterally reminds me of Gus Fring
"Lalo Salamanca lives."😐
Intresting as fuck
feel like theres a filter
o o... i'm 13 years old and want a sat collision on my game but this math pfff...
Don't worry, just use the collision functions that your engine already provides. This math will only make real sense omce you're in high-school. 🙂
holy fuck Gus Fring