Surface Partitions for Progressive Loading and Display and Dynamic Simplification of Polygonal Surfaces

We present a new method for (1) automatically generating multiple Levels Of Detail (LODs) of a polygonal surface, (2) progressively loading, or transmitting, and displaying a surface, and for (3) changing interactively the LOD when displaying. We build the LODs using any algorithm that performs edge collapses and certain vertex removals to simplify surfaces, and provides an ordered list of ordered vertex pairs (edge collapse specifications). We propose a Surface Partition for encoding surface LODs: we define vertex and triangle levels during simplification; vertices and triangles are partitioned and sorted according to their level, and are passed to the display algorithm in decreasing level order, one level at a time, together with a vertex representatives array. Each level of vertices and triangles, together with higher levels and the vertex representatives, form a valid surface. We propose a data structure using a Directed Acyclic Graph (DAG) for recording a partial ordering among edge collapses, and varying the LODs across the surface.

KEY-WORDS: Edge Collapse, Vertex and Triangle Levels, Surface Levels of Detail, Surface Partition, Progressive Transmission and Display, Dynamic Simplification.