We consider the problem of designing fast and compact solutions for representing the connectivity information of triangle meshes. Classical data structures (such as Half-Edge, Corner Table, …) are redundant and store a significant amount of information in order to offer a user-friendly interface and a fast implementation of common mesh navigational operators. Their memory consumption is expressed in terms of references per vertex (rpv) and typically ranges from 13 to 19 rpv which may prevent their use in the case of very large graphs. Compression schemes allows us to match asymptotically the information-theory lower bounds and to encode a triangulation with few bits per vertex, but they do not permit to navigate the graph structure without first decompressing the entire mesh.

In this work, we introduce novel compact representations for triangle meshes that take graph regularity into account and offer various trade-offs between space requirements and runtime performance (local navigation is performed in O(1) time). For instance, one of our solutions exhibits a storage cost of 2 rpv in the case of very regular triangulations (with a large majority of low degree vertices), while having a worst case cost of 3.67 rpv. We also propose another structure, a bit more involved, that requires at most 3.33 rpv in the worst case: this is currently the best-known worst case bound that outperforms all previous results. Our experimental results confirm the practical interest of our compact data structures, which are only slightly slower (between 1.7x and 3.8x slower) than classical mesh data structures.

This is joint work with Olivier Devillers, Loria.