Off-centre Steiner points for Delaunay-refinement on curved surfaces. (March 2016)

• Record Type: Journal Article
• Authors: Engwirda, Darren; Ivers, David
• Is Part Of: Computer aided design. Volume 72(2016)
• Page Start: 157
• Page End: 171
• Publication Date: 2016-03
• Subjects: Surface mesh generation -- Delaunay-refinement -- Advancing-front -- Frontal-Delaunay -- Off-centre Steiner points -- Element quality; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2015.10.007
• Languages: English
• ISSNs: 0010-4485

Abstract

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. Highlights: Development of a new unstructured triangulation algorithm for smooth surfaces. Hybridisation of existing Delaunay-refinement and advancing-front techniques. Combines desirable aspects of both methods: high element quality, robustness. Provably good behaviour: guaranteed termination, bounded element quality.