zbMATH — the first resource for mathematics

An isotropic unstructured mesh generation method based on a fluid relaxation analogy. (English) Zbl 1441.65075
Summary: In this paper, we propose an unstructured mesh generation method based on Lagrangian-particle fluid relaxation, imposing a global optimization strategy. With the presumption that the geometry can be described as a zero level set, an adaptive isotropic mesh is generated by three steps. First, three characteristic fields based on three modeling equations are computed to define the target mesh-vertex distribution, i.e. target feature-size function and density function. The modeling solutions are computed on a multi-resolution Cartesian background mesh. Second, with a target particle density and a local smoothing-length interpolated from the target field on the background mesh, a set of physically-motivated model equations is developed and solved by an adaptive-smoothing-length Smoothed Particle Hydrodynamics (SPH) method. The relaxed particle distribution conforms well with the target functions while maintaining isotropy and smoothness inherently. Third, a parallel fast Delaunay triangulation method is developed based on the observation that a set of neighboring particles generates a locally valid Voronoi diagram at the interior of the domain. The incompleteness of near domain boundaries is handled by enforcing a symmetry boundary condition. A set of two-dimensional test cases shows the feasibility of the method. Numerical results demonstrate that the proposed method produces high-quality globally optimized adaptive isotropic meshes even for high geometric complexity.

