CMSC 741: Geometric and Solid Modeling (Fall 2010)

Course Information

Location

CSIC 3118

Meeting times

Fridays 9:00-11:30 AM

Instructors

Hanan Samet

Email

hjs

( at )

cs.umd.edu

Office

AVW 4425

Office Hours

TBD

Leila De Floriani

Email

deflo

( at )

umiacs.umd.edu

Office

AVW 3213

Office Hours

TBD

Kenneth Weiss

Email

kweiss

( at )

cs.umd.edu

Office

AVW 3212

Course Objectives

An introduction to modeling for solid objects, surfaces, and scalar fields. Covers fundamental concepts from areas of computer aided design, computer graphics, scientific visualization, finite elements and spatial indexing. Topics include boundary models for solid objects, object representations based on volumetric decompositions, constructive object models, representations of shapes in two, three and higher dimensions through simplicial meshes, mesh simplification techniques, morphological representations of shapes and multiresolution models.

Graduate Credit

Course counts for both MS and Ph.D. qualifying coursework in the Visual and Geometric Computing area.

Prerequisites

CMSC 420, CMSC 427, or equivalents.

Course Work

Course work will consist of a semester-long project in which the students will be required to evaluate existing ideas through implementation and experimentation or through an open-ended research project which can lead to publication. There will be two exams: a midterm and a final exam.

Weights: Project 1/3, Midterm 1/3, Final 1/3.

Detailed outline

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

Preliminaries

• Basic elements of point-set topology: topological spaces, metric spaces, manifolds.
• Notions from combinatorial topology: cell and simplicial complexes (meshes), pseudo-manifolds, combinatorial manifolds.

Spatial data structures and indexing methods

• Sorting in space.
• Space-based shape representations: Region quadtrees, octrees and kD-trees.
• Object-based shape representations: BSP-trees; PM-quadtrees, octrees and kD-trees.
• Hierarchical representations for point location.

Mesh-based shape models

• Cell and simplicial complexes for shape representation.
• Boundary representations for three dimensional shapes.
• Volumetric decompositions of shapes.
• Combinatorial shape characterization: manifold and non-manifold.

Data structures for mesh-based shape models

• Data structures for two-dimensional shapes discretized as cell complexes.
• Data structures for triangle and tetrahedral complexes: adjacency-based, incidence-based and edge-based representations.
• Data structures for simplicial complexes in arbitrary dimensions.

Generating shape representations

• Euler operators for boundary representations of three dimensional shapes.
• Delaunay triangulation and tetrahedralization: basic definitions and properties, an incremental algorithm.
• Relations between Delaunay triangulation and Voronoi diagram.
• Constructive Solid Geometry (CSG).

Multiresolution mesh-based shape modeling

• Approximation of shapes through triangle and tetrahedral complexes.
• Algorithms for incremental decimation and refinement of triangle and tetrahedral meshes.
• Multiresolution representations based on irregular triangle and tetrahedral meshes.

Multiresolution models for scalar fields

• Multiresolution representations based on nested simplicial complexes.
• Nested simplicial bisection schemes.
• Clustering techniques for crack-free approximations.
• Applications: terrain modeling, volume data visualization.

Morphology-based shape modeling

• Morphological shape descriptors based on Morse theory.
• Algorithms for computing Morse- and Morse-Smale complexes.
• Shape segmentation through Morse- and Morse-Smale complexes.
• Reeb graphs.