Wrap&zip: Linear decoding of planar triangle graphs

The Edgebreaker compression technique, introduced in [11], encodes any unlabeled triangulated planar graph of t triangles using a string of 2t bits. The string contains a sequence of t letters from the set {C, L, E, R, S} and 50 % of these letters are C. Exploiting constraints on the sequence, we show that the string may in practice be further compressed to 1.6t bits using model independent codes and even more using model specific entropy codes. These results improve over the 2.3t bits needed by Keeler and Westbrook [6] and over the various 3D triangle mesh compression techniques published recently, which all exhibit larger constants or non-linear worst case storage costs. As in [11], we compress the mesh using a spiraling triangle-spanning tree and generate the same sequence of letters. Edgebreaker's decompression uses a look-ahead procedure to identify the third vertex of split triangles (S letter) by counting letter occurrences in the remaining part of the sequences. We introduce here a new decompression technique, which eliminates this look-ahead and thus exhibits a linear asymptotic time complexity. Wrap&zip converts the string into the corresponding triangle-spanning tree and assigns orientations to each one of its free edges. During that “wrapping ” process, whenever two consecutive edges point to the same vertex, it glues them together, possibly continuing the “zip ” along the next pair of edges that just became adjacent. By labeling the vertices according to the order in which they first appear in the triangle-spanning tree, this compression approach may be used to encode the connectivity (incidence of labeled graphs) of three-dimensional triangle meshes that are homeomorphic to a sphere. Being able to decompress connectivity prior to vertex locations is essential for the most advanced geometry compression schemes, which use connectivity to predict the location of a vertex from the location of its previously decoded neighbors