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(n log n) simplification algorithm transforming an input mesh of n vertices into a multiresolution hierarchy. Note that a single approximation having κ < n vertices is obtained in linear running time. We show that, without using these operations, mesh simplification using global error has o(n~2) computational complexity in the RAM model. Our approach uses a generalized vertex decimation method which allows for choosing the optimal vertex in the rate-distortion sense. Additionally, our algorithm can also be applied to other types of subdivision connectivity such as triangular quadrisection, e.g., obtained from Loop subdivision.