LR: Compact connectivity representation for triangle meshes Metadata

Metadata describes a digital item, providing (if known) such information as creator, publisher, contents, size, relationship to other resources, and more. Metadata may also contain "preservation" components that help us to maintain the integrity of digital files over time.


  • Main Title LR: Compact connectivity representation for triangle meshes


  • Author: Gurung, T
    Creator Type: Personal
  • Author: Luffel, M
    Creator Type: Personal
  • Author: Lindstrom, P
    Creator Type: Personal
  • Author: Rossignac, J
    Creator Type: Personal


  • Sponsor: United States. Department of Energy.
    Contributor Type: Organization


  • Name: Lawrence Livermore National Laboratory
    Place of Publication: Livermore, California
    Additional Info: Lawrence Livermore National Laboratory (LLNL), Livermore, CA


  • Creation: 2011-01-28


  • English


  • Content Description: 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.
  • Physical Description: PDF-file: 1 pages; size: 6.6 Mbytes


  • Keyword: Implementation
  • Keyword: Construction
  • Keyword: Hamiltonians
  • STI Subject Categories: 97 Mathematical Methods And Computing


  • Journal Name: ACM Transactions on Graphics; Journal Volume: 30; Journal Issue: 4


  • Name: Office of Scientific & Technical Information Technical Reports
    Code: OSTI


  • Name: UNT Libraries Government Documents Department
    Code: UNTGD

Resource Type

  • Article


  • Text


  • Report No.: LLNL-JRNL-468333
  • Grant Number: W-7405-ENG-48
  • Office of Scientific & Technical Information Report Number: 1038583
  • Archival Resource Key: ark:/67531/metadc830751