A topology modifying progressive decimation algorithm

Triangle decimation techniques reduce the number of triangles in a mesh, typically to improve interactive rendering performance or reduce data storage and transmission requirements. Most of these algorithms are designed to preserve the original topology of the mesh. Unfortunately, this characteristic is a strong limiting factor in overall reduction capability, since objects with a large number of holes or other topological constraints cannot be effectively reduced. In this paper we present an algorithm that yields a guaranteed reduction level, modifying topology as necessary to achieve the desired result. In addition, the algorithm is based on a fast local decimation technique, and its operations can be encoded for progressive storage, transmission, and reconstruction. In this paper we describe the new progressive decimation algorithm, introduce mesh splitting operations and show how they can be encoded as a progressive mesh. We also demonstrate the utility of the algorithm on models ranging in size from 1,132 to 1.68 million triangles and reduction ratios of up to 200:1.