This is fantastic. As a 2D amateur game developer I find these algorithms very tricky and even wanted to use box 2D to avoid thinking about them. I appreciate your lessons. Please teach a complete series on collision even about broad and narrow phase and about concave collision too.
You blew my mind just by this 23:16 Didn't know that was posible. Holy moly. I had never used the | operator that way. Very muchas gracias, you are the best.
As always you did a very clever explanation. Are you a teacher? because you have a very good way to explain to the other mortals like me how things must be done. I'm not a native english speaker but I can understand you very well because your pronunciation is very accurate and your pace is perfect. Keep like that and thank you so much!
Thank you greatly for the video and code samples. I tried implementing these algos into my own system, and while the simple detection versions of SAT and diagonals worked perfectly, I was seeing some buggy behaviour when using the statically resolved versions of both. After trying many things, I tried normalizing the projection axis in SAT and that instantly solved the problem (my overlap values were way over inflated). The code sample says the normalization is optional, so I'm not sure if I have something else off in my code, but I just thought I'd drop that here in case anyone else has been going through the same thing.
Yeah, I went through the same experience, and this was actually helpful. However, for me, the second version, static diagonal intersection resolution worked just as shown in the video. What specific behavior did you encounter for the 2nd one?
welp, time to start learning about dot products because this is like wizardry, like i know how this works and such but my methods take like a page of trig just... bruh it's so CLEAN why are you so good at code
from the SAT algorithm, the sign of the dot product tells you which 'side' of the side the point is on. if you switch the nesting of the loops, then you can determine if each point is on the 'inside' of each side of the polygon. the magnitude of the dot product will give you the distance (after normalization - which can be cached).
About the only problem I can see with the static diagonal approach is if you tried to put the pentagon between the square and triangle and then use the triangle to push it into the square. If I understood things right, it would resolve the pentagon/triangle first, pushing the pentagon into the square and then resolve the pentagon/square pushing the pentagon out of (and back into) the triangle. A possible solution from the top of my head would be use two loops of intersection checks. One forward and one backwards, thus swapping the pushing priority. So first T pushes P into S, then S pushes P back into T. Now the backwards check has P pushing T away.
There's another easy way to check for the collision of two convex 2D polygons; replace one polygon with a point, and the other polygon with the morphological dilation of one polygon by the other. Then the intersection test can be reduced to a point-in-polygon test. The morphological dilation of two convex polygons can be easily created by taking all the edges of both polygons and then sorting them into clockwise order by angle, then reconnecting them in that order. I don't remember the name of this technique but it works very well.
Jurassic Park: Trespasser, used an invisible square box for player movement. It was attached at the base of the character model, rolling around every which way based on the terrain underneath it. Wonky!
Have you looked at the GJK algorithm at all? It's a very nice algorithm which can operate on convex polygons, lines, points, and even mathematically 'perfect' shapes (like a circle, ellipse, etc)... any non-concave shape that can implement a "support function" that provides the "farthest point in a given direction". Essentially the algorithm "subtracts" one shape from the other and determines if the resulting shape (minkowski difference (sum)) intersects with the origin. If so, the shapes intersect. The end result of the GJK is also a convenient starting place for the Expanding Polytrope Algorithm (EPA) for collision resolution.
Superb video as always! Isn't it called "separating axis theorem" rather than "separated" though? Since you're looking for the separating axis, the axis isn't separated.
Do you want to address a more challenging, but related problem? Do tool path calculation (find vector trajectory of the center of a circle that maintains contact with CAD elements as it traces around them. CAD elements include line segments of width W, arcs of width W, and polygons (may be concave). CAD elements may be overlapping or disconnected. "Clean" CAD files (with elements perfectly connected) cause the most trouble!
I think your diagonals approach can return a false negative (incorrectly not detect a collision) if a smaller shape is entirely contained within one 'pie section' of a bigger one (between an edge and its two diagonals).
You are correct Pleeg, but you could argue they must have previously collided to be in such a state. Though this depends entirely on the rest of your set up of course.
The "Diagonals" theorem you mentioned is pretty ingenious. Did you come up with it yourself? Also, I am trying to think how this can be proved. How can we say with certainty that if we apply this theorem to both shapes and if none of the edges of one shape intersect with the other's diagonal (and vice versa) that they are not intersecting.
my brain is hurting... i not sure if it is because i'am programming on javascript, and trying to understand and convert to it, or the math is enought to brick my mind already LOL i got all lines from both my polygons, but going forwards looks impossible rightnow... i will try make it 1:1 first... those really heavy math part are tricking me, if i not wrong your video from line to circle detection was easier to reproduce LOL Just update here, it worked! i not know exactly how it work, dude i have a totally different language and code base, mine structure uses lines not points and i adapted to run all lines and only get startpoint of those... also i did only one function and then make another function to call it with reverse polygon paramters soo it test both ways... in the end it worked!!! man i hope this not burn down cpus when people play my game, looks like a lot of tests per logic cicle, also i need to check circle with polygons and line with polygons too now LOL it will be another day
But... How to detect collision between a Circle and a Polygon? BTW... Great video... Your teaching method is amazing... I have been trying to understand this for the past few day for my game... This is very helpful... :)
diagonals isn't perfect, if a smaller polygon is fully inside the triangle formed by 2 diagonals and the side. So it is not a perfect overlap test. Another good collision test for convex shapes is the jgk algorithm. Often very poorly described though.
@@javidx9 Assuming your small shapes move slower per frame than their size of course. Otherwise they can just jump in. An edge case to be sure, but a case nevertheless. Edit: Also let's not forget that depending on the application you may not actually want to displace the objects based on whether they overlap or not, just know whether they actually overlap or not. So it can also fail there.
Lol you are quite right of course, if the step per frame permitted this. You can mitigate against this with a more sophisticated trajectory system like I did with the balls collisions examples though. However none of these systems are infallible.
For some reason I can't get the overlap value to work. When I debug the value I'm getting for overlap its always a negative number if overlap isn't happening or its 0 if they are overlapping.
Wait, are you a real Flash Programmer with flacc ( successor of gcc with Flash ) I remember that Nape Physic Box2d. Is it correct or wrongly? Because I feel like you were developed Physics 2D collision at Flash Player 9 or 10 ? Right? I never forget that like triangle, quad, circle etc...
Hi javidx. This video is very useful to me. But there is problem you didn't mentioned in this video. And the problem is collision detection in high speeds will break up. Becuse speed is teleporting and not walking so it might not touch the other object and walk through it. This problem can be solved by splitting the steps. But how much must i split it ?? For the best experience i must split it to one pixel. Like if my speed was 10 i will make it walk 1 pixel each time using for loops. So by this i will check for collision 10 times each time i walk. This might reduce the fps and the performance. So i asking you if there is any other solution other than splitting. Like an algorithm to check if this object will collide in future or will collide if it walks in this way.
Hey javidx9, I have a question. At minute 26:40, the displacement of the object is calculated. Actually, the moving object would have to stop at the same place as before the colliding (It would be no gentle but a jerky motion). However, it moves so very smooth and fluid over the edge. Can you explain that to me. Yours sincerely Lukas
the diagonal approach is a little buggy, because if you are trying to collide with a smaller shape(rect) right in the middle of a side of a bigger shape, it starts jiggering because the difference is calculated for multiple diagonals and then added to the position twice, or thrice etc... instead of once. I will try to fix that
this is a code in python, but main thing I added was that I just devided displacement by number of diagonals intersected, and now it is supposingly has solved the problem when if I collide by 2 diagonals with 1 side it is thrown back twice as much as it is supposed to
Very good video! Tried the code myself and the diagonals static collision works perfectly except when 2 rectangles collide when both there sides are parallel one of the rectangles is offseted to the side instead of just being pushed back Any way I can fix this?
Thanks Tobey, the errant pixel is due to rounding error when quantising to the screen, the actual objects in the geometry domain have certainly not penetrated each other, I dont believe they can by definition. Still a good observation none-the-less. I shall be less lazy next time when extrapolating screen coordinates from floating point data :D
Yes, and it's the approach generally used (=split the concave into convexes). However, it's not trivial to split it. Long times ago, I tried to tesselate doom sectors. Basically, a doom sector is defined by a set of lines. Each line has two side, and each side tells which sector it is facing. This define the shape, and it can not only be convex, but also concave, or with holes, or be in multiple pieces not connected at all etc. Three connected points with a valid angle may still not form a valid triangle. You can have a triangle with a "nick" on a side (ok, it's not a triangle. It's to hlpe you visualize it. Draw a triangle ABC, put a "tooth" on the side CA -> When you go from A to B and from B to C, everything seem fine. To find that you cannot make a triangle from ABC, you'll have to go farther. And the tooth can come from actually very far in the polygon. The other case. Take your triangle with a nick (ABC, a nick on CA). Pull the nick to A, so you split the triangle in two. Still AB BC looks ok, and now there isn't even a nick to detect. It's easier to draw than to describe. I had to tacle with this kind of problems XD Note that once you have a tesselation of your not-convex polygon, it's easy to group triangles into convex polygons (=it is easy to detect if adding a triangle to an existing convex polygon would make it not convex).
Here is an image I made some time ago jme-hub-cdn-jmonkeyengineor.netdna-ssl.com/uploads/default/original/2X/7/74d15c97e38c725b6b2ab8495ce304d8c462c2d0.png If you want I'll make a picture tomorrow to illustrate my message. But it is really not a big deal. About the "nick" problem : take the image on the first column, third row. If you follow red arrows you may consider that it is a valid triangle (the angle is ok). But it isn't. Or if you look at the third column, first row : everything seem fine from the point of view of the red arrows, but it isn't.
@@avvvqvvv99 Ok, I tried to do something i.imgur.com/7pc185O.png The first is the "triangle with a nick" (a tooth, I don't know the english word). The second (the very big one) is to illustrate that the "nick" can comes from very far in the polygon. If you iterate on sides, it's not enough to just check the next side, or even n next sides. The last image (two triangles connected) is a degenerated form of the tooth. Because now there isn't any tooth at all, there is not point in the "triangle formed by A B C". There is no point to trigger a "ABC contains an other point, it's not a valid triangle". Still, it's not a valid triangle. I hope it helps to understand my first post.
@@javidx9 Yeah I figured it out as well, thanks anyway :D I'm currently stuck with finding the 'shadows' of the shapes on the normal vector relative axis but I'm sure I can figure it out.
It's insane how much this channel aligns with my personal interests. Synthesizers, mazes, 3d rendering, splines, line of sight, and now collision detection are all things I've done short projects with just for fun in python. Seeing them here and reading the code helps me both get better with C++ and further my knowledge on these topics. Your explanations are also incredibly useful (particularly of all the math which is often glossed over), so thank you so much. :)
For the diagonals method: What if you have a large first polygon, with a small second polygon inside it, where the second polygon is placed such that it does not intersect any of the diagonals of the first polygon. Then, it will report them as not intersecting, even though the second polygon is completely contained. The diagonals method is good to avoid objects from colliding, since it will always find cases where edges are intersecting. For small fast moving objects there may be issues though.
@@mohammedj2941 In this case the pulling-out algorithm will behave fairly unpredictable. Imagine that you already have one shape inside another after an update of a window. In what direction should you pull the inner shape? It is doable, but it doesn't look like an easily-maintainble approach to this specific problem.
for your case the maximal project on arbitrary edge of large object will also contain the maximal project of small object. So it contains the other (special kind of intersection)
You could always do a fast bounding sphere test small and if the circle/sphere is fully contained in the bigger one then use the SAT otherwise use DIAG. You can also use this test for early broad phase.
Hey Javidx, I don't use C++ (I'm mainly a Java dev) but I want you to know that your videos help me out so much as an aspiring game developer. You basically single handedly got me out of tutorial hell and taught me so many useful game development skills, and I am very grateful for your videos.
Sir, I can't program in c++ (yet), but your videos are very useful for other programming languages too. Because of your didactic skills, I can translate it to the programming languages I'm familiar with. Awesome. Thank you.
Thats great to hear! I do try and write the code to be as accessible as I can, and people do have success taking the ideas and using other languages. Thanks!
I’m don’t know about others here but I can listen to this all day. Well done for this top video. You’d make such a good teacher and any pupils would be so lucky to have you teaching them coding.
Great stuff, really! it's possible to scale the polygons? You can rotate the and move the polygon, but it's possibile to scale those? Could you please update the function adding the scaling capability? I tried this way "s1.o.push_back({ 30.0f * cosf(fTheta * i) * scaleFactor, 30.0f * sinf(fTheta * i)*scaleFactor })" but i'm not an expert in math... Moreover, the update position part and the collision part should take care of the scaling too.
You are a blessing from god to all programmers, all your videos has really great explanation and quality. You are the best coder I've seen and will be the best coder I will ever see. Thanks for this video but I wonder something, I know it's really complex but are you willing to make a "dynamic resolution" tutorial for convex polygons?
Thanks you k4dir, that means a lot! Im thinking about doing dynamic responses, I may do a crude version for my top down car game, and then I would likely extend it to include angular momentum and velocities, but its gets complex fast!
I think, depending on the number of collisions vs number of polys, you'd want one algorythm over the other. SAT exits early if there's no collision, DIAG exits early if there's collision. So, DIAG will exert maximum load when there aren't any collisions, and reduce the number of needed checks as new collisions occur (nice byproduct in my opinion, very useful since that saved time can be used to actually resolve the collision).
I can’t believe I’m only just finding your channel. I’ve been the type to just have a go at something without doing any research first (which can be fun at first, but quickly becomes tedious) thank you for making these videos, I really appreciate them
@@delofon Thrice is an actual word, plus, triple doesn't actually fit in the sentence. Same way as you wouldn't say "I wish I could like this video double", you don't say "I wish I could like this video triple".
i was looking for a collision detection for my game, and I came up with a one that is complicated and in theory should work, but in code it doesn't. thank you for introducing me to AABB
In sat if theres only 2 shapes we can check only the one with less sides, or not? If there is no overlap we are good, i am assuming if a triangle doest overlap a dodecahedron the latter wont overlap the first unlike with the diagonal algo as you prooved you need tou check both
Hey man. Great video as usual! In case you are suffering of some kind of lack of inspiration for future videos, please let me suggest you a topic :) What about a video to explain a good algorithm for bounding boxes occlusion culling done on the CPU side? I'm currently working on a project where I'm using occlusion queries on the GPU. They work well but, as you surely know, the query result becomes available only after a few frames and it causes sometimes objects to appear on the screen with a little delay (especially if they move fast). A nice prepass done by the CPU to compute which AABB are visible before to actually render the objects would solve lot of my problems (even better if the alghoritm can run at a decent speed, say... less than 5 msec). I think this would be a good topic for a future video and it may also be a nice addition to your 3D engine... right? :P Joking aside, please forgive if I allow myself to give you a suggestion, but, judging by your past videos, you look like the perfect guy to explain such a complex topic with your usual clarity and effectiveness. Keep up the good work.
Hi and thanks Razie, Im always open to suggestions! Im hoping to expand on the 3D engine a bit, I had not considered BB occlusion culling, so I'll look into it!
Im using this SAT algorithm to detect the collision before mapping it to screen space, so I have a [-1,1] x Axis and [-1,1] y Axis. And some of my figures are negative x or negative y or both, or both positive, however this algorithm is only working when the collisions occur in the positive subspace (all of the intercepted polygon points are x positive and y positive) Do you know why this happen? Or How can I fix it?
little optimization for the diagonal method: instead using an additional center point to build the diagonals, one can use one of the polygon corners. this reduces the required intersection calculations by the number of edges of both polygons.
Looking at the source code I can see that the collision check runs once for each polygon, but... I think I am not yet sure why?? I have rewatched the bit where javidx9 adds the code, but he glossses over it, I think? Or I cant pinpoint where in the video does he explain why to loop over both polygons :c
I won't write a formal proof of the diagonals method... but consider: For two convex polygons to intersect, one of them must have a vertex inside the other polygon. They can't intersect otherwise. So... the moment the vertex enters the other polygon... the diagonal FROM that vertex must now intersect the edge that the vertex just crossed.
wow that's is really helpful. I am actually working on a robotics projects and this video is really to the point. I was just wondering if this code can be used with matlab.
I've discovered a problem with the diagonal method. If you have a shape completely inside of another much larger shape, it's possible for them to not detect any collision. If a shape can't get inside of another this isn't a problem, but it is important to note that method isn't perfect. On another note I think I've come up with another. You could measure the angle of every vertex on one shape with the every the angle of every vertex on another shape. If the angle from every vertex on shape A to one angle on shape B is between the angles to the two connected vertexes on shape A, then that vertex on shape B is inside of shape A. Using actual angles involving trig functions seems too inefficient, but calculating the slope seems easy enough. I'll have to do some math or run some tests to see if it's worth doing at all.
So sad that this is just static SAT. If only this implementation had some more obvious ways of pulling the contact points just to combat me being brain dead :(
damn guess ill go have to look at the theroms this is a bit high level and in c++ instead of c but i already kno that since i watch you all the time but i know c and I get the concept but am not sure of c code
Is it improove perfomance if for each polygon create box that contains this polygon in any rotation in it, and first check is this boxses intersects, and if true only then check intersection with polygons?
@@javidx9 thats always good. Just a tough about the diagonals methode, Would it not be a bit more computional optimize to do the same line intersection, but with edges only? (so all edges of P vs all edges of Q) Also, using edges i guess would allow you to test concave polygons with the same algorithm. (for intersection only, not the "move back" function)
