CS 294-74: Mesh Generation and Geometry Processing

(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:

Contouring algorithms for isosurfaces and medical data, such as marching cubes.
Triangular and tetrahedral mesh generation techniques: Delaunay-based, grid-based, octree-based, and advancing front.
Delaunay triangulations and constrained Delaunay triangulations.
Curve and surface reconstruction from point clouds.
Parametrization, simplification, and editing of surface meshes.
Optimal triangulations, such as Delaunay, min-max angle, and minimum weight triangulations.
Quadrilateral and hexahedral mesh generation.
Mesh improvement: vertex smoothing and element transformations.
Refinement and coarsening of simplicial meshes.
Geometric primitives and numerical robustness.
Interpolation, including barycentric and mean value coordinates.

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.

Lectures

Lecture 1 (January 18): Marching cubes and variants (marching triangles, squares, tetrahedra).

Jules Bloomenthal, An Implicit Surface Polygonizer, Graphics Gems IV, Paul Heckbert (editor), pages 324–349, Academic Press (Boston, Massachusetts), 1994. PDF (634k). To save paper, print only the first 8 pages. The rest is code.
William E. Lorensen and Harvey E. Cline, Marching Cubes: A High Resolution 3D Surface Construction Algorithm, Computer Graphics (SIGGRAPH ’87 Proceedings) (Anaheim, California), pages 163–170, July 1987. The most cited SIGGRAPH paper of all time. Read Section 4.
Optional web page, good for the pictures. James Sharman, The Marching Cubes Algorithm.
Optional. This paper solves the problem of holes in the triangulated surfaces produced by the original marching cubes algorithm. I discuss it briefly in class, but it's not required reading. Gregory M. Nielson and Bernd Hamann, The Asymptotic Decider: Resolving the Ambiguity in Marching Cubes, Proceedings of the 2nd Conference on Visualization ’91 (San Diego, California), pages 83–91, October 1991. PDF (23,696k).

Lecture 2 (January 23): Dual contouring—including an introduction to quadtrees, octrees, and constructive solid geometry (CSG) operations with isosurfaces.

Tao Ju, Frank Losasso, Scott Schaefer, and Joe Warren, Dual Contouring of Hermite Data, Proceedings of SIGGRAPH 2002 (San Antonio, Texas), pages 339–346, July 2002. Skip the discussions of QR decompositions (and ask me if you want to know a better way to obtain numerical stability). Section 4 is optional reading, but good reading.
Optional. You might want this if you ever implement dual contouring. Scott Schaefer and Joe Warren, Dual Contouring: “The Secret Sauce,” Technical Report TR02-408, Department of Computer Science, Rice University, 2002. PDF (376k).

Lecture 3 (January 25): Definitions: simplicial complexes; manifolds; triangulations of point sets, polygons, and planar straight-line graphs.

Marshall Bern and David Eppstein, Mesh Generation and Optimal Triangulation, pages 23–90 of Computing in Euclidean Geometry, Ding-Zhu Du and Frank Hwang (editors), World Scientific, Singapore, 1992. PostScript (937k) or PDF (1,120k). Read pages 1–7. Over the semester, we'll read most of this survey.
Optional. Herbert Edelsbrunner, Geometry and Topology of Grid Generation, lecture notes, Spring 1999. Meeting 6: Simplicial Complexes (PostScript, 137k or PDF, 135k) and Meeting 7: Spaces and Manifolds (PostScript, 120k or PDF, 115k). Skip the “Nerves” section. Don't worry if you don't understand the “Topological spaces” section; replace that with the (more intuitive) metric spaces in my lecture notes below.
Optional. My Lecture Notes on Delaunay Mesh Generation, Sections 1.3–1.7. An alternative source for definitions of complexes, homeomorphisms, and manifolds.

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).

Bern and Eppstein, pages 7–14.
Optional. Lecture Notes, Sections 2.1–2.7.

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.

