Computational Topology Algorithms for Discrete 2-Manifolds

Author: Wood, Zoë Justine

Year: 2003

Degree: Dissertation (Ph.D.)

Advisor: Schroeder, Peter

Committee Members: Schroeder, Peter; Barr, Alan H.; Hoppe, Hugues; Desbrun, Mathieu; Perona, Pietro

Option: Computer Science

Abstract

This thesis presents computational topology algorithms for discrete 2-manifolds. Although it is straightforward to compute the genus of a discrete 2-manifold, this topological invariant does not tell us enough for most computer graphics applications where we would like to know: what does the topology look like? Genus is a scalar value with no associated geometric appearance. We can, however, isolate geometric regions of the surface that are topologically interesting. The simplest topologically interesting, and perhaps most intuitive, regions to consider are those with genus equal to one. By isolating and examining such regions we can compute measures to better describe the appearance of relevant surface topology. Thus, this work focuses on isolating handles, regions with genus equal to one, in discrete 2-manifolds.

In this thesis, we present novel algorithms guaranteed to identify and isolate handles for various discrete surface representations. Additionally, we present robust techniques to measure the geometric extent of handles by identifying two locally minimal-length non-separating cycles for each handle. We also present algorithms to retain or simplify the topology of a reconstructed surface as desired. Finally, the value of these algorithms is demonstrated through specific applications to computer graphics. For example, we demonstrate how geometric models can be greatly improved through topology simplification both for models represented by volume data or by triangle meshes.

The contributions of this work include:

A robust and efficient method for identifying and isolating handles for discrete 2-manifolds.
A method to robustly represent the topology of the surface with an augmented Reeb graph.
A robust method to find two locally minimal-length non-separating cycles for each handle.
A simple method to simplify the topology for volume data and triangle meshes which preserves the local geometry as much as possible.
An out-of-core method for topology simplification for volume data.

Files

phd_thesis.pdf (application/pdf)