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

CS 294-1
Mesh Generation and Geometry Processing in Graphics, Engineering, and Modeling

Jonathan Shewchuk

Spring 2008
Mondays and Wednesday, 5:30-7:00 pm
320 Soda Hall


This class is for computer graphics students who use triangle meshes, engineers and scientists who want to generate unstructured meshes for the finite element method or for manufacturing, and students of GIS (geographical information systems) who work with TINs (triangulated irregular networks). It will be accessible to students in engineering and the sciences, as well as in computer science.

The only prerequisite is a thorough familiarity with fundamental data structures (CS 61B or the equivalent).

Topics include:

Paper presentation requirement

Every student (including auditors) is asked to give a presentation, 25 to 40 minutes long, of a paper from this list of notable meshing publications or of your own choosing. Please choose a presentation date by February 27. Please choose a paper at least two weeks before your presentation date, and give me a practice presentation at least one week in advance. Also see my advice on Giving an Academic Talk.


Lecture 1 (January 23): Marching cubes and variants (marching triangles, squares, tetrahedra). Lecture 2 (January 28): Dual contouring—including an introduction to quadtrees, octrees, and constructive solid geometry (CSG) operations with isosurfaces. Lecture 3 (January 30): Definitions: simplicial complexes; manifolds; triangulations of point sets, polygons, and planar straight-line graphs. Lecture 4 (February 4): Delaunay triangulations in the plane. Edge flips and the flip algorithm. Existence, uniqueness, and optimality of the Delaunay triangulation. Lazy triangulations. Note: this lecture is almost identical to the lecture in my computational geometry class (CS 274).

Edge flip cookie courtesy of Bryan Klingner

Lecture 5 (February 6): The incremental insertion algorithm for constructing a Delaunay triangulation. Point location methods: walking, conflict graphs, bucketing. Biased randomized insertion orders.

Lecture 6 (February 11): Higher-dimensional Delaunay triangulations. Sizes of triangulations. The gift-wrapping algorithm for constructing Delaunay triangulations. Lecture 7 (February 13): Data structures for two- and three-dimensional triangulations. February 18 is Presidents' Day.

Lecture 8 (February 20): Constrained Delaunay triangulations. Comparison of Delaunay triangulation algorithms. Geometric predicates and geometric robustness.

Lecture 9 (February 25): The goals of mesh generation. Introduction to finite element mesh generation techniques. Chew's first Delaunay refinement algorithm for triangular mesh generation. Lecture 10 (February 27): Ruppert's Delaunay refinement algorithm for triangular mesh generation. Lecture 11 (March 3): Advancing front methods for triangular and tetrahedral mesh generation. Lecture 12 (March 5): Isosurface stuffing—grid-based tetrahedral mesh generation for isosurfaces. Lecture 13 (March 10): Optimal triangulation of polygons. Its application to edge removal in tetrahedral meshes. Optimal triangulation of point sets by edge insertion. Lecture 14 (March 12): Mesh improvement through smoothing and topological transformations. Lecture 15 (March 17): Curve reconstruction by the NN-Crust algorithm. The medial axis, ε-samples, and local feature size. Lecture 16 (March 19): Surface reconstruction by the Cocone and Wrap algorithms. Restricted Delaunay triangulations. March 24-28 is Spring Recess.

Lecture 17 (March 31): Surface mesh editing. Laplacian coordinates. Rotation-invariant mesh representation.

Lecture 18 (April 2): The paving algorithm—advancing front quadrilateral mesh generation.

Lecture 19 (April 7): Student presentations: Jessica Schoen on provably good anisotropic Voronoi diagrams. Nuttapong Chentanez on variational tetrahedral meshing. Mini-lecture on polygon triangulation by finding diagonals.

Lecture 20 (April 9): Student presentation: Ilya Landa on generating building facade meshes by driving a truck with lasers around Berkeley. Surface mesh simplification. Lecture 21 (April 14): Element-nested refinement of triangular and tetrahedral meshes. Coarsening of triangular meshes. Lecture 22 (April 16): Student presentations: Jimmy Andrews on dual marching cubes. Darsh Ranjan on implicit mesh fairing. Mini-lecture on Chew's second Delaunay refinement algorithm and Boivin and Ollivier-Gooch's modification to handle curved boundaries.

Lecture 23 (April 21): Triangulations and Steiner triangulations of polyhedra. Constrained Delaunay triangulations in three dimensions. Lecture 24 (April 23): Student presentations: James Hamlin on quadrilateral mesh improvement. Peter Bogatsky on view-dependent progressive meshes. Mini-lecture on adapting Ruppert's and Chew's algorithms to handle domains with small angles (Miller, Pav, and Walkington). Lecture 25 (April 28): Tetrahedral mesh generation by Delaunay refinement. Lecture 26 (April 30): Student presentations: Meng Yu on meshing for cloth simulation at Pixar. Siyu Song on repairing surface meshes. Mini-lecture on Chew's Delaunay flips on surfaces and their relation to restricted Delaunay triangulations. Lecture 27 (May 5): Barycentric interpolation. Mean value coordinates in two and three dimensions. Lecture 28 (May 7): Student presentations: Hagen Wille on Bézier-based moving meshes. Dino Bellugi on anisotropic quadrilateral-dominant surface remeshing. Lecture 29 (May 12): Surface mesh parametrization. Didn't have time left for this lecture: Quadtree- and octree-based algorithms for mesh generation.


Related sites

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


Supported in part by the National Science Foundation under Awards ACI-9875170, CMS-9980063, CCR-0204377, CCF-0430065, CCF-0635381, and EIA-9802069, in part by a gift from the Okawa Foundation, and in part by an Alfred P. Sloan Research Fellowship.

(Man and Woman. Fernand Léger, 1881-1955.)