Bézier Guarding
Precise Higher-Order Meshing of Curved 2D Domains
Manish Mandad & Marcel Campen
Osnabrück University
Manish Mandad & Marcel Campen
Osnabrück University
We present a novel approach to the problem of meshing curved domains with higher-order triangles.
Quite different from previous work, strict guarantees are provided about the resulting meshes' validity.
The input is an arbitrary set of polynomial curves, whether domain boundary curves, interface curves, or feature curves. Arbitrarily high polynomial order is supported.
We shield off the curves' complexity using envelope triangles. These are elements specifically designed to perfectly conform to the curve while being free of inversions.
By enveloping curves in a piecewise manner where necessary, we can ensure that all envelopes are disjoint. The remainder of the domain is a straight-edge polygon; it can be triangulated with standard linear meshing techniques.
We prove that disjoint envelopes can be constructed for any set of valid input curves, no matter how complex, how close, or how acute the corners. We prove that the constructed mesh elements are injective and conforming in any case.
The algorithm is remarkably robust in the face of numerical imprecisions. Even better: it makes use exclusively of rational arithmetic, thus can be implemented in an exact manner for strict guarantees even in the most complex cases.
The method was tested and verified on various datasets with more than 15,000 test cases in total. Full evaluation statistics, further experiments, and all technical details can be found in the paper (link below).
The following is an interactive web-based demo of the core algorithm.
Click in the first window while holding Shift to add curves (every four consecutive points make one cubic curve).
Afterwards you can modify curves by dragging their control points.
The other windows visualize intermediate stages of the algorithm.
