delaunay meshing of piecewise smooth complexes without expensive predicates德劳内啮合的分段光滑复合体没有昂贵的谓词.pdfVIP

Algorithms 2009, 2, 1327 - 1349; doi:10.3390/a2041327 OPEN ACCESS algorithms ISSN 1999-4893 /journal/algorithms Article Delaunay Meshing of Piecewise Smooth Complexes without Expensive Predicates Tamal K. Dey ⋆ and Joshua A. Levine Department of Computer Science and Engineering, The Ohio State University, DL395, Columbus, OH, USA; E-Mail: levinej@ ⋆ Author to whom correspondence should be addressed: E-Mail: tamaldey@; Tel.: +1-614-292-3563; Fax: +1-614-292-2911. Received: 25 September 2009; in revised form: 17 October 2009 / Accepted: 19 October 2009 / Published: 11 November 2009 Abstract: Recently a Delaunay refinement algorithm has been proposed that can mesh piecewise smooth complexes which include polyhedra, smooth and piecewise smooth surfaces, and non-manifolds. However, this algorithm employs domain dependent numerical predicates, some of which could be computationally expensive and hard to implement. In this paper we develop a refinement strategy that eliminates these complicated domain dependent predicates. As a result we obtain a meshing algorithm that is practical and implementation-friendly. Keywords: Delaunay refinement; mesh generation; piecewise-smooth complexes; non-smoothness; non-manifoldness 1. Introduction Delaunay mesh generation of non-smooth domains such as piecewise smooth surfaces and complexes is a difficult challenge. Aided by recent developments in sampling theory and computational topology, Chew’s furthest point strategy [1, 2]