A 2D Advancing-Front Delaunay Mesh Refinement Algorithm

Area of Science:

• Computational Geometry
• Mesh Generation
• Computer-Aided Design

Background:

• Delaunay mesh refinement is crucial for accurate simulations.
• Existing algorithms have limitations on minimum angles and performance with small input angles.
• Chew's first algorithm provides a foundation for Delaunay mesh refinement.

Purpose of the Study:

• To generalize Chew's first algorithm for Delaunay mesh refinement.
• To improve the quality of generated meshes, specifically focusing on minimum angles.
• To handle planar straight line graphs (PSLG) efficiently.

Main Methods:

• Splitting line segments of a PSLG proportionally to local feature size.
• Refining Delaunay triangulations by inserting off-center Steiner vertices.
• Prioritizing triangles with the shortest edges using an advancing front approach.

Main Results:

• Achieved size-optimal, truly or constrained Delaunay meshes with minimum angles < 30° (without small input angles).
• Improved minimum angles compared to prior algorithms (26.4° and 28.6°).
• Reduced the upper bound on the maximum angle to > 120° (improvement from ~137°).

Conclusions:

• The generalized algorithm offers superior mesh quality, particularly regarding minimum angles.
• The method effectively refines meshes for PSLGs, even with small input angles.
• This advancement contributes to more accurate and reliable computational simulations.