CMSC828L, Advanced Topics in Information
Processing: Geometric and Solid Modeling, Spring 2002.
Instructor: Leila De Floriani
CMSC 420, CMSC 427, or equivalents
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.
The topics and the order listed below
are tentative and subject to change.
First part (Underlying Representations):
Second Part (Modeling surfaces
and scalar fields through meshes):
- 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
- Data structures for two-dimensional
and three-dimensional simplicial 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
Third Part (Solid Modeling):
- 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.
- Representation schemes for solid
objects: Mathematical models and a taxonomy
- Boundary Representations (Brep)s:
Euler operators for constructing BReps.
- Space-based and Object-based
- Constructive Solid Geometry
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.
Notes on Solid Modeling:
- 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 Multiresolution Mesh
- A. A.G. Requicha, Geometric Modeling:
A First Course, University of Southern California, 1999 (available on-line).
Notes on Mesh Compression:
- 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
Survey papers on Mesh Simplification:
- E.Danovaro, L. De Floriani, P.
Magillo, Compression Methods for Triangle Meshes(preliminary version), Tech.
Report DISI- University of Genova, 2002
- 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
- P. Lindstrom , G.Turk, Evaluation
of Memoryless Simplification, IEEE Transactions on Visualization and Computer
pp. 98-115, April-June 1999.
- D.Luebke, Developer's Survey of Polygonal Simplification
Algorithms,IEEE Computer Graphics &Applications.