Continuous Collision Detection

Question

So I'm playing around with the separating axis theorem and collision. Obviously the problem of what face it collided with arose. I need the unit normal which is tangent to that face it collided with to resolve depth penetration. For rectangles it's easy.

Update Y velocity
If collision
    collision happened on the y axis.
Update X velocity
If collision
    collision happened on the x axis.

But I wanted a more general that would work with all cases. I came up with two solutions

1.) So I thought about the solution above with a triangle. Obviously it wouldn't work because the rectangles faces are axis aligned and a triangles faces are not. So I figured I could just project the face and velocity using the dot product to solve it like the rectangle but for every face with its own axis. This would of course involve checking collision with the whole shape again for each face.

2.) I also figured I could do Polygon v Ray collision detection to figure out what face it collided with.

My question is: Which solution is faster? Or is there a better one that hasn't come to my mind?

I don't know how to do Polygon v Ray collision but I would guess that foreach face, find intersection point between ray and segment of face.

Answer 1

Separating axis theorem on x and y is often only used for a quick pre-test if more accurate collision tests are necessary. These usually include accurate ray/polygon tests etc.. Keep in mind that the general approach of finding a separating axis/hyperplane works only for convex objects! See Wiki.

Generally, it is not a good idea to update positions on the axis separately - if you find a collision, you might still want to update the other axis depending on your resolve strategy. Instead you should just check all objects that have moved since the last simulation step.

Polygon vs Ray 2D:
As you suggested, just test the ray vs every edge. Only if a single polygon is extremely complicated (>100 edges) you may need to think about more involved data-structures for this task.

Polygon vs Ray 3D:
Polygon vs ray works by first intersecting the ray with the polygon's plane (early out if no hit). This reduces the problem to two dimensions: For triangles you need to determine the barycentric coordinates and check weather they're inside. For more complex polygons you can check for every edge if the point lies inside or outside - only if the tests return "inside" for every edge, the ray has hit the polygon.