A 3D Advancing-Front Delaunay Mesh Refinement Algorithm
share
I present a 3D advancing-front mesh refinement algorithm that generates a constrained Delaunay mesh for any piecewise linear complex (PLC) and extend this algorithm to produce truly Delaunay meshes for any PLC. First, as in my recently published 2D algorithm, I split the input line segments such that the length of the subsegments is asymptotically proportional to the local feature size (LFS). For each facet, I refine the mesh such that the edge lengths and the radius of the circumcircle of every triangular element are asymptotically proportional to the LFS. Finally, I refine the volume mesh to produce a constrained Delaunay mesh whose tetrahedral elements are well graded and have a radius-edge ratio less than some ω^* > 2/√(3) (except “near” small input angles). I extend this algorithm to generate truly Delaunay meshes by ensuring that every triangular element on a facet satisfies Gabriel's condition, i.e., its diametral sphere is empty. On an “apex” vertex where multiple facets intersect, Gabriel's condition is satisfied by a modified split-on-a-sphere (SOS) technique. On a line where multiple facets intersect, Gabriel's condition is satisfied by mirroring meshes near the line of intersection. The SOS technique ensures that the triangles on a facet near the apex vertex have angles that are proportional to the angular feature size (AFS), a term I define in the paper. All tetrahedra (except “near” small input angles) are well graded and have a radius-edge ratio less than ω^* > √(2) for a truly Delaunay mesh. The upper bounds for the radius-edge ratio are an improvement by a factor of √(2) over current state-of-the-art algorithms.
READ FULL TEXT