# Topological matching for the compression of combinatorial maps ## Project Geometrical objects are classically produced when designing objects for manufacturing, 3D printing, video games, animation movies, virtual reality and so on. Our goal in this project is to focus on the *compression* of such objects. [Many methods](https://perso.liris.cnrs.fr/guillaume.lavoue/revue/CSUR2015.pdf) [^1] have been designed for this task with various goals, in particular the ability to quickly get a coarse version of the object and progressively stream additional details, or the ability to locally decompress some areas. This problem can be viewed as a special case of graph compression focusing on generalized planar graphs. The classical approach consists in describing the object as a sequence of simple construction operations such as gluing additional polygons or splitting vertices. Using a limited set of operations encoded by symbols, this sequence can be described by a word to be compressed. As a practical example, let's say that we want to encode a mesh for a cube. We will build the cube by gluing squares next to each other, using the following naive rules: * we traverse the faces of the cube in a depth first order * the edges of a square are considered in the order: bottom, right, top, left * when considering an edge, we can either: - A: add a new square across this edge - F: create a flap to be glued on some other edge later on - G(i): glue the edge on the ith created flap Using these rules, we can describe the combinarorics of the cube with the word AAAFAFFFAFFFG(3)G(5)G(2)G(6)G(1)G(0)G(4), illustrated below, starting from the top square. <center> <img alt="template of a cube corresponding to the word" src="https://codimd.math.cnrs.fr/uploads/upload_bc38fda1d915d5abf4b453ee84634fbc.png" width=300 style="margin-bottom: 40px" /> </center> In the above example, the G symbols are associated with a number, which is going to be costly to encode. Most methods try to avoid using indices as much as possible, replacing these by operations such as "glue with the top flap on some stack" and similar tricks. Designing the right rules to define the construction protocol is the key to high compression ratios. Specifically, we focus on [Combinatorial maps](https://en.wikipedia.org/wiki/Combinatorial_map) [^2] which are a classical data structure for the representation of geometrical objects, in particular polygon meshes and polyhedral volumes. Compared to other data structures, they are able to robustly and efficiently encode polygonal arrangements in arbitrary dimension and provide quick access to traverse the connectivity of these arrangements. Compressing combinatorial maps has already been studied [^3] and the produced sequence of symbols to be encoded is actually very similar to *map signatures* [^4]. In essence, both are used to fully encode the combinatorial map, but the latter has also been applied to the detection of isomorphisms between combinatorial maps or subsets of them [^5]. Our goal for this project is to explore the applications of map signatures to further improve the compression ratio. This could be done in several ways. An idea could be to analyze big datasets of meshes and extract frequent subsets of these meshes as a dictionnary of building blocks in a way similar to [dictionary coders](https://en.wikipedia.org/wiki/Dictionary_coder). Another approach could be to reduce the information required to store how to glue meshes together by automatically detecting matching subsets to be connected. We will start by studying the case of 2D meshes, where lots of data is available such as in the [thingi 10k](https://ten-thousand-models.appspot.com/) dataset, but compression is well established with very efficient existing methods. We will however keep a focus on producing a general method applicable to any combinatorial map whatever the dimension. The approach will therefore also be tested on 3D volume meshes, but with less data available. ## Skills This project lies in the field of computational geometry and computer graphics, but the required background is mostly graph theory and algorithms to traverse graphs. The designed algorithms are meant to be efficiently implemented. Code will be produced in C++, based on the combinatorial maps [CGAL package](https://doc.cgal.org/latest/Combinatorial_map). ## Advisors * Guillaume Damiand, research director at CNRS, LIRIS * Vincent Nivoliers, associate professor at Université Claude Bernard Lyon 1, LIRIS [^1]: Adrien Maglo, Guillaume Lavoué, Florent Dupont, Céline Hudelot. 3D Mesh Compression: Survey, Comparisons, and Emerging Trends. ACM Computing Surveys, 2015, 47 (3), 40 p. [Link to the paper](https://perso.liris.cnrs.fr/guillaume.lavoue/revue/CSUR2015.pdf) [^2]: Lienhardt, P. (1994). "N-dimensional generalized combinatorial maps and cellular quasi-manifolds". International Journal of Computational Geometry and Applications. 4 (3): 275–324. [doi:10.1142/S0218195994000173](https://doi.org/10.1142/S0218195994000173) [^3]: Sylvain Prat, Patrick Gioia, Yves Bertrand, Daniel Meneveaux. Connectivity Compression in Arbitrary Dimension. The Visual Computer, 2005, 21 (8), pp.876-885. [Link to the paper](https://xlim-sic.labo.univ-poitiers.fr/publications/files/publi796.pdf) [^4]: Stéphane Gosselin, Christine Solnon, Guillaume Damiand. Efficient Search of Combinatorial Maps using Signatures. Theoretical Computer Science, 2011, 412 (15), pp.1392-1405. [Link to the paper](https://hal.science/hal-00567332v2/document) [^5]: Guillaume Damiand, Vincent Nivoliers. Query-replace operations for topologically controlled 3D mesh editing. Computers and Graphics, 2022, 106, pp.187-199. [Link to the paper](https://hal.science/hal-03717765v1/document)