Convex polygon based collision detection

A lot of people have asked me: Why use a convex polygon only engine like Box2D? In this post I will provide some info on why convex polygons is the optimal polygon type to use.

What does convex mean?

Convex polygons needs to satisfy the following requirements:

• All internal angles must be below 180 degrees
• Every line segment between two vertices can be contained fully inside or at the edge the polygon

A non-convex polygon is called a concave polygon and it must have an internal angle measuring greater than 180 degrees. As you might have thought about yourself; concave polygons can be quite handy. Convex-only engines can’t represent a simple player polygon like Pac-Man.

Why use convex-only?

There are really only one big juicy reason: performance

Physics engines are able to take quite a few shortcuts and use cheap algorithms to determine the closest vertex, shortest distance and a lot more. An algorithm like Separating Axis Theorem and the Gilbert – Johnson – Keerthi (GJK) (pdf) algorithm both operate on convex polygons and provide fast, yet robust methods of getting collision information. Fundamentally there are two great features of convex polygons:

• The existence of a separating plane between two non-colliding convex polygons
• When two points on two different geometries are at a minimum, they are at a global minimum.

That might sound like gibberish for the layman. I’m not going to explain what those two characteristics involve, but suffice to say that you can cut down on the complexity of the algorithms used.

Problems with using convex-only engines

In a performance point of view there are really no problems with using convex-only algorithms. The problems that arise are mainly usability (ease of use and convenience for the users). If the user supply the engine with a concave polygon, all kinds of weird collisions will happen. A check is needed to make sure the supplied polygon is of convex nature. But that topic is reserved for another blog post.

The main approach for supporting concave polygons in a convex-only engines is described below.

Convex decomposition

This method involves the use of either triangulation algorithms or algorithms that finds a number of convex polygons from a convex polygon. The idea behind convex decomposition is to simply split a concave polygon into smaller convex polygons. This way a convex-only engine can support concave polygons. A lot of algorithms exist to do this. To name a few: Earclip, Delaunay triangulation and Seidel’s triangulation algorithm.

Here is an example of a triangulated concave polygon using a Constrained Delaunay Triangulation algorithm.