How do 2D physics engines solve the problem of resolving collisions along tiled walls/floors in non-grid-based worlds?

Question

I've been working on implementing my SAT algorithm which has been coming along well, but I've found that I'm at a wall when it comes to its actual use. There are plenty of questions regarding this issue on this site, but most of them either have no clear, good answer or have a solution based on checking grid positions.

To restate the problem that I and many others are having, if you have a tiled surface, like a wall or a floor, consisting of several smaller component rectangles, and you traverse along them with another rectangle with force being applied into that structure, there are cases where the object gets caught on a false collision on an edge that faces the inside of the shape.

I have spent a lot of time thinking about how I could possibly solve this without having to resort to a grid-based system, and I realized that physics engines do this properly. What I want to know is how they do this. What do physics engines do beyond basic SAT that allows this kind of proper collision resolution in complex environments? I've been looking through the source code to Box2D trying to find out how they do it but it's not quite as easy as looking at a Collision() method. I think I'm not good enough at physics to know what they're doing mathematically and not good enough at programming to know what they're doing programmatically. This is what I aim to fix.

Answer 1

The standard approach to fixing this problem is to preprocess the scene and mark all "internal" edges and then when you collide with one of these edges you determine a different collision feature to use in collision response. (i.e. maybe respond to all adjacent faces for which dot(face.normal, body.linearVel) < 0 or something - this doesn't address rotations though)

Box 2d addresses this with "Ghost vertices" there's a tutorial about it here. http://www.iforce2d.net/b2dtut/ghost-vertices

Paul Firth talks about this issue on his blog here: http://www.wildbunny.co.uk/blog/2012/10/31/2d-polygonal-collision-detection-and-internal-edges/

Edit: Thinking about this in 2d a bit more it seems like if you have edge-edge connectivity the heuristic you should use is to back the collision point up a little bit along the collision point's velocity and then see if it projects to either edge closer than the vertex (intuitively trying to determine if that point approached within the collision feature's voronoi region) and then use that edge instead of the vertex.