CMSC828L, Advanced Topics in Information
Processing: Geometric and Solid Modeling, Spring 2002.
Instructor: Leila De Floriani
___________________________________________________________________________________________
Prerequisites:
CMSC 420, CMSC 427, or equivalents
_____________________________________________________________________
Course Objectives:
An introduction to modeling for solid
objects, surfaces, and scalar fields. Covers applications from areas of
computer aided design, computer graphics, scientific visualization and finite
elements. Topics include boundary models for solid objects, representations
based on volumetric decompositions, constructive object models (Constructive
Solid Geometry), representations of surfaces and scalar fields through triangle
and tetrahedral meshes, mesh simplification techniques, compact encoding of
triangle and tetrahedral meshes, multi-resolution techniques.
_____________________________________________________________________
Topics:
The topics and the order listed below
are tentative and subject to change.
First part (Underlying Representations):
- Background: Basic notions from
point-set topology and from algebraic topology
- Representation for meshes:
- Topological relations in cell
and simplicial complexe
- Data structures for two-dimensional
meshes
- Data structures for two-dimensional
and three-dimensional simplicial meshes
Second Part (Modeling surfaces
and scalar fields through meshes):
- Mesh simplification:
- Approximation of surfaces and
scalar fields through meshes
- Taxonomy of simplification techniques
for triangle meshes.
- Techniques for meshes describing
two-dimensional scalar fields
- Algorithms for incremental decimation
and refinement of triangle meshes.
- Non-incremental techniques.
- Delaunay triangulation in
two and three dimensions:
- Definitions and properties in
the 2D case
- Algorithms for building and
updating a 2D Delaunay triangulation
- Delaunay triangullation
in 3D: definitions, properties and issues
- Geometric compression: compression
techniques for trianglemeshes:
- Compression of geometric information
- Triangle strips
- Techniques based on graph traversal
- Progressive techniques
- Multi-resolution models:
- The Multi-Tessellation (MT):
a framework for multiresolution modeling.
- Nested hierarchical representations
for regular meshes.
- Multi-resolution representations
based on irregular meshes.
Third Part (Solid Modeling):
- Representation schemes for solid
objects: Mathematical models and a taxonomy
- Boundary Representations (Brep)s:
Euler operators for constructing BReps.
- Space-based and Object-based
decompositions.
- Constructive Solid Geometry
Course Work:
Course work will consist of a project
and possibly some homework assignments.
There will be two exams: a midterm
and a comprhensive final.
Weights: Projects 1/3,
midterm 1/3, final exam 1/3.
__________________________________________________________________________________________
Course Material:
Recommended Books:
- C. Hoffmann, Geometric and Solid
Modeling, Morgan Kaufmann, San Mateo, California, 1989 (Chapters 1-3).
- M. Mantyla, An Introduction
to Solid Modeling, Computer Science Press, 1988.
Notes on Solid Modeling:
- A. A.G. Requicha, Geometric Modeling:
A First Course, University of Southern California, 1999 (available on-line).
Notes on Multiresolution Mesh
Representation:
- L. De Floriani, P. Magillo, Multi-resolution
Mesh Representations - Models and Data Structures, European School on Multiresolution
Geometric European School on Multiresolution Geometric Modeling, 2001 (available
on-line).
Notes on Mesh Compression:
- E.Danovaro, L. De Floriani, P.
Magillo, Compression Methods for Triangle Meshes(preliminary version), Tech.
Report DISI- University of Genova, 2002
Survey papers on Mesh Simplification:
- M. Garland, Multiresolution modeling:
Survey and Future Opportunities, Eurographics'99, State-Of-The-ART Report.
- P.Heckbert and M.Garland, Survey of Polygonal Surface
Simplification Algorithms, CMU- Technical Report 1997, Course Notes
SIGGRAPH1997.
- P. Lindstrom , G.Turk, Evaluation
of Memoryless Simplification, IEEE Transactions on Visualization and Computer
Graphics, 5(2),
pp. 98-115, April-June 1999.
- D.Luebke, Developer's Survey of Polygonal Simplification
Algorithms,IEEE Computer Graphics &Applications.
(May 2001).