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

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

Jonathan Shewchuk

Spring 2012
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 18): Marching cubes and variants (marching triangles, squares, tetrahedra). Lecture 2 (January 23): Dual contouring—including an introduction to quadtrees, octrees, and constructive solid geometry (CSG) operations with isosurfaces. Lecture 3 (January 25): Definitions: simplicial complexes; manifolds; triangulations of point sets, polygons, and planar straight-line graphs. Lecture 4 (January 30): 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 1): The incremental insertion algorithm for constructing a Delaunay triangulation. Point location methods: walking, conflict graphs, bucketing. Biased randomized insertion orders.

Lecture 6 (February 6): Higher-dimensional Delaunay triangulations. Sizes of triangulations. Constrained Delaunay triangulations. Lecture 7 (February 8): Data structures for two- and three-dimensional triangulations. Lecture 8 (February 13): Geometric predicates and geometric robustness. Polygon triangulation by finding diagonals. PSLG triangulation by segment insertion. Comparison of Delaunay triangulation algorithms. Lecture 9 (February 15): The goals of mesh generation. Introduction to finite element mesh generation techniques. Chew's first Delaunay refinement algorithm for triangular mesh generation. February 20 is Presidents' Day.

Lecture 10 (February 22): Ruppert's Delaunay refinement algorithm for triangular mesh generation.

Lecture 11 (February 27): Advancing front methods for triangular and tetrahedral mesh generation. Lecture 12 (February 29): Isosurface stuffing—grid-based tetrahedral mesh generation for isosurfaces. Lecture 13 (March 5): Optimal triangulation of polygons. Its application to edge removal in tetrahedral meshes. Optimal triangulation of point sets by edge insertion. Lecture 14 (March 7): Mesh improvement through smoothing and topological transformations. Lecture 15 (March 12): Curve reconstruction by the NN-Crust algorithm. The medial axis, ε-samples, and local feature size. Lecture 16 (March 14): Surface reconstruction by the Cocone and Wrap algorithms. Restricted Delaunay triangulations. Lecture 17 (March 19): Surface mesh editing. Laplacian coordinates. Rotation-invariant mesh representation. Lecture 18 (March 21): The paving algorithm—advancing front quadrilateral mesh generation.

March 26–30 is Spring Recess.

Lecture 19 (April 2): Surface mesh parametrization.

Lecture 20 (April 4): Student presentations: Anand Kulkarni on sliver exudation. Brian Van Straalen on robust geometric predicates in floating-point arithmetic.

Lecture 21 (April 9): Triangulations and Steiner triangulations of polyhedra. Constrained Delaunay triangulations in three dimensions. Lecture 22 (April 11): Student presentations: Ethan Van Andel on Bézier-based moving meshes. Pardeep Kumar on estimating curvature on triangular meshes.

Lecture 23 (April 16): Tetrahedral mesh generation by Delaunay refinement. Lecture 24 (April 18): Student presentations: Allen Xiao on Delaunay refinement with optimized Steiner points. Ricardo Garcia on surface reconstruction from range images.

Lecture 25 (April 23): Student presentation: Sushrut Pavanaskar on sketch-based quadrilateral mesh generation. Surface mesh simplification. Lecture 26 (April 25): Student presentations: Eric Turner on Laplacian surface reconstruction. Laura Devendorf on anisotropic bubble meshing. Element-nested refinement of triangular meshes.

Lecture 27 (April 30): Barycentric interpolation. Mean value coordinates in two and three dimensions. Lecture 28 (May 2): Student presentations: Peter Cottle on generating building facade meshes by driving a truck with lasers around Berkeley. Youngwook Kwon on dual marching cubes.

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, IIS-0915462, in part by the University of California Lab Fees Research Program under Award 09-LR-01-118889-OBRJ, 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.)