Connectivity compression for three-dimensional planar triangle meshes

Graphical display of three-dimensional surfaces is the most effective means of conveying our everyday world in a computer application. Such programs are often executed remotely through a computer network. Transmission of the large amount of data required for an accurate rendering requires substantial channel bandwidth. Lossless compression algorithms for mesh data can therefore improve the performance of these computer programs. A mesh is generally represented by a list of vertices and a list of faces, each of which is a list of vertex indices. The list of faces, referred to as the connectivity data because it shows how the vertices are connected to each other, constitutes the bulk of the mesh data. In this dissertation, I propose a new reversible compression algorithm for connectivity data of a mesh.; In the new method, the connectivity of a three-dimensional object is snapped onto a two-dimensional grid before being encoded. After encoding, a lossless compression algorithm, such as Huffman coding, is used to further compress the symbol stream. The capability of this new method is demonstrated with three-dimensional planar triangle meshes. For a planar triangle, meshes containing V vertices, our technique provides between 1.4V and 3.0V bits for the connectivity cost, compared to 6Vlog₂V bits required without compression. As our approach does not depend on the vertex locations, we may separately compress the vertex data with any vertex-encoding method currently available.