Computational Analysis of Mesh Simplification Using Global Error

Meshes with (recursive) subdivision connectivity, such as subdivision surfaces, are increasingly popular in computer graphics. They present several advantages over their Delaunay-type based counterparts, e.g., Triangulated Irregular Networks (TINs), such as efficient processing, compact storage and numerical robustness. A mesh having subdivision connectivity can be described using a tree structure and recent work exploits this inherent hierarchy in applications such as progressive terrain visualization, surface compression and transmission. We propose a hierarchical, fine to coarse (i.e., using vertex decimation) algorithm to reduce the number of vertices in meshes whose connectivity is based on quadrilateral quadrisection (e.g., subdivision surfaces obtained from Catmull–Clark or 4-8 subdivision rules). Our method is derived from optimal tree pruning algorithms used in modeling of adaptive quantizers for compression. The main advantage of our method is that it allows control of the global error of the approximation, whereas previous methods are based on local error heuristics only. We present a set of operations allowing the use of global error and use them to build an O(nlogn) simplification algorithm transforming an input mesh of n vertices into a multiresolution hierarchy. Note that a single approximation having k