Delaunay meshing of implicit domains with boundary edge sharpening and sliver elimination

A.I. Belokrys-Fedotov, V.A. Garanzha and L.N. Kudryavtseva

Mathematics and Computers in Simulation (MATCOM), 2018, vol. 147, issue C, 2-26

Abstract: In 2004 Strang and Persson suggested the Delaunay mesh generation algorithm in implicit domains with smooth boundary based on the self-organization of elastic network, where each Delaunay edge is treated as a strut. Implicit domains in the algorithm are defined by the signed distance functions. Repulsive forces were suggested which allow to distribute mesh vertices according to prescribed size function. The Delaunay property is restored after each elastic relaxation step. This algorithm was generalized in Garanzha, Kudryavtseva, 2012 for the case of domains defined as zero levels of piecewise-smooth functions using edge sharpener suggested by Belyaev, Ohtake, 2002. In this paper we present variational version of self-organization algorithm. Suggested elastic potential is combination of repulsion potential and sharpening potential which acts on boundary edges and serves to minimize deviation of cell boundary normals from direction of gradient of implicit function which allows to approximate sharp edges on the boundary as polylines made from mesh edges without their predefinition. Numerical experiments demonstrated that Belyaev–Ohtake edge sharpener based on alignment of boundary cell normals becomes unstable when implicit function strongly deviates from the signed distance function. Stable version of sharpener is suggested and verified by numerical tests. When surface near sharp edge is highly curved sharpener based on alignment of normals fails to place vertices precisely on the sharp edge. To this end we apply special sharp edge attraction procedure. While theoretical foundations are not available numerical evidence shows that Delaunay meshes can be constructed for domains with very acute and curved sharp boundary edges. As soon as domain boundary is recovered cell shape deformation terms are added to the elastic potential and subsequent iterations allow to eliminate slivers without deterioration of approximation of sharp edges.

Keywords: Delaunay meshing; Elastic network; Edge sharpening; Variational method; Surface reconstruction (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378475417302781
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matcom:v:147:y:2018:i:c:p:2-26

DOI: 10.1016/j.matcom.2017.07.007

Access Statistics for this article

Mathematics and Computers in Simulation (MATCOM) is currently edited by Robert Beauwens

More articles in Mathematics and Computers in Simulation (MATCOM) from Elsevier
Bibliographic data for series maintained by Catherine Liu ().