Triangulation Algorithms 2D / 3D

[glennDittmann]

Hi, I was wondering which triangulation algorithms are implemented in geogram.

For my thesis I have implemened both Bowyer & Watsons original idea (this), as well as the randomized incremental algorithm based on flips by Edelsbrunner and Shah (this).

Which algos are implemented for:
GEO::Delauany{2d, 3d} and GEO::ParallelDelauany3d?

Is it one of the two above ? And I guess the parallel version is yet another version. There I would also be curious, which one it is.

[BrunoLevy]

Hi,
The basic algorithm is Bowyer-Watson (as most in of other efficient codes for Delaunay triangulation, such as CGAL, tetgen and others), plus a set of additional techniques to make it faster, more or less the same ones as in CGAL:

• Nina Amenta and Marshall Bern's BRIO: spatially sorting the vertices in a multires manner makes the algorithm spectacularly faster
• structural filtering (locate with inexact predicates then refine with exact predicates)
• randomized line walk (Devillers et.al)

The complete list of references is cited in the source, here and the
corresponding .bib file is here.

You can also run any geogram program with biblio=true command line argument, then it will output a LaTeX report of what was used.

In addition, ParallelDelaunay3d and PeriodicDelaunay3d are multithreaded. They work in an optimistic commit/rollback mode: points are inserted, and the new tetrahedra are committed or rolled back if a conflict between different threads was detected.

The 2D version Delaunay2d is a bit less optimized, and not parallel.

The 2D constrained version CDT2d is based on Sloane's algorithm (triangle flipping). It is slower than cavity remeshing (a-la Bowyer-Watson, there exists a constrained version), but it is much easier to implement. It remains super difficult to implement (made me suffer like hell !), so I wanted to keep one difficulty at a time.

[glennDittmann]

Thanks for the super quick and detailed answer !

Good to know! I thought Bowyer-Watson was a little bit slower compared to the flipping algorithm regarding theoretical runtime.
Is that true or does that simply not matter in the "real world"?

Thanks for the improvement tips, I was already looking at BRIO, as I have seen it in geograms docs. So that has highest prio.

Which of the other two would have more impact: structural filtering VS randomized walk?

And thanks for the details on the parallel and constrained versions! :D Luckily, I do not need to touch these areas (for now), but I can empathize with the geometrical algo implementation pain. :')

[BrunoLevy]

• The most impactful optimization is (by far) BRIO, without it, a locate() operation traverses in average $N^{1/3}$ triangles, with it it reduces to a handful of triangles. As a first step, you can implement spatial sorting.
• Then, Bowyer-Watson is significantly faster than Sloan (flipping), because it results in a smaller number of evaluations of the in_sphere / in_circle predicate, which is the second hot spot after locate()
• Finally, structural filtering and randomized walk will only gain a few percent (or around 10 percent if I remember well).

[glennDittmann]

Thank you very much for your valuable, experienced insights! All is clear.

Just for the 2. point, I actually meant the non-constrained algorithms:
Bowyer-Watson ~= Edelsbrunner-Shah regarding the runtime, I assume then?

[BrunoLevy]

About the comparision between Bowyer/Watson and Edelsbrunner/Shah, I don't know (I have never implemented Edelsbrunner/Shah). Maybe there are some complexity analyses in the articles that can give a hint.
Intuitively, I think the Bower/Watson is very good, because it traverses the triangles to be deleted only once, so I have the intuition that a triangle-flipping algorithm cannot do better than that (but I may be wrong). You may ask in computational geometry forums, or in the CGAL mailing list, there are excellent experts there !

[glennDittmann]

Thank you! That are good starting points to investigate further.