Separating Axis Theorem: Polygon Collision Detection for Physics Engines

[00:00:00]hello everyone gustavo here today i want to look at an algorithm that is super popular to detect collision between polygons right convex polygons and the name of the algorithm is sat the separating axis theorem the context that we're going to use the separating axis theorem is if we have polygons right we are using boxes in this case but we want to find out if there is a collision if there is a separation or an overlap between these two convex polyes right and then the sat will probably return to us boolean true or false if they are colliding or not so let's look at what the sat algorithm the separating axis theorem is all about and for that i want to start discussing these ideas of this shape that we're going to look right this is what we call an obb right and that stands for oriented bounding box and oriented bounding boxes they are these boxes these polygons that are not aligned with the x's right they are rotated so in a nutshell if we have this axis x and y if we look at the edges of this box you see this edge right here between the vertices these edge these edges they are not aligned with the x's x and y so again in a nutshell oriented bounding boxes they are boxes that are rotated if you ever read in a physics book or a 2d physics engine source code someone called obb they are talking about oriented bounding boxes and that's it right and also the algorithm the sat algorithm that we're going to learn to detect collision between oriented bounding boxes it will also work for any other type of convex polygon so the algorithm doesn't work only for boxes it works for triangles boxes pentagons hexagons heptagons you got the idea right so this algorithm is going to be super useful because not only detecting collision between these simple boxes if we have a more elaborate polygon as long as it is convex the sat is going to work well for these shapes as well so we are going to learn what we call the s-a-t algorithm or the separating axis theorem and the whole context that we are going to apply is this think that you have these two polygons right they just happen to be boxes in this case but they are polygons right convex polymers the sat says that if we have one axis right if there is one axis that we can find that separates those two bodies then there is no collision between those bodies let me read that again the sat algorithm states that if there is at least one axis that separates both shapes then we can safely say that these bodies are not colliding and for the human brain it's very easy to just use your eyes and visualize that there is that axis right there that is separating these two bodies right but mathematically we have to come up with an algorithm a recipe step-by-step instructions that we are going to have to put in a function to find what is that axis that is separating these two bodies again it is not only the x's x or y now we have this several x's right here we have this infinite number of x's what is the axis that is separating those three bodies do we have that axis that is separating if we find one axis at least one axis that is separating those two objects then we do not have a collision that is the heart of what the sat is all about the separating axis theorem so the sat is one of the most popular collision detection algorithms for rigid bodies polygon shape rigid bodies so the sat is one of the most popular collision detection algorithms together with something that you probably read out there called the gjk algorithm so i would say that the sat and the gjk they are the two most popular algorithms for detecting collision between polygons the gjk is very elegant it's very smart but i want to focus on the s80 the sat is a little bit easier to reason about if we're talking about this separating axis between these two bodies all right and i just want to point out something super important that i have been saying is that the sap will only work for convex polygons and i have been saying convex polygons convex polygons for a long time now i think it's time for me to quickly explain what i mean by that if we pick a polygon right any polygon that polygon can be convex or it can be a concave polygon and the difference between convex polygons and concave polygons is that let's look at the convex polygon if we pick any two points inside my convex polygon write any two random points inside my convex polygon the line that connects those two points will always be contained inside the polygon so let's just pick another two points these two the line that connects those two points will always be inside completely inside the polymer if this is always true we are talking about a convex polygon and if we look at a concave polygon if i get two points they might be containing side but there are cases that i can get two points and the line connected those two points might get outside the boundaries of that polygon this is a concave polygon sure there are techniques that we can use to break a concave polygon apart into convex polygons internal convex polygons right i can just break that concave polygon into smaller triangles but if you look at the original polygon it is concave right if we connect those two dots with a line we will get outside the boundaries of our polygon and also another property they will see is that a convex polygon has all of its internal angles less than 180 degrees so this is true for convex polygons the internal angles will always be less than 180 and if we look at concave polygon a concave polygon has at least one of its internal angles greater than 180 degrees and that is why we have the property of if we get two points there is a possibility that those two points if we connect them the line will get outside these angles right because if we look at the internal angle this angle right here is definitely greater than 180 so we have a concave polygon right so this difference between convex polygons and concave polygons this is one of the main reasons why i'm stating that the sat algorithm the separating axis theorem will only work and detect collision between convex polygons for example a triangle is a convex polygon a box is a convex polygon a pentagon is a convex polygon a hexagon is a convex polygon an eptagon and you get the idea right so this convex polygons they are the ones that we're going to use with the sat algorithm the gjk algorithm that i mentioned before works with both convex and concave polygons so the gjk is more elegant is smarter and surprisingly enough it is actually faster in most cases than the sat but in order for us to start diving in and getting our feet wet with these detections i want to focus on the sap algorithm for now right so the sat will only work with convex polygons meaning that if that is true the sat will also detect box with box collision right oriented bounding boxes if it works for convex polygons it will definitely work for our oriented bounding boxes oh good so i want to propose something do you know how we are talking about oriented bounding boxes i want to propose that instead of using boxes for us to analyze what happens with this sat algorithm how about we simplify our problem and work with triangles if this algorithm will work for any type of convex polygon we can replace these boxes with triangles and we can probably understand a little bit better and faster what we need to do to perform this detection using the sat right there are still polygons they are still convex polygons but instead of looking at a four-sided polygon i'm going to look at a three-sided polygon just to simplify the reasoning behind the algorithm a little bit more for us right so i want to look at this scenario where i want to start dissecting what the sat is all about we're going to have an object a a triangle a with vertices and edges and i'm going to have a triangle b with its own vertices and edges we are looking at this thing right here the sat stated that if we can find an axis that is separating those two objects then those two objects are not colliding and i'm going to say this again it's super easy for the human brain to look at this scenario and find that axis that is separating these two right our eye can just easily say oh yeah that is the axis that is separating these two shapes but how can we formalize this in terms of a function how can we create this step-by-step algorithm instructions looking at the vertices looking at the edges looking at these two shapes mathematically how do we find this axis of separation well if we think about this we have an infinite number of x's right and i think the first question that i asked myself whenever i was learning this algorithm was okay what x's right what are the x's that i have to test again and to find the gap and the answer to that is we are going to use the normal of the edges of our polygon right so if we have our polygons we have those normal the perpendicular vector for each one of the edges right we are going to use the normals as the testing axis so we're going to use that normal right there this thing right here is going to be an axis right this is normal that is going to be one of the x's that we have to test if we find an overlap this one right here is going to be another axis that we're going to project everything and test if there is an overlap so these are the x's that we have to test the normals for each one of the edges of our triangles in this case that is going to be true for boxes as well we're going to get all the normal of the boxes of the four sides of the box if we have a pentagon the normal of the five size of the pentagon so we are going to use the normal of the edges of each one of the polygons to test as our x's to see if that axis is separating those two bodies yes or no and if we find at least one of this axes that is separating if we find a gap between them then we can safely say that these two bodies are not colliding that is it the algorithm says that we're going to start one by one we're going to look at one normal we're going to test if there is a separation and then if we don't find the separation we go to the next normal and then if we don't find the separation we go to the next normal and then if we don't find a separation we go to the other body we test the other normal so we're going to test all the normals they are going to be our axis of test and if any one of these normal x's finds a separation between those two bodies we can already say yeah there is no collision return false they are not collide right so we're going to test that normal right there that is going to be the first normal axis that i have to test to see if we have a separation so what is the axis of that normal well it's going to be that axis right there you see that is the axis that is passing through the normal vector i'm going to test everything with that axis there so i'm just going to choose to move i'm going to move a little bit to this side i'm going to pull this right here this is still the same axis right this is the axis of that normal right there so now that i have these axis right here how do we test if there is an overlap we saw that before right i can just start projecting everything so i can project all the vertices of a and b if i come here and i project that vertex right there the other vertex and then the second one i am going to have right here the a maximum and the a minimum all right so if i just project all the vertices i'm going to find the maximum vertex and the minimum vertex in this axis of projection and i'm going to do the same thing with my x's b i'm going to loop all the vertices of b projecting and finding the b minimum and the b maximum coordinate that i have so having the a maximum and a minimum how do we check if there is an overlap we know how to do that right we're going to get this range from a minimum to a maximum and check with the range from b minimum to the maximum do we find an overlap in this case we found an overlap right this thing these two things are overlapping so if we got those two bodies and we project into these x's right here that came from that normal we found an overlap so if we found an overlap this axis has an overlap so we have to proceed to the next one we haven't found what we're looking for which is a separating axis so do you see where we're going with this we're going to test all the axes looking for a separation this one right here is not the one that we're looking for because there was an overlap so we're going to have to move to the next one so let's just say that we're going to go counterclockwise so we're going to test that other normal right there you see we tested that one now we're going to test that other one what is the axis of that normal well it is that axis that is crossing that normal right there right that is the axis of the normal vector for that edge i'm going to do the same thing i'm going to get this thing and i'm just going to offset a little bit and move to the top but it's pretty much the same thing right so now that i have this axis right here i want to test everything with that axis is that axis a separating axis let's see so if i go and i project all the vertices of a onto that axis i'm going to find an a minimum maximum again so i have the minimum of the projection and the maximum of the projection and i'm going to do the same thing for the object b i get and i'm going to have a b minimum and a b maximum and then the same thing right i get the range amin a max b mean b max and i can go ahead and perform a quick check with those range values and i will see that we found an overlap again so that means that this axis also has an overlap so we have to proceed to the next one this axis was not a separating axis that axis is not a separating axis let's look at the next one maybe the next one is a separating axis what is the next one so if we had that one we're going counter clockwise i'm going to test this one right here so this is the new normal the new axis that i'm going to test to see if we have a separation that is what we're looking for we're looking for the separating axis right the separating axis theorem let's what is the axis that we have to test is the one that crosses that normal vector right there so we have that x is right there i'm going to move again still the same axis i just moved now i have to test everything with that axis right there let's start doing the same thing projecting everything from a on to that axis finding the a minimum and a maximum and projecting everything from b into that axis finding the b minimum and the b maximum so if we start projecting all the vertices of a onto that axis we're going to have an a minimum and an a maximum and if we start projecting every vertex of b onto that axis we're going to have a b minimum and a b maximum that is our scenario look at that if we look at those ranges between a minimum and a maximum and the range between b minimum and b maximum oh i think you're getting pretty happy right now because there is no overlap that means that we just found an axis right we found our separating axis because there is no overlap between those ranges of minimum and max this is the separating axis theorem if we arrive right here and we found this axis that is separating where there is no overlap between those two projection of the shapes then we can say that there is no collision between those two shapes in a nutshell this is what the separating axis theorem is telling us if we find one separating axis then those bodies are not colliding and the beautiful part is that we are testing things with triangles but this is going to hold true for boxes we just have to loop all the four sides of the boxes that is going to hold true for pentagons we have to loop all the five sides of the pentagon and etc as long as these polygons are convex the separating axis theorem is going to work every time right that's it and oh and just to point out just to make sure that we understand if by any chance this axis right here was not the separating axis we have to continue and test all the normal vectors of b again so we have to loop all the normal vectors of a test if there is a separating axis and if we don't find we test with b again we test this normal that normal that normal see if there is a separating axis on the b side so we have to loop all the vertices of a and all the vertices of b testing every normal vector to see if that normal axis is a separating axis and since we are talking about programming and simulating a physics engine in code right using software let's look at an implementation i'm not going to go into too much detail but i just want to go into a very high level overview of the recipe that i like to use whenever i'm coding and find the separation between these two rigid bodies using sat so different programmers different source code i have seen out there they tackle the sat problem a little bit different the way that i like to implement right you can go several ways about implementing the sat the way that i like to implement is thinking about the separation between those two rigid bodies so i want to find a separation value i'm going to test all those axes but i'm going to come up with a separation value between those polygons are we colliding do we have no separation or do we have a gap do we have a separation between the bodies so we're going to have to loop all the vertices finding the x's normals looping all the other vertices of the other polygon i am going to give you my recipe right so my recipe to find the separation between two polygons using sap is and let's go step by step i have a very high level pseudocode of how i implement the output of my function whenever i say get the sat and calculate using the sap i want to come out of that function with a value a separation value and the separation value is going to be positive for example in this case right here where we have no overlap this is going to give me a positive number so we have a separation or a negative separation value if the separation is negative mean that we have an overlap these things are colliding with each other so this thing right here is an example of the output right of the return of the function that is going to find the separation between these two polynomials and this is going to be true for triangles boxes polygons with more vertices you get the idea right so this is what we want we want a separation value out of our function and for that this is my recipe i am going to start by looping all the vertices of the polygon a and i'm going to find for each one of the vertices i'm going to find the normal the perpendicular normal for each one of the edges of my polygon a so i'm going to loop all the vertices of polygon a i'm going to find all the edges and then i'm going to get the normal for each one of those edges of the polygon a now that i loop everything i'm going to find for each normal axis i'm going to then loop all the vertices of polygon b so for each one of the normal x's of a i'm going to compare with that normal there all the vertices of b and i am going to get the separation between each one of these vertices of b by projecting these vertices onto the normal axis that i'm testing and remember if we are talking about projection if you ever took a course with me before you know that projection means dot product right the dot product between two vectors means projecting one vector onto another vector so we're going to get that b point the vertex and then we're going to project that vector onto the normal vector and that is going to give me a separation that projection of b onto the normal is going to give me a separation between that vertex and that axis normal that i have right so i am going to get a separation of each vertex by projecting them onto the normal axis and we're going to do that for each one of the normal x's and all the vertices of my b polygon right we are testing all the x's of a with the vertices of b so now we're going to get the separation by projecting them onto the normal and i want to keep track of the best projection for each one of these normal x's so i want to have a variable that is going to keep track of the best projection the best separation right and then at the end this is what i have right if the at the end of all the for loops if the separation value is positive it means that we have no overlap those two bodies are not colliding and if the separation value is negative means that we are overlapping this is an example of a value that is negative it means that these two bodies are colliding with each other right and if you look here in this very short pseudo code this is exactly a translation of what i have here in my recipe for all the vertices of a i'm going to calculate the normal vector by using a perpendicular function right at that vertex so we can find the perpendicular we can find the normal vector at that edge at that vertex and then for each one of the vertices of b now so we get the normal we're going to test this normal x's with all the vertices of my polygon b and then i'm going to calculate the projection right the separation which is the dot product v b minus v a is going to give me that vector until vb right and then i test the projection of vb minus va on to the normal vector this axis to test if this normal is an axis of separation and then i keep track right mean separation valuable i'm going to keep track of the minimum separation the projection out of all these vertices of b and at the end the separation variable i want to save the greatest the biggest separation value out of all the normal axes that we have tested at the end after i perform all these for loops from a to b and all the vertices projecting them into the normal saving the minimum separation and saving the greatest separation out of everything i return my separation value which is this separation is going to be positive or negative depending if we are not colliding or colliding does that make sense this is a very high level overview of my approach to the sat algorithm i like to think about the separation between the bodies and we use these ideas of projecting vectors onto the normal axis by using the dot product and at the end my output is usually just a number that is going to be positive or negative depending if we are apart or overlapping these two bodies right these two polygons these convex polymers right and you know what i'm going to throw you into the deep waters and i'm going to show you the c plus plus implementation of how i approach things so you will see that here are the two examples the output positive and negative if we are not colliding and colliding overlapping and then this function right here which is called find the minimum separation between these two parameters a reference to the polygon a and a reference to a polygon shape b i receive these two polygons and i want to see what is the separation value at the end between these two polygons right the minimum separation axis of these three polynomials so this function is going to return the minimum separation between polygons a and b if the separation is greater than zero we have no penetration meaning no collision and if it is negative less than zero there is penetration we are overlapping there is collision right so let's go line by line very quickly uh how i approach these things i am going to have a float separation and this variable is going to be responsible for keeping track of the best separation right i want to find what is the best separation that i have out of this axis of penetration and since i want to get the greatest separation i am going to start this variable with the lowest possible number that floating points can represent this is the c plus plus way of getting the limit of the floating point so it's the lowest you can think of it as almost minus infinity right so i start with minus infinity because i want to keep track at the end of the biggest one so i loop all the vertices of my polygon a so now i am going for every vector va of my a vertices right remember that polygons they have this list of vertices inside so for all the vertices of a i am going to come here and i have to find for each vertex for each edge i have to find the normal that x is normal and i have a function called perpendicular right it already goes there and finds me the perpendicular at that vertex so i get that normal and then for each one i have to keep track of the minimum separation of all the vertices b onto the normal so if i want to keep track of the minimum separation of all the vertices of b onto the normal i am going to start this mean separation floating point variable with the maximum value that floating points can represent almost like plus infinity so this is the c plus plus way of getting this limit of maximum number so i start with infinity and now for each vertex of b i am going to compare each vertex of b project them onto the normal so i am using to keep track of the minimum i am already using that function standard colon colon minimum that is a c plus plus standard function that gets the minimum between this mean sap that i have before and this dot product between vb minus va that vector that is the subtraction vb minus va i project this vb onto the normal vector i get the dot product this is going to give me a value of projection and i want to keep track always the minimum value right so i get the minimum between what i had before mean cept and this projection this dot product between this vector and the normal vector does that make sense so we are keeping track of the minimum projection and at the end what we really want to get is out of all these computations and all these loops between things i want to get the best separation so if my mean separation now is greater than what i had before in the ultimate final separation value then i just replace i say the separation now is this mean separation because i want to return at the end the best separation right the greatest of them all if the separation at the end is positive we have a separation they are not colliding if the separation is negative means that we have an overlap you get the idea right but just keep in mind that this function right here it finds the separation from a to b right we are looping all the values from a to b so we are comparing a with b we need to compare b with a as well right to see if we have an overlap or a separation now from the other side so this is what i have to do i have another function that is going to call this fine minimum separation between a and b and then between d and a testing the two outputs so i have this function called is colliding polygon polygon and then i pass these two polygon references right s parameter and then i return find minimum separation between a and b if it is less than or greater than zero so if we have a collision between a and b and if we find the minimum separation between d and a now so i compared before a with b now i have to compare all the normals of b with the vertices of a to find the separation between those two if these two things are less than zero so if these two things are all actually overlapping if we have no separation then i can safely return true out of this function right this is how we can see this thing of course there are ways that you could optimize this thing you could replace this end logical end with an or so then you just flip the test so you don't have to test two things if the first one is already false we return false but i think looking at this function right here is easy to understand how we should approach this problem right we have to compare a with b b with a we find the separation this is my implementation of the sat right this will work for any convex polygon and if we go now we copy this thing we paste in our source code we should be able to check if these two polygons let's say these two boxes they can be rotating are they colliding or not right so we have this detection this boolean detection of the separation are we overlapping or are we not overlapping these two rotated boxes these two convex polygons that happen to be colliding or not with each other good stuff so that's it that's what i wanted to cover quick and easy the sat algorithm you saw the logic behind algorithm is actually not that hard it's just implementation you have to really make sure that you're testing the correct signs if you're projecting one vector onto the normal just pay attention to the details but like i said easy stuff right remember if you like this type of content at ekuma.com i have several comprehensive courses really in-depth courses about the low-level details of computer science mathematics this overlap between mathematics and computer science this is what we do right this is what i teach so if you like this type of content i'm pretty sure you're going to love the courses that i have there and as always subscribe give me a thumbs up and always spread the word right because the more you spread the word about my courses the more bright students i get thank you very much i'll see you very soon