2D polygonal collision-detection and internal edges

Figure 2
Submit to StumbleUpon

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

About Paul Firth

A games industry veteran of ten years, seven of which spent at Sony Computer Entertainment Europe, he has had key technical roles on triple-A titles like the Bafta Award Winning Little Big Planet (PSP), 24: The Game (PS2), special effects work on Heavenly Sword (PS3), some in-show graphics on the BBC’s version of Robot Wars, the TV show, as well as a few more obscure projects.   Now joint CEO of Wildbunny, he is able to give himself hiccups simply by coughing.   1NobNQ88UoYePFi5QbibuRJP3TtLhh65Jp
This entry was posted in Collision Detection, Geometry, Polygons, Technical and tagged , , , . Bookmark the permalink.

14 Responses to 2D polygonal collision-detection and internal edges

  1. Disclaimer: I haven’t been doing physics engine stuff for a while, so am totally rusty.

    What about circles? Seems like they’d be less of a problem, but if you’re treating them as a single-vertex object with the radius subtracted from distance calculations, you do need vertex-vertex collisions.

    Not sure I understand the problems with the approach of marking some edges as internal and not using them, but I’ve never tried using it so that’s not too surprising.

    • Paul Firth says:

      Yes, circles present more of a problem potentially, although I haven’t thought much about them yet to be honest :)

      The problem with the pre-process is that it can’t cope with objects butting up against each other which weren’t part of the same object originally.

      • Oh right, so if you’re walking on a floor of crates pushed together for example? That makes sense.

        Hmm, on further thought I’m not convinced that the vertex-vertex contact will always be the one found. In the bottom-right figure in (5), won’t the closest features be vertex-edge? And in the top two, you only need a small amount of penetration for vertex-edge to be the closest features.

        A lot of this could depend on the details of your detection system I guess.

        • Paul Firth says:

          Hi alan,

          Actually, I you’re right about the bottom-right in figure 5, my mistake! :)

          Also, your right about penetration – as soon as you start to get some, your vertex vs vertex contacts start becoming the other two cases.

          Cheers, Paul.

  2. Raigan says:

    I’m afraid I don’t have anything to contribute in terms of suggestions, but I wanted to say that I looooove this sort of article as it’s a hard problem everyone always solves with special-case hacks, and no one really discusses, and it’s great to try to join forces and figure out a better approach. Also your insight into ignoring the v-v cases is great!

  3. Hamish Atkinson says:

    Hi,
    How do you store the vertices of the two conjoined convex polygons? It strikes me that all the conjoined shapes you have shown in your examples actually share two vertices. (The T-join in the asteroids is perhaps different)

    I assume that your collision detection algorithm is trying to determine the point at which the shape P sliding along shape B contacts the joined shape C (so it can correctly modify the behaviour of both shapes following the collision)?

    Looking at your examples, in every case the actual intersection point will be the vertex shared by the 2 conjoined shapes (i.e. it satisfies both a collision with the internal edge and the external edge). If you algorithm randomly chooses one or the other then that must be a rounding error caused by your algorithm.

    As I expect that these sorts of collisions are rare, can’t you just detect the cases where your algorithm indicates a collision with an internal edge and instead run a collision test with the other edges of the collided objects? In the case of concave joins, extend the edge to infinity instead of stopping it at the vertex. This should produce a collision with the correct edge.

    • Paul Firth says:

      You can, yes but the algorithm is complex in the extreme and it doesn’t deal with the case of two separate objects butted up together. That’s what this article is primarily trying to address :)

  4. Spider says:

    Hi,
    I wanted to share how I solved the internal edge problem on SAT algorithm which also gave me some bonuses.
    I used a visibility flag for edges. So when the normals are calculated if current edge has the visibility flag set to false I add to a list the normal axis.

    Now when the collision occurs there are 2 methods of dealing with it:
    1. When calculating the penetration depth and is smaller than previous one, check the ignore axis list, if dot product with those axis is > 1 – epsilon then ignore that axis and don’t add it to solution.
    2. (I’m using this) more optimal is after choosing the collision response axis just search in the ignore axis list with a dot product, if its the same axis + epsilon then ignore that collision.
    This is more optimal but feels like it can cause problems because of ignoring the collision, anyway I didn’t have any of problems and the collision response feels good.

    Now about bonuses:
    1. If the character and platform is an AABB or platform include the axis aligned axises then using edge visibility you can create one sided platforms
    2. Automatic stair behavior, just set the front side of the stair to have invisible edge, the collision routine will ignore it as soon as the character will penetrate the stair enough to make the smaller collision the upper part of the stair and snap to it.

    • Paul Firth says:

      Hi Spider,

      Interesting set of solutions there, thanks for sharing!

      Did you find any problems with objects falling though each other if they are heavily inter-penetrating due to the ignored collisions?

      Cheers, Paul.

      • Spider says:

        I’m using visibility edges only for static objects,
        I use them usually for adjacent edges,
        So there is a possibility for a small object to pass thru a small platform, but to solve this, I use relative big enough boundings for characters and limited velocity. If an object has a chance to have a bigger velocity then segmentation can be used.

        here is a small prototype:
        http://www.sendspace.com/file/095pc9
        left-right move, space jump, mouse click shot.
        character is AABB, collisions are SAT
        red edges are invisible edges. blue visible.
        bullets uses ray-convex intersection (ignores edges visibility), mouse circle uses point-convex (take account of edge visibility and snaps to nearest visible edge if inside)

  5. demented hedgehog says:

    I suspect that the problem is that you don’t have all the information you need to make a reasonable decision in this case.

    In Figure 2.. When object P gets to the bottom of the slope in real life it would collide with B and C simultaneously. We’re being forced to handle collisions pairwise here? (well that’s the way all? of the other 2D speculative collision algos I’ve looked at seem to suggest).

    I think forcing the pairwise resolution throws away useful information. So my proposal (and cut me a bit of slack here I’ve not thought it through) is that you have to
    do all combinations of possible collisions and (I’m guessing at an heuristic here ->) choose the order of collisions that gives the object P the largest change in position.

    So when P gets to the bottom in Figure 2 it can collide with \A,/B *xor* \A,-B. (for each corner collision you need to fork and do an extra x2 number of detections) (notation \A is the top face of A, /B is the internal edge of B, -B is the top of B). In the case of \A,/B the object P gets stuck on the internal edge and stops abruptly. In the case of \A,-B the object P moves out onto the top of B. So we calculate the distance moved in both cases and choose \A,-B because it’s greater.

    So that approach opens up its’ own can of worms.. firstly it’s complicated to implement, then what happens when you have a particle system explosion.. how many collisions do you have to work out (lots)? What happens when you have, say, a ring of things all hitting one another?

    So in brief i) does it scale too badly? ii) what happens with multiple moving objects? iii) does it even work?

  6. demented hedgehog says:

    I guess you’d implement my previous idea by treating each object as a node and your AABB pass would add edges to the nodes.. then for each unvisited node handle the connected subgraph of collisions with that node in it and mark every node in the subgraph as visited. So the problems mentioned in my previous post are large subgraphs and cyclic subgraphs.

  7. blaize rhodes says:

    OK .. I’ve been thinking about my approach. I wonder whether the move the player the furthest heuristic would push him down stairs!

    So now I reckon that if you treat the collisions as horizontal, vertical and corners then do the corner collisions after the horizontal and vertical collisions then that solves the problem? The theoretical basis of this is that you collide with the closest edges first and because of the triangle inequality internal edges will be further away than floors under the player.

    Check this conversation out to..
    http://www.reddit.com/r/gamedev/comments/1w92dm/2d_collision_detection_and_resolution_solving_the/

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

WP-SpamFree by Pole Position Marketing