Implementing progressive meshes using a topologically robust data structure

Abstract

In this thesis I address the level-of-detail (LOD) problem and its relevance to real-time rendering of complex polygonal meshes. In computer graphics there has always been a need to create detailed geometric models for display. However, there is a trade-off between level of detail and efficient rendering of a model. One solution to this problem, the progressive mesh (PM), was developed recently by Hugues Hoppe. Progressive meshes allow for loss-less, smooth level-of-detail (LOD) control that is ideal for real-time applications. A progressive mesh can smoothly refine itself to better approximations of the original mesh based on selective refinement criteria. Development of robust data structures to efficiently store mesh data is also a major problem in computer graphics. A robust data structure guarantees topological consistency. Efficient storage entails vertex information, mesh connectivity, and rendering information be organized in a compact, yet accessible, manner. Such a robust and efficient structure, the Doubly Linked Face List (DLFL), has recently been introduced. The DLFL structure maintains the two manifold property for a mesh while providing methods for manipulating the data. My approach to solving the LOD problem involves using Hoppe's progressive mesh scheme along with the DLFL mesh representation. In this thesis I discuss the background, methodology, and details needed to implement progressive meshes using the DLFL data structure.