Convex Polygon Collisions #1

[@ApertureCombine]

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

[@javidx9]

lol Aperture thank you very much!

[@punkisinthedetails1470]

It's nice to see them in C++ after py overload

[@punkisinthedetails1470]

after watching countless well meaning but lightweight channels finally found THE channel.

[@delofon]

Aperture Combine... OH NO

[@victornaut]

This has got to be the best explanation of any subject I've came across in my entire lifetime.

[@kalebbruwer]

Gotta love how you wrote "Convex polygon" entirely out of concave polygons

[@fuuryuuSKK]

any concave polygon can be separated into convex polygons

[@brainloading5543]

@@fuuryuuSKK **summons fractals**

[@horowirtz9415]

A fractal isn't a polygon

[@theycallmerye3]

the first 2 "O"s are convex on the outside.

[@brdevll]

@@theycallmerye3 so.... if you ignore half of the vertices they are convex, I see..

[@guy-dev]

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.

[@ДенисОлегович-ф8д]

Super! Thanks for explanation! You are the best coder in KZbin!

[@javidx9]

Glad I can help buddy!

[@Hsubetakevol]

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.

[@javidx9]

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!

[@Mannershark]

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]

Isn't it perhaps straightforward though to avoid this problem by checking if any vertex is inside the other polygon?

[@JamesSmith-fg8hp]

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

[@tungdoan380]

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)

[@omarator]

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.

[@teeboh99]

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

[@hugobreno1816]

definitely you are the best bro. Keep it on.

[@javidx9]

Thanks Hugo, I will!

[@chriswinslow]

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.

[@javidx9]

Thanks Chris, Im trying a bit harder with vocal clarity this year so Im pleased its being picked up on!

[@Gargantupimp]

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.

[@javidx9]

lol thanks Apricot, one step at a time :D

[@YoomarTuNoOmar]

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.

[@javidx9]

lol thanks Yoomar, its surprising when people give feedback of things theyve not seen before, makes it all worthwhile!

[@epsilonadept7301]

I never looked at the operator in such way to be able to literally assign two values to a variable!

[@seebaastian]

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!

[@javidx9]

Hi Sebastian, Im not a teacher but I have taught in the past, mainly to non native english speakers, so I guess I adapted. Thanks man!

[@mjdev-i1p]

I cant believe how you manage to put not only so muc effort but also so much value in each video. Sir you have my gratitude and respect. Please keep up the good work. 😊

[@javidx9]

HI Marko, thank you for such kind words, they are much appreciated, I will!

[@VanillaMidgetSSBM]

It's been a whole....Month or so, BUT NEVERTHELESS I'm glad we got Collisions out of the way so now we can make cool stuff! *Also first*

[@javidx9]

Two weeks!

[@TheSharkasmCrew]

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.

[@abhay_more]

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?

[@kaede_elfen]

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?

[@javidx9]

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!

[@marmoripelaao9830]

Haha, a couple of months ago I thought like: I need nothing like this. However, now I am VERY glad that I found the video again. Thanks!

[@ibemper1850]

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

[@Otakutaru]

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

[@fj12n3]

Dude you are such an amazing person, thank you for making all these insanely high quality videos!

[@O5MO]

From this video i understood better what the dot product is than from other videos especially on this topic.

[@zanzaraloggan3713]

you're like the Daniel Shiffman of C++ :D

[@5daydreams]

No, Shiffman is javidx9 of js

[@neillunavat]

@@5daydreams hehe. Javidx9 is bob ross of c++

[@ScibbieGames]

You seriously upload everything I need, every time.

[@justinhart4010]

Im so glad as you said its good for programmers to work out their own algorithms!! i was thinkin all this time on the videos ive been watching to do that instead and i just started learning calculus,but you literally make all your own algorithms

[@hexhackbangla8368]

thanks a lot , i was searching for this kind of video

[@javidx9]

Hey no problem noman, thanks!

[@glitchy_weasel]

