
(Course icon, at left, is courtesy of
Nina Amenta.)
CS 29474
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:
Delaunaybased, gridbased, octreebased, 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, minmax 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 TR02408, Department of Computer Science, Rice University,
2002.
PDF (376k).
Lecture 3 (January 25):
Definitions:
simplicial complexes;
manifolds;
triangulations of point sets, polygons, and planar straightline graphs.

Marshall Bern and David Eppstein,
Mesh Generation and Optimal Triangulation,
pages 23–90 of Computing in Euclidean Geometry,
DingZhu 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 edgebased data structure called
the quadedge, which simultaneously represents a planar subdivision
and its dual (e.g. a Delaunay triangulation and a Voronoi diagram).
It also gives pseudocode for the divideandconquer
and incremental insertion (with a notsogood 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):
Higherdimensional Delaunay triangulations.
Sizes of triangulations.
Constrained Delaunay triangulations.
Lecture 7 (February 8):
Data structures for two and threedimensional 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 2Dimensional
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—gridbased 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 OllivierGooch,
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 NNCrust 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 BetaSkeleton: 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), SpringerVerlag, 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 onestop shop for everything in Lectures 15 and 16.
Restricted Delaunay triangulations on pages 21–23 and 50–57;
the NNCrust 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.
Rotationinvariant mesh representation.

Yaron Lipman, Olga Sorkine, Daniel CohenOr and David Levin,
Linear RotationInvariant 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 CohenOr, Yaron Lipman, Marc Alexa,
Christian Rössl, and HansPeter 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.
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 floatingpoint arithmetic.

SiuWing Cheng, Tamal Krishna Dey, Herbert Edelsbrunner, Michael A. Facello,
and ShangHua Teng, Sliver Exudation,
Journal of the ACM 47(5):883–904, September 2000.
Gnuzipped PostScript (120k) or
PDF (294k).

Jonathan Richard Shewchuk,
Adaptive Precision FloatingPoint
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ézierbased moving meshes.
Pardeep Kumar on estimating curvature on triangular meshes.

David Cardoze, Alexandre Cunha, Gary L. Miller, Todd Phillips, and
Noel Walkington,
A BézierBased 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 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 sketchbased 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.
Elementnested 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örgRüdiger Sack and Jorge Urrutia (editors), Elsevier Science,
1999.
Gnuzipped PostScript (961k) or
PDF (1,231k).
Read pages 1618, 3031 (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 octreebased 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
ThreeDimensional 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 sizeoptimal guaranteedquality
meshing algorithm
(from before Ruppert invented his Delaunay refinement algorithm).
Grading
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 ACI9875170, CMS9980063, CCR0204377, CCF0430065, CCF0635381,
IIS0915462, in part by the University of California Lab Fees Research Program
under Award 09LR01118889OBRJ,
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.)