How does CDT compare to Triangle

[artem-ogre]

Original post by @RotateMe:

Hi, first of all thanks for all the effort and for providing an extremely easy-to-use and easy-to-add-to-my-cmake-project library for CDTs. from what I've read it must be one hell of a task to implement this. My preliminary tests all worked flawlessly.

I'm currently looking into using this library for various steps in fitting NURBS surfaces to meshes, which might be a surprising usage, but both the parameterization step, as well as "cutting" the spline surface and remeshing it benefit vastly from a good CDT library.

My question concerns the only real C alternative that I would consider, which is John Shewchuck's "triangle" library (https://www.cs.cmu.edu/~quake/triangle.html): How well do you know it, and how well does your library compare to it? "Triangle" provides quite a lot of options, which is not always a good thing, since your library just seems to "just work", but I'm wondering if there are things that "Triangle" does that this library can't (as of yet).

At the moment I'm trying to make a wrapper that emulates "Triangle"'s i/o structure so that I can use your library for the parts of libigl (https://github.com/libigl/libigl) that rely on "Triangle" (the reason being licensing issues with "Triangle"), and for now it seems, that the way to go is to ignore almost all of the command line options.

Thanks again for this wonderful project!

[artem-ogre]

TL;DR: If you only need to do constrained Delaunay triangulations CDT is a great replacement for Triangle. Give it a go: I would really love to hear how it worked and see some results!

Licensing

As you mentioned, Triangle lacks a comprehensive/commonly used/permissive license.
From Triangle license:

Distribution of this code as part of a commercial system is permissible ONLY BY DIRECT ARRANGEMENT WITH THE AUTHOR.

I tried to reach Prof. Shewchuck regarding licensing Triangle, but my attempts were left without answer.

Even Shewchuck's code for robust predicates being "in public domain" is a problem for licensing: public domain is not a software license and arguably is not open source. That's why CDT uses a different BSD-3-Clause licensed implementation.

Triangle needs patching for x64

Original Triangle code does not work properly on x64 and some patching is needed to make it work. For example libigl is using patched Triangle.

Functionality

CDT can definitely be used to replace Triangle for computing constrained Delaunay triangulations (I've done it). However Triangle is a swiss-army knife for triangulations: it can also do conforming Delaunay triangulations and re-meshing via Steiner-point insertion (Ruppert's algorithm) to produce quality meshes for applications like finite-element analysis.
CDT does not do that, but I would really love to implement Ruppert's algorithm in CDT when I get time. It’s a fun thing to do and there was a request for it.

Performance

Lastly Triangle positions itself as being very fast. CDT was definitely designed with performance in mind and we optimized things where we saw potential for it. For example boost's r-tree and flat_set are used to speed things up. But we never benchmarked CDT against Triangle. So Triangle may potentially be faster than CDT. Benchmarking is on my TODO list, but any help or input is appreciated. Maybe when you have libigl adapter for CDT working you could run some numbers? :)

[RotateMe]

Thanks a lot for the quick and extensive reply. The licensing issue, and not being able to contact Prof. Shewchuck was the main point that required us to find an alternative to Triangle, but the other points you mentioned were more reasons to switch to CDT.

Glad to hear that CDT can replace Triangle for constrained Delaunay triangulations, I think all other functions of Triangle can be replaced easier. Although a re-meshing algorithm would be nice, I hope you get around doing that someday.

By now I've created a wrapper library that replaces Triangle in libigl by emulating the header/input-output structure of Triangle, but internally uses CDT. This worked flawlessly for SCAF parameterizations (https://github.com/libigl/libigl/blob/master/tutorial/710_SCAF/main.cpp) and the quality of the output is the same, although performance was a bit worse for large meshes, but that's not a problem in our case. I'll make a minimal github project for the wrapper once I find the time, but I wanted to test the rest of the libigl methods that use Triangle before that and fine-tune some things. Once I'm done I'll report back with a link.

[artem-ogre]

Sounds good. What kind of performance difference was it? Did you use CDT with Boost?

[RotateMe]

Right, I forgot, this was without Boost, and the performance difference was something like 25%-50% slower. I'll try to come back with some more substantial numbers after enabling Boost.