Optional. Leonidas J. Guibas and Jorge Stolfi, Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams, ACM Transactions on Graphics 4(2):74–123, April 1985. This paper discusses an edge-based data structure called the quad-edge, which simultaneously represents a planar subdivision and its dual (e.g. a Delaunay triangulation and a Voronoi diagram). It also gives pseudocode for the divide-and-conquer and incremental insertion (with a not-so-good version of walking point location) algorithms for constructing Delaunay triangulations. Section 9 or 10 might help you with Project I (though I want you to use the Blandford–Blelloch–Cardoze–Kadow data structure). The rest of the paper is pretty interesting too, but you'll probably want to skip Section 3.
Optional. Lecture Notes, Sections 3.1–3.5 and 5.4.
Optional. Nina Amenta, Sunghee Choi, and Günter Rote. Incremental Constructions con BRIO, Proceedings of the Nineteenth Annual Symposium on Computational Geometry (San Diego, California), pages 211–219, June 2003. PDF (461k). Everyone should know about the BRIO paper, though I don't make it required reading for the class. Even if you don't want to immerse yourself in the heartbreakingly elegant analysis, Sections 1, 2, 7, 8, and 9 make good light reading.

Lecture 6 (February 6): Higher-dimensional Delaunay triangulations. Sizes of triangulations. Constrained Delaunay triangulations.

Optional. Lecture Notes, Sections 2.8 and 4.1–4.3.

Lecture 7 (February 8): Data structures for two- and three-dimensional triangulations.

Daniel K. Blandford, Guy E. Blelloch, David E. Cardoze, and Clemens Kadow, Compact Representations of Simplicial Meshes in Two and Three Dimensions, International Journal of Computational Geometry and Applications 15(1):3–24, February 2005. PDF (2,364k).
Optional. Leonidas J. Guibas and Jorge Stolfi, Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams, ACM Transactions on Graphics 4(2):74–123, April 1985. See description above under Lecture 5.

Lecture 8 (February 13): Geometric predicates and geometric robustness. Polygon triangulation by finding diagonals. PSLG triangulation by segment insertion. Comparison of Delaunay triangulation algorithms.

My Lecture Notes on Geometric Robustness. Gnuzipped PostScript (125k) or PDF (213k). Read Sections 2–3.2. Make sure you know what's in Section 3 in case you ever need it as a reference. It might help you implement your projects. Section 1 is entirely optional.
Bern and Eppstein, pages 6–7.

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.

Jonathan Richard Shewchuk, What Is a Good Linear Element? Interpolation, Conditioning, and Quality Measures, Eleventh International Meshing Roundtable (Ithaca, New York), pages 115–126, Sandia National Laboratories, September 2002. PostScript (1,083k) or PDF (250k).
Bern and Eppstein, pages 38–45, 62–64.
Optional. Lecture Notes, Sections 1.1–1.3 and 1.6.

February 20 is Presidents' Day.

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

Lecture Notes, Chapter 6.
Optional. Jim Ruppert, A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation, Journal of Algorithms 18(3):548–585, May 1995. PostScript (192k) or PDF (443k). This material is mostly covered in the lecture notes, but Ruppert's original paper is excellent.

Lecture 11 (February 27): Advancing front methods for triangular and tetrahedral mesh generation.

Jaime Peraire, Joaquim Peir�, and Ken Morgan, Advancing Front Grid Generation, Chapter 17 of Handbook of Grid Generation (Joe F. Thompson, Bharat K. Soni, and Nigel P. Weatherill, editors), CRC Press, 1999.
David L. Marcum, Unstructured Grid Generation Using Automatic Local Point Insertion and Local Reconnection, Chapter 18 of Handbook of Grid Generation (Joe F. Thompson, Bharat K. Soni, and Nigel P. Weatherill, editors), CRC Press, 1999. Only Sections 18.1 and 18.2 are required reading, but Section 18.6 is also recommended because it so concisely summarizes many of the common concerns of engineering mesh generation papers. Some translations: Marcum's “local reconnection” is our bistellar flips. Marcum's “direct subdivision” is our lazy vertex insertion.

Lecture 12 (February 29): Isosurface stuffing—grid-based tetrahedral mesh generation for isosurfaces.

François Labelle and Jonathan Richard Shewchuk, Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles, ACM Transactions on Graphics 26(3), August 2007. Special issue on Proceedings of SIGGRAPH 2007. PDF (3,530k).

Lecture 13 (March 5): Optimal triangulation of polygons. Its application to edge removal in tetrahedral meshes. Optimal triangulation of point sets by edge insertion.

