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. :)
@javidx95 жыл бұрын
lol Aperture thank you very much!
@punkisinthedetails14704 жыл бұрын
It's nice to see them in C++ after py overload
@punkisinthedetails14704 жыл бұрын
after watching countless well meaning but lightweight channels finally found THE channel.
@delofon4 жыл бұрын
Aperture Combine... OH NO
@victornaut3 жыл бұрын
This has got to be the best explanation of any subject I've came across in my entire lifetime.
@kalebbruwer4 жыл бұрын
Gotta love how you wrote "Convex polygon" entirely out of concave polygons
@fuuryuuSKK2 жыл бұрын
any concave polygon can be separated into convex polygons
@brainloading55438 ай бұрын
@@fuuryuuSKK **summons fractals**
@horowirtz94154 ай бұрын
A fractal isn't a polygon
@theycallmerye33 ай бұрын
the first 2 "O"s are convex on the outside.
@brdevll2 ай бұрын
@@theycallmerye3 so.... if you ignore half of the vertices they are convex, I see..
@guy-dev3 жыл бұрын
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д5 жыл бұрын
Super! Thanks for explanation! You are the best coder in KZbin!
@javidx95 жыл бұрын
Glad I can help buddy!
@Hsubetakevol5 жыл бұрын
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.
@javidx95 жыл бұрын
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!
@Mannershark5 жыл бұрын
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.
@mohammedj29414 жыл бұрын
Isn't it perhaps straightforward though to avoid this problem by checking if any vertex is inside the other polygon?
@JamesSmith-fg8hp4 жыл бұрын
@@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.
@tungdoan3804 жыл бұрын
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)
@omarator4 жыл бұрын
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.
@teeboh993 жыл бұрын
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
@hugobreno18165 жыл бұрын
definitely you are the best bro. Keep it on.
@javidx95 жыл бұрын
Thanks Hugo, I will!
@chriswinslow5 жыл бұрын
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.
@javidx95 жыл бұрын
Thanks Chris, Im trying a bit harder with vocal clarity this year so Im pleased its being picked up on!
@Gargantupimp5 жыл бұрын
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.
@javidx95 жыл бұрын
lol thanks Apricot, one step at a time :D
@YoomarTuNoOmar5 жыл бұрын
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.
@javidx95 жыл бұрын
lol thanks Yoomar, its surprising when people give feedback of things theyve not seen before, makes it all worthwhile!
@epsilonadept73014 жыл бұрын
I never looked at the operator in such way to be able to literally assign two values to a variable!
@seebaastian5 жыл бұрын
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!
@javidx95 жыл бұрын
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-i1p5 жыл бұрын
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. 😊
@javidx95 жыл бұрын
HI Marko, thank you for such kind words, they are much appreciated, I will!
@VanillaMidgetSSBM5 жыл бұрын
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*
@javidx95 жыл бұрын
Two weeks!
@TheSharkasmCrew9 ай бұрын
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_more9 ай бұрын
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_elfen5 жыл бұрын
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?
@javidx95 жыл бұрын
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!
@marmoripelaao98304 жыл бұрын
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!
@ibemper18504 жыл бұрын
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
@Otakutaru3 жыл бұрын
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).
@fj12n33 жыл бұрын
Dude you are such an amazing person, thank you for making all these insanely high quality videos!
@O5MO3 жыл бұрын
From this video i understood better what the dot product is than from other videos especially on this topic.
@zanzaraloggan37135 жыл бұрын
you're like the Daniel Shiffman of C++ :D
@5daydreams4 жыл бұрын
No, Shiffman is javidx9 of js
@neillunavat3 жыл бұрын
@@5daydreams hehe. Javidx9 is bob ross of c++
@ScibbieGames5 жыл бұрын
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
@hexhackbangla83685 жыл бұрын
thanks a lot , i was searching for this kind of video
@javidx95 жыл бұрын
Hey no problem noman, thanks!
@glitchy_weasel4 жыл бұрын
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!
@Ganerrr4 жыл бұрын
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
@prank8555 жыл бұрын
Will you be going over stuff like quad-trees or other optimization techniques?
@javidx95 жыл бұрын
Hi Prankster, maybe, but probably not in the context of collision detections. I do like a good quad tree though :D
@nebojsazakic5 жыл бұрын
Optimal is a boolean. More optimal and the most optimal are just optimal. Thanks for the video.
@PumpReactivationProject5 жыл бұрын
Wooow this tutorial is so informative and so easy to understand. Thank you for that!
@javidx95 жыл бұрын
Im pleased you found it accessible PRP! Cheers!
@coolmind24764 жыл бұрын
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.
@NeZversSounds4 жыл бұрын
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.
@minhcaohuu36913 жыл бұрын
thanks bro ;))) (nice stickman 8:04 btw)
@gdclemo4 жыл бұрын
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.
@Spongman5 жыл бұрын
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).
@DownloadableFox3 жыл бұрын
I love this man. This channel is gold.
@JackTheSpades4 жыл бұрын
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.
@skylersmith86964 жыл бұрын
"I'm no good at drawing straight things on the screen" Me tooooooo!
@SonictheHedgehogInRealLife4 жыл бұрын
Y’all draw gay things instead on screen
@benstech7263 жыл бұрын
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
@123eee5555 жыл бұрын
Awesome video! Thanks so much! The math of this had been giving my trouble for a while.
@javidx95 жыл бұрын
Hey no problem Nimbiz, thanks!
@NeilRoy5 жыл бұрын
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.
@javidx95 жыл бұрын
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-wo1wc5 жыл бұрын
Extraordinary!
@javidx95 жыл бұрын
Thanks Wayne!
@binary_gaming1135 жыл бұрын
Good video. Will you also do concave polygons?
@javidx95 жыл бұрын
Thanks Erazor, maybe, the naive approach is to partition your concave object into groups of convex objects and do the same.
@stumbling5 жыл бұрын
"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. :)
@federicocaputo39892 жыл бұрын
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 😅
@ps5games8215 жыл бұрын
Top games.You have the most best KZbin channel
@javidx95 жыл бұрын
Thankyou!
@Shadow-bc5nr2 жыл бұрын
Thanks alot for creating this video!
@munteanionut39935 жыл бұрын
This channel is really cool !!
@javidx95 жыл бұрын
Thanks Muntean!
@lucaxtal5 жыл бұрын
Really great explanation and clean code.
@klaus-udokloppstedt62572 ай бұрын
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.
@devinmurray49845 жыл бұрын
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.
@jursamaj2 жыл бұрын
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.
@miguelmejia32354 жыл бұрын
This is amazing! Also, I lost it at 36:04
@JackieSL95 жыл бұрын
What kind ofmonster dislikes these vids?! Thanks Javid for another great video.
@javidx95 жыл бұрын
Cheers bari!
@quillaja5 жыл бұрын
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.
@MrBidouilles2 күн бұрын
very instructive, thanks !
@whoshotdk3 жыл бұрын
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.
@leonardoherfianto8974 жыл бұрын
With diagonal every section is made from triangle, then combine with point in triangle formula can also detect the overlaping shape
@bpark100014 жыл бұрын
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!
@ragedprogrammer39524 ай бұрын
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?
@alterego47675 жыл бұрын
Oh wow, an excellent video on collision handling between convex polygons, fantastic! What prompted you to explore this topic?
@javidx95 жыл бұрын
Thanks AlterEgo, I guess you'll see at the end XD
@regarrzo5 жыл бұрын
It's a physics engine, I know it 👀
@Johannes003 жыл бұрын
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!
@jsflood5 жыл бұрын
Great video! Superb explanation as always :-)
@javidx95 жыл бұрын
Cheers D-Eye
@RetroDelux5 жыл бұрын
Sensacional meu amigo!
@javidx95 жыл бұрын
lol thanks again Jose!
@rapplejab5 жыл бұрын
This is great! Thank you very much :)
@javidx95 жыл бұрын
You're welcome rapplejab!
@francescopiazza48824 жыл бұрын
Very interesting! In a convex polygon, any couple of points is joined by an internal segment.
@davidecalaminici29373 жыл бұрын
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.
@marianapivetagiachini8505 жыл бұрын
javid u are the best
@javidx95 жыл бұрын
Far from the best Mariana, but I appreciate the sentiment! Thank you!
@racorescript5 жыл бұрын
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.
@javidx95 жыл бұрын
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!
@racorescript5 жыл бұрын
@@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
@gabigagu65992 жыл бұрын
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.
@badwrong3 жыл бұрын
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.
@wilykary3 жыл бұрын
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.
@JakeND11 ай бұрын
Gotta love that the video has 20k more likes than it has views
@zleapingbear5 жыл бұрын
Great video. Helpful. Also, thats a fast video output currently :)
@javidx95 жыл бұрын
Thanks zleapingbear, yeah went well this one XD
@zleapingbear5 жыл бұрын
@@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)
@pjh7775 жыл бұрын
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
@javidx95 жыл бұрын
Hi Pjh, the smaller one would need to enter the larger one first, and its diagonals would stop that from happening
@pjh7775 жыл бұрын
@@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.
@javidx95 жыл бұрын
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
@EmmittBrownBTTF15 жыл бұрын
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.?
@javidx95 жыл бұрын
There are a few techniques to do it, ultimately if you represent the structure as triangles then all the primitives are convex
@AndroidsReview4 жыл бұрын
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?
@Urre55 жыл бұрын
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.
@dercoder20575 жыл бұрын
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
@PleegWat5 жыл бұрын
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).
@javidx95 жыл бұрын
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.
@TheWeirdo8794 жыл бұрын
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.
@tanan81165 жыл бұрын
I wish I could like this video thrice
@tanan81163 жыл бұрын
@@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".
@thyandyr73695 жыл бұрын
I like the drawings and explanations parts
@bueno_excelente3 жыл бұрын
you honor the programmers
@Red-di7zb4 жыл бұрын
This is amazing, thanks for this. I was looking for it. =)
@AB-ut3ce4 жыл бұрын
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-ilyas5 жыл бұрын
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... :)
@Chrescoe15 жыл бұрын
Thanks!
@FredM805 жыл бұрын
I did'nt know the diagonal method, this is very useful ! Do you think it can be generalised for polyedron in 3D ?
@javidx95 жыл бұрын
Hi Fred, I think it can be, but it would be diagonals vs planes instead.
@FredM805 жыл бұрын
@@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 :)
@noahfletcher30194 жыл бұрын
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
@5daydreams2 жыл бұрын
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
@michaelmahn43735 жыл бұрын
I'm not remembering the details but could you not have re-used the collision detection module of the physics engine you have built?
@javidx95 жыл бұрын
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.
@michaelmahn43735 жыл бұрын
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.
@ratchet1freak5 жыл бұрын
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.
@javidx95 жыл бұрын
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.
@BanzayIkoyama5 жыл бұрын
@@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.
@SleepyHarryZzz5 жыл бұрын
@@BanzayIkoyama heh, "edge" case. Nice.
@ratchet1freak5 жыл бұрын
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
@javidx95 жыл бұрын
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.
@RSchenal5 жыл бұрын
Спасибо огромное!
@jumhig4 жыл бұрын
I think you can do concave poly collisions by breaking the concave poly into 2 or more convex polygons.
@shrutichakraborty13094 жыл бұрын
Is it possible to use this theorem to find the area of intersection between two shapes?
@valseedian4 жыл бұрын
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.
@TimothyChapman4 жыл бұрын
What would happen if you had two polygons that clearly overlapped, but none of the vertices of any polygon was inside the other polygon?