Optimal bit allocation in compressed 3D models

To use 3D models on the Internet or in other bandwidth-limited applications, it is often necessary to compress their triangle mesh representations. We consider the problem of balancing two forms of lossy mesh compression: reduction of the number of vertices by simplification, and reduction of the number of bits per vertex coordinate. Let A(V, B) be a triangle mesh approximation for an original model O. Suppose that A(V, B) has V vertices, each represented using B bits per coordinate. Given a limit F on the file size for A(V, B), what are the optimal values of B and V that minimize the approximation error? Given a desired error bound E, what are optimal B and V, and how many total bits are needed? We develop answers to these questions by using a shape complexity measure K, which, for any given object approximates the product EV. We give formulae linking B, V, F, E and K, and we explore a simple algorithm for estimating K and the optimal B and V for piecewise spherical approximations of arbitrary triangle meshes. (C) 1999 Elsevier Science B.V. All rights reserved.