“LR: compact connectivity representation for triangle meshes” by Gurung, Luffel, Lindstrom and Rossignac

  • ©Topraj Gurung, Mark Luffel, Peter Lindstrom, and Jarek Rossignac




    LR: compact connectivity representation for triangle meshes



    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.


    1. Arkin, E. M., Held, M., Mitchell, J. S. B., and Skiena, S. S. 1996. Hamiltonian triangulations for fast rendering. The Visual Computer 12, 9, 429–444.Google ScholarCross Ref
    2. Baumgart, B. G. 1972. Winged edge polyhedron representation. Tech. Rep. CS-TR-72-320, Stanford University. Google ScholarDigital Library
    3. Blandford, D. K., Blelloch, G. E., Cardoze, D. E., and Kadow, C. 2005. Compact representations of simplicial meshes in two and three dimensions. International Journal of Computational Geometry and Applications 15, 1, 3–24.Google ScholarCross Ref
    4. Brisson, E. 1989. Representing geometric structures in d dimensions: Topology and order. In ACM Symposium on Computational Geometry, 218–227. Google Scholar
    5. Campagna, S., Kobbelt, L., and Seidel, H.-P. 1998. Directed edges—A scalable representation for triangle meshes. Journal of Graphics Tools 3, 4, 1–11. Google ScholarDigital Library
    6. Castelli Aleardi, L., Devillers, O., and Mebarki, A. 2006. 2D triangulation representation using stable catalogs. In Canadian Conference on Computational Geometry, 71–74.Google Scholar
    7. Castelli Aleardi, L., Devillers, O., and Schaeffer, G. 2006. Optimal succinct representations of planar maps. In ACM Symposium on Computational Geometry, 309–318. Google Scholar
    8. Courbet, C., and Hudelot, C. 2009. Random accessible hierarchical mesh compression for interactive visualization. In Symposium on Geometry Processing, 1311–1318. Google ScholarDigital Library
    9. Evans, F., Skiena, S., and Varshney, A. 1996. Optimizing triangle strips for fast rendering. In IEEE Visualization, 319–326. Google Scholar
    10. Gopi, M., and Eppstein, D. 2004. Single-strip triangulation of manifolds with arbitrary topology. Computer Graphics Forum 23, 3, 371–379.Google ScholarCross Ref
    11. Guibas, L., and Stolfi, J. 1985. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics 4, 2, 74–123. Google ScholarDigital Library
    12. Gurung, T., Laney, D., Lindstrom, P., and Rossignac, J. 2011. SQuad: Compact representation for triangle meshes. Computer Graphics Forum 30, 2, 355–364.Google ScholarCross Ref
    13. Kallmann, M., and Thalmann, D. 2001. Star-vertices: A compact representation for planar meshes with adjacency information. Journal of Graphics Tools 6, 1, 7–18. Google ScholarDigital Library
    14. Khodakovsky, A., Alliez, P., Desbrun, M., and Schröder, P. 2002. Near-optimal connectivity encoding of 2-manifold polygon meshes. Graphical Models 64, 3–4, 147–168. Google ScholarDigital Library
    15. Mantyla, M. 1988. Introduction to Solid Modeling. W. H. Freeman & Co. Google Scholar
    16. Mebarki, A. 2008. Implantation de structures de données compactes pour les triangulations. PhD thesis, Université de Nice-Sophia Antipolis.Google Scholar
    17. Rossignac, J., and Cardoze, D. 1999. Matchmaker: Manifold BReps for non-manifold r-sets. In ACM Symposium on Solid Modeling and Applications, 31–41. Google Scholar
    18. Rossignac, J. 1994. Through the cracks of the solid modeling milestone. In From object modelling to advanced visualization. Springer Verlag, 1–75.Google Scholar
    19. Rossignac, J. 1999. Edgebreaker: Connectivity compression for triangle meshes. IEEE Transactions on Visualization and Computer Graphics 5, 1, 47–61. Google ScholarDigital Library
    20. Rossignac, J. 2001. 3D compression made simple: Edgebreaker with zip&wrap on a corner-table. In International Conference on Shape Modeling & Applications, 278–283. Google Scholar
    21. Snoeyink, J., and Speckmann, B. 1999. Tripod: A minimalist data structure for embedded triangulations. In Computational Graph Theory and Combinatorics.Google Scholar
    22. Upadhyay, A. K., 2010. Contractible Hamiltonian cycles in triangulated surfaces. http://arxiv.org/pdf/1003.5268.Google Scholar
    23. Yoon, S.-E., and Lindstrom, P. 2007. Random-accessible compressed triangle meshes. IEEE Transactions on Visualization and Computer Graphics 13, 6, 1536–1543. Google ScholarDigital Library

ACM Digital Library Publication: