carrier image

Local Optimization-Based Untangling Algorithms for Quadrilateral Meshes

Freitag, Lori A. and Paul E. Plassmann

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


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

Paul E. Plassmann
Department of Computer Science and Engineering
The Pennsylvania State University,
University Park, PA 16802

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)

Contact author(s) or publisher for availability and copyright information on above referenced article