CONSTRUCTION OF 3-DIMENSIONAL IMPROVED-QUALITY TRIANGULATIONS USING LOCAL TRANSFORMATIONS

Three-dimensional Delaunay triangulations are the most common form of three-dimensional triangulations known, but they are not very suitable for tetrahedral finite element meshes because they tend to contain poorly shaped sliver tetrahedra. In this paper, we present an algorithm for constructing improved-quality triangulations with respect to a tetrahedron shape measure. This algorithm uses combinations of two or more local transformations to improve a given triangulation toward an optimal triangulation. Experimental results on finite element meshes show that this algorithm is much more effective than previous methods at removing slivers from Delaunay triangulations and producing nearly optimal triangulations. A variation of this algorithm for improving a pseudo locally optimal non-Delaunay triangulation toward a Delaunay triangulation is also presented.