Implementing Watson's algorithm in three dimensions

Computer generated solid models must be decomposed into finite element meshes for analysis by the Finite Element Method. To enable decompositions of complex solid models, tetrahedra are employed and to avoid badly skewed tetrahedra for finite element analysis, a Delaunay triangulation is created by Watson's Algorithm [6]. Certain two-dimensional properties of Delaunay triangulations do not extend to the three-dimensional implementation of Watson's Algorithm. Furthermore, serious numerical difficulties can occur due to the nonrandomness of triangulation points, Nonrandomness imposed by the geometry can be ameliorated by using tetrahedral decompositions of icosahedra to fill space. A measure of the quality of tetrahedra is proposed and used to identify undesirable tetrahedra created due to point distributions and geometric constraints of solid models. Postprocessing Delaunay triangulations to rectify undesirable tetrahedra is briefly discussed.