Zipper: A compact connectivity data structure for triangle meshes

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.4× 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.5× 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.

► Zipper uses about 6 bits per triangle to store the connectivity of triangle meshes. ► Zipper supports access, incidence and adjacency queries in constant time. ► The most compact prior solution is both slower and uses 4.4× more space on average. ► Zipper construction from an indexed face set format has linear time complexity. ► Zipper is not suited for applications that perform connectivity changes.