
(Course icon, at left, is courtesy of
Nina Amenta.)
CS 2941
Mesh Generation and Geometry Processing in
Graphics, Engineering, and Modeling
Jonathan Shewchuk
Spring 2008
Mondays and Wednesday, 5:307: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 23):
Marching cubes and variants (marching triangles, squares, tetrahedra).

Jules Bloomenthal,
An Implicit Surface Polygonizer,
Graphics Gems IV, Paul Heckbert (editor), pages 324349,
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 163170, July 1987.
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 8391, October 1991.
PDF (23,696k).
Lecture 2 (January 28):
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 339346, 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 30):
Definitions:
simplicial complexes;
manifolds;
triangulations of point sets, polygons, and planar straightline graphs.

Marshall Bern and David Eppstein,
Mesh Generation and Optimal Triangulation,
pages 2390 of Computing in Euclidean Geometry,
DingZhu Du and Frank Hwang (editors), World Scientific, Singapore, 1992.
PostScript (937k) or
PDF (1,120k).
Read pages 17.
Over the semester, we'll read most of this survey.

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 I teach in class.
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).

Bern and Eppstein,
pages 714.

My Lecture Notes on Delaunay Mesh Generation,
pages 110.
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 notes, pages to be written.

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 211219, 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 11):
Higherdimensional Delaunay triangulations.
Sizes of triangulations.
The giftwrapping algorithm for constructing Delaunay triangulations.

Lecture notes, pages to be written.
Lecture 7 (February 13):
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):324, 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):74123, 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 BlandfordBlellochCardozeKadow data structure).
The rest of the paper is pretty interesting too, but you'll probably
want to skip Section 3.
February 18 is Presidents' Day.
Lecture 8 (February 20):
Constrained Delaunay triangulations.
Comparison of Delaunay triangulation algorithms.
Geometric predicates and geometric robustness.

Lecture notes,
pages 1016.

My Lecture Notes on Geometric Robustness.
Gnuzipped PostScript (125k)
or
PDF (213k).
Read Sections 23.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.
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.

Jonathan Richard Shewchuk,
What Is a Good Linear Element?
Interpolation, Conditioning, and Quality Measures,
Eleventh International Meshing Roundtable (Ithaca, New York),
pages 115126, Sandia National Laboratories, September 2002.
PostScript (1,083k) or
PDF (250k).

Bern and Eppstein,
pages 3845, 6264.

Lecture notes, pages to be written.
Lecture 10 (February 27):
Ruppert's Delaunay refinement algorithm for triangular mesh generation.

Lecture notes, pages 4159.

Optional.
Jim Ruppert, A Delaunay Refinement Algorithm for Quality 2Dimensional
Mesh Generation, Journal of Algorithms 18(3):548585, 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 (March 3):
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 (March 5):
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 10):
Optimal triangulation of polygons.
Its application to edge removal in tetrahedral meshes.
Optimal triangulation of point sets by edge insertion.

Bern and Eppstein,
pages 1418, 4547.
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 1418 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:4765, 1993.
Gnuzipped PostScript (72k) or
PDF (245k).
Lecture 14 (March 12):
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:39794002,
1997.
Gnuzipped PostScript (223k) or
PDF (359k).

Bryan Matthew Klingner and Jonathan Richard Shewchuk,
Aggressive Tetrahedral Mesh Improvement,
Proceedings of the 16th International Meshing Roundtable (Seattle, Washington),
pages 323, October 2007.
PDF (26,567k).
Bryan's talk in PDF (36,723k).
Lecture 15 (March 17):
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 893894, 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.
Nina Amenta, Marshall Bern, and David Eppstein,
The Crust and the BetaSkeleton: Combinatorial Curve Reconstruction,
Graphical Models and Image Processing 60/2(2):125135, 1998.
Gnuzipped PostScript (134k) or
PDF (326k).
Lecture 16 (March 19):
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(12):125141, 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 379404 of
Discrete and Computational Geometry: The GoodmanPollack 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 2123 and 5057;
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.
March 2428 is Spring Recess.
Lecture 17 (March 31):
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):479487, 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 179188, 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 (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.
Minilecture on polygon triangulation by finding diagonals.

François Labelle and Jonathan Richard Shewchuk,
Anisotropic Voronoi Diagrams and
GuaranteedQuality Anisotropic Mesh Generation,
Proceedings of the Nineteenth Annual Symposium on
Computational Geometry (San Diego, California), pages 191200,
Association for Computing Machinery, June 2003.
PostScript (910k) or
PDF (284k).
Jessica's talk in PowerPoint (5,278k).
Slides from a related
talk (PDF, 1,301k) are also available.

Pierre Alliez, David CohenSteiner, Mariette Yvinec, and Mathieu Desbrun,
Variational Tetrahedral Meshing,
ACM Transactions on Graphics 24(3):617625, 2005.
Special issue on Proceedings of SIGGRAPH 2005.
PDF (778k).
Nuttapong's talk in PDF (22,064k).

Bern and Eppstein,
pages 67.
Lecture 20 (April 9):
Student presentation:
Ilya Landa on generating building facade meshes by
driving a truck with lasers around Berkeley.
Surface mesh simplification.

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):159184,
February 2005.
PDF (5,778k).
Ilya's talk in PDF (2,383k).

