carrier image

Aggressive Tetrahedral Mesh Improvement

Klingner, Bryan Matthew and Jonathan Richard Shewchuk

Proceedings, 16th International Meshing Roundtable, Springer-Verlag, pp.3-23, October 14-17 2007


16th International Meshing Roundtable
Seattle, Washington, U.S.A.
October 14-17, 2007

University of California at Berkeley

We present a tetrahedral mesh improvement schedule that usually creates meshes whose worst tetrahedra have a level of quality substantially better than those produced by any previous method for tetrahedral mesh generation or "mesh clean-up." Our goal is to aggressively optimize the worst tetrahedra, with speed a secondary consideration. Mesh optimization methods often get stuck in bad local optima (poor-quality meshes) because their repertoire of mesh transformations is weak. We employ a broader palette of operations than any previous mesh improvement software. Alongside the best traditional topological and smoothing operations, we introduce a topological transformation that inserts a new vertex (sometimes deleting others at the same time). We describe a schedule for applying and composing these operations that rarely gets stuck in a bad optimum. We demonstrate that all three techniques-smoothing, vertex insertion, and traditional transformations-are substantially more effective than any two alone. Our implementation usually improves meshes so that all dihedral angles are between 31 degrees and 149 degrees, or (with a different objective function) between 23 degrees and 136 degrees.

Download Full Paper (PDF Format)

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