This post is out-of-date. Check out V-HACD 2.0!

V-HACD: Hierarchical Approximate Convex Decomposition Revisited

Lately, I have found time to work on improving the HACD algorithm. The new V-HACD library tries to tackle the problem of convex-hulls inter-penetration usually encountered when using HACD. Figure 1 illustrates this limitation by comparing V-HACD results to those generated by using HACD.

Figure 1. V-HACD vs. HACD: V-HACD generates non-overlapping convex-hulls.

V-HACD works only with manifold closed meshes of arbitrary genus, which makes it less general than HACD algorithm (which handles open and non-manifold meshes). The V-HACD code  is available under New BSD License. However, the current version relies on the following other libraries:

• Triangle to compute constrained delaunay triangulation which has a non permissive license, which should be replaced [Thanks to Erwin Coumans for noticing that]
• Ole Kniemeyer's implementation of the convex-hull algorithm provided with bullet
• John Tsiombikas's kd-tree algorithm

The first results are encouraging. However, the code is still buggy and not optimized. I hope that people would be interested in helping me improve this first version.

To play with the algorithm, a pre-compiled win32 executable is available here
Pre-computed decomposition results are available here

V-HACD parameters are the following:

testVHACD fileName.off depth maxConcavity invertInputFaces posSampling angleSampling posRefine angleRefine alpha targetNTrianglesDecimatedMesh

• fileName.off: 3D mesh in off format (type: string, example: block.off )
• depth: maximum number of decomposition stages (type: integer, default: 10)
• maxConcavity: maximum allowed concavity (type: float, default 0.01)
• invertInputFaces: indicates whether mesh normals should be inverted or not (type: boolean, default 0)
• posSampling: clipping plane position sampling resolution for coarse search (type: int, default 10)
• angleSampling: clipping plane orientation sampling resolution for coarse search (type: int, default 10) 
• posRefine: clipping plane position sampling resolution for refined search (type: int, default 5) 
• angleRefine: clipping plane orientation sampling resolution for refined search (type: int, default 5)
• alpha: parameter controlling the compromise between concavity and balance between convex-hulls. (type: float, default: 0.01)
• targetNTrianglesDecimatedMesh: number of triangles in the decimated mesh. V-HACD decimates the input mesh to reduce computation times. (type: integer, default: 1000)

To apply V-HACD to the input mesh "input.off" use the following command line:

testVHACD.exe input.off 30 0.01 0 64 32 8 64 0.001 2000

Below, some screen-shots of the obtained results.

The current version of V-HACD provides poor results or errors for the following three meshes. As soon as I get some free time I'll try to fix these bugs.

• dancer2
• elk
• hand1
• hand2
• hero
• octopus
• polygirl
• shark_b
• Sketched-Brunnen
• torus
• tstTorusModel
• tstTorusModel3