Delaunay Meshing of Piecewise Smooth Complexes without
Tamal K. Dey, Joshua A. Levine · 2009
Abstract: Recently a Delaunay refinement algorithm has been proposed that can meshpiecewise smooth complexes which include polyhedra, smooth and piecewise smoothsurfaces, and non-manifolds. However, this algorithm employs domain dependent numericalpredicates, some of which could be computationally expensive and hard to implement.In this paper we develop a refinement strategy that eliminates these complicated domaindependent predicates. As a result we obtain a meshing algorithm that is practical andimplementation-friendly.Keywords: Delaunay refinement; mesh generation; piecewise-smooth complexes;non-smoothness; non-manifoldness1. IntroductionDelaunaymeshgenerationofnon-smoothdomainssuchaspiecewisesmoothsurfacesandcomplexesis a difficult challenge. Aided by recent developments in sampling theory and computational topology,Chew’s furthest point strategy [1, 2] (Delaunay refinement) has been applied to generate Delaunaymeshes for smooth surfaces with provable guarantees [3, 4]. The lack of global smoothness posestwo main difficulties in extending these methods to non-smooth domains. First, the sampling theorydeveloped for smooth surfaces breaks down for non-smooth surfaces. Secondly, small input anglespossibly present at non-smooth regions pose problems for the termination of Delaunay refinement [5].