×

Revisiting optimal Delaunay triangulation for 3D graded mesh generation. (English) Zbl 1298.49049

Summary: This paper proposes a new algorithm to generate a graded three-dimensional tetrahedral mesh. It revisits the class of methods based on Optimal Delaunay Triangulation (ODT) and proposes a proper way of injecting a background density function into the objective function minimized by ODT. This continuous/analytic point of view leads to an objective function that is continuous and Delaunay consistent, in contrast with the discrete/geometrical point of view developed in previous works. To optimize the objective function, this paper proposes a hybrid algorithm that combines a local search (quasi-Newton) with a global optimization method (simulated annealing). The benefits of the method are both improved performances and an improved quality of the result in terms of dihedral angles. This results from the combination of two effects. First, the local search has a faster speed of convergence than previous work due to the better behavior of the objective function, and second, the algorithm avoids getting stuck in a poor local minimum. Experimental results are evaluated and compared using standard metrics.

MSC:

49M30 Other numerical methods in calculus of variations (MSC2010)
49M15 Newton-type methods
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
90C26 Nonconvex programming, global optimization
90C53 Methods of quasi-Newton type

Software:

TetGen; adsimp; GHS3D
PDFBibTeX XMLCite
Full Text: DOI