Collision Detection with SAT (Math for Game Developers)

In this video, you'll learn a collision detection algorithm called the "Separating Axis Theorem."

This quick tutorial will explain the intuition behind the SAT algorithm, and give you an example of how to implement polygon-polygon collision using the Separating Axis Theorem in the context of physics engines.

The SAT is probably one of the most popular collision detection algorithms out there, together with the GJK algorithm.

I hope you enjoy this short tutorial on the world of collision detection.

For comprehensive courses on computer science, programming, and mathematics, visit:

Don't forget to subscribe to receive updates and news about new courses and tutorials:

Enjoy!

[Jaqopx]

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

[dinosoeren]

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.

[ManWithoutSoup_]

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!

[Killerkraft]

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

[sleepnaught]

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.

[firaoldereje]

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

[TT.]

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!

[nguyenoanthanhcao]

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

[tinydoggames]

Nice one Gustavo! Keep up the good work Amigo.

[myelinsheathxd]

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

[ignacioja]

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]

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

[firstacc]

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 😄

[rautamies]

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.

[danielsharp]

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.

[alessiostefanelli]

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.

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

[keresztesjonatan]

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

[Sam-imlk]

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.

[mohsinmd]

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