Monday, 12 November 2012

V-HACD: Replacing Triangle's Constrained Delaunay Triangulation

As mentioned in my previous post, the first version of V-HACD relies on the library Triangle to compute 2D constrained Delaunay triangulations. In fact, the V-HACD algorithm involves clipping the mesh against a plane and filling the produced holes (cf. Figure 1).

The Triangle library produces excellent results and is very stable. However, as pointed out by Erwin Coumans it has a non permissive license. Another alternative to Triangle is the poly2tri, which is released under a New BSD License. Poly2tri turned out to be non-usable in my case because it supports only simple polygons as constraints. After searching the internet for a "good" and stable implementation with a permissive license, I ended up developing a simple triangulation algorithm (it is not a Constrained Delaunay Triangulation), which is enough for V-HACD needs. My implementation is a very simplified version of the Incremental Delaunay algorithm 

The new triangulation algorithm was uploaded to the git repository and could be compared to the Triangle library by adding #define USE_TRIANGLE to vhacdMesh.cpp

The code is still ugly and not optimized at all. For now, I am trying to have some first results and understand better the algorithm limitations. Hopefully, I'll have soon the time to clean up the code.

Wednesday, 7 November 2012

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 depth maxConcavity invertInputFaces posSampling angleSampling posRefine angleRefine alpha targetNTrianglesDecimatedMesh
  • 3D mesh in off format (type: string, example: )
  • 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 "" use the following command line:

testVHACD.exe 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