Implementing Watson's algorithm in three dimensions

ABSTRACT

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.

REFERENCES

• 1: Boyse, J. W. and Gilchrist, J. E., GMSOLID~ interactive modeling for hull algorithms, BYTE 24, (1984) 2-13.
• 2: Cavendish, J. C., Field, D. A. and Frey, W. B., An approach to automatic threedimensional finite element mesh generation, International Journal for Numerical Methods in Engineering 21, (1985) 329-347.
• 3: Field, D. A. and Frey, W. H., Automation of tetrahedral mesh generation, General Motors Research Laboratories, Warren, MI, GMR-4967.
• 4: Krouse, J. K, Industry gets serious about solid modeling, Computer Aided Engineering (Nov./Dec. 1982) 22-26.
• 5: Rodgers, C. A, Packing and Covering, Cambridge Mathematical Tracts, No. 54, Cambridge University Press, Cambridge, England.
• 6: Watson, D. F, Computing the n-dimensional Delaunay tesselation with applications to Voronoi polytopes, The Computer Journal 24, 2, (1981) 167-172.
• 7: Zienkeiwicz, O. C, The Finite Element Method, McGraw-Hill, New York, 3rd Edition, 1977.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Theory, Verification