Size-optimal Steiner points for Delaunay-refinement on curved surfaces
Preprint
Abstract
An extension of the restricted Delaunay-refinement algorithm for surface mesh generation is described, where a new point-placement scheme is introduced to improve element quality in the presence of mesh size constraints. Specifically, it is shown that the use of off-centre Steiner points, positioned on the faces of the associated Voronoi diagram, typically leads to significant improvements in the shape- and size-quality of the resulting surface tessellations. The new algorithm can be viewed as a Frontal-Delaunay approach -- a hybridisation of conventional Delaunay-refinement and advancing-front techniques in which new vertices are positioned to satisfy both element size and shape constraints. The performance of the new scheme is investigated experimentally via a series of comparative studies that contrast its performance with that of a typical Delaunay-refinement technique. It is shown that the new method inherits many of the best features of classical Delaunay-refinement and advancing-front type methods, leading to the construction of smooth, high quality surface triangulations with bounded radius-edge ratios and convergence guarantees. Experiments are conducted using a range of complex benchmarks, verifying the robustness and practical performance of the proposed scheme.Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- A frontal Delaunay quad mesh generator using the L ∞ normInternational Journal for Numerical Methods in Engineering, 2013
- Delaunay Refinement for Piecewise Smooth ComplexesDiscrete & Computational Geometry, 2008
- A Practical Delaunay Meshing Algorithm for a Large Class of Domains*2008
- Mesh size functions for implicit geometries and PDE-based gradient limitingEngineering with Computers, 2006
- Approximating the Medial Axis from the Voronoi Diagram with a Convergence GuaranteeAlgorithmica, 2003
- Surface Reconstruction by Voronoi FilteringDiscrete & Computational Geometry, 1999
- NETGEN An advancing front 2D/3D-mesh generator based on abstract rulesComputing and Visualization in Science, 1997
- A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh GenerationJournal of Algorithms, 1995
- An Advancing Front Delaunay Triangulation Algorithm Designed for RobustnessJournal of Computational Physics, 1995
- Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson AlgorithmJournal of Computational Physics, 1993