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.

No comments:

Post a Comment