
Progressive Mesh Decomposition in the Operational RateDistortion Sense Using Global Error
Balmelli, Laurent
Proceedings, 10th International Meshing Roundtable, Sandia National Laboratories, pp.5769, October 710 2001

IMR PROCEEDINGS

10th International Meshing Roundtable
Newport Beach, California, U.S.A.
October 710, 2001
Visual and Geometric Computing IBM T.J. Watson Research Center, USA
Email: balmelli@us.ibm.com
Abstract
Given a semiregular mesh whose subdivision connectivity is obtained with the
48 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 treedriven, 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 ratedistortion 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 ratedistortion 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, CatmullClark,...) and has also applications in compression and finite
element analysis.
Download Full Paper (Postscript Format)
Contact author(s) or publisher for availability and copyright information on above referenced article