Michael Garland and Paul Heckbert,
Surface Simplification Using Quadric Error Metrics,
Computer Graphics (SIGGRAPH '97 Proceedings), August 1997.
PostScript (2,328k) or
PDF (390k).
Slides from their
talk (PDF, 601k) are also available.
Lecture 21 (April 14):
Elementnested refinement of triangular and tetrahedral meshes.
Coarsening of triangular meshes.

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

Optional. Sections 1, 2, 3, and 6 are recommended reading.
(The proofs, in Sections 4 and 5, are more difficult.)
Gary L. Miller, Dafna Talmor, and ShangHua Teng,
Optimal GoodAspectRatio Coarsening for Unstructured Meshes,
Proceedings of the Eighth Annual ACMSIAM Symposium on Discrete Algorithms
(New Orleans, Louisiana), January 1997.
Gnuzipped PostScript (263k) or
PDF (421k).
Lecture 22 (April 16):
Student presentations:
Jimmy Andrews on dual marching cubes.
Darsh Ranjan on implicit mesh fairing.
Minilecture on Chew's second Delaunay refinement algorithm
and Boivin and OllivierGooch's modification to handle curved boundaries.

Scott Schaefer and Joe Warren,
Dual Marching Cubes: Primal Contouring of Dual Grids,
Computer Graphics Forum 24(2):195201, 2005.
PDF (1,037k).
Jimmy's talk in PDF (1,849k).

Mathieu Desbrun, Mark Meyer, Peter Schröder, and Alan H. Barr,
Implicit Fairing of Irregular Meshes Using Diffusion and Curvature Flow,
Computer Graphics (SIGGRAPH ’99 Proceedings) (Los Angeles, California),
pages 317324, August 1999.
PDF (1,735k).
Darsh's talk in PDF (794k).
Lecture 23 (April 21):
Triangulations and Steiner triangulations of polyhedra.
Constrained Delaunay triangulations in three dimensions.

Bern and Eppstein, pages 5155.

Lecture notes, pages to be written.
Lecture 24 (April 23):
Student presentations:
James Hamlin on quadrilateral mesh improvement.
Peter Bogatsky on viewdependent progressive meshes.
Minilecture on adapting Ruppert's and Chew's algorithms to handle
domains with small angles (Miller, Pav, and Walkington).

Paul Kinney,
CleanUp: Improving Quadrilateral Finite Element Meshes,
Sixth International Meshing Roundtable (Park City, Utah),
pages 449461, October 1997.
Gnuzipped PostScript (40k) or
PDF (36k).
James' talk in PDF (910k).

Hugues Hoppe,
ViewDependent Refinement of Progressive Meshes, Computer Graphics
(SIGGRAPH ’97 Proceedings), pages 189198, August 1997.
Gnuzipped PostScript (3,891k) or
PDF (601k).
Peter's talk in PDF (11,169k).
Lecture 25 (April 28):
Tetrahedral mesh generation by Delaunay refinement.

Lecture Notes on Delaunay Mesh Generation, Chapter 4.
Lecture 26 (April 30):
Student presentations:
Meng Yu on meshing for cloth simulation at Pixar.
Siyu Song on repairing surface meshes.
Minilecture on Chew's Delaunay flips on surfaces and
their relation to restricted Delaunay triangulations.

Fakir S. Nooruddin and Greg Turk,
Simplification and Repair of Polygonal Meshes Using Volumetric
Techniques,
IEEE Transactions on Visualization and Computer Graphics 9(2):191205,
AprilJune 2003.
PDF (14,745k).
Siyu's talk in
Google
Docs or PDF (2,055k).

Optional.
L. Paul Chew,
GuaranteedQuality Mesh Generation for Curved Surfaces,
Proceedings of the Ninth Annual Symposium on Computational Geometry
(San Diego, California), pages 274280, May 1993.
Although he didn't know it at the time,
Chew's definition of Delaunay edge flips on curved surfaces is consistent with
the restricted Delaunay triangulation.
Lecture 27 (May 5):
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):561566, July 2005.
Special issue on Proceedings of SIGGRAPH 2005.
PDF (1,743k).
Lecture 28 (May 7):
Student presentations:
Hagen Wille on Bézierbased moving meshes.
Dino Bellugi on anisotropic quadrilateraldominant surface remeshing.

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 310319, June 2004.
PDF (691k).
Hagen's talk in PDF (694k).

Pierre Alliez, David CohenSteiner, Olivier Devillers, Bruno Lévy,
and Mathieu Desbrun,
Anisotropic Polygonal Remeshing,
ACM Transactions on Graphics 22(3):485493,
July 2003.
Special issue on Proceedings of SIGGRAPH 2003.
PDF (19,950k).
Dino's talk in PowerPoint (45,075k).
Lecture 29 (May 12):
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):105171,
2006.
PDF (15,635k).
Read Sections 13.
The rest is good too, but optional.
Didn't have time left for this lecture:
Quadtree and octreebased algorithms for mesh generation.

Bern and Eppstein, pages 2225, 4041, 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 needn't 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:709749,
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):384409, June 1994.
Gnuzipped PostScript (151k) or
PDF (341k).
This classic paper gives the first sizeoptimal guaranteedquality
meshing algorithm (from before Ruppert invented his 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,
and EIA9802069, 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, 18811955.)