Local Optimization-Based Untangling Algorithms for Quadrilateral Meshes

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