GVU Technical Report Number:
GIT-GVU-99-08
Title:
Wrap & Zip: Linear decosing of planar triangle graphs
Authors:
Jarek Rossignac
Andrzej Szymczak
Abstract:
The Edgebreaker compression technique, introduced by Rossignac, 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 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 Edgebreaker, 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.
Keywords:
Compression, triangle mesh, connectivity, 3D representations
You can access this technical report via:
PDF
Postscript
|
