Hierarchical Approximate Convex Decomposition

SourceCode

The source code of the HACD approach is available here. The HACD library is distributed under a BSD license and was tested on Windows, Mac OSX and Linux Ubuntu.

You can dowload test data and results from here (78 MBytes). For visualization you can use MeshLab .

Abstract

Collision detection is essential for realistic physical interactions in video games and computer animation. In order to ensure real-time interactivity with the player/user, video game and 3D modeling software developers usually approximate the 3D models composing the scene (e.g. animated characters, static objects...) by a set of simple convex shapes such as ellipsoids, capsules or convexhulls. In practice, these simple shapes provide poor approximations for concave surfaces and generate false collision detections.

A second approach consists in computing an exact convex decomposition of a surface S, which consists in partitioning it into a minimal set of convex sub-surfaces. Exact convex decomposition algorithms are NP-hard and non-practical since they produce a high number of clusters.

To overcome this limitation, we relax the exact convexity constraint and coonsider instead the problem of computing an approximate convex decomposition of S. Here, the goal is to determin a partition of the mesh vertices with a minimal number of clusters, while ensuring that each cluster has concavity lower than a user defined threshold.

HACD vs. ACD ( John Raltcliff's approach)

Results