Local optimization-based simplicial mesh untangling and improvement

International Journal for Numerical Methods in Engineering, John Wiley, Vol 49, Num 1, pp.109-125, September 10-20 2000

MESHING
RESEARCH
CORNER

Special Edition on Unstructured Mesh Generation
International Journal for Numerical Methods in Engineering, Vol 49 Number 1-2, 10-20 September 2000

Correspondence to: Lori A. Freitag, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL 60439, U.S.A.
E-mail: freitag@mcs.anl.gov

Abstract
We present an optimization-based approach for mesh untangling that maximizes the minimum area or volume of simplicial elements in a local submesh. These functions are linear with respect to the free vertex position; thus the problem can be formulated as a linear program that is solved by using the computationally inexpensive simplex method. We prove that the function level sets are convex regardless of the position of the free vertex, and hence the local subproblem is guaranteed to converge. Maximizing the minimum area or volume of mesh elements, although well suited for mesh untangling, is not ideal for mesh improvement, and its use often results in poor quality meshes. We therefore combine the mesh untangling technique with optimization-based mesh improvement techniques and expand previous results to show that a commonly used two-dimensional mesh quality criterion can be guaranteed to converge when starting with a valid mesh. Typical results showing the effectiveness of the combined untangling and smoothing techniques are given for both two- and three- dimensional simplicial meshes.