DOE OSTI · 1038583
LR: Compact connectivity representation for triangle meshes
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.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Gurung, T, Luffel, M, Lindstrom, P, Rossignac, J. 2011-01-28. LR: Compact connectivity representation for triangle meshes. https://doi.org/10.1145/1964921.1964962
Cite the original work for its findings. Save a collection to share your selection of sources.