Broad Area Colloquium For AI-Geometry-Graphics-Robotics-Vision

Constrained Delaunay Tetrahedralizations and Provably Good Mesh Generation

Jonathan Richard Shewchuk
Department of Electrical Engineering and Computer Science
University of California At Berkeley

Monday, January 13, 2003, 4:15PM
TCSeq 201 (Note the ROOM CHANGE!)


Unstructured meshes of Delaunay or Delaunay-like tetrahedra have many advantages in such applications as rendering and visualization, interpolation, and numerical methods for simulating physical phenomena such as mechanical deformation, heat transfer, and fluid flow. One of the most difficult parts of tetrahedral mesh generation is forcing the mesh to conform to complicated domain boundaries having small angles. Although simple tetrahedralization algorithms are known, they tend to produce poorly-shaped tetrahedra. Recovering domain boundaries while maintaining the Delaunay property is difficult. My solution to this problem combines a theory about the existence of constrained Delaunay tetrahedralizations with an algorithm that carefully chooses new vertices to guarantee existence. The boundary recovery algorithm is ``provably good'' in the sense that the edges of the boundary-conforming mesh are not much shorter than necessary for a good-quality mesh. The boundary recovery step is the first step for a mesh generation algorithm that refines the constrained Delaunay tetrahedralization by inserting additional vertices. These vertices are placed so as to improve the quality of the mesh for interpolation and finite element methods. The refinement algorithm maintains guaranteed bounds on edge lengths, and also offers some guarantees on tetrahedron shapes.

Back to the Colloquium Page