unity-delaunay VS geogram

I wrote a moderately popular Delaunay/Voronoi library for Unity a few years back [1] with a neat little demo video [2]. I implemented the incremental Bowyer-Watson algorithm for generating the triangulations, and then took the dual to generate the Voronoi tesselation (I also added a "clipper" that clips the voronoi diagram to a convex outline, which was fun, I haven't seen that anywhere else before and had to figure out how to do it myself).

Bowyer-Watson (which is described in this article) seems very simple to implement when you start: just start with a "big triangle" and then add points iteratively to it, and perform the flips you need to do. To do it performant, you have to build up a tree structure as you go, but it's not very tricky.

However: almost every description and implementation of Bowyer-Watson I could find was wrong. There's an incredibly subtle and hard to deal with issue with the algorithm, which is the initial "big triangle". Most people who implement it (and indeed I did the same initally) just make the triangle big enough to contain all the points, but that's enough: it needs to be big enough to contain all the points in all the circumcircles of the triangles. These circumcircles can get ENORMOUS: in the limit of three points on a line, it's an infinite half-plane. Even if they aren't literally collinear, just close, the triangle becomes way to huge to deal with.

The answer is that you have to put the points "at infinity", which is a very weird concept. Basically, you have to have special rules for these points when doing comparisons, it's really tricky and very hard to get right.

If I were doing this again, I wouldn't use Bowyer-Watson, this subtlety is too tricky and hard to get right. Fortune's sweep-line is more complex on the surface, but that's the one I would go with. Or the 3D convex hull technique (which I also wrote a library for, by the way [3]).

[1]: https://github.com/OskarSigvardsson/unity-delaunay

[2]: https://www.youtube.com/watch?v=f3T5jtsokz8

[3]: https://github.com/OskarSigvardsson/unity-quickhull

Fortunately for me, the internet came in clutch with the Oskar Sigvardsson Delaunay Unity Library with the vast majority of the work done for me!

Here's a link for the destruction use i mentioned: https://github.com/OskarSigvardsson/unity-delaunay

Interesting question! By virtue of being a tree, the MST produces at most 3 edges coming out of any vertex, so this should be the same in 3D. The MST then adds (sometimes) a 4th edge, so, although you could build both graphs in 3D space, you would still end up with 4 edges coming out of any vertex, I think.

In 3D space the Delaunay triangulation would produce a bunch of irregular tetrahedra, so the edges coming out from every vertex would vary between a minimum of 3, and a maximum of 12, if I get it right (ref: [1] :-).

The 3D Voronoi cells are another story... I found some implementation that you can play with to see how it looks [2] [3], each cell is of a shape called "convex polytope". It feels like these cells are packed like each of the sub-cubes of a rubik, but I'm not 100% sure :-) ... if that's true, you could jump from each vertex to the next in at most 17 directions? (hand-waves :-p)

--

1: https://en.wikipedia.org/wiki/Tetrahedron#/media/File:M_tic....

2: https://github.com/BrunoLevy/geogram/wiki/Delaunay3D

3: https://math.lbl.gov/voro++/examples/

Geogram, it has some pointsets to surface functionality : https://github.com/BrunoLevy/geogram

Thank you very much for this feedback, it is super useful. Do not hesitate to post this type of comment to geogram's github (https://github.com/BrunoLevy/geogram/issues)

Please note that the Logger mechanism can be redirected to a GUI, it is used for instance in the GUI applications made with Geogram (https://github.com/BrunoLevy/geogram/wiki/Applications) and in Graphite (https://github.com/BrunoLevy/GraphiteThree)

About using std::string as path under Windows, I understand that it may cause some problems with users who use general characters in their directories, but it does not prevent the application from running and from loading/writing files. In the future, when std::filesystem is well standardized, I plan to get read of my FileSystem implementation.