mesh

Mesh generation and optimization

It has been inccoperated into CGAL - one of the most popular software packages for compuational geometry; see 3D Mesh Generation (search odt).

• L. Chen and J. Xu. Optimal Delaunay triangulations. Journal of Computational Mathematics, 22(2):299-308, 2004.

This is the first paper we propose a new concept: optimal Delaunay triangulation (ODT) for the mesh adaptation. Given a convex function, an optimal Delaunay triangulation is a triangulation that minimizes the interpolation error among all triangulations with the same number of vertices, i.e. the distribution of vertices are optimized in order to minimize the interpolation error.

• L. Chen. Mesh smoothing schemes based on optimal Delaunay triangulations. In13th International Meshing Roundtable, pages 109-120, Williamsburg, VA, 2004. Sandia National Laboratories.

We then apply the ODT to the mesh smoothing to improve the mesh quality. The algorithms are developed for any dimensions but the numerical examples are restricted to 2-D. Later on, a French research group improved ODT smoothing scheme and have done the 3-D numerical examples using this approach. See ftp://ftp-sop.inria.fr/geometrica/alliez/vtm.pdf

• L. Chen, P. Sun, and J. Xu. Optimal anisotropic simplicial meshes for minimizing interpolation errors in $L^p$ norm.Mathematics of Computation, 76(257):179-204, 2007.

We present anisotropic interpolation error analysis based on ODT although the concept ODT is not explicitly stated out.

• L. Chen. New analysis of the sphere covering problems and optimal polytope approximation of convex bodies. Journal of Approximation Theory, 133(1):134-145, 2005.

We apply ODT to obtain sharp estimates of some constants in the sphere covering problem and optimal polytope approximation of convex bodies

• L. Chen. On minimizing the linear interpolation error of convex quadratic functions and the optimal simplex.East Journal on Approximations, 14(3), 271--284, 2008.

We explicitly write out some constants which are important in the approximation theory.

• L. Chen and M.J. Holst. Efficient Mesh Optimization Schemes based on Optimal Delaunay Triangulations. Computer Methods in Applied Mechanics and Engineering 200, 967–984, 2011.

We develop a new global mesh optimization scheme to construct ODT. Numerical experiments indicate our method produce a well shaped triangulation in a fast way.

Recently ODT is used quite often to generate shape regular tetrahedral meshes in three dimensions. It has been inccoperated into CGAL - one of the most popular software packages for compuational geometry; see 3D Mesh Generation (search odt).

The following papers on ACM SIGGRAPH (SIGGRAPH is widely considered the most prestigious forum for the publication of computer graphics research).

• Alliez, Pierre and Cohen-Steiner, David and Yvinec, Mariette and Desbrun, Mathieu. Variational tetrahedral meshing. ACM Transactions on Graphics . 24(3):617--625, 2005.

...our results indicate that in practice, our minimization
procedure generates well-shaped tets inside the domain, with better
radius ratio distribution curves than any of the tet meshes we came
across.

• Tournois, Jane and Wormser, Camille and Alliez, Pierre and Desbrun, Mathieu. Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation. ACM Transactions on Graphics . 28(3):1--9, 2009.

Among the large body of work in mesh opti mization, the
Optimal Delaunay Triangulation approach (ODT for short) stands out, as
it casts both geometric and topological mesh improvement as a single,
unified functional optimization [Chen and Xu 2004; Chen 2004] that
tries to minimize in R4 the volume between a paraboloid and the
linear interpolation of the mesh vertices lifted onto the paraboloid.

• Leman Feng, Pierre Alliez, Laurent Buse, Herve Delingette, and Mathieu Desbrun. Curved Optimal Delaunay Triangulation.ACM Transactions on Graphics 37, no. 4 (July 30, 2018): 1--16. https://doi.org/10.1145/3197517.3201358.

Most notably, the concept of Optimal Delaunay Triangulations
(ODT) [Chen 2004; Chen and Xu 2004] anchored in functional
approximation has garnered attention ... Today, the isotropic meshes
obtained via ODT optimization consistently outperform other approaches
(based on advancing front, bubble packing, etc) in terms of element
quality (dihedral angles, aspect ratio, etc) for a given vertex
budget.

Other important references on ODT include:

• Z. Gao, Z. Yu, and M. Holst. Quality Tetrahedral Mesh Smoothing via Boundary-Optimized Delaunay Triangulation. Computer Aided Geometric Design 29(9), 707–21, 2012.
• Z. Chen, W. Wang, B.L. Evy, and F. Sun. Revisiting Optimal Delaunay Triangulation for 3D Graded Mesh Generation. SIAM J. Sci. Comput., 36(3), 930–954, 2014.