**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.

- Beyond what is described in the paper, in case the curves are intersecting, the implementation
*attempts*to resolve this by splitting the curves. *Note:*Due to tight memory limitations in this web-based setting (using WebAssembly), the demo may simply hang at some point.

Thanks to Hendrik Brückler for implementation support.

Bézier Guarding: Precise Higher-Order Meshing of Curved 2D Domains

SIGGRAPH 2020

ACM Transactions on Graphics 39(4).

Paper

Code

Dataset

Prof. Dr. Marcel Campen

Universität Osnabrück

Institut für Informatik

Wachsbleiche 27

D-49090 Osnabrück

Raum: 50 / 518

Tel: +49 541 969 3524

E-Mail: campen@uos.de

Universität Osnabrück

Institut für Informatik

Wachsbleiche 27

D-49090 Osnabrück

Raum: 50 / 518

Tel: +49 541 969 3524

E-Mail: campen@uos.de