Sliver-free perturbation for the Delaunay tetrahedrization

✍ Scribed by Kokichi Sugihara

• Publisher: Elsevier Science
• Year: 2007
• Tongue: English
• Weight: 419 KB
• Volume: 39
• Category: Article
• ISSN: 0010-4485
• DOI: 10.1016/j.cad.2006.10.002

✦ Synopsis

This paper studies symbolic perturbation schemes in the context of Delaunay meshing in the three-dimensional space. Symbolic perturbation is a general and powerful technique for removing geometric degeneracy. However, a straightforward application of this technique to Delaunay meshing does not work well, because the perturbation generates volume-zero tetrahedra, called slivers, which should not appear in meshes for the finite element method.

First we characterize the set of directions in which a point can be perturbed without generating slivers. Next, as an application of this characterization, we construct a graph-theoretic method for finding a sliver-free perturbation. We also show that an ordinary symbolic perturbation cannot avoid slivers for integer-grid points, and point out that there is a generalized type of perturbation that can avoid slivers completely.