Edgebreaker on a Corner Table: A Simple Technique for Representing and Compressing Triangulated Surfaces
A triangulated surface S with V vertices is sometimes stored as a list of T independent triangles, each described by the 3 floating-point coordinates of its vertices. This representation requires about 576V bits and provides no explicit information regard
- PDF / 677,518 Bytes
- 10 Pages / 439 x 666 pts Page_size
- 68 Downloads / 181 Views
Abstract. A triangulated surface S with V vertices is sometimes stored as a list of T independent triangles, each described by the 3 floating-point coordinates of its vertices. This representation requires about 576V bits and provides no explicit information regarding the adjacency between neighboring triangles or vertices. A variety of boundary-graph data structures may be derived from such a representation in order to make explicit the various adjacency and incidence relations between triangles, edges, and vertices. These relations are stored to accelerate algorithms that visit the surface in a systematic manner and access the neighbors of each vertex or triangle. Instead of these complex data structures, we advocate a simple Corner Table, which explicitly represents the triangle/vertex incidence and the triangle/triangle adjacency of any manifold or pseudo-manifold triangle mesh, as two tables of integers. The Corner Table requires about 12Vlog2 V bits and must be accompanied by a vertex table, which requires 96V bits, if Floats are used. The Corner Table may be derived from the list of independent triangles. For meshes homeomorphic to a sphere, it may be compressed to less that 4V bits by storing the “clers” sequence of triangle-labels from the set {C,L,E,R,S}. Further compression to 3.6V bits may be guaranteed by using context-based codes for the clers symbols. Entropy codes reduce the storage for large meshes to less than 2V bits. Meshes with more complex topologies may require O(log2 V) additional bits per handle or hole. We present here a publicly available, simple, state-machine implementation of the Edgebreaker compression, which traverses the corner table, computes the CLERS symbols, and constructs an ordered list of vertex references. Vertices are encoded, in the order in which they appear on the list, as corrective displacements between their predicted and actual locations. Quantizing vertex coordinates to 12 bits and predicting each vertex as a linear combinations of its previously encoded neighbors leads to short displacements, for which entropy codes drop the total vertex location storage for heavily sampled typical meshes below 16V bits.
1
Introduction
3D graphics plays an increasingly important role in applications where 3D models are accessed through the Internet. Due to improved design and model acquisition tools, to the wider acceptance of this technology, and to the need for higher accuracy, the number and complexity of these models are growing more rapidly than phone and network bandwidth. Consequently, it is imperative to continue increasing the terseness of 3D data transmission forG. Farin et al. (eds.), Hierarchical and Geometrical Methods in Scientific Visualization © Springer-Verlag Berlin Heidelberg 2003
42
J. Rossignac et al.
mats and the performance and reliability of the associated compression and decompression algorithms. Although many representations have been proposed for 3D models, polygon and triangle meshes are the de facto standard for exchanging and viewing 3D models. A
Data Loading...
