Distributed combinatorial maps for parallel mesh processing. (English) Zbl 1461.65256
Summary: 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 \(n\)D 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.
MSC:
| 65N50 | Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs |
| 68P05 | Data structures |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68U10 | Computing methodologies for image processing |
| 65Y05 | Parallel numerical computation |
References:
| [1] | Botsch, M.; Kobbelt, L.; Pauly, M.; Alliez, P.; Levy, B.; ; Polygon Mesh Processing: Natick, MA, USA 2010; . |
| [2] | Bajaj, C.L.; Schaefer, S.; Warren, J.D.; Xu, G.; A subdivision scheme for hexahedral meshes; Vis. Comput.: 2002; Volume 18 ,343-356. |
| [3] | Wu, J.; Westermann, R.; Dick, C.; ; Physically-Based Simulation of Cuts in Deformable Bodies: A Survey: Hoboken, NJ, USA 2014; ,1-19. |
| [4] | Döllner, J.; Buchholz, H.; Continuous Level-of-detail Modeling of Buildings in 3D City Models; Proceedings of the 13th GIS ’05 Annual ACM International Workshop on Geographic Information Systems: New York, NY, USA 2005; ,173-181. |
| [5] | Sharir, M.; Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications; Algorithms and Data Structures: Berlin/Heidelberg, Germany 1995; ,109-121. · Zbl 1502.68346 |
| [6] | Arroyo Ohori, K.; Ledoux, H.; Stoter, J.; Modelling and manipulating spacetime objects in a true 4D model; J. Spat. Inf. Sci.: 2017; Volume 14 ,61-93. |
| [7] | Liu, J.; Zhang, X.; Zhang, X.; Zhao, H.; Gao, Y.; Thomas, D.; Low, D.A.; Gao, H.; 5D respiratory motion model based image reconstruction algorithm for 4D cone-beam computed tomography; Inverse Probl.: 2015; Volume 31 ,115007. · Zbl 1344.68264 |
| [8] | Baumgart, B.G.; A polyhedron representation for computer vision; Proceedings of the American Federation of Information Processing Societies: 1975 National Computer Conference: ; ,589-596. |
| [9] | Weiler, K.; Edge-based data structures for solid modelling in curved-surface environments; Comput. Graph. Appl.: 1985; Volume 5 ,21-40. |
| [10] | Mäntylä, M.; ; An Introduction to Solid Modeling: New York, NY, USA 1988; . |
| [11] | De Berg, M.; ; Computational Geometry: Algorithms and Applications: Berlin, Germany 2000; . · Zbl 0939.68134 |
| [12] | Guibas, L.J.; Stolfi, J.; Primitives for the Manipulation of General Subdivisions and Computation of Voronoi Diagrams; ACM Trans. Graph.: 1985; Volume 4 ,74-123. · Zbl 0586.68059 |
| [13] | Weiler, K.; The radial edge structure: A topological representation for non-manifold geometric boundary modeling; Geometric Modeling for CAD Applications: New York, NY, USA 1988; ,217-254. |
| [14] | Rossignac, J.; 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): ; ,278. |
| [15] | Edmonds, J.; A Combinatorial Representation for Polyhedral Surfaces; Not. Am. Math. Soc.: 1960; Volume 7 ,646. |
| [16] | Tutte, W.; A census of planar maps; Canad. J. Math.: 1963; Volume 15 ,249-271. · Zbl 0115.17305 |
| [17] | Jacques, A.; Constellations et graphes topologiques; Proc. Comb. Theory Appl.: 1970; Volume 2 ,657-673. · Zbl 0213.25901 |
| [18] | Ringel, G.; ; Map Color Theorem: Berlin, Germany 1974; . · Zbl 0287.05102 |
| [19] | Dobkin, D.; Laszlo, M.; Primitives for the Manipulation of Three-Dimensional Subdivisions; In Proceeding of the Symposium on Computational Geometry: ; ,86-99. · Zbl 0664.68023 |
| [20] | Lopes, H.; Tavares, G.; Structural Operators for Modeling 3-manifolds; Proceeding of the ACM Symposium on SMA ’97 Solid Modeling and Applications, Atlanta, GA, USA, 14-16 May 1997: New York, NY, USA 1997; ,10-18. |
| [21] | Kremer, M.; Bommes, D.; Kobbelt, L.; OpenVolumeMesh - A Versatile Index-Based Data Structure for 3D Polytopal Complexes; Proceeding of the of 21st International Meshing Roundtable: Berlin, Germany 2012; ,531-548. |
| [22] | Dyedov, V.; Ray, N.; Einstein, D.R.; Jiao, X.; Tautges, T.J.; AHF: Array-based half-facet data structure for mixed-dimensional and non-manifold meshes; Eng. Comput. Lond.: 2015; Volume 31 ,389-404. |
| [23] | Edelsbrunner, H.; Algorithms in Combinatorial Geometry; EATCS Monographs on Theoretical Computer Science: Berlin, Germany 1987; . · Zbl 0634.52001 |
| [24] | Rossignac, J.; O’Connor, M.; 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: ; ,145-180. |
| [25] | Lienhardt, P.; N-Dimensional Generalized Combinatorial Maps and Cellular Quasi-Manifolds; Int. J. Comput. Geometry Appl.: 1994; Volume 4 ,275-324. · Zbl 0821.57016 |
| [26] | Damiand, G.; Lienhardt, P.; ; Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing: Natick, MA, USA 2014; . · Zbl 1305.68012 |
| [27] | Damiand, G.; Combinatorial Maps; CGAL User and Reference Manual: 2011; . |
| [28] | Fléchon, E.; Zara, F.; Damiand, G.; Jaillet, F.; A Unified Topological-Physical Model for Adaptive Refinement; Proceedings of the 11th Workshop on Virtual Reality Interaction and Physical Simulation (VRIPHYS): Bremen, Germany 2014; ,39-48. |
| [29] | Kraemer, P.; Untereiner, L.; Jund, T.; Thery, S.; Cazier, D.; CGoGN: n-dimensional Meshes with Combinatorial Maps; Proceedings of the 22nd IMR 2013, International Meshing Roundtable: ; ,485-503. |
| [30] | Damiand, G.; Teillaud, M.; A Generic Implementation of dD Combinatorial Maps in CGAL; Proceedings of the 23rd International Meshing Roundtable (IMR): London, UK 2014; Volume Volume 82 ,46-58. |
| [31] | De Cougny, H.; Shephard, M.; Parallel volume meshing using face removals and hierarchical repartitioning; Comput. Methods Appl. Mech. Eng.: 1999; Volume 174 ,275-298. · Zbl 0963.76073 |
| [32] | Coupez, T.; Digonnet, H.; Ducloux, R.; Parallel meshing and remeshing; Appl. Math. Model.: 2000; Volume 25 ,153-175. · Zbl 1076.74551 |
| [33] | Chrisochoides, N.; Parallel Mesh Generation; Numerical Solution of Partial Differential Equations on Parallel Computers: Berlin/Heidelberg, Germany 2006; ,237-264. · Zbl 1097.65122 |
| [34] | Freitas, M.O.; Wawrzynek, P.A.; Neto, J.B.C.; Vidal, C.A.; Martha, L.F.; Ingraffea, A.R.; A distributed-memory parallel technique for two-dimensional mesh generation for arbitrary domains; Adv. Eng. Softw.: 2013; Volume 59 ,38-52. |
| [35] | Löhner, R.; Recent Advances in Parallel Advancing Front Grid Generation; Arch. Comput. Methods Eng.: 2014; Volume 21 ,127-140. · Zbl 1349.65667 |
| [36] | Ghisi, I.T.; Camata, J.J.; Coutinho, A.L.G.A.; Impact of tetrahedralization on parallel conforming octree mesh generation; Int. J. Numer. Methods Fluids: 2014; Volume 75 ,800-814. · Zbl 1455.65220 |
| [37] | Zhao, D.; Chen, J.; Zheng, Y.; Huang, Z.; Zheng, J.; Fine-grained parallel algorithm for unstructured surface mesh generation; Comput. Struct.: 2015; Volume 154 ,177-191. |
| [38] | Diachin, L.F.; Hornung, R.; Plassmann, P.; Wissink, A.; Parallel Adaptive Mesh Refinement; Parallel Processing for Scientific Computing: Portland, OR, USA 2006; ,143-162. |
| [39] | Freitas, M.O.; Wawrzynek, P.A.; Neto, J.B.C.; Vidal, C.A.; Carter, B.J.; Martha, L.F.; Ingraffea, A.R.; Parallel generation of meshes with cracks using binary spatial decomposition; Eng. Comput. (Lond.): 2016; Volume 32 ,655-674. |
| [40] | Tautges, T.J.; Kraftcheck, J.; Bertram, N.; Sachdeva, V.; Magerlein, J.; 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: ; ,1670-1679. |
| [41] | Langer, A.; Lifflander, J.; Miller, P.; Pan, K.; Kalé, L.V.; Ricker, P.M.; 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: ; ,100-107. |
| [42] | Ray, N.; Grindeanu, I.; Zhao, X.; Mahadevan, V.; Jiao, X.; Array-based, parallel hierarchical mesh refinement algorithms for unstructured meshes; Comput. Aided Des.: 2017; Volume 85 ,68-82. |
| [43] | Kirk, B.S.; Peterson, J.W.; Stogner, R.H.; Carey, G.F.; libMesh: A C++ library for parallel adaptive mesh refinement/coarsening simulations; Eng. Comput. (Lond.): 2006; Volume 22 ,237-254. |
| [44] | Ibanez, D.A.; Seol, E.S.; Smith, C.W.; Shephard, M.S.; PUMI: Parallel Unstructured Mesh Infrastructure; ACM Trans. Math. Softw.: 2016; Volume 42 ,17:1-17:28. · Zbl 1369.65155 |
| [45] | Damiand, G.; Lienhardt, P.; Removal and Contraction for N-Dimensional Generalized Maps; Proceedings of the 11th International Conference on Discrete Geometry for Computer Imagery (DGCI): Berlin, Germany 2003; Volume Volume 2886 ,408-419. · Zbl 1254.68333 |
| [46] | ; CGAL User and Reference Manual: Boston, MA, USA 2009; . |
| [47] | Alliez, P.; Tayeb, S.; Wormser, C.; 3D Fast Intersection and Distance Computation; CGAL User and Reference Manual: Boston, MA, USA 2009; . |
| [48] | Gabriel, E.; Fagg, G.E.; Bosilca, G.; Angskun, T.; Dongarra, J.J.; Squyres, J.M.; Sahay, V.; Kambadur, P.; Barrett, B.; Lumsdaine, A.; Open MPI: Goals, Concept, and Design of a Next Generation MPI Implementation; Proceedings of the 11th European PVM/MPI Users’ Group Meeting: ; ,97-104. |
| [49] | Untereiner, L.; Kraemer, P.; Cazier, D.; Bechmann, D.; CPH: A Compact Representation for Hierarchical Meshes Generated by Primal Refinement; Comput. Graph. Forum: 2015; Volume 34 ,155-166. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
