Progressive Mesh Decomposition in the Operational Rate-Distortion Sense Using Global Error

Proceedings, 10th International Meshing Roundtable, Sandia National Laboratories, pp.57-69, October 7-10 2001

MESHING
RESEARCH
CORNER

10th International Meshing Roundtable
Newport Beach, California, U.S.A.
October 7-10, 2001

Visual and Geometric Computing IBM T.J. Watson Research Center, USA
Email: balmelli@us.ibm.com

Abstract
Given a semi-regular mesh whose subdivision connectivity is obtained with the 4-8 scheme, we propose an algorithm to decompose the mesh into a control mesh and a series of embedded detail meshes. Hence, the output representation is adaptive and progressive. We use a tree-driven, fine to coarse approach to simplify the mesh using vertex decimation. Previous approaches use local error and greedy strategies to simplify meshes. Our method uses global error and a generalized vertex decimation technique borrowed from optimal tree pruning algorithms used in compression. Although global error is used, our algorithm has cost e(nlogn). We show that a direct approach using the same error criterion has at least cost 9(n2). We have a rate-distortion framework: each approximation satisfies a constraint in rate (e.g. number of triangles) while minimizing the distortion (e.g. distance in 12 norm with the input mesh). The algorithm aims at the optimal approximations in the rate-distortion sense. We analyze the optimality of the algorithm and give several proofs for its properties. Our algorithm can be applied to meshes obtained -ith other subdivision schemes (e.g. Loop, Catmull-Clark,...) and has also applications in compression and finite element analysis.

Download Full Paper (Postscript Format)