A topology modifying progressive decimation algorithm

Abstract

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. The author presents 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. He describes the new progressive decimation algorithm, introduces mesh splitting operations and shows how they can be encoded as a progressive mesh. He also demonstrates 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.