Assignment A2 — Concave Collision Handling

An implementation of collision detection and handling for concave polygons.

See our previous blog on A2.

The Problem

Unfortunately, GJK and EPA do not work for concave obstacles. We cannot use concave shapes when using the GJK algorithm because when taking the Minkowski difference of two non-­convex shapes, we get a convex shape. Therefore, when using the GJK algorithm, though our Minkowski difference may not contain the origin, our simplex can. The Minkowski difference of 2 convex shapes will produce a convex shape for which there is no chance of a simplex containing the origin and the resulting convex shape not containing the origin.

The Solution

In order to get around this problem, we triangulate all of the concave polygons and then run the collision detection on all pairs of triangles from shape A and shape B. If none of them are intersecting, then the two concave shapes are not colliding. Otherwise, they are, and we can calculate translation vectors from normal GJK and EPA.

The Solution’s Problem

Unfortunately, doing pairwise intersection tests for the triangles of the two shapes is expensive — O(m * n), where m = the number of triangles in the triangulation of shape 1 and n = the number of triangles in the triangulation of shape 2. This gets very expensive very fast if the two shapes have a large number of vertices.

Partial Improvements

One improvement that we made is that we only do this collision handling if at least one of the shapes is concave. If both are convex, we just run the normal GJK and EPA algorithm, which runs very efficiently. Otherwise, we fallback to this inefficient method.

One minor improvement that we can make, is computing bounding boxes and convex hulls where we can rule out collisions very fast if they are not very close to occur. This does not help in the worst case, however.

What we really want to do is make static and dynamic improvements:

• Reduce the number of shapes from triangulation — this can be done by merging the triangles together in a way that it maintains convex shapes
• Reduce the number of collision checks— this can be done by using an efficient data structure that rules out some collisions (like the improvement mentioned above). Options include some form of bounding volume hierarchy and sweep and prune.

Final Words

Unfortunately it seems that concave shapes are just more difficult to deal with than their convex counterparts. Although we agree that it would be wrong to not have them, it is clear that they require careful analysis and consideration as they are difficult to implement and at least a magnitude less efficient than collision handling for convex shapes.