Meshing and Triangulation

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

CS 294-5
Meshing and Triangulation in Graphics, Engineering, and Modeling

Jonathan Shewchuk

Autumn 1999
Tuesdays and Thursdays, 2:00-3:30pm
606 Soda Hall

Some lecture transparencies (1, 4, 11, 12, 13) are on line. To read them, click on a lecture in the list below.

Student presentation requirement: Every student (including auditors) is asked to present a paper from this list of notable meshing publications. Please choose a presentation date by September 28. Please choose a paper at least a week before your presentation date.

The best 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.)
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++).

Lectures

Lecture 1 (August 23): Nonoptimal triangulations of point sets and polygons.

Marshall Bern and David Eppstein, Mesh Generation and Optimal Triangulation, pp. 23-90 of Computing in Euclidean Geometry, Ding-Zhu Du and Frank Hwang (editors), World Scientific, Singapore, 1992. PostScript is available here. Read pages 1-7.
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications, Springer, Berlin, 1997. Read pages 49-60.

Lecture 2 (August 25): The goals of mesh generation. Two-dimensional Delaunay triangulations.

Lecture Notes on Delaunay Mesh Generation, pages 1-14. PostScript is available here.

Lecture 3 (August 31): Two-dimensional Delaunay triangulations (continued). The Voronoi diagram. Constrained Delaunay triangulations.

Lecture notes, pages 14-19.
Bern and Eppstein, pages 7-14.

Lecture 4 (September 2): Higher-dimensional Delaunay triangulations. Sizes of triangulations (in any dimension).

Lecture notes, pages 19-26.
Bern and Eppstein, pages 50-51.
(Optional.) Raimund Seidel, An Upper Bound Theorem for Polytopes: An Easy Proof of its Asymptotic Version, Computational Geometry: Theory and Applications 5(2):115-116, September 1995. (You only really need to read the abstract, which contains the entire proof.)

Lecture 5 (September 7): Higher-dimensional constrained Delaunay triangulations. Conforming tetrahedralizations.

Lecture notes, pages 26-30.
Bern and Eppstein, pages 51-59.

Lecture 6 (September 9): The incremental insertion algorithm for constructing a Delaunay triangulation.

