Convex Polygon Collisions #1


In this video I look at collisions between convex polygons, including rectangles. A quick examination of AABB (Axis Aligned Bounding Box) followed by SAT (Separated Axis Theorem) and an alternative I don’t know the name of. As well as checking for overlap, I experiment with resolving the collisions statically.





Xem thêm bài viết khác:


  1. Hi Javid, what do you think of running around the convex, and just collect the signs of the Dot-Products of edge-normals with difference vector to points of other polygon and if they are all the same sign, it is a collision:

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

  3. 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?

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

  5. Best explanation of SAT I've seen. I've been putting off looking into it properly for years but this video really demystified it.

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

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

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

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

  10. Hmmmm. I think a technique similar to the "diagonals" is possible, where you just check if any of the sides intersect. This wouldnt be so good for resolving static collisions, but it would save some processing time, because you only have to check one polygon

  11. 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?

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

  13. 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!

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


Please enter your comment!
Please enter your name here