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

in the form of slides (the slides are quite detailed to be used as course notes)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

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)Survey papers

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

The following

(available in CS library):recommended books

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)

see hereUseful software and sample data sets:

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

___________________________________________________________________________________

Lecture schedule:

____________________________________________________________________________

- Sept.2:
CourseIntroduction - 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]