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.

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.