65M50 Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
Full Text: DOI
[1] Chew, L. P., Guaranteed-Quality Triangular MeshesTech. Rep. (1989), Cornell University
[2] Křížek, M.; Neittaanmäki, P., Superconvergence phenomenon in the finite element method arising from averaging gradients, Numer. Math., 45, 1, 105-116 (1984) · Zbl 0575.65104
[3] Huang, Y.; Qin, H.; Wang, D., Centroidal Voronoi tessellation-based finite element superconvergence, Internat. J. Numer. Methods Engrg., 76, 12, 1819-1839 (2008) · Zbl 1195.65171
[4] Fabritius, B.; Tabor, G., Improving the quality of finite volume meshes through genetic optimisation, Eng. Comput., 32, 3, 425-440 (2016)
[5] McRae, D.; Laflin, K., Dynamic grid adaptation and grid quality (1998)
[6] Löhner, R., Progress in grid generation via the advancing front technique, Eng. Comput., 12, 3-4, 186-210 (1996)
[7] Frey, P. J.; Borouchaki, H.; George, P.-L., 3d Delaunay mesh generation coupled with an advancing-front approach, Comput. Methods Appl. Mech. Engrg., 157, 1, 115-131 (1998) · Zbl 0947.65130
[8] Shewchuk, J. R., Delaunay refinement algorithms for triangular mesh generation, Comput. Geom., 22, 1-3, 21-74 (2002) · Zbl 1016.68139
[9] Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms, SIAM Rev., 41, 4, 637-676 (1999) · Zbl 0983.65021
[10] Du, Q.; Gunzburger, M., Grid generation and optimization based on centroidal Voronoi tessellations, Appl. Math. Comput., 133, 2, 591-607 (2002) · Zbl 1024.65118
[11] Szeliski, R.; Tonnesen, D., Surface Modeling with Oriented Particle Systems, vol. 26 (1992), ACM
[12] Witkin, A. P.; Heckbert, P. S., Using particles to sample and control implicit surfaces, (Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques (1994), ACM), 269-277
[13] Rebay, S., Efficient unstructured mesh generation by means of Delaunay triangulation and Bowyer-Watson algorithm, J. Comput. Phys., 106, 1, 125-138 (1993) · Zbl 0777.65064
[14] Engwirda, D.; Ivers, D., Off-centre steiner points for Delaunay-refinement on curved surfaces, Comput. Aided Des., 72, 157-171 (2016)
[15] Lloyd, S. P., Least squares quantization in PCM, IEEE Trans. Inf. Theory, 28, 2, 129-137 (1982) · Zbl 0504.94015
[17] Du, Q.; Emelianenko, M., Uniform convergence of a nonlinear energy-based multilevel quantization scheme, SIAM J. Numer. Anal., 46, 3, 1483-1502 (2008) · Zbl 1171.65011
[18] Ostrovsky, R.; Rabani, Y.; Schulman, L. J.; Swamy, C., The effectiveness of Lloyd-type methods for the k-means problem, (Foundations of Computer Science, 2006 FOCS’06 47th Annual IEEE Symposium on (2006), IEEE), 165-176
[19] Liu, Y.; Wang, W.; Lévy, B.; Sun, F.; Yan, D.-M.; Lu, L.; Yang, C., On centroidal Voronoi tessellation energy smoothness and fast computation, ACM Trans. Graph. (ToG), 28, 4, 101 (2009)
[20] Valette, S.; Chassery, J.-M.; Prost, R., Generic remeshing of 3d triangular meshes with metric-dependent discrete Voronoi diagrams, IEEE Trans. Vis. Comput. Graph., 14, 2, 369-381 (2008)
[21] Du, Q.; Wang, D., Anisotropic centroidal voronoi tessellations and their applications, SIAM J. Sci. Comput., 26, 3, 737-761 (2005) · Zbl 1121.65306
[22] Meyer, M. D.; Georgel, P.; Whitaker, R. T., Robust particle systems for curvature dependent sampling of implicit surfaces, (Shape Modeling and Applications, 2005 International Conference (2005), IEEE), 124-133
[23] Bronson, J. R.; Levine, J. A.; Whitaker, R. T., Particle systems for adaptive, isotropic meshing of CAD models, (Proceedings of the 19th International Meshing Roundtable (2010), Springer), 279-296
[24] Bossen, F., Anisotropic Mesh Generation with ParticlesTech. Rep., DTIC Document (1996)
[25] Persson, P.-O.; Strang, G., A simple mesh generator in MATLAB, SIAM Rev., 46, 2, 329-345 (2004) · Zbl 1061.65134
[26] Persson, P.-O., Mesh Generation for Implicit Geometries (2005), Massachusetts Institute of Technology, (Ph.D. thesis)
[27] Persson, P.-O., Mesh size functions for implicit geometries and PDE-based gradient limiting, Eng. Comput., 22, 2, 95-109 (2006)
[28] 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)
[29] 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
[30] Han, L.; Hu, X.; Adams, N., 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
[31] Samet, H., The quadtree and related hierarchical data structures, ACM Comput. Surv., 16, 2, 187-260 (1984)
[33] Fu, L.; Hu, X. Y.; Adams, N. A., Single-step reinitialization and extending algorithms for level-set based multi-phase flow simulations, Comput. Phys. Comm., 221, 63-80 (2017)
[34] Sussman, M.; Smereka, P.; Osher, S., A level set approach for computing solutions to incompressible two-phase flow, J. Comput. Phys., 114, 1, 146-159 (1994) · Zbl 0808.76077
[35] Crane, K.; Weischedel, C.; Wardetzky, M., The heat method for distance computation, Commun. ACM, 60, 11, 90-99 (2017)
[36] Monaghan, J. J., Smoothed particle hydrodynamics, Rep. Progr. Phys., 68, 1703-1759 (2005)
[37] Hu, X. Y.; Adams, N. A., A multi-phase SPH method for macroscopic and mesoscopic flows, J. Comput. Phys., 213, 844-861 (2006) · Zbl 1136.76419
[38] Yang, X. F.; Liu, M. B.; Peng, S. L., Smoothed particle hydrodynamics modeling of viscous liquid drop without tensile instability, Comput. & Fluids, 92, 199-208 (2014) · Zbl 1391.76644
[39] Hockney, R. W.; Eastwood, J. W., Computer Simulation Using Particles (1988), CRC Press · Zbl 0662.76002
[40] 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
[41] Verlet, L., Computer experiments on classical fluids. I. Thermodynamical properties of Lennard-Jones molecules, Phys. Rev., 159, 98-103 (1967)
[42] 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
[43] Fortune, S., A sweepline algorithm for voronoi diagrams, Algorithmica, 2, 1-4, 153-174 (1987) · Zbl 0642.68079
[44] Frey, P. J.; Borouchaki, H., Surface mesh quality evaluation, Internat. J. Numer. Methods Engrg., 45, 1, 101-118 (1999) · Zbl 0939.65020
[45] Nguyen, H.; Burkardt, J.; Gunzburger, M.; Ju, L.; Saka, Y., Constrained CVT meshes and a comparison of triangular mesh generators, Comput. Geom., 42, 1, 1-19 (2009) · Zbl 1152.65035
[46] Amenta, N.; Levy, S.; Munzner, T.; Phillips, M., Geomview: A system for geometric visualization, (Proceedings of the Eleventh Annual Symposium on Computational Geometry (1995), ACM), 412-413
[47] Schäling, B., The boost c++ libraries, (Boris Schäling (2011))
[48] Zalesak, S. T., Fully multidimensional flux-corrected transport algorithms for fluids, J. Comput. Phys., 31, 3, 335-362 (1979) · Zbl 0416.76002
[51] Du, Q.; Wang, D., The optimal centroidal voronoi tessellations and the Gersho’s conjecture in the three-dimensional space, Comput. Math. Appl., 49, 9, 1355-1373 (2005) · Zbl 1077.65019
[52] Fu, L.; Ji, Z.; Hu, X. Y.; Adams, N. A., Parallel fast-neighbor-searching and communication strategy for particle-based methods, Eng. Comput. (2019)
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.