Paola Magillo - PhD Thesis
This page contains pointers to my PhD thesis, entitled
"Spatial Operations on Multiresolution Cell Complexes"
which I defended
on February, 1999 at the Dipartimento di Informatica e Scienze
dell'Informazione of the University of Genova, Italy.
Cell complexes are used for modeling geometric entities
in several application fields.
In this approach, an object of arbitrary shape is represented through an
aggregation of simple, basic shapes, called cells.
A high number of cells is necessary to obtain accurate descriptions,
thus involving high costs for managing a complex.
Costs can be reduced by locally adapting the
resolution of a complex to the needs of each task.
A multiresolution complex is a structure which encodes
alternative representations of a geometric entity
at different resolution, and can be inquired by the user
to retrieve any of such complexes.
Several multiresolution models for cell complexes have been
proposed in the literature, but the field still lacks of a
In this thesis, we propose a general model for multiresolution cell
complexes, which encompasses most existing proposals, and
we define standard access operations for such a model.
We specialize the model and its operations for case-study
applications, with the design of data structures and algorithms:
selected applications include the representation of terrains,
of free-form surfaces, of three-dimensional scalar fields,
and of the volume of solid objects.
Experimental results from prototype implementations are reported.
Table of Contents and pointers to files
- Title page, Abstract, Table of Contents:
(6 unnumbered pages + pages 1-7)
- Some Basic Concepts
- Motivations and Goals
- Contributions of the Thesis
- Thesis Outline
- Basic Geometric Entities
- Cell Complexes and their Properties
- Approximation of Geometric Entities through Cell Complexes
- Applications of Cell Complexes
- Mesh Compression
- Case-Study Topics
- Previous and Related Work:
- Building an Approximated Cell Complex
- Multiresolution Models
- Compression of Triangle Meshes
- A Model for Multiresolution Cell Complexes:
- The Multi-Complex
- Adjacency Relations in a Multi-Complex
- Evaluating the Quality of a Multi-Complex
- Existing Multiresolution Models as Multi-Complexes
- Querying a Multiresolution Cell Complex:
- Query Operations on Multiresolution Complexes
- Algorithms for Global Queries
- Algorithms for Local Queries
- A Dynamic Approach to Global Queries
- Experimental Results
- A Specification of Query Operations on an MC
- Data Structures and Algorithms:
- Generation of Adjacency Relations in the Output Mesh
- General-Purpose Data Structures
- Compressed Data Structures
- A Data Structure for Secondary Storage
- Construction of a Multiresolution Cell Complex:
- Histories and History Generators
- From a History to a Multi-Complex
- A Specification of Operations for the Construction of an MC
- Influence of the History Generator on Quality of a Multi-Complex
- Applications of the Multi-Complex:
- Terrains in Geographic Information Systems
- Approximation of Surfaces
- Reconstruction of Solid Objects
- Volumetric Data Visualization
- Progressive Compression of Triangle Meshes
- A Software Library Based on the Multi-Complex
- Concluding Remarks:
- Main Contributions
- Current and Future Developments
- Open Problems}
The thesis can be references as:
"Spatial Operations on Multiresolution Cell Complexes", PhD Thesis,
Report No. DISI-TH-1999-03,
Dipartimento di Informatica e Scienze dell'Informazione,
University of Genova, Italy, 1999.