(
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:
Resources for dealing with robustness problems in your projects
(in increasing order of difficulty):
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 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 14 (October 7):
Andy Neureuther on surface simplification.
Jason Riedy on the Whisker Weaving algorithm for
hexahedral mesh generation.
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.
Lecture 22 (November 9):
Okan Arikan on approximating height fields.
Tolga Goktekin on view-dependent progressive meshes.
Lecture 23 (November 11):
Maryann Simmons on comparing algorithms for two-dimensional Delaunay
triangulation.
Fran輟is 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
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.)