Guaranteed-quality mesh generation for curved surfaces

ABSTRACT

For several commonly-used solution techniques for partial differential equations, the first step is to divide the problem region into simply-shaped elements, creating a mesh. We present a technique for creating high-quality triangular meshes for regions on curved surfaces. This technique is an extension of previous methods we developed for regions in the plane. For both flat and curved surfaces, the resulting meshes are guaranteed to exhibit the following properties: (1) internal and external boundaries are respected, (2) element shapes are guaranteed—all elements are triangles with angles between 30 and 120 degrees (with the exception of badly shaped elements that may be required by the specified boundary), and (3) element density can be controlled, producing small elements in “interesting” areas and large elements elsewhere. An additional contribution of this paper is the development of a practical generalization of Delaunay triangulation to curved surfaces.

REFERENCES

• Rup92: Jim Ruppert, A New and Simple Algorithm for Quality 2-Dimensional Mesh Generation, University of California at Berkeley, Berkeley, CA, 1992
• BE92: M. Bern and D. Eppstein, Mesh Generation and Optimal Triangulation, Computing in Euclidean Geometry, edited by F. K. Hwang and D.-Z. Du, World Scientific, 1992, to appear. Also appears as Tech Report CSL-92-1, Xerox PARC, March 1992.
• BEG90: M. Bern, D. Eppstein, and J. R. Gilbert, Provably Good Mesh Generation, Proceedings o/the 31st IEEE Symposium on the Foundations o/ Computer Science, 231-241, 1990. To appear in JCSS.
• Che89: L. P. Chew, Guaranteed-Quality Triangular Meshes, Department of Computer Science Tech Report TR 89-983, Cornell University, 1989.
• MV92: Scott A. Mitchell , Stephen A. Vavasis, Quality mesh generation in three dimensions, Proceedings of the eighth annual symposium on Computational geometry, p.212-221, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142720]
• MS92: Elefterios A. Melissaratos , Diane L. Souvaine, Coping with inconsistencies: a new approach to produce quality triangulations of polygonal domains with holes, Proceedings of the eighth annual symposium on Computational geometry, p.202-211, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142719]

INDEX TERMS

Primary 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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Theory