Paper Info
Title
Zipper: A compact connectivity data structure for triangle meshes
Abstract
We propose Zipper, a compact representation of incidence and adjacency for manifold triangle meshes with fixed connectivity. Zipper uses on average only 6 bits per triangle, can be constructed in linear space and time, and supports all standard random-access and mesh traversal operators in constant time. Similarly to the previously proposed LR (Laced Ring) approach, the Zipper construction reorders vertices and triangles along a nearly Hamiltonian cycle called the ring. The 4.4x storage reduction of Zipper over LR results from three contributions. (1) For most triangles, Zipper stores a 2-bit delta (plus three additional bits) rather than a full 32-bit reference. (2) Zipper modifies the ring to reduce the number of exceptional triangles. (3) Zipper encodes the remaining exceptional triangles using 2.5x less storage. In spite of these large savings in storage, we show that Zipper offers comparable performance to LR and other data structures in mesh processing applications. Zipper may also serve as a compact indexed format for rendering meshes, and hence is valuable even in applications that do not require adjacency information.
Year
DOI
Venue
2013
10.1016/j.cad.2012.10.009
Computer-Aided Design
Keywords
Field
DocType
storage reduction,lr result,compact connectivity data structure,triangle mesh,adjacency information,compact representation,constant time,zipper construction reorders vertex,zipper encode,zipper use,zipper store,exceptional triangle,differential coding,hamiltonian cycle
Adjacency list,Discrete mathematics,Combinatorics,Tree traversal,Polygon mesh,Vertex (geometry),Hamiltonian path,Linear space,Zipper,Mathematics,Triangle mesh
Journal
Volume
Issue
ISSN
45
2
0010-4485
Citations 
PageRank 
References 
8
0.44
14
Authors
4
Name
Order
Citations
PageRank
Topraj Gurung1572.80
Mark Luffel2262.14
Peter Lindstrom31838103.19
Jarek Rossignac43101330.15