Box2D and Approximate Convex Decomposition (ACD)
Jyh-Ming Lien
 | OverviewBox2d 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:
- For Linux an OSX only. Windows version is coming soon. (Sept. 12, 2012)
- There are four examples in the package: main_n_c, where n goes from 1 to 4. Copy one of it to main.cpp and compile.
- You may need to have glut library if you want to visualize the results. You can get glut from freeglut for linux and from this page for win32.
- Source code (in C++) is available on request
- Report bugs to jmlien@cs.gmu.edu
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.
 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
- Box2d official site
- Approximate Convex Decomposition page
- b2Separator by Antoan Angelov is another alternative. As far as we know, it does exact convex decomposition.