I really like this video. It helped me a lot to get used to collisions and resolving collision, something that I had seriously trouble understanding and getting right. Your videos are really informative and educatinal, keep it up :) After playing with the code myself, and investigating on other websites and blogs, I have a suggestion. That is in the SAT/Static algorithm to displace the shape not by the line between their middle points, but rather by the axis in which the overlap occured. Just store the corresponding axis alongside when overwriting the minimum overlap, I think it will make it a little more stable. Cheers!

[@Ganerrr]

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

[@prank855]

Will you be going over stuff like quad-trees or other optimization techniques?

[@javidx9]

Hi Prankster, maybe, but probably not in the context of collision detections. I do like a good quad tree though :D

[@nebojsazakic]

Optimal is a boolean. More optimal and the most optimal are just optimal. Thanks for the video.

[@PumpReactivationProject]

Wooow this tutorial is so informative and so easy to understand. Thank you for that!

[@javidx9]

Im pleased you found it accessible PRP! Cheers!

[@coolmind2476]

Love the diagonals algorithm 👍❤️ Simple and very effective. Just need to pay attention if one polygon is already contained inside another as starting position or if there are bigger "jumps" possible so that an edge can be crossed without touching it - which is of course not the case here.

[@NeZversSounds]

This gave me many ideas for making my own simple collision libraries. I've been wondering for a long time what's behind the old top-down GTA collision solving with rotation.

[@minhcaohuu3691]

thanks bro ;))) (nice stickman 8:04 btw)

[@gdclemo]

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.

[@Spongman]

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

[@DownloadableFox]

I love this man. This channel is gold.

[@JackTheSpades]

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.

[@skylersmith8696]

"I'm no good at drawing straight things on the screen" Me tooooooo!

[@SonictheHedgehogInRealLife]

Y’all draw gay things instead on screen

[@benstech726]

For aabb approach easiest method I found is getting min of both cubes' maximums and max of both cubes' minimums. If cube min < cube max the. Collision exists and the mins and maxes per axis gives the overlapping area. So min(cube1Max, cube2Max) max(cube2Min, cube2Max

[@123eee555]

Awesome video! Thanks so much! The math of this had been giving my trouble for a while.

[@javidx9]

Hey no problem Nimbiz, thanks!

[@NeilRoy]

I always use an even simpler method to test for AABB in 2D, and that is not to test if they overlap, but instead, to test if they do NOT overlap like this... if (Px+w < Qx) no overlap, return false for collision if (Px > Qx+w) no overlap, return false for collision if (Py+h < Qy) no overlap, return false for collision if (Py > Qy+w) no overlap, return false for collision That's it! IF all of these tests fail, than we absolutely have a collision and can deal with it. But these tests will return false the moment any one of them test positive as it will be impossible for there to be a collision in any of these four cases. Much simpler than testing for overlap.

[@javidx9]

Hi Neil, yeah there are loads of early rejection optimisations I think its important for programmers to try and implement for lots of algorithms.

[@Wayne-wo1wc]

Extraordinary!

[@javidx9]

Thanks Wayne!

[@binary_gaming113]

Good video. Will you also do concave polygons?

[@javidx9]

Thanks Erazor, maybe, the naive approach is to partition your concave object into groups of convex objects and do the same.

[@stumbling]

"the naive approach is to partition your concave object into groups of convex objects and do the same." Ah, that was going to be my naive question. :)

[@federicocaputo3989]

8:34 love how he draws the other vertex that generated the parallel line as a different point when mathematically they are the same

[@Saleca]

Well spotted 😅

[@ps5games821]

Top games.You have the most best KZbin channel

[@javidx9]

Thankyou!

[@Shadow-bc5nr]

Thanks alot for creating this video!

[@munteanionut3993]

This channel is really cool !!

[@javidx9]

Thanks Muntean!

[@lucaxtal]

Really great explanation and clean code.

[@klaus-udokloppstedt6257]

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.

