Greedy quantization of control points for 2D and 3D data using blending surfaces representation

A greedy optimization algorithm for quantization of control points is proposed. These control points define the triangular surfaces found in 2D polynomial blending coding and in VRML 3D objects. The control point quantization poses an interesting problem: each control point is shared by the neighboring triangles and, as a consequence, both the distortion and bit-rate are not independent as assumed in quantization schemes based on Lagrangian optimization. The proposed sub-optimal greedy algorithm addresses this dependency problem and significantly improves the coding performance achieved by Mayer and Langdon (see 32nd Asilomar Conference on Signals, Systems and Computers, 1998). The algorithm reduces the entropy at each iteration while introduces the least distortion possible. We also propose the extension of this algorithm for encoding 3D coordinates as found in VRML files and present results for an approximation of a sphere generated by a mesh of triangles.