# Distributed Combinatorial Maps for Parallel Mesh Processing
## 1 Introduction
This model has several advantages that justify its use. (1) There is a formal mathematical definition, including consistency constraints, with a clear distinction between the structure information and the shape information; (2) This mathematical foundation allows us to formally define the sets of corresponding subdivisions; this is important, since many classical mathematical notions and properties can thus be applied to combinatorial maps; (3) Since the structure is well-defined, the operations producing combinatorial maps are also well-defined, i.e., they construct the representation of valid geometric objects; (4) Elementary local operations can be conceived, and make it possible to carefully control the objects during their construction; (5) Many operations exist, often based on the elementary local operations, to compute characteristics and to modify \(n\)D meshes; (6) Efficient data structures have been conceived, based on combinatorial maps, together with operations for handling these structures; (7) The formal links between combinatorial maps and ordered models, combinatorial maps and incidence graphs, combinatorial maps and simplicial structures, are well-known; it is thus possible to conceive conversion operations between all these structures; (8) Lastly, a free implementation is proposed, including several operations, in Cgal[27], a major C++ library of computational geometry. To sum up, this topological representation can be used to describe an \(n\)D mesh, while providing high level operations to iterate through the cells of the mesh, retrieve the incidence and adjacency relations between the cells, and modify the mesh by using the numerous existing operations. For all these reasons, combinatorial maps were used in many applications (see references in [26]) of geometric modeling, computational geometry, discrete geometry, computer graphics, image processing and analysis, etc. Nevertheless, one main limitation of combinatorial maps is the large number of elements required to describe a very complex mesh. This implies long computational time for algorithms that deal with such meshes. Moreover, this can forbid handling such big meshes when they do not fit in the memory of a single computer. To solve these problems, the main contribution of this paper is the definition of \(\mathbf{n}D\)_distributed combinatorial maps_. The main idea of this distributed data structure is to split a combinatorial map in independent blocks, while adding some information to link the different parts and retrieve information at the interfaces. Our solution allows us to: (1) work with big meshes that cannot fit in the memory of a single computer; (2) define parallel mesh processing algorithms that process each block in parallel. In this paper, we illustrate these two major advantages by showing how it is possible to use 3D distributed combinatorial maps to implement a parallel adaptive hexahedral mesh refinement. This shows the interest of our new solution. Moreover, we can imagine other mesh processing algorithms that can be adapted and improved by using distributed combinatorial maps. The remainder of this paper is organized as follows. Section 2 presents the theoretical background of combinatorial maps and hexahedral subdivision. Section 3 introduces the concept of \(n\)D distributed combinatorial map. In Section 4, we validate this distributed data structure through a parallel hexahedral recursive decomposition method. Section 5 presents experimental results and discussion. At the end, Section 6 concludes this article and gives some perspectives.