Curved optimal delaunay triangulation

Leman Feng, Pierre Alliez, Laurent Busé, Hervé Delingette, Mathieu DesbrunACM Trans. Graphics 2018 · DOI · OpenReview

Overview

This paper introduces Curved Optimal Delaunay Triangulation (CODT), a novel framework that extends traditional Optimal Delaunay Triangulation (ODT) to generate high-order Bézier meshes. By reinterpreting mesh optimization through the lens of physical elasticity (elastostatics), the authors have developed a method to create curved meshes that fit complex geometries with significantly fewer elements and higher numerical accuracy than traditional straight-edged simplices.

The Challenge of Curvilinear Meshing

In computer graphics and engineering simulations, shapes are typically represented using "flat" simplices—triangles in 2D or tetrahedra in 3D. However, real-world objects often possess curved boundaries. Capturing these curves accurately with flat elements requires a massive number of tiny triangles, which drastically increases the computational cost of simulations.

While "high-order" or curvilinear meshes use polynomial curves (such as Bézier patches) to represent complex curves with fewer elements, they are notoriously difficult to generate. These meshes often suffer from "fold-overs" (degenerate Jacobians) and are difficult to snap onto a boundary without distorting the interior elements.

Methodology: A Physics-Based Approach

The researchers’ breakthrough lies in a fundamental reinterpretation of the ODT energy functional. Traditionally viewed as a way to minimize interpolation error, the authors prove that ODT is mathematically equivalent to minimizing the potential energy of a deformation in a physical material.

A high-order Bézier mesh generated using CODT on a complex geometric model, showing the adaptation to surface curvature and element quality mapping.

Key components of the CODT method include:

  • The "Unit" Reference Mesh: The optimization process imagines an ideal "rest state" where every element is a perfect equilateral simplex, striving to keep the final configuration as close to this isotropic ideal as possible.
  • Bézier Simplices: By applying a physics-based energy functional, the method can optimize the control points of Bézier elements of any order (quadratic, cubic, etc.).
  • Isotropic-Stress Boundary Conditions: To prevent mesh shrinkage, a novel boundary treatment applies a "traction" force mimicking internal pressure. This allows vertices to slide freely along the boundary to find optimal positions rather than being strictly pinned.
  • Two-Sided Fitting: A force field simultaneously pulls the mesh toward the true boundary and the boundary toward the mesh, ensuring a tight geometric fit.

Key Results and Performance

The CODT method demonstrates significant improvements in both efficiency and mesh quality over standard linear approaches:

  • Efficiency: Curved meshes achieve the same geometric accuracy (Hausdorff distance) as linear meshes while using orders of magnitude fewer elements. For example, a curved mesh with only 110 vertices can outperform a linear mesh containing thousands.
  • Quality: The method effectively eliminates "slivers" (degenerate, ultra-thin tetrahedra). On a benchmark sphere model, CODT improved the minimum dihedral angle from 17.25° (standard ODT) to 24.75°.
Comparison of mesh quality between standard ODT (NODT) and CODT on a sphere, highlighting the reduction in slivers and improved dihedral angle distribution.
  • Robustness and Speed: The polynomial nature of the energy functional makes optimization more stable than previous non-linear models. Furthermore, by offloading numerical integration (cubature) to the GPU, the authors achieved a 5x speedup, making the generation of large-scale curved meshes practical for real-world applications.

Limitations and Future Work

While CODT represents a significant step forward, several areas remain for future development. Currently, the method only creates isotropic (regular) elements, whereas some simulations require anisotropic (stretched) elements. Additionally, while the optimization pushes patches toward a smooth state, they currently only guarantee $C^0$ continuity (touching at edges) rather than $G^1$ smoothness. Future work will also address explicit self-intersection checks and improved topological handling for very low vertex counts.

Summary updated

Abstract

Meshes with curvilinear elements hold the appealing promise of enhanced geometric flexibility and higher-order numerical accuracy compared to their commonly-used straight-edge counterparts. However, the generation of curved meshes remains a computationally expensive endeavor with current meshing approaches: high-order parametric elements are notoriously difficult to conform to a given boundary geometry, and enforcing a smooth and non-degenerate Jacobian everywhere brings additional numerical difficulties to the meshing of complex domains. In this paper, we propose an extension of Optimal Delaunay Triangulations (ODT) to curved and graded isotropic meshes. By exploiting a continuum mechanics interpretation of ODT instead of the usual approximation theoretical foundations, we formulate a very robust geometry and topology optimization of Bézier meshes based on a new simple functional promoting isotropic and uniform Jacobians throughout the domain. We demonstrate that our resulting curved meshes can adapt to complex domains with high precision even for a small count of elements thanks to the added flexibility afforded by more control points and higher order basis functions.
BibTeX
@article{feng2018curved,
  author = {Leman Feng and Pierre Alliez and Laurent Busé and Hervé Delingette and Mathieu Desbrun},
  title = {{Curved optimal delaunay triangulation}},
  journal = {ACM Trans. Graphics},
  year = {2018},
  doi = {10.1145/3197517.3201358},
}
Figure