Guaranteed 3.67V Bit Encoding of Planar Triangle Graphs
Davis King, Jaroslaw R. Rossignac · 1999
We present a new representation that is guaranteed to encode any planar triangle graph of V vertices in less than 3.67V bits. Our code improves on all prior solutions to this well studied problem and lies within 13% of the theoretical lower limit of the worst case guaranteed bound. It is based on a new encoding of the CLERS string produced by Rossignacs Edgebreaker compression [Rossignac99]. The elegance and simplicity of this technique makes it suitable for a variety of 2D and 3D triangle mesh compression applications. Simple and fast compression/decompression algorithms with linear time and space complexity are available. Keywords: 3D representations, triangle meshes, planar graph encoding, geometry compression. 1. INTRODUCTION Many 3D models used in engineering, scientific, medical, geographical, and visualization applications are represented by an irregular mesh of bounding triangles. The simplest representation of such a mesh stores the geometry (a table of the coordinates of i...