[@devinmurray4984]

2 observations with your diagonal algorithm. It can be made to work with "star convex" shapes, i.e. any shape where the line from your center point to your extreme points is contained in the shape. This includes a lot more shapes. An issue though is that the intersection of a diagonal of one shape and the edge of the other isn't always a unique point. For example, this is an issue if you are moving a very obtuse triangle parallel to one of its diagonals. You can end up with an edge of the one shape coinciding with the diagonal very easily. This could crash your algorithm, or teleport the triangle further into the shape depending on what your intersection function spits out.

[@jursamaj]

2:05 Just a note: if knowing that 2 shapes *don't* intersect is sufficient (not distance between them) then the AABB check is still useful and fast. In most applications, even for shapes that aren't axis aligned rectangles, your shape storage probably has their AABBs anyway (altho you don't do this in your examples). If the AABBs intersect, then you can go on to use a deeper method to find out if the shapes actually collide. For very simple shapes (few edges) pretty much any test method will be about equal. For larger number of edges, there is a pretty standard method called GJK, which is highly efficient. I can see this being a good exercise for a budding programmer. But ultimately, the game dev is probably wasting their time by not using a library for this.

[@miguelmejia3235]

This is amazing! Also, I lost it at 36:04

[@JackieSL9]

What kind ofmonster dislikes these vids?! Thanks Javid for another great video.

[@javidx9]

Cheers bari!

[@quillaja]

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.

[@MrBidouilles]

very instructive, thanks !

[@whoshotdk]

Ironically I find this sooo much easier than AABB. My dad always said; "son, you always do things the hard way". I think he was right.

[@leonardoherfianto897]

With diagonal every section is made from triangle, then combine with point in triangle formula can also detect the overlaping shape

[@bpark10001]

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!

[@ragedprogrammer3952]

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?

[@alterego4767]

Oh wow, an excellent video on collision handling between convex polygons, fantastic! What prompted you to explore this topic?

[@javidx9]

Thanks AlterEgo, I guess you'll see at the end XD

[@regarrzo]

It's a physics engine, I know it 👀

[@Johannes00]

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!

[@jsflood]

Great video! Superb explanation as always :-)

[@javidx9]

Cheers D-Eye

[@RetroDelux]

Sensacional meu amigo!

[@javidx9]

lol thanks again Jose!

[@rapplejab]

This is great! Thank you very much :)

[@javidx9]

You're welcome rapplejab!

[@francescopiazza4882]

Very interesting! In a convex polygon, any couple of points is joined by an internal segment.

[@davidecalaminici2937]

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.

[@marianapivetagiachini850]

javid u are the best

[@javidx9]

Far from the best Mariana, but I appreciate the sentiment! Thank you!

[@racorescript]

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.

[@javidx9]

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!

[@racorescript]

@@javidx9 Hey javidx! Thank you for answering. It´s a nice topic still with no clear solution. I hope you'll find it interesting. Enjoy

[@gabigagu6599]

Hey javidx9, I love your videos but I have a question: I implementer the SAT in my project and it wont work. I replaced the Polygons multiple times but I cant figure out why the function returns always false.

[@badwrong]

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.

[@wilykary]

Is there any way to get the edge that is being collided? I have a simple 2d game and my terrain is a big polygon. When a ship collides I want to be able to find the side with which the terrain collided with the ship.

[@JakeND]

Gotta love that the video has 20k more likes than it has views

[@zleapingbear]

Great video. Helpful. Also, thats a fast video output currently :)

[@javidx9]

Thanks zleapingbear, yeah went well this one XD

[@zleapingbear]

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

[@pjh777]

Just to add that 'diagonals algorithm' won't detect a collision if you place a smaller polygon in a bigger one in such a way that it doesn't intersect any of the 'diagonal' lines

[@javidx9]

Hi Pjh, the smaller one would need to enter the larger one first, and its diagonals would stop that from happening

[@pjh777]

