[Question] robust geometric predicates, polygon triangulation

[artem-ogre]

Hello, Emmett (@elalish),

I have recently discovered manifold and spent some time reading the documentation and the blog. I very much enjoyed the read and excited about the library. I hope to get to try it hands on in the nearest future. Thank you!

When reading the part about "Polygon triangulation" I kept asking myself: could the degeneracy problems you are describing be solved by using robust adaptive floating-point geometric predicates? I can imagine how robust predicates can be useful for solving a handful of challenges faced when implementing robust Boolean operations on 3D meshes: not only for re-triangulating intersecting triangles but also for exactly detecting triangle-triangle intersections with all the possible edge cases.

Did you consider such predicates as part of the related work?

Sorry if this question is already answered by you somewhere. I did my best to search for an answer. I searched GitHub documentation, issues, discussions. I also searched in Julian M. Smith's dissertation and found that it only cites Schewchuk's "Lecture notes on geometric robustness" but in the context not directly related to the predicates.

P.S. I was hesitating whether this should be placed in Discussions, I hope it is okay to open this question as an Issue.

P.P.S
There are several ways of doing robust adaptive precision floating-point geometric predicates, but the most cited paper is probably this one.

[elalish]

Thank you! It's certainly a possibility, and one which I have not explored much. The main reason is that exact arithmetic (I'd consider robust geometry predicates to be a form of said) is how most geometry libraries have been made thus far, and I've been underwhelmed by their robustness. I was introduced to computational geometry by Julian Smith's paper, which made me more inclined to look for inexact solutions instead. I also heard anecdotally that exact arithmetic has a serious performance penalty.

The most fundamental reason I think exact geometry will be problematic is that the internal representations are not exact, nor are the input or output representations (all floating-point). This is why I use the concept of ε-valid, where we should gracefully handle input that is not quite geometrically valid as though it is perturbed enough to be valid. I think using exact geometry would make this more difficult.

I don't really feel like writing a third triangulator, but if you want to contribute one and show how it's an improvement in robustness and performance, I'd be happy to review.

[artem-ogre]

@elalish
Thanks for taking your time to reply!

I also heard anecdotally that exact arithmetic has a serious performance penalty.

Yes, in general case this is true, but it's a broad brush: the predicates are designed in a clever way. They are adaptive.
The error is tracked and as long it can not change the sign of the predicate no extended precision is used. Only when necessary the precision is extended and an error estimate is updated. Only when necessary the precision is expanded again to the level where exact outcome is guaranteed for any possible floating point inputs. This means that in the vast majority of the invocations the predicates are almost as fast as the inexact ones with only some overhead for error estimation.

The most fundamental reason I think exact geometry will be problematic is that the internal representations are not exact, nor are the input or output representations (all floating-point).

Right, I see :) Indeed this can be a blocker: constrained Delaunay triangulation with robust predicates can only guarantee correct output for inputs that satisfy two preconditions:

• no duplicate vertices (exact bit-to-bit duplicates): it is possible to work around this by detecting and removing duplicates and remapping the edges
• no intersecting edges: there are no ways to work around this in a way that keeps strong mathematical guarantee of a correct output (except maybe perturbing the inputs until intersections go away)

This is why I use the concept of ε-valid, where we should gracefully handle input that is not quite geometrically valid as though it is perturbed enough to be valid.

I am very interested what mechanism do you use to achieve that. Do you have any pointers, where should I look for more details? Does it provide a guaranteed correct output for the ε-valid input, or are there still some cases when it may break? Does it involve attempts to perturbate the input?

I don't really feel like writing a third triangulator, but if you want to contribute one and show how it's an improvement in robustness and performance, I'd be happy to review.

I am already an author of one 😄 (artem-ogre/CDT)
It has been used as a part of mesh Booleans libraries, but given the points above I'm not sure it is the right tool for the job in this case. Regardless, I would love to know more about the domain, constraints, and possible triangulation inputs in the case of manifold. Can using exact predicates on inexact inputs can bring any value?🤔 It's an interesting topic to puzzle over for sure.

[elalish]

Excellent, I'm happy to meet another who has struggled through making a robust triangulator! As for what mechanism, I take the approach of for each geometric check I make, I test if it's certain (beyond the precision distance that keeps track of my worst-case error), or not. If it's not certain, then I walk the polygon making more checks until I find certainty.

And of course I need to gracefully handle polygons that are certainly invalid as well, so I need to operate in a way that will always create a manifold result, even if it's not a proper CCW triangulation. My first attempt was a sweep line algorithm based on monotone subdivision, but sweep lines are pretty disastrous with inexact input. Now I have an ear clipping routine that is quite robust because it sorts things by certainty, which helps both with robustness and with triangle quality. Of course the hard part is connecting holes to outer contours, but it does quite well.

My current guarantee is the result is definitely manifold (according to the directed edges input) for absolutely all input. Beyond that, I'd say it's best effort - I'm not sure how I'd go about guaranteeing it produces an ε-valid triangulation for all ε-valid polygons. However, I do have a Boolean that conveniently produces an enormous number of very difficult degenerate polygons, and in debug mode it automatically checks every triangulation for validity and creates a test case for any that fail. So, I now have a pretty solid corpus of interesting polygon test cases that you can find here.

[pca006132]

Not sure if I understand this correctly, but it seems that those robust predicates just eliminate errors when checking those predicates, and things like interpolation, matrix multiplication used in union or transformation can still introduce errors. When there is such error, polygons may be self-intersecting and cannot be triangularized even if there is some way to use the robust predicates?

[artem-ogre]

Yes, I understand it the same way. If input data are the truth the predicates give truthful answers about the data. For example, in the case of 3D mesh Booleans: predicates tell exactly what triangles intersect and how (including if it's a touching vertex, overlapping edge, etc.). But as soon as you start constructing new geometry (resolving intersections in the case of mesh Booleans): the constructions are inexact. They are a subject to rounding errors. Often correct answers can't be physically represented with IEEE 754 floats. So when invoking predicates on constructed inputs the answers can't be considered truthful anymore.

side note: CGAL calls it "exact predicates, inexact constructions"