CPS296.2: Advanced Topics in Computer Science
Mesh Generation

Fall 2002

MW 10:20-11:35am

LSRC D243

Alper Üngör
course ad announcements schedule homeworks references syllabus

Mesh generation finds numerous applications in scientific computing, computer graphics, solid modeling, computer aided design, geographic information system, and medical imaging. In modeling the problems in these applications, the domains are partitioned into meshes consisting of small and simple elements (e.g. triangles, quadrilaterals, tetrahedra and hexahedra). Design and analysis of unstructured mesh generation algorithms will be the main theme in this course.

Announcements

Schedule (tentative)

Date Lecture Topic Assignments
Aug 26 M Syllabus, course structure, etc. HW#0 out [ps, pdf]
Aug 28 W Triangulations and convex hulls [BKOS00, Chapter 1 & 11]: definitions; plane sweep algorithms; point set triangulations; amortized analysis; orientation test  
Sep 2 M Triangulations and convex hulls: Jarvis' march [J73]; Graham's scan [G72, A79], Chan's algorithm [C96]; polygon triangulations, size complexity, existence, finding diagonals, a recursive algorithm HW#1 out [ps, pdf]
Sep 4 W Polygon triangulations[BKOS00, Chapter 3]: triangulating monotone polygons; partitioning simple polygons into monotone polygons; coloring a triangulation; dual of a triangulation  
Sep 9 M Planar straight line graphs[E01, Chapter 2; BKOS00, Chapter 3]: definitions, triangulations, algorithm
Voronoi diagrams and Delaunay triangulations [E01, Chapter 1; BKOS00, Chapters 7 & 9]: definitions, duality, empty-circle property, embedding 		HW#1 due
Sep 11 W Delaunay triangulation algorithm [E01, Chapter 1]: edge-flip, algorithm, local Delaunay condition, lifting to paraboloid, incircle test, termination, flip-connectivity, max-min angle property, worst-case construction Graded HW#1 out
Sep 16 M Int. Meshing Roundtable, Ithaca NY(no class) HW#2 out [ps, pdf]
Sep 18 W  
Sep 23 M Randomized incremental DT algorithm [E01, Chapter 1; BKOS00, Chapter 9]: open problem: flip graph in 3D; incremental algorithm, proof of correctness, randomized analysis, point location[MSZ99], history DAG, searching time  
Sep 25 W Data Structures [GS85]: quad-edge structure, triangle-based structure, comparison
Element quality measures[TW00] smallest angle, largest angle, aspect ratio, radius-edge ratio, equivalence
Constrained/conforming Delaunay triangulations[E01] 		HW#2 due
Sep 30 M Delaunay Refinement[E01]: algorithm; Chew's and Ruppert's versions; quality guarantee, packing argument, local feature size, size optimality HW#3 out [ps, pdf]
Oct 2 W This class is moved to Oct 18 Friday  
Oct 7 M 3D Delaunay Refinement[E01]: Schönhardt's and Chazelle's polyhedra, Chew's and Schewchuk's algorithms, slivers Graded HW#2 out
Oct 9 W Optimal triangulations[BE95]: min-max angle, min-max height, edge-insertion, anchor property; min weight triangulation, min max area triangulation
Quad-tree refinement[BE95]: splitting, balancing, warping; 		HW#3 due
Project proposal due
Oct 14 M Fall Break (no class)  
Oct 16 W Nonobtuse triangulations [BE95, BE92]: motivation; no large vs. no small angles; optimality of non-obtuse triangulations: max-min angle, min-max angle, max-min height; slab algorithm; HW#0 due
Oct 18 F Acute and nonobtuse triangulations [BE95,BMR95]: circle-packing algorithm; space-filling tetrahedra, almost regular triangulations, acute tilings, space, slab; quality of tilings, open problems Graded HW#3 out
Oct 21 M Cubical meshing: cubical complex; transforming a simplicial complex into a cubical complex through refinement/coarsening HW#4 out [ps, pdf]
Oct 23 W Quadrilateral and hexahedral meshing: existence; flipping cubical meshes [BEE02]; circle-packing [BE96]; heuristics: advancing front methods (paving, plastering), mapping, duality and whisker weaving;  
Oct 28 M Sphere packings [LTU99]: well-spaced point set, simulatenous refinement and coarsening, adaptive meshing;  
Oct 30 W Smoothing and optimization [ABE99]:: Laplacian smoothing; LP-type optimization;
Sliver removal [E01, ELMSTTUW00]: orthosphere, weighted Delaunay, perturbation 		HW#4 due
Nov 4 M Parallel mesh generation [STU02] conflicts and independence, parallelizing Chew's algorithm, parallelizing Ruppert's algorithm, edge classes.  
Nov 6 W Space-time meshing [EGSU02]:  
Nov 11 M Terrain reconstruction by Till Brenner  
Nov 13 W Shelling by Hai Yu  
Nov 18 M Software and 3D printer demo
by Vijay Natarajan (meet at the Algorithms lab) 		 
Nov 20 W Conference travel ( no class)  
Nov 25 M Hierarchical unstructured mesh generator for discretization of solids
by Tian Xiao 		Project report due
Nov 27 W Hexahedron based mesh generation for quasi-3D objects
by Gang Zhao 		 

