Premium
Local optimization‐based simplicial mesh untangling and improvement
Author(s) -
Freitag Lori A.,
Plassmann Paul
Publication year - 2000
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/1097-0207(20000910/20)49:1/2<109::aid-nme925>3.0.co;2-u
Subject(s) - polygon mesh , laplacian smoothing , t vertices , mathematical optimization , vertex (graph theory) , simplex , smoothing , computer science , regular polygon , position (finance) , mathematics , linear programming , mesh generation , graph , combinatorics , theoretical computer science , finite element method , engineering , geometry , computer graphics (images) , structural engineering , finance , economics , computer vision
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. Copyright © 2000 John Wiley & Sons, Ltd.