(Course icon, at left, is courtesy of Nina Amenta.)

CS 294-5
Meshing and Triangulation in Graphics, Engineering, and Modeling

Jonathan Shewchuk

Autumn 1999
Tuesdays and Thursdays, 2:00-3:30pm
606 Soda Hall

Some lecture transparencies (1, 4, 11, 12, 13) are on line. To read them, click on a lecture in the list below.

Student presentation requirement: Every student (including auditors) is asked to present a paper from this list of notable meshing publications. Please choose a presentation date by September 28. Please choose a paper at least a week before your presentation date.

The best related sites:

Resources for dealing with robustness problems in your projects (in increasing order of difficulty):


Lecture 1 (August 23): Nonoptimal triangulations of point sets and polygons. Lecture 2 (August 25): The goals of mesh generation. Two-dimensional Delaunay triangulations. Lecture 3 (August 31): Two-dimensional Delaunay triangulations (continued). The Voronoi diagram. Constrained Delaunay triangulations. Lecture 4 (September 2): Higher-dimensional Delaunay triangulations. Sizes of triangulations (in any dimension). Lecture 5 (September 7): Higher-dimensional constrained Delaunay triangulations. Conforming tetrahedralizations. Lecture 6 (September 9): The incremental insertion algorithm for constructing a Delaunay triangulation. Lecture 7 (September 14): The gift-wrapping algorithm for constructing Delaunay triangulations and constrained Delaunay triangulations in any dimension. Divide-and-conquer algorithms for constructing two-dimensional Delaunay triangulations and constrained Delaunay triangulations. High-level summary of Fortune's sweepline algorithm. Lecture 8 (September 16): Introduction to mesh generation techniques. Two-dimensional Delaunay refinement. Lecture 9 (September 21): Chew's first Delaunay refinement algorithm. Ruppert's Delaunay refinement algorithm. Lecture 10 (September 23): Ruppert's Delaunay refinement algorithm (continued). Negative result on quality triangulations of PSLGs that have small angles. Practical handling of small angles. Lecture 11 (September 28): Advancing front algorithms for mesh generation. Lecture 12 (September 30): Quadtree- and octree-based algorithms for mesh generation. Lecture 13 (October 5): Geometric robustness. Mesh improvement through smoothing and topological transformations. Lecture 14 (October 7): Andy Neureuther on surface simplification. Jason Riedy on the Whisker Weaving algorithm for hexahedral mesh generation. No lecture on October 12. But you're welcome to take Amtrak to South Lake Tahoe and join me at the Eighth International Meshing Roundtable.

Lecture 15 (October 14): Surface mesh simplification. Topology-preserving edge contraction.

Lecture 16 (October 19): Curve and surface reconstruction. Lecture 17 (October 21): Borlin Shyu on the Geode algorithm for hexahedral mesh generation. Jae Kim on dynamic point location in Delaunay triangulations. Lecture 18 (October 26): The paving algorithm for quadrilateral mesh generation. Lecture 19 (October 28): Mesh refinement and coarsening. Lecture 20 (November 2): Jordan Smith on Voronoi diagrams of polygons. Dan Simkins on advancing front quadrilateral meshing. Lecture 21 (November 4): Ganping Sun on anisotropic bubble meshing. Michael Downes on progressive simplicial complexes. Lecture 22 (November 9): Okan Arikan on approximating height fields. Tolga Goktekin on view-dependent progressive meshes. Lecture 23 (November 11): Maryann Simmons on comparing algorithms for two-dimensional Delaunay triangulation. François Labelle on parallel two-dimensional Delaunay triangulation. Lecture 24 (November 16): Jane Wang on reconstructing planar cross sections. Steve Chien on hexahedral mesh generation by sweeping. Lecture 25 (November 18): Chris Tchou on surface reconstruction. Yan Zhuang on constructing generalized Voronoi diagrams. Lecture 26 (November 23): Tzi-cker Chiueh on compressing triangular surface meshes. Minimum weight triangulations. No lecture on November 25 or on November 30.

Lecture 27 (December 2): Three-dimensional Delaunay refinement.

Course Description

Applications in scientific computing, physical modeling, graphics, and geographical information systems use unstructured meshes composed of triangles, quadrilaterals, tetrahedra, hexahedra, and other simple geometric shapes. This course covers techniques for generating and modifying triangulations and other meshes. The material should be useful for students in engineering and the sciences, as well as computer science.

Topics include:

Students should have a thorough familiarity with fundamental data structures (CS 61B or the equivalent).


Supported in part by the National Science Foundation under Awards ACI-9875170, CMS-9980063, and EIA-9802069, and in part by a gift from the Okawa Foundation. The views and conclusions in this document are those of the author. They are not endorsed by, and do not necessarily reflect the position or policies of, the Okawa Foundation or the U. S. Government.
(Man and Woman. Fernand Léger, 1881-1955.)