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

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.