Bern and Eppstein, pages 14–18, 45–47. There's a rather important typo in the middle of Page 18: the sentence beginning, “We compute these values in increasing order of i...” should read “in decreasing order of i.”
Optional readings. Bern and Eppstein's survey is well written, but very concise. If you want to have pages 14–18 unpacked for you, the following papers go into detail.
- My unpublished tutorial, Two Discrete Optimization Algorithms for the Topological Improvement of Tetrahedral Meshes, 2002. PostScript (295k) or PDF (168k). Section 2 discusses Klincsek's dynamic programming algorithm for optimal triangulation of polygons in detail, and shows how to use it to perform edge removal operations to improve tetrahedral meshes.
- Marshall Bern, Herbert Edelsbrunner, David Eppstein, Scott Mitchell, and Tiow Seng Tan, Edge Insertion for Optimal Triangulations, Discrete & Computational Geometry 10:47–65, 1993. Gnuzipped PostScript (72k) or PDF (245k).

Lecture 14 (March 7): Mesh improvement through smoothing and topological transformations.

Lori A. Freitag and Carl Ollivier-Gooch, Tetrahedral Mesh Improvement Using Swapping and Smoothing, International Journal for Numerical Methods in Engineering 40:3979–4002, 1997. Gnuzipped PostScript (223k) or PDF (359k).
Optional. Bryan Matthew Klingner and Jonathan Richard Shewchuk, Aggressive Tetrahedral Mesh Improvement, Proceedings of the 16th International Meshing Roundtable (Seattle, Washington), pages 3–23, October 2007. PDF (26,567k).

Lecture 15 (March 12): Curve reconstruction by the NN-Crust algorithm. The medial axis, ε-samples, and local feature size.

Tamal K. Dey and Piyush Kumar, A Simple Provable Algorithm for Curve Reconstruction, Proceedings of the Tenth Annual Symposium on Discrete Algorithms (Baltimore, Maryland), pages 893–894, January 1999. Gnuzipped PostScript (88k) or PDF (151k).
Optional. My lecture includes Lemma 1 from this pioneering paper, which Dey and Kumar use in their correctness proof. This paper's algorithm produces the crust, the first provably good curve reconstruction. Nina Amenta, Marshall Bern, and David Eppstein, The Crust and the Beta-Skeleton: Combinatorial Curve Reconstruction, Graphical Models and Image Processing 60/2(2):125–135, 1998. Gnuzipped PostScript (134k) or PDF (326k).

Lecture 16 (March 14): Surface reconstruction by the Cocone and Wrap algorithms. Restricted Delaunay triangulations.

Nina Amenta, Sunghee Choi, Tamal K. Dey, and N. Leekha, A Simple Algorithm for Homeomorphic Surface Reconstruction, International Journal of Computational Geometry and Applications 12(1–2):125–141, 2002. PDF (2,151k). Feel free to skip the proofs (but read the theorems).
Optional. Herbert Edelsbrunner, Surface Reconstruction by Wrapping Finite Sets in Space, pages 379–404 of Discrete and Computational Geometry: The Goodman–Pollack Festschrift, Boris Aronov (editor), Springer-Verlag, 2003. PDF (400k). Better known as the Wrap algorithm. Be warned that some heavy translation is required to get from this paper to how I describe it in lecture.
Optional. Tamal Krishna Dey, Curve and Surface Reconstruction: Algorithms with Mathematical Analysis, Cambridge University Press, New York, 2007. The preface, contents, Chapters 3 and 4, and errata. This book is your one-stop shop for everything in Lectures 15 and 16. Restricted Delaunay triangulations on pages 21–23 and 50–57; the NN-Crust algorithm in Section 2.3 (with proofs in Section 2.1); the Cocone algorithm in Chapter 4 (with proofs in Chapter 3); the Wrap algorithm in Chapter 10.

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

