Bézier Guarding

Precise Higher-Order Meshing of Curved 2D Domains


Manish Mandad & Marcel Campen
Osnabrück University

Overview

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.

Input

The input is an arbitrary set of polynomial curves, whether domain boundary curves, interface curves, or feature curves. Arbitrarily high polynomial order is supported.

Idea

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.

Approach

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.

Guarantees

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.

Numerics

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.

Results

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

Interactive Demo

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.

Downloads

Manish Mandad, Marcel Campen
Bézier Guarding: Precise Higher-Order Meshing of Curved 2D Domains
SIGGRAPH 2020
ACM Transactions on Graphics 39(4).
Paper

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

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

Contact

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