2
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ I'm not sure what your question is. SAT is pretty robust for any kind of collision detection. There are other algorithms but, for most purposes, it is not needed. If there is a error in your collision detection, it's most likely because you didn't implement SAT properly, or working with polytopes that are non-convex. \$\endgroup\$
    – xcrypt
    Nov 20, 2012 at 10:14
  • \$\begingroup\$ The issue I'm having is covered here and here and, to some extent, here. As far as I can tell this IS a problem that will happen with SAT and needs to be solved. If I'm wrong, then please save me a lot of anguish and tell me how \$\endgroup\$
    – ssb
    Nov 20, 2012 at 10:23
  • \$\begingroup\$ Also somewhat covered here \$\endgroup\$
    – ssb
    Nov 20, 2012 at 10:25
  • 1
    \$\begingroup\$ Oh, I think I get it. The problem you are having isn't really an issue with SAT, it's collision resolution that you need. To have decent collision resolution is not always easy. I recommend this book: books.google.be/books/about/… \$\endgroup\$
    – xcrypt
    Nov 20, 2012 at 10:26
  • \$\begingroup\$ Thanks for clarifying that, I edited my post to change the language a bit. \$\endgroup\$
    – ssb
    Nov 20, 2012 at 10:35

1 Answer 1

4
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .