Instructor: Dr.Leila De Floriani 

________________________________________________________________

Prerequisites:

• MATH 240, CMSC 420 (or equivalent), or permission of instructor.
• Knowledge of basic algorithmic techniques
• Knowledge of basic data structures
  

_____________________________________________________________________

Graduate Credit:

The course counts for both MS and Ph.D. qualifying coursework. It can be used to satisfy the MS qualifying exam and the PhD core in the area of Visual and Geometric Computing. 
_____________________________________________________________________

Course Objectives:

An introduction to modeling geometric shapes, such as solid objects, free-form surfaces, 2D and 3D scalar fields. Topics include boundary and volumetric representations for solid objects, mesh-based representations for solid objects, free-form surfaces and  scalar fields, algorithms for generatingtriangle and tetrahedral meshes, mesh simplification techniques, compression techniques for triangle and tetrahedral meshes, multi-resolution mesh-based representations, topology-based representations for 3D shapes and 2D scalar fields.  It covers applications  from areas of computer graphics, scientific
visualization, computer aided design,  finite element analysis and animation.

_____________________________________________________________________

Detailed Outline:

The topics and the order in which they are listed below are tentative and subject to change

• Preliminaries:

• Basic elements from Euclidean geometry (by Prof. Mount)

• Basic elements of point-set topology: topological spaces, metric spaces, manifolds.

• Notions from combinatorial topology: cell and simplicial complexes (meshes), pseudo-manifolds, combinatorial  manifolds.

• Mesh-based  shape representations:

• Mesh-based representations of shapes in two, three and arbitrary dimensions.

• Topological relations in cell and simplicial complexes. 

• Representations for two-dimensional  manifold cell complexes.

• Representations for triangle and tetrahedral complexes: adjacency-based, incidence-based and edge-based representations.

• Representations for simplicial complexes in arbitrary dimensions.

• Computing mesh-based representations (by Prof. Mount):

• Convex hull of a set of points.

• Polygon triangulation.

• Triangulation of a set of points.

• Delaunay triangulation: basic definitions and properties, an incremental algorithm.

• Relations between Delaunay triangulation and Voronoi diagram

• Delaunay tetrahedralization

• Mesh simplification:

• Approximation of surfaces and scalar fields through triangle and tetrahedral  complexes.

• Techniques for meshes describing two-dimensional scalar fields.

• Algorithms for incremental decimation and refinement of triangle and tetrahedral meshes.

• Non-incremental techniques.

• Mesh compression:

• Compression of geometric information.

• Compression of connectivity information.

• Triangle strips

• Techniques based on graph traversal.

• Progressive techniques.

• Multi-resolution mesh-based shape modeling:

• Hierarchical representations of triangle meshes for point location: Kirkpatrick’s method, History DAGs (by Prof. Mount).

• Multi-resolution representations  based on  irregular triangle and tetrahedral meshes.

• Multi-resolution representations based on nested triangle and tetrahedral meshes.

• Applications: terrain modeling, volume data visualization

• Topology-based shape modeling:

• Topological shape descriptors: classification

• Reeb graphs 

• Medial Axis Transform

• Morse-Smale decomposition of 2D scalar fields

• Modeling schemes for solid objects:

• Basic definitions and properties 

• A taxonomy of modeling schemes

• Boundary representations (Breps): data structures, Euler operators, Boolean operators

• Space-based and object-based  decompositions

• Constructive representations: Constructive Solid Geometry (CSG)
  

---

Course Work

The course will have a midterm and a final (not comprehensive) exam.
Tentative weights: midterm 25-30% and final 30%.

The rest of the work (which will account for 40-45%  of the final grade) will be a reading project,  in which  students will be required to summarize,  compare, classify and analyze papers  in a subfield, complementary to the  subjects covered in class,  or a project on the design, analysis and possible implementation of some new  representation,  or  a programming project.
The students will be required to do a short presentation of their work in class.

________________________________________________________________________ __________________
 

Course Material

The course does not have a required textbook, but we will cover chapters from books, and survey papers. A copy of the slides used in class will be available from the course Web page

• Course notes in the form of slides (the slides are quite detailed to be  used as course notes)

• M. de Berg, M.van Kreveld, M.Overmars, O. Schwarzkopf, Computational Geometry, Springer Verlag, 1998 (available in CS library) - for the lectures given by Prof.Mount

• Survey papers on multi-resolution models, mesh simplification, mesh compression, topology-based shape modeling, data structures for simplicial meshes (they will be  made available from the course Web page)

• Notes on solid modeling:  A. A.G. Requicha, Geometric Modeling: A First Course, University of Southern California, 1999 (available on line )

• The following recommended books (available in CS library):

• H.Edelsbrunner, Geometry and Topology for Mesh Generation, Cambridge University Press, 2001(available in CS library).

• D. Luebke, M. Reddy,  J.Cohen, A. Varshney, B. Watson, R. Huebner, Level Of Detail for 3D Graphics, Morgan Kaufmann, 2002 (available in CS library).
  

• C. Hoffmann, Geometric and Solid Modeling, Morgan Kaufmann, San Mateo, California, 1989 (Chapters 1-3). (available on line and a copy in CS library )

• M. Mantyla, An Introduction to Solid Modeling, Computer Science Press, 1988. (available in CS library)

• A. Paoluzzi, Geometric Programming for Computer-Aided Geometric Design, John Wiley and Sons, 2003(available in CS library)

• M.K.Agoston, Computer Graphics and Geometric Modeling: Mathematics, Springer Verlag, 2005 (available in  CS library)

• Useful software and sample data sets: see here

• Notes by Annie Hui on how to create non-manifold shapes by using Wings3D: see here
  

___________________________________________________________________________________


Lecture schedule:

• Sept.2:    Course Introduction - Elements of point-set topology [sections 1 and 2]
• Sept.9:  
• Elements of point-set topology [section 2]
• Basic notions from Euclidean geometry (prof. Mount) [section 4]
• Sept.16 :    Cell and simplicial complexes [section 3]  
• Sept. 23:    Computing mesh-based representations - part 1 (prof. Mount) [section 5]
• Convex hulls
• Polygon triangulation
  
• Sept. 30:    Computing mesh-based representations - part 2 (prof. Mount): [section 6]
• Voronoi diagrams and Delaunay triangulations: properties
• Computing the Delaunay triangulation
• Oct. 7: Combinatorial characterization of shapes [section 7]
• Oct.14:
• Topological relations in cell and simplicial complexes [section 8]
• Data structures for manifold 2D cell complexes [section 9]
• Oct. 21: 
• Data structures for manifold 2D cell complexes [section 9]
  
• Data structures for triangle meshes [section 10]
• Oct. 28: Data structures for triangle and tetrahedral meshes [section 10]
• Nov. 4:
• Dimension-specific representations [section 11]
• Nov.11: 
• Planar point location [section 12]
• Nov. 18: 
• Dimension-independent representations [section 13]
  
• Incremental modifications of Delaunay meshes [section 14]
• Dec. 2:
  
• Representation schemes for solid modeling [section 15]
• Mesh simplification [section 16]
  

____________________________________________________________________________