Submit to StumbleUpon Share

Hi and welcome back to my blog!

I wanted to share something I've recently discovered about the heinous problem of internal edges in 2D polygonal collision detection. It's not a full-solution, but maybe it will give some other programmers an idea or two. Food for thought!

What are internal edges?

In general, polygonal collision detection refers to convex polygons, because algorithms for detecting and resolving against convex polygons are well understood and documented; techniques like SAT and Minkowski Difference are common-place.

But this convexity requirement presents a problem: not all things we want to represent are convex. In to mitigate this, concave objects are broken down into convex sub-parts.

Figure 1

In Figure 1 concave object A is broken down into two convex sub-parts B and C. In doing so we have now created an internal edge between the two shapes shown as a thick black line.

Why are they a problem?

Internal edges start becoming a serious problem as soon as you have any object sliding along another one, like a block being pushed down a hill, or even just the player walking along (if their collision shape is an AABB for instance).

Figure 2

Figure 2 shows just such an example. Block P is sliding down object B and will start to collide with C quite soon. Intuition says that P will collide with the top edge of C and continue sliding smoothly, however that may not be the case. If P is exactly on the surface of B as it slides, there is nothing but chance which will dictate which edge of C will be the collision edge. It's just as likely to chose the left edge and produce the blue normal n as the collision normal. This will cause the sliding object to get stuck on the internal edge, just as if it had hit a brick wall, which is highly undesirable.

As far as the collision engine is concerned B and C are totally separate objects so it must consider any possible candidate edges of C.

Figure 3

Figure 3 shows what the collision engine sees (left) when it's deciding which normal to return. This situation can also arise if the object is sliding along the bottom edge (as shown on the right). Here, we often end up getting stuck again, but this time it will be an opposing normal from object B which stops P in its tracks.

Speculative contacts

This whole situation is exacerbated if we're using Speculative Contacts because then we're always asking for the closest points on two objects, whether they're touching or not, which will tend to pick out internal edges much more often.

Lets quickly review the possible closest features between two convex polygons.

Figure 4

Figure 4 shows the first two primary collision cases (where either a vertex from P is closest to an edge of C, or visa versa), and on the right the usually degenerate vertex vs vertex case. I say degenerate because generally in 2D collision detection you're either dealing with finding where two objects just touch, or finding how far penetrated into each other they are and in both of those scenarios, the vertex vs vertex case can either be expressed as edge vs vertex or vertex vs edge, making it redundant or degenerate.

However, with speculative contacts you want to find these closest features when the objects are penetrating or separated, which means this previously degenerate case is no longer degenerate.

While I was looking at this problem again from the POV of solving it somehow while still being able to use speculative contacts I noticed something interesting. All the cases I could see where there was an internal edge causing problems were in fact vertex vs vertex.

Figure 5

Figure 5 shows a few cases where the collision is vertex vs vertex. The two on the left represent problem cases for the proposed technique whereas the two on the right are easily solvable.

Traditional approaches to solving this

Traditionally, this problem is mitigated by 'instrumenting' your objects as a pre-process, to identify internal edges and then to have the collision system chose an adjacent edge to the internal one and return that instead using some kind of heuristic to determine which edge to chose. This is fraught with problems, not least of which is how to deal with two entirely separate objects which are butted up together and have never been part of the same object in the first place. There's also the problem of what to do if you have two instrumented objects sliding over each other, the choice of which alternative edge to chose suddenly gets a lot more complex.

I've personally used this technique myself and was never fully satisfied with it.

Towards a new way

Simply discarding all contacts which are vertex vs vertex will get us a long way towards a full solution.

This will solve two out of the four cases I've illustrated in Figure 5, as discarding those contacts doesn't remove any useful information. The left hand cases, however will need some attention because it's possible the object P will end up embedded into C without an alternative contact normal to deflect it, or if P is travelling fast enough it could miss the collision altogether.

Figure 6

Figure 6 shows the situation in this case.

However, this technique does hold very significant advantages because you no longer need to instrument any objects and because of that it will deal correctly with two separate objects butted up together. Or in the case of collision detection against lines, it will deal with T-junctions.

Figure 7

Figure 7 shows a maze with T-junctions which would otherwise have caused the triangular ship to catch as it slides along the edge.

I am currently using this technique in my game mmoAsteroids, which you can play by clicking the link in the side-bar if you'd like to try this out for yourself. I find it far preferable to getting stuck on edges, even taking into account the problem it has with the case illustrated. The bottom left case in Figure 5 is extremely difficult to reproduce as you need pixel perfect alignment to trigger it, which means in practice all you deal with in the bottom right case.

I'd love to hear your thoughts on whether you think this can be improved to take account of the two problem cases in Figure 5.

That's all for now, until next time: have fun!

Cheers, Paul.

Submit to StumbleUpon Share