Spacing Control and Sliver-free Delaunay Mesh

Proceedings, 9th International Meshing Roundtable, Sandia National Laboratories, pp.295-306, October 2000

MESHING
RESEARCH
CORNER

Xiang-Yang Li
Department of Computer Science
University of Illinois at Urbana-Champaign
Email: xli2@cs.uiuc.edu

Abstract
We are often required to generate a Delaunay mesh whose element size is within a constant factor of a control spacing function, i.e., well-conformed, in addition to the fact that each mesh element has small aspect ratio, i.e., well-shaped. However, generating well-shaped Delaunay meshes is an open problem for a long time. Observe that slivers have small radius-edge ratio thus the Delaunay triangulation of well-spaced point set can not guarantee a sliver-free mesh.

In this paper, we present a refinement-based method that, given a PLC domain with no acute input angles, guarantees to generate a well-shaped and well-conformed Delaunay mesh. Specifically, for any tetrahedron T generated by this algorithm, its radius-edge ratio is at most a small constant p > 2, which can be given as an input parameter. Moreover, we show that there is a constant o > 0 depending on p such that V/L^3 &ge o, where V is the volume of T and L is the shortest edge length of T. Thus, the algorithm generates a well-shaped Delaunay mesh: the aspect ratio of each tetrahedron is at most a constant depending on p. The size of each tetrahedron element is also within a small constant factor of the qiven control spacinq.

Download Full Paper (Postscript Format)