Polygonal Simplification

Download a copy of my doctoral dissertation, completed in the summer of 1998 (19 Mb).

HTML version of my dissertation defense presentation.

My SIGGRAPH paper, written with Carl Erikson, summarizes the ideas presented in my thesis.

Polygonal simplification is the study of how to automatically simplify polygonal models without losing too much visual fidelity. For example, suppose I've got a beautifully crafted, 10,000 polygon model of chair that I intend to use in an architectural walkthrough. There's no point in using those 10,000 polygons if the chair is going to end up covering only a few pixels on the screen. A 10-polygon version of the chair could undoubtably be made that would do the job just as well under these circumstances.

Polygonal simplification is at once a very current and a very old topic in computer graphics. As early as 1976 James Clark described the benefits of representing objects within a scene at several resolutions, and flight simulators have long used hand-crafted multi-resolution models of airplanes to guarantee a constant frame rate . With the mainstream debut of 3-D CAD and workstation-based computer graphics, recent years have seen a flurry of research into generating such multi-resolution representations of objects automatically by simplifying the polygonal geometry of the object.

My thesis introduces hierarchical dynamic simplification (HDS), a new framework for polygonal simplification with some novel features. HDS is dynamic, retessellating the scene continually as the user's viewing position shifts, and global, processing the entire database without first decomposing the environment into individual objects. The resulting system enables real-time display of very complex polygonal CAD models consisting of thousands of parts and millions of polygons. HDS supports various preprocessing algorithms and various run-time criteria, providing a general framework for dynamic view-dependent simplification.

Briefly, HDS works by clustering vertices together in a hierarchical fashion. The simplification process continually queries this hierarchy to generate a scene containing only those polygons that are important from the current viewpoint. When the volume of space associated with a vertex cluster occupies less than a user-specified amount of the screen, all vertices within that cluster are collapsed together and degenerate polygons filtered out. HDS maintains an active list of visible polygons for rendering. Since frame-to-frame movements typically involve small changes in viewpoint, and therefore modify this list by only a few polygons, the method takes advantage of temporal coherence for greater speed.

Some pictures from the paper: