CMSC828D, Advanced Topics
in Information Processing: Geometric and Solid Modeling, Fall
2003
Instructor: Dr. Leila
De Floriani
____________________________________________________________________
Prerequisites:
CMSC 420, CMSC 427, or equivalents
_____________________________________________________________________
Graduate Credit:
Course counts for both MS and Ph.D. qualifying coursework
_____________________________________________________________________
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, and
Level-Of-Detail (LOD) techniques.
_____________________________________________________________________
Detailed Outline:
The topics and the order in which they are listed below
are tentative and subject to change
- Some background notions from
- point-set topology (mathematical models of objects)
- algebraic topology
(cell and simplicial complexes (meshes))
- Representations for cell and simplicial complexes
- Topological relations in cellular and simplicial complexes
(meshes)
- Data structures
for two-dimensional cellular complexes
- Data structures
for triangle and tetrahedral meshes
- Data structures
for meshes in higher dimensions
- Representation schemes for solid objects
- Representations for solid objects: properties and issues
- A taxonomy of representations
schemes
- Boundary Representations
(Breps)
- Space-based and
object-based decompositions
- Constructive Solid
Geometry (CSG)
- Building triangle and tetrahedral meshes
- Delaunay triangulation in two and three dimensions: definitions
and properties
- Algorithms for building
and updating a Delaunay mesh
- Surface reconstruction
algorithms
- Mesh simplification
- Approximation of surfaces and scalar fields through triangle
and meshes
- Taxonomy of simplification
techniques for triangle meshes
- Techniques for meshes
describing two-dimensional scalar fields
- Algorithms for incremental
decimation and refinement of triangle and tetrahedral meshes
- Non-incremental
techniques
- Geometric compression: compression techniques for triangle
and tetrahedral meshes
- Compression of geometric information
- Compression of connectivity
information
- Triangle strips
- Techniques based
on graph traversal
- Progressive techniques
- Level-Of-Detail (LOD) modeling
- The Multi-Tessellation (MT): a dimension-independent framework
for LOD modeling
- Nested hierarchical
representations for regular meshes
- LOD representations
based on irregular meshes
- Applications: virtual
reality, terrain modeling and visualization, scientific visualization
Course Work:
Course work will
consist of a reading project in which the students would be required to summarize
and compare papers related to the material
taught in class or a programming project, if requested by the
students.
There will be two
exams: a midterm and a final exam.
Weights: Project 1/3, Midterm 1/3, Final 1/3
________________________________________________________________________
__________________
Course Material
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. de
Berg, M.van Kreveld, M.Overmars, O. Schwarzkopf, Computational
Geometry, Springer Verlag, 1998 (available in CS library)
Notes on Solid Modeling:
- A. A.G. Requicha, Geometric Modeling: A First Course, University
of Southern California, 1999 (available on line )
Surevey papers on LOD Modeling:
- L. De Floriani, P. Magillo, Multiresolution mesh representation:
Models and data structures, In Multiresolution in Geometric Modeling,
M.Floater and A.Iske and E.Quak (Editors), Springer-Verlag, 2002,
pp. 363-418
- E. Danovaro, L.
De Floriani, P. Magillo, E. Puppo, Data structures for 3D Multi-Tessellations:
an Overview, in: F.H.Post
G.P.Bonneau, and G.M.Nielson (Editors), Proceedings of the
Dagstuhl Scientific Visualization Seminar, Kluwer Academic Publishers,
2003.
Survery paper on Mesh Compression:
- E.Danovaro, L. De Floriani, P. Magillo, Compression Methods
for Triangle Meshes (preliminary version), Tech. Report University
of Genova, Genova (Italy), 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, 21(3), pp. 24-35, May 2001.
Triangle-segment
meshes:
- L. De Floriani, P. Magillo, E. Puppo, D.Sobrero, A Multi-Resolution
Topological Representation for Non-manifold Meshes, Proceedings Solid
Modeling 2002, Saarbruecken, Germany, June 2002.
___________________________________________________________________________
L