Box2D and Approximate Convex Decomposition (ACD)


Jyh-Ming Lien


image
Overview
Box2d is a popular 2D physics engine. A limitation of Box2d is that it only handles convex shapes. Non-convex (or concave) polygons need to be represented as edge shapes or a collection of covex shapes. This page provides a solution using Approximate Convex Decomposition (ACD) to address this limitation. ACD decomposes a polygon with or without holes into a set of nearly convex shapes. In this demo, we simply create convex hulls of each ACD components and create them in Box2d. The image on the right shows an example of Box2d/ACD using the Nazca Monkey polygon.



Software

This package b2ACD2d contains (1) ACD2d library (headers and library), (2) glue code with Box2D, (3) Box2d headers and binary
and (4) some example polygons.

download b2ACD2d.zip

Notes:

Video

This video shows Box2d simulation using the Nazca monkey polygon. The left half of the video
shows approximating the shape using 30 convex shapes and the right half uses 434 convex shapes.
If you look closely, some monkeys are overlapping on the left side but not on the right side.


image
The Nazca monkey has 1,204 vertices and 584 notches (concave vertices).

This following video show a variety of polygons (even polygon with holes) created in Box2d.
Random impulses are applied to the polygons.



Related Links
Computer Science @ George Mason University