Local Optimization-based Simplicial Mesh Untangling and Improvement

2nd Symposium on Trends in Unstructured Mesh Generation, University of Colorado, Boulder, August 1999

MESHING
RESEARCH
CORNER

Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL 60439
freitag@mcs.anl.gov

Abstract

We describe a local optimization-based approach for both removing invalid or inverted elements from a simplicial mesh and for subsequently improving those elements. In this method, the position of an individual vertex is adjusted to obtain improvement in a neighborhood around that vertex. Some number of sweeps over the adjustable vertices are performed to achieve overall improvement in the mesh. This approach has been used to improve the elements of a local submesh, e.g. [1], and in this talk we focus on the modifications necessary for mesh untangling.

The general operation for the optimization-based approach to mesh untangling is given by

where x_new is the proposed new position of v, |V| is the number of adjacent vertices, and conn(V) is the adjacent vertex connectivity information. Ideally, x_new will either untangle the local submesh, or improve the local submesh in such a way that it can be untangled in a succeeding sweep through the mesh. The action of the operator Untangle can take a variety of forms ranging from heuristic procedures such as Laplacian smoothing to optimization techniques that directly improve mesh quality as measured by a particular metric such as minimum angle in the mesh.

We show that the quality metrics commonly used for mesh improvement are not suitable for mesh untangling because they cannot be guaranteed to converge for an invalid mesh. Instead we use a formulation based on minimum element area (volume in 3D) which is not ideal for mesh improvement but is suitable for mesh untangling. Because this function is linear in x_new, we formulate the untangling problem as a linear program which is solved using the simplex method. We give the conditions for which this technique can be guaranteed to converge, and show cases for which this technique succeeds when heuristic approaches, such as Laplacian smoothing, fail.

We present typical results in both two and three dimensions that show the effectiveness of this approach for mesh untangling. We show that increasing the amount of overlap a tangled element has with neighboring elements significantly increases the number of untangling passes required to create a valid mesh. In contrast, increasing the number of inverted elements has no effect on the number of sweeps required to untangle the mesh.

[1] Lori Freitag and Carl Ollivier-Gooch. Tetrahedral mesh improvement using swapping and smoothing. International Journal of Numerical Methods in Engineering, 40, 1997.