New Lepp-Algorithms for Quality Polygon and Volume Triangulation: Implementation Issues and Practical Behavior

AMD-Vol. 220 Trends in Unstructured Mesh Generation, ASME, pp.1-8, July 1997

MESHING
RESEARCH
CORNER

Department of Computer Science, University of Chile, Casilia 2777, Santiago, Chile
email: mcrivara@dcc.uchile.cl; mpalma@dcc.uchile.cl

presented at
The 1997 Joint ASME/ASCE/SES Summer Meeting
June 29-July 2, 1997
Northwestern University
Evanston Illinois

Abstract
In this paper we discuss the implementation and practical behavior of new LEPP- algorithms for the automatic construction of good-quality polygon and surface triangulations, which naturally extend to 3dimensions. The algorithms essentially combine two basic techniques: a Backward Longest-Edge (interior) point insertion strategy and a Boundary Treatment technique, which together (in 2-dimensions) guarantee the construction of good- quality triangulations of smallest angles greater than or equal to 30'. The triangulations obtained have in practice an optimal number of points (analogously to the circumcenter point insertion algorithm of Ruppert). Different practical variants of the point insertion strategy are discussed and compared in this paper. We show that, in practice, they tend to produce the best mesh for a maximum number of allowable triangles. These techniques are in turn the basis to design automatic general algorithms to produce good- quality (adapted to the geometry) volume triangulations of general polyhedra including small details. Empirical evidence which shows the successful use of these ideas in 3- dimensions is also included.