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

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