{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:00:24Z","timestamp":1760241624165,"version":"build-2065373602"},"reference-count":49,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2018,7,13]],"date-time":"2018-07-13T00:00:00Z","timestamp":1531440000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100010665","name":"H2020 Marie Sk\u0142odowska-Curie Actions","doi-asserted-by":"publisher","award":["659526"],"award-info":[{"award-number":["659526"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We propose a new strategy for the parallelization of mesh processing algorithms. Our main contribution is the definition of distributed combinatorial maps (called n-dmaps), which allow us to represent the topology of big meshes by splitting them into independent parts. Our mathematical definition ensures the global consistency of the meshes at their interfaces. Thus, an n-dmap can be used to represent a mesh, to traverse it, or to modify it by using different mesh processing algorithms. Moreover, an nD mesh with a huge number of elements can be considered, which is not possible with a sequential approach and a regular data structure. We illustrate the interest of our solution by presenting a parallel adaptive subdivision method of a 3D hexahedral mesh, implemented in a distributed version. We report space and time performance results that show the interest of our approach for parallel processing of huge meshes.<\/jats:p>","DOI":"10.3390\/a11070105","type":"journal-article","created":{"date-parts":[[2018,7,16]],"date-time":"2018-07-16T04:05:33Z","timestamp":1531713933000},"page":"105","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Distributed Combinatorial Maps for Parallel Mesh Processing"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1580-5517","authenticated-orcid":false,"given":"Guillaume","family":"Damiand","sequence":"first","affiliation":[{"name":"CNRS, LIRIS, UMR5205, Universit\u00e9 de Lyon, 69622 Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aldo","family":"Gonzalez-Lorenzo","sequence":"additional","affiliation":[{"name":"CNRS, LIRIS, UMR5205, Universit\u00e9 de Lyon, 69622 Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0118-7204","authenticated-orcid":false,"given":"Florence","family":"Zara","sequence":"additional","affiliation":[{"name":"CNRS, LIRIS, UMR5205, Universit\u00e9 de Lyon, 69622 Lyon, France"},{"name":"Facult\u00e9 des Sciences et Technologies Department, Universit\u00e9 Lyon 1, 69100 Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florent","family":"Dupont","sequence":"additional","affiliation":[{"name":"CNRS, LIRIS, UMR5205, Universit\u00e9 de Lyon, 69622 Lyon, France"},{"name":"Facult\u00e9 des Sciences et Technologies Department, Universit\u00e9 Lyon 1, 69100 Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,7,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., and Levy, B. (2010). Polygon Mesh Processing, AK Peters.","DOI":"10.1201\/b10688"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s003710100150","article-title":"A subdivision scheme for hexahedral meshes","volume":"18","author":"Bajaj","year":"2002","journal-title":"Vis. Comput."},{"key":"ref_3","unstructured":"Wu, J., Westermann, R., and Dick, C. (2014). Physically-Based Simulation of Cuts in Deformable Bodies: A Survey, Eurographics Association. Eurographics (State of the Art Reports)."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"D\u00f6llner, J., and Buchholz, H. (2005, January 4\u20135). Continuous Level-of-detail Modeling of Buildings in 3D City Models. Proceedings of the 13th GIS \u201905 Annual ACM International Workshop on Geographic Information Systems, Bremen, Germany.","DOI":"10.1145\/1097064.1097089"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Akl, S.G., Dehne, F., Sack, J.R., and Santoro, N. (1995). Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications. Algorithms and Data Structures, Springer.","DOI":"10.1007\/3-540-60220-8"},{"key":"ref_6","first-page":"61","article-title":"Modelling and manipulating spacetime objects in a true 4D model","volume":"14","author":"Ledoux","year":"2017","journal-title":"J. Spat. Inf. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"115007","DOI":"10.1088\/0266-5611\/31\/11\/115007","article-title":"5D respiratory motion model based image reconstruction algorithm for 4D cone-beam computed tomography","volume":"31","author":"Liu","year":"2015","journal-title":"Inverse Probl."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Baumgart, B.G. (1975, January 19\u201322). A polyhedron representation for computer vision. Proceedings of the American Federation of Information Processing Societies: 1975 National Computer Conference, Anaheim, CA, USA.","DOI":"10.1145\/1499949.1500071"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1109\/MCG.1985.276271","article-title":"Edge-based data structures for solid modelling in curved-surface environments","volume":"5","author":"Weiler","year":"1985","journal-title":"Comput. Graph. Appl."},{"key":"ref_10","unstructured":"M\u00e4ntyl\u00e4, M. (1988). An Introduction to Solid Modeling, Computer Science Press."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"De Berg, M. (2000). Computational Geometry: Algorithms and Applications, Springer. [2nd ed.].","DOI":"10.1007\/978-3-662-04245-8"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/282918.282923","article-title":"Primitives for the Manipulation of General Subdivisions and Computation of Voronoi Diagrams","volume":"4","author":"Guibas","year":"1985","journal-title":"ACM Trans. Graph."},{"key":"ref_13","unstructured":"Weiler, K. (1988). The radial edge structure: A topological representation for non-manifold geometric boundary modeling. Geometric Modeling for CAD Applications, Elsevier Science."},{"key":"ref_14","unstructured":"Rossignac, J. (2001, January 7\u201311). 3D Compression Made Simple: Edgebreaker with Zip&Wrap on a Corner-Table. Proceedings of the 2001 International Conference on Shape Modeling and Applications (SMI 2001), Genoa, Italy."},{"key":"ref_15","first-page":"646","article-title":"A Combinatorial Representation for Polyhedral Surfaces","volume":"7","author":"Edmonds","year":"1960","journal-title":"Not. Am. Math. Soc."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"249","DOI":"10.4153\/CJM-1963-029-x","article-title":"A census of planar maps","volume":"15","author":"Tutte","year":"1963","journal-title":"Canad. J. Math."},{"key":"ref_17","first-page":"657","article-title":"Constellations et graphes topologiques","volume":"2","author":"Jacques","year":"1970","journal-title":"Proc. Comb. Theory Appl."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Ringel, G. (1974). Map Color Theorem, Springer.","DOI":"10.1007\/978-3-642-65759-7"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Dobkin, D., and Laszlo, M. (1987, January 8\u201310). Primitives for the Manipulation of Three-Dimensional Subdivisions. In Proceeding of the Symposium on Computational Geometry, Waterloo, ON, Canada.","DOI":"10.1145\/41958.41967"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Lopes, H., and Tavares, G. (1997). Structural Operators for Modeling 3-manifolds. Proceeding of the ACM Symposium on SMA \u201997 Solid Modeling and Applications, Atlanta, GA, USA, 14\u201316 May 1997, ACM.","DOI":"10.1145\/267734.267745"},{"key":"ref_21","unstructured":"Jiao, X., and Weill, J.C. (2012). OpenVolumeMesh - A Versatile Index-Based Data Structure for 3D Polytopal Complexes. Proceeding of the of 21st International Meshing Roundtable, Springer."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/s00366-014-0378-6","article-title":"AHF: Array-based half-facet data structure for mixed-dimensional and non-manifold meshes","volume":"31","author":"Dyedov","year":"2015","journal-title":"Eng. Comput. Lond."},{"key":"ref_23","unstructured":"Brauer, W., Rozenberg, G., and Salomaa, A. (1987). Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, Springer."},{"key":"ref_24","unstructured":"Rossignac, J., and O\u2019Connor, M. (1989, January 18\u201322). SGC: A Dimension-Independant Model for Pointsets with Internal Structures and Incomplete boundaries. Proceedings of the Geometric Modeling for Product Engineering: Selected and Expanded Papers from the IFIP WG 5.2\/NSF Working Conference on Geometric Modeling, Rensselaerville, NY, USA."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1142\/S0218195994000173","article-title":"N-Dimensional Generalized Combinatorial Maps and Cellular Quasi-Manifolds","volume":"4","author":"Lienhardt","year":"1994","journal-title":"Int. J. Comput. Geometry Appl."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Damiand, G., and Lienhardt, P. (2014). Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing, CRC Press.","DOI":"10.1201\/b17403"},{"key":"ref_27","unstructured":"Damiand, G. (2011). Combinatorial Maps. CGAL User and Reference Manual, CGAL Editorial Board. [3.9th ed.]. Available online: http:\/\/www.cgal.org\/Pkg\/CombinatorialMaps."},{"key":"ref_28","unstructured":"Fl\u00e9chon, E., Zara, F., Damiand, G., and Jaillet, F. (2014, January 24\u201325). A Unified Topological-Physical Model for Adaptive Refinement. Proceedings of the 11th Workshop on Virtual Reality Interaction and Physical Simulation (VRIPHYS), Bremen, Germany."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Kraemer, P., Untereiner, L., Jund, T., Thery, S., and Cazier, D. (2013, January 13\u201316). CGoGN: n-dimensional Meshes with Combinatorial Maps. Proceedings of the 22nd IMR 2013, International Meshing Roundtable, Orlando, FL, USA.","DOI":"10.1007\/978-3-319-02335-9_27"},{"key":"ref_30","first-page":"46","article-title":"A Generic Implementation of dD Combinatorial Maps in CGAL","volume":"Volume 82","author":"Damiand","year":"2014","journal-title":"Proceedings of the 23rd International Meshing Roundtable (IMR)"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/S0045-7825(98)00300-4","article-title":"Parallel volume meshing using face removals and hierarchical repartitioning","volume":"174","author":"Shephard","year":"1999","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0307-904X(00)00045-7","article-title":"Parallel meshing and remeshing","volume":"25","author":"Coupez","year":"2000","journal-title":"Appl. Math. Model."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Bruaset, A.M., and Tveito, A. (2006). Parallel Mesh Generation. Numerical Solution of Partial Differential Equations on Parallel Computers, Springer.","DOI":"10.1007\/3-540-31619-1"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.advengsoft.2013.03.005","article-title":"A distributed-memory parallel technique for two-dimensional mesh generation for arbitrary domains","volume":"59","author":"Freitas","year":"2013","journal-title":"Adv. Eng. Softw."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/s11831-014-9098-8","article-title":"Recent Advances in Parallel Advancing Front Grid Generation","volume":"21","year":"2014","journal-title":"Arch. Comput. Methods Eng."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1002\/fld.3918","article-title":"Impact of tetrahedralization on parallel conforming octree mesh generation","volume":"75","author":"Ghisi","year":"2014","journal-title":"Int. J. Numer. Methods Fluids"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/j.compstruc.2015.04.004","article-title":"Fine-grained parallel algorithm for unstructured surface mesh generation","volume":"154","author":"Zhao","year":"2015","journal-title":"Comput. Struct."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Heroux, M.A., Raghavan, P., and Simon, H.D. (2006). Parallel Adaptive Mesh Refinement. Parallel Processing for Scientific Computing, SIAM. Chapter 8.","DOI":"10.1137\/1.9780898718133"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1007\/s00366-016-0444-3","article-title":"Parallel generation of meshes with cracks using binary spatial decomposition","volume":"32","author":"Freitas","year":"2016","journal-title":"Eng. Comput. (Lond.)"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Tautges, T.J., Kraftcheck, J., Bertram, N., Sachdeva, V., and Magerlein, J. (2012, January 21\u201325). Mesh Interface Resolution and Ghost Exchange in a Parallel Mesh Representation. Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium Workshops & PhD Forum, IPDPS 2012, Shanghai, China.","DOI":"10.1109\/IPDPSW.2012.208"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Langer, A., Lifflander, J., Miller, P., Pan, K., Kal\u00e9, L.V., and Ricker, P.M. (2012, January 24\u201326). Scalable Algorithms for Distributed-Memory Adaptive Mesh Refinement. Proceedings of the IEEE 24th International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2012, New York, NY, USA.","DOI":"10.1109\/SBAC-PAD.2012.48"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.cad.2016.07.011","article-title":"Array-based, parallel hierarchical mesh refinement algorithms for unstructured meshes","volume":"85","author":"Ray","year":"2017","journal-title":"Comput. Aided Des."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s00366-006-0049-3","article-title":"libMesh: A C++ library for parallel adaptive mesh refinement\/coarsening simulations","volume":"22","author":"Kirk","year":"2006","journal-title":"Eng. Comput. (Lond.)"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"17:1","DOI":"10.1145\/2814935","article-title":"PUMI: Parallel Unstructured Mesh Infrastructure","volume":"42","author":"Ibanez","year":"2016","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1007\/978-3-540-39966-7_39","article-title":"Removal and Contraction for N-Dimensional Generalized Maps","volume":"Volume 2886","author":"Damiand","year":"2003","journal-title":"Proceedings of the 11th International Conference on Discrete Geometry for Computer Imagery (DGCI)"},{"key":"ref_46","unstructured":"The CGAL Project (2009). CGAL User and Reference Manual, CGAL Editorial Board. Available online: http:\/\/www.cgal.org\/."},{"key":"ref_47","unstructured":"Alliez, P., Tayeb, S., and Wormser, C. (2009). 3D Fast Intersection and Distance Computation. CGAL User and Reference Manual, CGAL Editorial Board. [3.5th ed.]. Available online: http:\/\/www.cgal.org\/Pkg\/AABB_tree."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Gabriel, E., Fagg, G.E., Bosilca, G., Angskun, T., Dongarra, J.J., Squyres, J.M., Sahay, V., Kambadur, P., Barrett, B., and Lumsdaine, A. (2004, January 19\u201322). Open MPI: Goals, Concept, and Design of a Next Generation MPI Implementation. Proceedings of the 11th European PVM\/MPI Users\u2019 Group Meeting, Budapest, Hungary.","DOI":"10.1007\/978-3-540-30218-6_19"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1111\/cgf.12667","article-title":"CPH: A Compact Representation for Hierarchical Meshes Generated by Primal Refinement","volume":"34","author":"Untereiner","year":"2015","journal-title":"Comput. Graph. Forum"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/7\/105\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:11:57Z","timestamp":1760195517000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/7\/105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,13]]},"references-count":49,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2018,7]]}},"alternative-id":["a11070105"],"URL":"https:\/\/doi.org\/10.3390\/a11070105","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,7,13]]}}}