Local Optimization-Based Untangling Algorithms for Quadrilateral Meshes

Proceedings, 10th International Meshing Roundtable, Sandia National Laboratories, pp.397-406, October 7-10 2001

IMR
PROCEEDINGS

10th International Meshing Roundtable
Newport Beach, California, U.S.A.
October 7-10, 2001

Lori A. Freitag
Mathematics and Computer Science Division
Argonne National Laboratory,
Argonne, IL 60439
Email: freitag@mcs.anl.gov

Paul E. Plassmann
Department of Computer Science and Engineering
The Pennsylvania State University,
University Park, PA 16802
Email: plassman@cse.psu.edu

Abstract
The generation of a valid computational mesh is an essential step in the solution of many complex scientific and engineering applications. In this paper we present a new, robust algorithm, and several variants, for untangling invalid quadrilateral meshes. The primary computational aspect of the algorithm is the solution of a sequence of local linear programs, one for each interior mesh vertex. We show that the optimal solution to these local subproblems can be guaranteed and found efficiently. We present experimental results showing the effectiveness of this approach for problems where invalid, or negative area, elements can arise near highly concave domain boundaries.

Download Full Paper (Postscript Format)