Ph. D. Thesis, Department of Computer Science, Brown University, June 1998.
Jeff Vitter, Pankaj Agarwal, and John Hughes were on my thesis committee.
A central problem in computer graphics is hidden-surface removal: given a set of objects (some of which may be moving continuously), a continuously-moving viewpoint, and an image plane, maintain the scene visible from the viewpoint as projected onto the image plane. Algorithms developed for this problem in computational geometry are theoretically efficient but are often difficult to implement. On the other hand, computer graphics techniques are designed to be fast in practice but may perform badly in the worst-case.
In this thesis, we describe our efforts to bridge this gap between theory and practice in the context of hidden-surface removal. Three themes underlie our research:
- the idea of analysing algorithms in terms of the geometric complexity of the input, which encourages the development of algorithms that are provably efficient for data sets that typically arise in practice,
- the notion of a kinetic data structure, which is a mechanism for efficiently processing continuously-moving objects, and
- object complexity, a model inspired by the performance characteristics of current graphics hardware, in which algorithms simply determine which objects are visible rather than compute exactly which portions of each object are visible.
We first describe an algorithm for removing geometric and topological flaws, such as missing polygons and cracks, from the input. Next, we present our algorithm for hidden-surface removal, which is based on the novel idea of employing a kinetic data structure for ray-shooting to determine a small superset of the visible objects and efficiently maintain this set as the viewpoint moves continuously. In the last part of the thesis, we describe the Binary Space Partition (BSP), a hierarchical spatial decomposition we use to efficiently implement both our model repair and hidden-surface removal algorithms. We present our BSP construction algorithms, which work particularly well for architectural environments and terrain-like data sets.
Since the size of the thesis is about 23MB when it is uncompressed, you can download the thesis in three forms:
- The complete thesis,
- The thesis without the colour page, or
- The colour pages (three consecutive pages).