@@javidx9 For small 'deltas' that's true - ie where the delta is small compared to polygon size, but with delta's of the same order of magnitude as the polygons the smaller one can get in the bigger on in a single jump. So yes in your example where the movement is small compared to the size of the polygon there is not problem, but for a small 'bullet' polygon moving a distance greater than its size per frame it can jump inside. SAT catches fully enclosed polygons every time though.

[@javidx9]

lol, im having this conversations in two places at once XD You are quite correct, this would be an issue, but personally, I would never use this approach for fast projectiles like bullets, I'd just do a ray intersection.

[@Saleca]

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

[@EmmittBrownBTTF1]

Can a concave polygons be converted to convex polygons by drawing lines from vertices with theta>180 to neighbouring vertices until all divisions are convex.?

[@javidx9]

There are a few techniques to do it, ultimately if you represent the structure as triangles then all the primitives are convex

[@AndroidsReview]

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?

[@Urre5]

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.

[@dercoder2057]

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

[@PleegWat]

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

[@javidx9]

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.

[@TheWeirdo879]

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.

[@tanan8116]

I wish I could like this video thrice

[@tanan8116]

@@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".

[@thyandyr7369]

I like the drawings and explanations parts

[@bueno_excelente]

you honor the programmers

[@Red-di7zb]

This is amazing, thanks for this. I was looking for it. =)

[@AB-ut3ce]

would applying displacement along the vector to both shapes according to weight ratio work for this car game?

[@viniciusschadeck4992]

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

[@hammad-ilyas]

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

[@Chrescoe1]

Thanks!

[@FredM80]

I did'nt know the diagonal method, this is very useful ! Do you think it can be generalised for polyedron in 3D ?

[@javidx9]

Hi Fred, I think it can be, but it would be diagonals vs planes instead.

[@FredM80]

@@javidx9 Yes, I think it could work in this way ! This technique is very intersecting (diagonals, 2D), I did not find this technique before, did you invent it or did you find it somewhere ? Do you know existing programs that use it, is (was) it patented ? I like to find all techniques used before, for example Carrier Command, the 3D engine on Atari ST, the used techniques :)

[@noahfletcher3019]

Could you quickly explain how to go from this and find the minimum translation vector and contact points. I'm having a real problem with this. Thanks

[@5daydreams]

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

[@michaelmahn4373]

I'm not remembering the details but could you not have re-used the collision detection module of the physics engine you have built?

[@javidx9]

Hi Micheal, that engine specifically only worked with circles and lines. In many ways yes you could use those tools to do this, but you would need to maintain the position of your circles to facilitate a rigid body, this can become very complicated.

[@michaelmahn4373]

javidx9 Ah, I see. I remembered the asteroids video and thought you had used your physics engine there but after rewatching it, I noticed that you didn't and that you've drawn the asteroids as polygons but detected collisions only as circles. Sorry for that.

[@ratchet1freak]

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]

Hi Ratchet, true about the small shapes, but it has to get inside first, and the diagonals of the smaller shape would not allow that to happen.

[@BanzayIkoyama]

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

[@SleepyHarryZzz]

@@BanzayIkoyama heh, "edge" case. Nice.

[@ratchet1freak]

yeah but tunneling is an issue and is easier when you only need to pass a single line. SAT and JGK both don't allow that kind of overlap

[@javidx9]

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.

[@RSchenal]

Спасибо огромное!

[@jumhig]

I think you can do concave poly collisions by breaking the concave poly into 2 or more convex polygons.

[@shrutichakraborty1309]

Is it possible to use this theorem to find the area of intersection between two shapes?

[@valseedian]

Projection short circuits after non collision, yours shorts after collision. In a game where most objects aren't constantly colliding, yours will be a lot more processor intensive. A particle physics simulator would be more apt.

[@TimothyChapman]

What would happen if you had two polygons that clearly overlapped, but none of the vertices of any polygon was inside the other polygon?