A consistent parallel isotropic unstructured mesh generation method based on multi-phase SPH. (English) Zbl 1436.65201

Summary: In this paper, we propose a consistent parallel unstructured mesh generator based on a multi-phase SPH method. A set of physics-motivated modeling equations are developed to achieve the targets of domain decomposition, communication volume optimization and high-quality unstructured mesh generation simultaneously. A unified density field is defined as the target function for both partitioning the geometry and distributing the mesh-vertexes. A multi-phase Smoothing Particle Hydrodynamics (SPH) method is employed to solve the governing equations. All the optimization targets are achieved implicitly and consistently by the particle relaxation procedure without constructing triangulation/tetrahedralization explicitly. The target of communication reduction is achieved by introducing a surface tension model between distinct partitioning sub-domains, which are characterized by colored SPH particles. The resulting partitioning diagram features physically localized sub-domains and optimized interface communication. The target of optimizing the mesh quality is achieved by introducing a tailored equation-of-state (EOS) and a smooth isotropic kernel function. The mesh quality near the interface of neighboring sub-domains is improved by gradually removing the surface-tension force once a steady state is achieved. The proposed method is developed basing on a new parallel environment for multi-resolution SPH to exploit both coarse- and fine-grained parallelism. A set of benchmarks are conducted to verify that all the optimization targets are achieved consistently within the current framework.


65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
76M28 Particle methods and lattice-gas methods
Full Text: DOI arXiv