References

Books
[E01]
H. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge Univ. Press, England, 2001. [course textbook]
[BKOS00]
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd edition, 2000.
Surveys
[B02]
M. Bern. Adaptive mesh generation. pp. 1-46 of Error Estimation and Adaptive Discretization Methods in Computational Fluid Dynamics, T. Barth and H. Deconinck (ed.), Springer-Verlag, Heidelberg, 2002.
[BE95]
M. Bern and D. Eppstein. Mesh generation and optimal triangulation. pp. 47-123 of Computing in Euclidean Geometry (2nd ed.), D.-Z. Du and F. Hwang (eds.), World Scientific, 1995.
[BP99]
M. Bern and P. Plassmann. Mesh generation. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds., Elsevier Science, 1999.
[E00]
H. Edelsbrunner. Triangulations and meshes in computational geometry. Acta Numerica, (2000), 133-213.
[TW00]
S.-H. Teng and C. W. Wong. Unstructured mesh generation: Theory, practice, and perspectives. Int. J. Computational Geometry & Applications, 10(3):227-266, Jun 2000
Other Papers
[ABE99]
N.Amenta, M. Bern and D. Eppstein. Optimal Point Placement for Mesh Smoothing. J. Algorithms 30:302-322, 1999
[A79]
A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters 9(5):216-219, 1979. [A left-to-right variant of Graham's scan]
[BE92]
M. Bern and D. Eppstein. Polynomial-Size Nonobtuse Triangulation Of Polygons. Int. J. of Comp. Geom. & Appl., 2:241-255, 1992
[BE96]
M. Bern and D. Eppstein. Quadrilateral Meshing by Circle Packing Int. J. of Comp. Geom. & Appl., 10(4):347-360, 1996
[BEE02]
M. Bern, D. Eppstein, and J. Erickson. Flipping cubical meshes. To appear in Engineering with Computers, 2002
[BMR95]
M. Bern, S. Mitchell, and J. Ruppert. Linear Size Nonobtuse Triangulation Of Polygons. Discrete & Computational Geometry,14:411-428, 1995
[C96]
T. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry 16:361-368, 1996.
[EGSU02]
J. Erickson, D. Guoy, J. Sullivan, and A. Üngör. Building space-time meshes over arbitrary spatial domains. Proceedings of the 11th International Meshing Roundtable, 391-402, 2002.
[G72]
R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters 1:132-133, 1972.
[GS85]
L. J. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics 4(2): 74-123 (1985)
[J73]
R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters 2:18-21, 1973.
[MSZ99]
E. P. Mücke, I. Saiass, B. Zhu. Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations. Computational Geometry 12(1-2):63-83, 1999.
[STU02]
D. Spielman, S.-H. Teng, and A. Üngör. Parallel Delaunay Refinement: Algorithms and Analyses. Proceedings of the 11th International Meshing Roundtable, 205-217, 2002.

Syllabus

Download the syllabus in [ps, pdf].

course ad announcements schedule homeworks references syllabus

Alper Üngör (ungor@cs.duke.edu) August 2002