Lecture notes, pages 30-39.
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. Feel free to skip Section 3, but read the rest of the paper. See also this list of errors in the Guibas and Stolfi paper, and Paul Heckbert, Very Brief Note on Point Location in Triangulations, December 1994. (The problem Paul points out can't happen in a Delaunay triangulation, but it's a warning in case you're ever tempted to use the Guibas and Stolfi walking-search subroutine in a non-Delaunay triangulation.)

Lecture 7 (September 14): The gift-wrapping algorithm for constructing Delaunay triangulations and constrained Delaunay triangulations in any dimension. Divide-and-conquer algorithms for constructing two-dimensional Delaunay triangulations and constrained Delaunay triangulations. High-level summary of Fortune's sweepline algorithm.

Lecture notes, pages 39-40.
Guibas and Stolfi, Section 9 (for the divide-and-conquer algorithm).
L. Paul Chew, Constrained Delaunay Triangulations, Algorithmica 4(1):97-108, 1989.

Lecture 8 (September 16): Introduction to mesh generation techniques. Two-dimensional Delaunay refinement.

Lecture notes, pages 40-52.
Bern and Eppstein, pages 38-45, 62-64.

Lecture 9 (September 21): Chew's first Delaunay refinement algorithm. Ruppert's Delaunay refinement algorithm.

Lecture notes, pages 52-66.
(Optional. This material is mostly covered in the lecture notes, but I include Ruppert's paper here for those who would like to see the original source.) Jim Ruppert, A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation, Journal of Algorithms 18(3):548-585, May 1995. PostScript is available here.

Lecture 10 (September 23): Ruppert's Delaunay refinement algorithm (continued). Negative result on quality triangulations of PSLGs that have small angles. Practical handling of small angles.

Lecture notes, pages 66-84.

Lecture 11 (September 28): Advancing front algorithms for 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. Section 18.6 is recommended because it so concisely summarizes many of the common concerns of engineering mesh generation papers.

Lecture 12 (September 30): Quadtree- and octree-based algorithms for mesh generation.

Bern and Eppstein, pages 22-25, 40-41, 63.
(Optional.) There's no publication that is both concise and detailed enough to satisfy me. Hence, I recommend that you read the lecture transparencies. Those wishing to learn more should consider the following optional references, though. The first reference is too abstract and omits too much detail. The second is more concrete, includes much detail, and is strongly oriented toward practice, but is a long difficult read. The third is theoretical, and is also a long difficult read. The warping rules in the third appear quite 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 Three-Dimensional Mesh Generation by the Finite Octree Technique, International Journal for Numerical Methods in Engineering 32:709-749, 1991.
- Marshall Bern, David Eppstein, and John R. Gilbert, Provably Good Mesh Generation, Journal of Computer and System Sciences 48(3):384-409, June 1994.

Lecture 13 (October 5): Geometric robustness. Mesh improvement through smoothing and topological transformations.

Lecture Notes on Geometric Robustness. PostScript is available here. Sections 2 and 3 may help you implement your projects.
Scott A. Canann, S. N. Muthukrishnan, and R. K. Phillips, Topological Refinement Procedures for Triangular Finite Element Meshes, Engineering with Computers 12(3 & 4):243-255, 1996.
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. PostScript is available here.

Lecture 14 (October 7): Andy Neureuther on surface simplification. Jason Riedy on the Whisker Weaving algorithm for hexahedral mesh generation.

Michael Garland and Paul Heckbert, Surface Simplification Using Quadric Error Metrics, Computer Graphics (SIGGRAPH '97 Proceedings), August 1997.
Timothy J. Tautges, Ted Blacker, and Scott Mitchell, The Whisker Weaving Algorithm: A Connectivity-Based Method for Constructing All-Hexahedral Finite Element Meshes.

No lecture on October 12. But you're welcome to take Amtrak to South Lake Tahoe and join me at the Eighth International Meshing Roundtable.

Lecture 15 (October 14): Surface mesh simplification. Topology-preserving edge contraction.

Herbert Edelsbrunner, Geometry and Topology of Grid Generation, lecture notes, Spring 1999. Meeting 9: Edge Contraction Algorithm (PostScript), Meeting 10: Preserving Topology (PostScript), and Meeting 12: Error Measure (PostScript).
(Optional.) If you don't know all the definitions used in the lecture notes above (and didn't get them from the lecture), you might also look at Meeting 6: Simplicial Complexes (PostScript), and Meeting 7: Spaces and Manifolds (PostScript).

Lecture 16 (October 19): Curve and surface 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. PostScript is available here. Skip Section 9.
Nina Amenta, Marshall Bern, and Manolis Kamvysselis, A New Voronoi-Based Surface Reconstruction Algorithm, Computer Graphics (SIGGRAPH '98 Proceedings), pages 415-421, July 1998. PostScript is available here.
(Video.) Nina Amenta, The Crust Algorithm for 3D Surface Reconstruction, Eighth Annual Video Review of Computational Geometry, ACM, June 1999. See also Proceedings of the Fifteenth Annual Symposium on Computation Geometry (Miami Beach, Florida), pages 423-424, ACM, June 1999.

Lecture 17 (October 21): Borlin Shyu on the Geode algorithm for hexahedral mesh generation. Jae Kim on dynamic point location in Delaunay triangulations.

Robert W. Leland, Darryl J. Melander, Ray W. Meyers, Scott A. Mitchell, and Timothy J. Tautges, The Geode Algorithm: Combining Hex/Tet Plastering, Dicing and Transition Elements for Automatic, All-Hex Mesh Generation, Seventh International Meshing Roundtable (Dearborn, Michigan), pages 515-521, October 1998.
Olivier Devillers, Improved Incremental Randomized Delaunay Triangulation, Proceedings of the Fourteenth Annual Symposium on Computation Geometry (Minneapolis, Minnesota), pages 106-115, ACM, June 1998.

Lecture 18 (October 26): The paving algorithm for 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:811-847, 1991.

Lecture 19 (October 28): Mesh refinement and coarsening.

Marshall Bern and Paul Plassmann, Mesh Generation, manuscript, 1997. PostScript is available here. Read pages 16-18, 30-31 (on mesh refinement).
Gary L. Miller, Dafna Talmor, and Shang-Hua Teng, Optimal Good-Aspect-Ratio Coarsening for Unstructured Meshes, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, Louisiana), January 1997. PostScript is available here. Read Sections 1, 2, 3, and 6.

Lecture 20 (November 2): Jordan Smith on Voronoi diagrams of polygons. Dan Simkins on advancing front quadrilateral meshing.

Martin Held, Computing Voronoi Diagrams, Chapter 5 of On the Computational Geometry of Pocket Machining, volume 500 of Lecture Notes in Computer Science, Springer Verlag, New York, 1991.
Steven J. Owen, Matthew L. Staten, Scott A. Canann, and Sunil Saigal, Advancing Front Quadrilateral Meshing Using Triangle Transformations, Seventh International Meshing Roundtable (Dearborn, Michigan), pages 409-428, October 1998.

Lecture 21 (November 4): Ganping Sun on anisotropic bubble meshing. Michael Downes on progressive simplicial complexes.

Kenji Shimada, Anisotropic Triangular Meshing of Parametric Surfaces via Close Packing of Ellipsoidal Bubbles, Sixth International Meshing Roundtable (Park City, Utah), pages 375-390, October 1997.
Jovan Popovic and Hugues Hoppe, Progressive Simplicial Complexes, Computer Graphics (SIGGRAPH '97 Proceedings), pages 217-224, August 1997.

Lecture 22 (November 9): Okan Arikan on approximating height fields. Tolga Goktekin on view-dependent progressive meshes.

Michael Garland and Paul Heckbert, Fast Triangular Approximation of Terrains and Height Fields, manuscript, May 1997.
Hugues Hoppe, View-Dependent Refinement of Progressive Meshes, Computer Graphics (SIGGRAPH '97 Proceedings), pages 189-198, August 1997.

Lecture 23 (November 11): Maryann Simmons on comparing algorithms for two-dimensional Delaunay triangulation. François Labelle on parallel two-dimensional Delaunay triangulation.

Peter Su and Robert L. Scot Drysdale, A Comparison of Sequential Delaunay Triangulation Algorithms, Proceedings of the Eleventh Annual Symposium on Computational Geometry (Vancouver, British Columbia, Canada), pages 61-70, ACM, June 1995.
Guy E. Blelloch, Gary L. Miller, and Dafna Talmor, Developing a Practical Projection-Based Parallel Delaunay Algorithm, Proceedings of the Twelfth Annual Symposium on Computation Geometry (Philadelphia, Pennsylvania), pages 186-195, ACM, May 1996.

Lecture 24 (November 16): Jane Wang on reconstructing planar cross sections. Steve Chien on hexahedral mesh generation by sweeping.

Chandrajit L. Bajaj, Edward J. Coyle, and Kwun-Nan Lin, Surface and 3D Triangular Meshes from Planar Cross Sections, Fifth International Meshing Roundtable (Pittsburgh, Pennsylvania), pages 169-178, October 1996.
Ted Blacker, The Cooper Tool, Fifth International Meshing Roundtable (Pittsburgh, Pennsylvania), pages 13-29, October 1996.

Lecture 25 (November 18): Chris Tchou on surface reconstruction. Yan Zhuang on constructing generalized Voronoi diagrams.

Brian Curless and Marc Levoy, A Volumetric Method for Building Complex Models from Range Images, Computer Graphics (SIGGRAPH '96 Proceedings), pages 303-312, 1996.
Kenneth E. Hoff III, Tim Culver, John Keyser, Ming Lin, and Dinesh Manocha, Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware. Computer Graphics (SIGGRAPH '99 Proceedings), August 1999.

Lecture 26 (November 23): Tzi-cker Chiueh on compressing triangular surface meshes. Minimum weight triangulations.

Jarek Rossignac, Edgebreaker: Connectivity Compression for Triangle Meshes, Technical Report GIT-GVU-98-35, GVU Center, Georgia Institute of Technology, October 1998.
Bern and Eppstein, pages 17-18. 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."
Matthew T. Dickerson and Mark H. Montague, A (Usually?) Connected Subgraph of the Minimum Weight Triangulation, Proceedings of the Twelfth Annual Symposium on Computational Geometry (Philadelphia, Pennsylvania), pages 204-213, ACM, May 1996.
(Video.) Patrice Belleville, Mark Keil, Michael McAllister, and Jack Snoeyink, On Computing Edges That Are In All Minimum-Weight Triangulations, Fifth Annual Video Review of Computational Geometry, ACM, May 1996. See also Proceedings of the Twelfth Annual Symposium on Computation Geometry (Pittsburgh, Pennsylvania), pages V7-V8, ACM, May 1996.

No lecture on November 25 or on November 30.

Lecture 27 (December 2): Three-dimensional Delaunay refinement.

Lecture Notes on Delaunay Mesh Generation, Chapter 4.

Course Description

Applications in scientific computing, physical modeling, graphics, and geographical information systems use unstructured meshes composed of triangles, quadrilaterals, tetrahedra, hexahedra, and other simple geometric shapes. This course covers techniques for generating and modifying triangulations and other meshes. The material should be useful for students in engineering and the sciences, as well as computer science.

Topics include:

Basic results about triangulations and tetrahedralizations.
Delaunay triangulations and Voronoi diagrams.
Constrained Delaunay and conforming Delaunay triangulations.
Minimum-weight and other optimal triangulations.
Triangular and tetrahedral mesh generation techniques: Delaunay-based, quadtree-based, and advancing front.
Refinement and coarsening of simplicial meshes.
Quadrilateral and hexahedral mesh generation techniques.
Mesh improvement: node smoothing and element transformations.
Curve and surface reconstruction.
Surface approximation/decimation and progressive meshes.
Topology preservation.
Interpolation.
Geometric primitives and numerical robustness.

Students should have a thorough familiarity with fundamental data structures (CS 61B or the equivalent).

Grading

20% for Project I: A Delaunay triangulation implementation.
40% for Project II: A mesh generator or triangulator.
20% for Examination I. Here are the solutions.
20% for Examination II.

Supported in part by the National Science Foundation under Awards ACI-9875170, CMS-9980063, and EIA-9802069, and in part by a gift from the Okawa Foundation. The views and conclusions in this document are those of the author. They are not endorsed by, and do not necessarily reflect the position or policies of, the Okawa Foundation or the U. S. Government.

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