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 are the optimal polygon type to use.
What does convex mean?#
Convex polygons need 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 of 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 is 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. Algorithms like Separating Axis Theorem and the Gilbert – Johnson – Keerthi (GJK) (pdf) 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#
From 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 supplies 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 engine is described below.
Convex decomposition#
This method involves the use of either triangulation algorithms or algorithms that find 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.
