Approximate Quality Mesh Generation Based on Small Edge Details

Proceedings, 9th International Meshing Roundtable, Sandia National Laboratories, pp.411-421, October 2000

MESHING
RESEARCH
CORNER

Bruce Simpson
Department of Computer Science, University of Waterloo, Ontario, Canada
Email: rbsimpson@uwaterloo.ca
Nancy Hitschfeld
Integrated Systems Laboratoty ETH-Zürich
Email: nancy@iis.ee.ethz.ch
Maria-Cecilia Rivara
Department of Computer Science, University of Chile
Email: mcrivara@dcc.uchile.cl

Abstract
We present two techniques for simplifying the list processing required by methods for quality mesh generation based on iterative bad triangle improvement over Delaunay meshes which use the standard basic components of insertion point selection and Delaunay insertion. The simplification involves compromising the shape quality requirement that the mesh triangles have angles all exceeding a global minimum angle tolerance. We refer to such methods as carrying out approximate quality mesh generation. These approximate methods are simpler to implement, more efficient to execute and have robust termination conditions. They are intended for geometry-based preconditioning of coarse initial meshes for subsequent refinement to meet data representation needs.

The more general technique is an algorithm reorganization to avoid maintaining a global list of triangles to be refined. The reorganization uses a recursive strategy based on: (1) the identification of the small edges in the input PSLG (planar straight line graph) describing the geometry; and (2) a recursive triangle improvement procedure around these small edges. ‘ftuncating the recursion depth results in an approximate method.

The second technique is an extension of the first which uses specific properties of the terminal-edge LEPP-Delaunay refinement method to further simplify the refinement algorithm. These properties are established in the paper. Comparisons of approximate to full quality meshes axe provided.

Download Full Paper (Postscript Format)