Yaron Lipman, Olga Sorkine, Daniel Cohen-Or and David Levin, Linear Rotation-Invariant Coordinates for Meshes, ACM Transactions on Graphics 24(3):479–487, July 2005. PDF (8,080 k). Special issue on Proceedings of SIGGRAPH 2005. Read Sections 1 and 4. If you make it to lecture, you can probably skip Sections 2 and 3: in class, I will simplify the formulation and notation a lot, and skip the discrete forms (but don't skip the discrete frames). Discrete forms are useful if you want a compact encoding or an understanding of the relationship to continuous differential geometry, but they aren't necessary to do mesh editing. If you don't catch my lecture, make sure you understand equations (2) and (5).
Optional. Olga Sorkine, Daniel Cohen-Or, Yaron Lipman, Marc Alexa, Christian Rössl, and Hans-Peter Seidel, Laplacian Surface Editing, Symposium on Geometry Processing 2004 (Nice, France), Eurographics Association, pages 179–188, July 2004. PDF (9,601 k). If you read this, skip everything involving the transformation T_i—i.e. from the paragraph following equation (4) to the end of Section 3.1. The problem that T_i is meant to solve is better handled by the paper above.

Lecture 18 (March 21): The paving algorithm—advancing front quadrilateral mesh generation.

Ted D. Blacker and Michael B. Stephenson, Paving: A New Approach to Automated Quadrilateral Mesh Generation, International Journal for Numerical Methods in Engineering 32(4):811–847, September 1991. Erratum: Equation (20) should end with “ε₁ > ε₂”.

March 26–30 is Spring Recess.

Lecture 19 (April 2): Surface mesh parametrization.

Alla Sheffer, Emil Praun, and Kenneth Rose, Mesh Parameterization Methods and Their Applications, Foundations and Trends in Computer Graphics and Vision 2(2):105–171, 2006. PDF (15,635k). Read Sections 1–3. The rest is good too, but optional.

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

Siu-Wing Cheng, Tamal Krishna Dey, Herbert Edelsbrunner, Michael A. Facello, and Shang-Hua Teng, Sliver Exudation, Journal of the ACM 47(5):883–904, September 2000. Gnuzipped PostScript (120k) or PDF (294k).
Jonathan Richard Shewchuk, Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates, Discrete & Computational Geometry 18(3):305–363, October 1997. PostScript (775k, 55 pages), PDF (556k, 55 pages).

Lecture 21 (April 9): Triangulations and Steiner triangulations of polyhedra. Constrained Delaunay triangulations in three dimensions.

Bern and Eppstein, pages 51–55.
Optional. Lecture Notes, Section 4.5.

Lecture 22 (April 11): Student presentations: Ethan Van Andel on Bézier-based moving meshes. Pardeep Kumar on estimating curvature on triangular meshes.

David Cardoze, Alexandre Cunha, Gary L. Miller, Todd Phillips, and Noel Walkington, A Bézier-Based Approach to Unstructured Moving Meshes, Twentieth Annual Symposium on Computational Geometry (Brooklyn, New York), pages 310–319, June 2004. PDF (691k).
Timothy D. Gatzke and Cindy M. Grimm, Estimating Curvature on Triangular Meshes, International Journal of Shape Modeling 12(1):1–29, June 2006. PDF (400k).

Lecture 23 (April 16): Tetrahedral mesh generation by Delaunay refinement.

Lecture Notes, Chapter 6.

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

Hale Erten and Alper Üngör, Triangulations with Locally Optimal Steiner Points, Symposium on Geometry Processing 2007 (Barcelona, Spain), pages 143–152, July 2007. PDF (615k).
Brian Curless and Marc Levoy, A Volumetric Method for Building Complex Models from Range Images, Computer Graphics (SIGGRAPH '96 Proceedings), pages 303–312, 1996. Gnuzipped PostScript (766k) or PDF (270k).

Lecture 25 (April 23): Student presentation: Sushrut Pavanaskar on sketch-based quadrilateral mesh generation. Surface mesh simplification.

Michael Garland and Paul Heckbert, Surface Simplification Using Quadric Error Metrics, Computer Graphics (SIGGRAPH '97 Proceedings), August 1997. PostScript (2,328k) or PDF (390k).

Lecture 26 (April 25): Student presentations: Eric Turner on Laplacian surface reconstruction. Laura Devendorf on anisotropic bubble meshing. Element-nested refinement of triangular meshes.

Michael M. Kazhdan, Matthew Bolitho, and Hugues Hoppe, Poisson Surface Reconstruction, Symposium on Geometry Processing 2006 (Cagliari, Italy), pages 61–70, June 2006. PDF (12,654k).
Frank Bossen and Paul Heckbert, A Pliant Method for Anisotropic Mesh Generation, Fifth International Meshing Roundtable (Pittsburgh, Pennsylvania), pages 63–74, October 1996. Gnuzipped PostScript (572k) or PDF (450k).
Marshall Bern and Paul Plassmann, Mesh Generation, Chapter 6 of Handbook of Computational Geometry, Jörg-Rüdiger Sack and Jorge Urrutia (editors), Elsevier Science, 1999. Gnuzipped PostScript (961k) or PDF (1,231k). Read pages 16-18, 30-31 (on mesh refinement).

Lecture 27 (April 30): Barycentric interpolation. Mean value coordinates in two and three dimensions.

Tao Ju, Scott Schaefer, and Joe Warren, Mean Value Coordinates for Closed Triangular Meshes, ACM Transactions on Graphics 24(3):561–566, July 2005. Special issue on Proceedings of SIGGRAPH 2005. PDF (1,743k).

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.

Christian Früh, Siddharth Jain, and Avideh Zakhor, Data Processing Algorithms for Generating Textured 3D Building Facade Meshes from Laser Scans and Camera Images, International Journal of Computer Vision 61(2):159–184, February 2005. PDF (5,778k).
Scott Schaefer and Joe Warren, Dual Marching Cubes: Primal Contouring of Dual Grids, Computer Graphics Forum 24(2):195–201, 2005. PDF (1,037k).

Didn't have time left for this lecture: Quadtree- and octree-based algorithms for mesh generation.

Bern and Eppstein, pages 22–25, 40–41, 63.
Optional readings. There's no publication that is both concise and detailed enough to satisfy me. Those wishing to learn more should consider the following optional references, though. The first reference is abstract and omits too much detail. The second is concrete, includes much detail, and is strongly practical, but is a long difficult read. The third is theoretical, and is also a long difficult read. Its warping rules appear useful in practice, and are worth studying. To obtain a theoretical guarantee of element quality, the authors split the quadrants too finely for practical use, but you don't have to do that in practice.
- Mark S. Shephard, Hugues L. de Cougny, Robert M. O'Bara, and Mark W. Beall, Automatic Grid Generation Using Spatially Based Trees, Chapter 15 of Handbook of Grid Generation (Joe F. Thompson, Bharat K. Soni, and Nigel P. Weatherill, editors), CRC Press, 1999. PDF (3,342k).
- Mark S. Shephard and Marcel K. Georges, Automatic Three-Dimensional Mesh Generation by the Finite Octree Technique, International Journal for Numerical Methods in Engineering 32:709–749, 1991. A strength of this paper is that the mesh generator is designed to work well with CAD geometry representations (where the mesher must query a CAD program), with all their numerical and topological flaws.
- Marshall Bern, David Eppstein, and John R. Gilbert, Provably Good Mesh Generation, Journal of Computer and System Sciences 48(3):384–409, June 1994. Gnuzipped PostScript (151k) or PDF (341k). This classic paper gives the first size-optimal guaranteed-quality meshing algorithm (from before Ruppert invented his Delaunay refinement algorithm).

Grading

25% for Project I: A Delaunay triangulation implementation.
40% for Project II: A mesh generator, surface reconstructor, or other triangulation processing program. (A project relevant to your personal research would be ideal.)
10% for your paper presentation.
25% for the take-home Examination.

Related sites

Robert Schneiders' unbelievably comprehensive mesh generation index.
Steve Owen's Meshing Research Corner (a guide to the literature).
David Eppstein's Geometry in Action and Geometry Junkyard.
Jeff Erickson's Computational Geometry Pages.
Herbert Edelsbrunner's course on the Geometry and Topology of Mesh Generation. (Locally cached. Sorry, the open problems are missing. Buy his book.)
A list of open problems in mesh generation from David Eppstein's course on mesh generation. I solved one.

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

My robust predicates page (floating-point inputs, C).
Chee Yap's CORE Library (C/C++).
David Bailey's extensive MPFUN arbitrary precision arithmetic package (floating-point, Fortran). Look for mpfun.tex and mpfun.f.
Olivier Devillers' predicates (integer inputs).
Stefan N�her et al.'s LEDA contains several arbitrary precision numerical types, including integers and floating-point (C++).

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.)