Compressing mesh geometry using spectral methods and a set partitioning algorithm

Abstract

The demand for visualizing 3D objects has been growing rapidly in recent years due to the use of 3D models in several contexts and an increasing number of applications such as computer aided design, manufacturing, defense, architecture, entertainment, etc. Accessing these models over networks is required in many cases and hence developing efficient encoding schemes has been an interesting research topic for a decade or two. VRML (Virtual Reality Modeling Language) and MPEG-4 (Motion Pictures Experts Group-4) are two multimedia standards developed for coding and displaying polygonal meshes. Coding 3D object data can take place in different domains and be classified in different ways. What primarily concerns us in this study is the progressive nature of the developed scheme. That is, while some applications may do with one instance of an encoded model and reconstruction performed on this single instance, other applications may require intermediate stages of a model that is reconstructed from coarse to fine in time. The latter case amounts to progressivity where a model can be viewed with higher and higher precision. In this work, we develop a progressive mesh geometry coder that operates on a frequently used family of polygonal meshes (i.e. triangle meshes). The tool operates on spectral coefficients obtained by the method of Karni and Gotsman and bit-plane codes these coefficients using ideas borrowed from a set partitioning sorting algorithm called SPECK (Set Partitioning Embedded Block Coder) formerly used for image coding purposes. The output code is truly embedded and our method has shown to produce results superior to those of the spectral method.