Это видео недоступно.
Сожалеем об этом.
EPA Explanation & Implementation
HTML-код
- Опубликовано: 31 июл 2024
- GJK tells us if there is a collision, but doesn't give enough information to respond to it. In this video I cover a supplemental algorithm called the Expanding Polytope algorithm that uses the pieces from GJK to give us this info. With it we can respond to collisions between any two convex polygons.
Check out the full article: winter.dev/articles/epa-algor...
GJK Tool: winter.dev/articles/gjk-algor...
Intro: 0:00
Explanation: 0:23
2D Implementation: 1:36
3D Implementation: 2:55
Demos: 5:25
Bruh, I was looking at GJK and EPA 2 yrs ago. I've looked at these algorithms so much that I remember these algorithms better than the sorting algorithms I learned at school.
lol after those videos me too, thanks for the comment
Amazing video, I find it very impressive that you can explain a topic like this as well as the 1 hour long talks can, but only in a couple minutes.
Thanks! You always gotta rewatch/read things to get an understanding well enough to implement, so might as well have that be like 5 mins instead of an hour :)
I've been researching on collision detection algorithms lately, reading various docs, articles, etc. and then I found your videos. The explanations are simply amazing! I'm also trying to figure out how to do ray casting with GJK. Any plans on doing an video about that?
Thanks, there is a good chance that I am going to need ray casts myself, I'll make a video when I do that. Probably, 2-3 videos out though. I want to cover some rendering next
i greatly appreciate these videos
Hello Winterdev.
Thanks for the great Video. When checking what faces to delete you check if the normal of the triangle and the supportpoint are in the same direction. This only works for some cases. Since you want to check if the support point is on one side of the triangle you want to use the supportpoint relative to the triangle.
So the check would look like this
if (SameDirection(normals[i], support-polytope[faces[i*3]])
Just found this comment and it solved the issue I was on for hours, thanks a lot!
10/10 amazing work
Great video! One thing to keep in mind; if delta is large enough, your objects can essentially go through each other. This might occur during a frame-drop or the like (unless your engine has a fixed timestep). A sweep check can fix that though (in the case of arbitrary convex sets a simple gjk pass should be enough)
Yeah I have a fixed time step but the issue I was running into was if that was larger than the regular delta time everything would grind to a halt. I wana look into sweep checks but none of my projects have needed that so I haven’t looked into it yet :)
Keep doing, it's brilliant !
Came here from the channel Reducible. 3Blue1Brown also a good channel. Nice visualizations.
Wow, very cool, I'll try implementing this into my engine after I get project loading and drag and drop file loading.
I wish you good luck!
I'm confused on the part where you reverse the distance and normal if the face is facing toward the origin. There is an edge case where if I have two cubes that are aligned on two axes and they collide, reversing the normal seems to be causing problems giving me the wrong normal. That's because the smallest normal becomes largest normal I guess, but I don't want to just cut the code out without understanding why it was there to begin with.
Amazing ! Can y make a video about inertia, and some complex rotation physics. I found an crazy cool effect called "Dzhanibekov effect" . To simulate it, there must be solid rotation physics background !
After a couple videos I plan to get back to physics, but I am going to go in a slightly different direction for the next few. That would be cool to try and simulate though, I wonder if it would work right off the bat, or if it needs more subtle detail that a physics engine optimized for speed would drop. Will keep in mind!
One question I have is how you resolve situations where one or both colliders aren't properly polytopes, but are surfaces/curves?
For example the support function for a sphere will always return a further point along the normal of any face made from points on its surface than any existing point on its surface. That means if a sphere collides with the corner of another object, the EPA could go into a theoretically infinite loop. How do you handle this? Do you just cut it off after a fixed number of iterations or a maximum size of polytope?
Yeah you got it I put a max iterations of 30 in my code. There is probably a proper way to do that, but I didn’t look into it. You could prob use a different method for curves and store shapes as a series of edges / splines and do something dif for each combo
Great video 👍 any plans on doing a video on conservative advancment or bilateral advancment using gjk?
Thanks! If that's to do with continuous time steps, I was thinking about doing that or rotational stuff next. I might take a little break from physics though and do some rendering videos but we'll see what comes up.
@@Winterdev Thanks for the reply, yeah I was thinking about continous detection. Been trying to implement it myself but it hasnt been going well. Thanks for making all these videos they are very helpful 👍
hmm yeah If I were to make a video I'd also be starting from scratch on that one. There is a cool talk that the creator of box2d did a few years back where he gives a high level view of it, ruclips.net/video/7_nKOET6zwI/видео.html. Also while finding that video I found this funny tweet where he links source code if you're interested, twitter.com/erin_catto/status/1315505365086216192
@@Winterdev Also interested in bilateral advancement. Btw, Erin tweeted about BA right after I asked a question about it on the box2d discord server...
For some reason it's not working with sphere-sphere collisions I think
It will get into a inf loop with sphere v sphere, so you can either add a max iteration loop. Or the real solution is to only use this for mesh v mesh and have a separate function for sphere v sphere. In my testing it works with sphere v mesh.
Great channel. What did you use for collision resolution?
There are ‘solvers’ that change the velocity and position. You can find them here github.com/IainWinter/IwEngine/blob/master/IwEngine/src/physics/Dynamics/ImpulseSolver.cpp
Don't you also need the full set of contact points?
Hey loving this series and I've got a kind of working implementation that works mathematically (don't have a renderer just yet) what license is this code under? I'd like to use your physics engine or a very modified version in my own engine. Mine would stay open source under MIT, or ZLib or something. Is that something you'd be willing to give permission for?
Also just to clarify, I'd obviously give credit in the code and github page if that's something you'd prefer
Yes go ahead anyone can use the code in these videos for whatever purpose. These are all hobby projects so go ahead. I do need to get an actual license on the GitHub tho, I’ll pick one soon. Feel free to use the code :)
where is the class CollisionPoints on the article? and now just need aabb dynamic tree
Oh good catch, I added that to the video last second.
And yeah things start to get a littttttle slllow after about 70 objects without any broad phase. I'll make a vid at some point, I wanna try a rendering one first though
@@Winterdev btw what math lib do you use?
@@matanmigdal7108 none other than IwMath! github.com/IainWinter/IwEngine/tree/master/IwEngine/include/iw/math. I made it to initially learn C++ :)
To implement the EPA, do we need to have all the possible Minkowski difference points?
Nope just the last simplex from gjk and the support function
Hey Winterdev, question, how does one get the two collision points from this algorithm?
Hey sorry for late reply, if you read the chain between DANISH AMIN and I, I cover this. Basically you need to do some more projections from the normal based on the distances from the origin
@@Winterdev Alright perfect thanks. I figured it out myself by now because one of my colliders was a sphere, which makes it easier. Anyway, great tutorials! If you ever want to, a dedicated video on collision response would also be kewl. I find there's a lack of resources on that online
@@Winterdev Where can I find this chain? This is the last piece I need for my physics engine.
do you have the time to make a third video explaining rotational physics?
Yes I plan to. I am on vacation coming back soon, hopefully with scripts in hand :)
Awesome! thanks so much!
uggh rust is so hard to read. EDIT: oh this is javascript. still don't know why the different language tho.
I put the first gjk in JavaScript cus I made that tool in the description that you can see the iterations. Mostly for debugging :)