[1] Frey, P. J.; George, P.-L., Mesh Generation: Application to Finite Elements (2007), ISTE
[2] Park, M. A.; Krakos, J. A.; Michal, T.; Loseille, A.; Alonso, J. J., Unstructured grid adaptation: Status, potential impacts, and recommended investments toward CFD Vision 2030 (2016)
[3] Feng, D.; Tsolakis, C.; Chernikov, A. N.; Chrisochoides, N. P., Scalable 3D hybrid parallel Delaunay image-to-mesh conversion algorithm for distributed shared memory architectures, Procedia Eng., 124, 18-30 (2015)
[4] Feng, D.; Chernikov, A. N.; Chrisochoides, N. P., A hybrid parallel Delaunay image-to-mesh conversion algorithm scalable on distributed-memory clusters, Proc. Eng., 163, 59-71 (2016)
[5] Slotnick, J.; Khodadoust, A.; Alonso, J.; Darmofal, D.; Gropp, W.; Lurie, E.; Mavriplis, D., CFD vision 2030 study: a path to revolutionary computational aerosciences (2014)
[6] Schöberl, J., NETGEN An advancing front 2D/3D-mesh generator based on abstract rules, Comput. Vis. Sci., 1, 1, 41-52 (1997) · Zbl 0883.68130
[7] Löhner, R., Recent advances in parallel advancing front grid generation, Arch. Comput. Methods Eng., 21, 2, 127-140 (2014) · Zbl 1349.65667
[8] Shewchuk, J. R., Delaunay refinement algorithms for triangular mesh generation, Comput. Geom., 22, 1-3, 21-74 (2002) · Zbl 1016.68139
[9] Chew, L. P., Guaranteed-quality delaunay meshing in 3D (short version), (Proceedings of the Thirteenth Annual Symposium on Computational Geometry (1997), ACM), 391-393
[10] Ni, S.; Zhong, Z.; Liu, Y.; Wang, W.; Chen, Z.; Guo, X., Sliver-suppressing tetrahedral mesh optimization with gradient-based shape matching energy, Comput. Aided Geom. Design, 52, 247-261 (2017) · Zbl 1366.65043
[11] Du, Q.; Faber, V.; Gunzburger, M., Centroidal voronoi tessellations: Applications and algorithms, SIAM Rev., 41, 4, 637-676 (1999) · Zbl 0983.65021
[12] Fu, L.; Han, L.; Hu, X. Y.; Adams, N. A., An isotropic unstructured mesh generation method based on a fluid relaxation analogy, Comput. Methods Appl. Mech. Engrg., 350, 396-431 (2019)
[13] Zhong, Z.; Guo, X.; Wang, W.; Lévy, B.; Sun, F.; Liu, Y.; Mao, W., Particle-based anisotropic surface meshing, ACM Trans. Graph., 32, 4, 99 (2013)
[14] Fu, L.; Hu, X. Y.; Adams, N. A., Adaptive anisotropic unstructured mesh generation method based on fluid relaxation analogy, Commun. Comput. Phys. (2019), in press
[15] Du, Q.; Wang, D., Tetrahedral mesh generation and optimization based on Centroidal Voronoi Tessellations, Internat. J. Numer. Methods Engrg., 56, 9, 1355-1373 (2003) · Zbl 1106.74431
[16] Persson, P.-O., Mesh size functions for implicit geometries and PDE-based gradient limiting, Eng. Comput., 22, 2, 95-109 (2006)
[17] Meyer, M. D.; Georgel, P.; Whitaker, R. T., Robust particle systems for curvature dependent sampling of implicit surfaces, (International Conference on Shape Modeling and Applications 2005. International Conference on Shape Modeling and Applications 2005, SMI’05 (2005), IEEE), 124-133
[18] C. Tsolakis, N. Chrisochoides, M.A. Park, A. Loseille, T.R. Michal, Parallel anisotropic unstructured grid adaptation, in: AIAA Scitech 2019 Forum, 2019, p. 1995.
[19] Chrisochoides, N., Parallel mesh generation, (Numerical Solution of Partial Differential Equations on Parallel Computers (2006), Springer), 237-264 · Zbl 1097.65122
[20] Rakotoarivelo, H.; Ledoux, F.; Pommereau, F., Fine-grained locality-aware parallel scheme for anisotropic mesh adaptation, Proc. Eng., 163, 123-135 (2016)
[21] Lohner, R.; Cebral, J. R., Parallel advancing front grid generation, (International Meshing Roundtable, Sandia National Labs (1999), Citeseer)
[22] Linardakis, L.; Chrisochoides, N., Delaunay decoupling method for parallel guaranteed quality planar mesh refinement, SIAM J. Sci. Comput., 27, 4, 1394-1423 (2006) · Zbl 1102.65123
[23] Loseille, A.; Menier, V.; Alauzet, F., Parallel generation of large-size adapted meshes, Procedia Eng., 124, 57-69 (2015)
[24] Nave, D.; Chrisochoides, N.; Chew, L. P., Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains, Comput. Geom., 28, 2-3, 191-215 (2004) · Zbl 1059.65022
[25] Galtier, J.; George, P. L., Prepartitioning as a way to mesh subdomains in parallel, (5th International Meshing Roundtable (1996), Citeseer)
[26] Chew, L. P.; Chrisochoides, N.; Sukup, F., Parallel constrained Delaunay meshing, ASME Appl. Mech. Div. Publ., 220, 89-96 (1997)
[27] Feng, D.; Chernikov, A. N.; Chrisochoides, N. P., Two-level locality-aware parallel Delaunay image-to-mesh conversion, Parallel Comput., 59, 60-70 (2016)
[28] Remacle, J.-F.; Bertrand, V.; Geuzaine, C., A two-level multithreaded Delaunay kernel, Procedia Eng., 124, 6-17 (2015)
[29] Rokos, G.; Gorman, G. J.; Jensen, K. E.; Kelly, P. H., Thread parallelism for highly irregular computation in anisotropic mesh adaptation, (Proceedings of the 3rd International Conference on Exascale Applications and Software (2015), University of Edinburgh), 103-108
[30] Feng, D.; Chernikov, A. N.; Chrisochoides, N. P., A hybrid parallel Delaunay image-to-mesh conversion algorithm scalable on distributed-memory clusters, Comput. Aided Des., 103, 34-46 (2018)
[31] Fu, L.; Hu, X. Y.; Adams, N. A., A physics-motivated Centroidal Voronoi Particle domain decomposition method, J. Comput. Phys., 335, 718-735 (2017) · Zbl 1380.65263
[32] Forum, M. P., MPI: A Message-Passing Interface StandardTech. Rep. (1994), University of Tennessee: University of Tennessee Knoxville, TN, USA
[33] Board, O. A.R., OpenMP application program interface vsersion 3.0 (2008), URL http://www.openmp.org/mp-documents/spec30.pdf
[34] Nickolls, J.; Buck, I.; Garland, M.; Skadron, K., Scalable parallel programming with CUDA, Queue, 6, 2, 40-53 (2008), URL http://doi.acm.org/10.1145/1365490.1365500
[35] Crespo, A. J.; Domínguez, J. M.; Rogers, B. D.; Gómez-Gesteira, M.; Longshaw, S.; Canelas, R.; Vacondio, R.; Barreiro, A.; García-Feal, O., DualSPHysics: Open-source parallel CFD solver based on Smoothed Particle Hydrodynamics (SPH), Comput. Phys. Comm., 187, 204-216 (2015) · Zbl 1348.76005
[36] Plimpton, S., Fast parallel algorithms for short-range molecular dynamics, J. Comput. Phys., 117, 1, 1-19 (1995) · Zbl 0830.65120
[37] Incardona, P.; Leo, A.; Zaluzhnyi, Y.; Ramaswamy, R.; Sbalzarini, I. F., OpenFPM: A scalable open framework for particle and particle-mesh codes on parallel computers, Comput. Phys. Comm. (2019)
[38] Ji, Z.; Fu, L.; Hu, X. Y.; Adams, N. A., A new multi-resolution parallel framework for SPH, Comput. Methods Appl. Mech. Engrg., 346, 1156-1178 (2019)
[39] Fu, L.; Ji, Z.; Hu, X. Y.; Adams, N. A., Parallel fast-neighbor-searching and communication strategy for particle-based methods, Eng. Comput., 36, 3, 899-929 (2019)
[40] Contreras, G.; Martonosi, M., Characterizing and improving the performance of intel threading building blocks, (Workload Characterization, 2008. IISWC 2008. IEEE International Symposium on (2008), IEEE), 57-66
[41] Fu, L.; Litvinov, S.; Hu, X. Y.; Adams, N. A., A novel partitioning method for block-structured adaptive meshes, J. Comput. Phys., 341, 447-473 (2017) · Zbl 1376.76049
[42] Osher, S.; Sethian, J. A., Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys., 79, 1, 12-49 (1988) · Zbl 0659.65132
[43] Piegl, L., On NURBS: a survey, IEEE Comput. Graph. Appl., 11, 1, 55-71 (1991)
[44] Han, L.; Hu, X.; Adams, N. A., Adaptive multi-resolution method for compressible multi-phase flows with sharp interface model and pyramid data structure, J. Comput. Phys., 262, 131-152 (2014) · Zbl 1349.76338
[45] Lorensen, W. E.; Cline, H. E., Marching cubes: A high resolution 3D surface construction algorithm, (ACM Siggraph Computer Graphics, Vol. 21, No. 4 (1987), ACM), 163-169
[46] Brackbill, J.; Kothe, D. B.; Zemach, C., A continuum method for modeling surface tension, J. Comput. Phys., 100, 2, 335-354 (1992) · Zbl 0775.76110
[47] Lafaurie, B.; Nardone, C.; Scardovelli, R.; Zaleski, S.; Zanetti, G., Modelling merging and fragmentation in multiphase flows with SURFER, J. Comput. Phys., 113, 1, 134-147 (1994) · Zbl 0809.76064
[48] Si, H., TetGen, a Delaunay-based quality tetrahedral mesh generator, ACM Trans. Math. Softw., 41, 2, 11 (2015) · Zbl 1369.65157
[49] Starinshak, D. P.; Owen, J.; Johnson, J., A new parallel algorithm for constructing Voronoi tessellations from distributed input data, Comput. Phys. Commun., 185, 12, 3204-3214 (2014) · Zbl 1360.65076
[50] Chen, R.; Gotsman, C., Localizing the delaunay triangulation and its parallel implementation, (Transactions on Computational Science XX (2013), Springer), 39-55 · Zbl 1406.68114
[51] Ji, Z.; Fu, L.; Hu, X. Y.; Adams, N. A., A Lagrangian Inertial Centroidal Voronoi Particle method for dynamic load balancing in particle-based simulations, Comput. Phys. Comm., 239, 53-63 (2019)
[52] Fu, L.; Ji, Z., An optimal particle setup method with Centroidal Voronoi Particle dynamics, Comput. Phys. Comm., 234, 72-92 (2019)
[53] Adami, S.; Hu, X.; Adams, N. A., A new surface-tension formulation for multi-phase SPH using a reproducing divergence approximation, J. Comput. Phys., 229, 13, 5011-5021 (2010) · Zbl 1346.76161
[54] Meyerhenke, H.; Monien, B.; Schamberger, S., Graph partitioning and disturbed diffusion, Parallel Comput., 35, 10-11, 544-569 (2009)
[55] Turk, G.; Levoy, M., Zippered polygon meshes from range images, (Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques (1994), ACM), 311-318
[56] Barnes, E.; Sloane, N., The optimal lattice quantizer in three dimensions, SIAM J. Algebr. Discrete Methods, 4, 1, 30-41 (1983) · Zbl 0509.52010
[57] Hoehn, B. R.; Oster, P.; Tobie, T.; Michaelis, K., Test methods for gear lubricants, Goriva i maziva, 47, 2, 141-152 (2008)
[58] Löhner, R.; Onate, E., An advancing front point generation technique, Commun. Numer. Methods. Eng., 14, 12, 1097-1108 (1998) · Zbl 0920.65071
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.