Precise Higher-Order Meshing of Curved 2D Domains
Manish Mandad & Marcel Campen
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).
Manish Mandad, Marcel Campen
Implementation of the mesh generation algorithm described in the paper. Does not include the mesh optimization post-process. Includes the floating point and the exact version.
Randomly generated A, B, C, D datasets, each containing 1000 test cases (domains formed by cubic Bézier curves), used in the paper for purposes of evaluation and demonstration.