LR: Compact Connectivity Representation for Triangle Meshes

SIGGRAPH 2011

Topraj Gurung, Mark Luffel, Peter Lindstrom, Jarek Rossignac

Abstract:

We propose LR (Laced Ring)-a simple data structure for representing the connectivity of manifold triangle meshes. LR provides the option to store on average either 1.08 references per triangle or 26.2 bits per triangle. Its construction, from an input mesh that supports constant-time adjacency queries, has linear space and time complexity, and involves ordering most vertices along a nearly-Hamiltonian cycle. LR is best suited for applications that process meshes with fixed connectivity, as any changes to the connectivity require the data structure to be rebuilt. We provide an implementation of the set of standard random-access, constant-time operators for traversing a mesh, and show that LR often saves both space and traversal time over competing representations.

pdf | slides [coming soon]

Please check out our Eurographics 2011 work (SQuad) which requires 2 references per triangle [project page].

And also our SPM 2009 work (SOT) which requires 4 references per tetrahedron for tetrahedral meshes [project page] and the SOT version for triangle meshes which requires 3 references per triangle [GT Technical report (2010)]

Source Code:

I will be putting up the code soon (Fall 2011), but if you are planning to implement it and have questions regarding the implementation, please do not hesitate to contact me at topraj [at] gatech [dot] edu.