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!)
http://robotics.stanford.edu/ba-colloquium/
Abstract
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.
Contact: bac-coordinators@cs.stanford.edu
Back to the Colloquium Page