×

Generalised primal-dual grids for unstructured co-volume schemes. (English) Zbl 1416.65325

Summary: The generation of high-quality staggered unstructured grids is considered, leading to the development of a new optimisation-based strategy designed to construct weighted ‘regular-power’ tessellations appropriate for co-volume type numerical discretisation techniques. This new framework aims to extend the conventional Delaunay-Voronoi primal-dual structure; seeking to assemble generalised orthogonal tessellations with enhanced geometric quality. The construction of these grids is motivated by the desire to improve the performance and accuracy of numerical methods based on unstructured co-volume type schemes, including various staggered grid techniques for the simulation of fluid dynamics and hyperbolic transport. In this study, a new hybrid optimisation strategy is proposed; seeking to optimise the geometry, topology and weights associated with general, two-dimensional regular-power tessellations using a combination of gradient-ascent and energy-based techniques. The performance of this new method is tested experimentally, with a range of complex, multi-resolution primal-dual grids generated for various coastal and regional ocean modelling applications.

MSC:

65M50 Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs
35L40 First-order hyperbolic systems
65M08 Finite volume methods for initial value and initial-boundary value problems involving PDEs
65M06 Finite difference methods for initial value and initial-boundary value problems involving PDEs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Harlow, F. H.; Welch, J. E., Numerical calculation of time-dependent viscous incompressible flow of fluid with free surface, Phys. Fluids, 8, 12, 2182-2189 (1965) · Zbl 1180.76043
[2] Arakawa, A.; Lamb, V. R., Computational design of the basic dynamical processes of the UCLA general circulation model, Methods Comput. Phys., 17, 173-265 (1977)
[3] Memari, P.; Mullen, P.; Desbrun, M., Parametrization of generalized primal-dual triangulations, (Proceedings of the 20th International Meshing Roundtable (2011), Springer), 237-253
[4] Shewchuk, J. R., Triangle: engineering a 2D quality mesh generator and Delaunay triangulator, (Applied Computational Geometry Towards Geometric Engineering (1996), Springer), 203-222
[5] Si, H., TetGen, a Delaunay-based quality tetrahedral mesh generator, ACM Trans. Math. Softw., 41, 2, 11 (2015) · Zbl 1369.65157
[6] Jamin, C.; Alliez, P.; Yvinec, M.; Boissonnat, J.-D., CGALmesh: a generic framework for Delaunay mesh generation, ACM Trans. Math. Softw., 41, 4, 23 (2015) · Zbl 1347.65047
[7] 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
[8] Geuzaine, C.; Remacle, J.-F., Gmsh: A 3-D finite element mesh generator with built-in pre- and post-processing facilities, Int. J. Numer. Methods Eng., 79, 11, 1309-1331 (2009) · Zbl 1176.74181
[9] Engwirda, D., JIGSAW-GEO (1.0): locally orthogonal staggered unstructured grid generation for general circulation modelling on the sphere, Geosci. Model Dev., 10, 6, 2117 (2017)
[10] Aurenhammer, F., Power diagrams: properties, algorithms and applications, SIAM J. Comput., 16, 1, 78-96 (1987) · Zbl 0616.52007
[11] Edelsbrunner, H., Algorithms in Combinatorial Geometry, vol. 10 (2012), Springer Science & Business Media
[12] Ringler, T.; Thuburn, J.; Klemp, J.; Skamarock, W., A unified approach to energy conservation and potential vorticity dynamics for arbitrarily-structured C-grids, J. Comput. Phys., 229, 9, 3065-3090 (2010) · Zbl 1307.76054
[13] Ringler, T.; Petersen, M.; Higdon, R.; Jacobsen, D.; Jones, P.; Maltrud, M., A multi-resolution approach to global ocean modeling, Ocean Model., 69, 211-232 (2013)
[14] Thuburn, J.; Ringler, T.; Skamarock, W.; Klemp, J., Numerical representation of geostrophic modes on arbitrarily structured C-grids, J. Comput. Phys., 228, 22, 8321-8335 (2009) · Zbl 1173.86304
[15] Korn, P., Formulation of an unstructured grid model for global ocean dynamics, J. Comput. Phys., 339, 525-552 (2017) · Zbl 1380.65275
[16] Korn, P.; Danilov, S., Elementary dispersion analysis of some mimetic discretizations on triangular C-grids, J. Comput. Phys., 330, 156-172 (2017) · Zbl 1380.65220
[17] Skamarock, W. C.; Klemp, J. B.; Duda, M. G.; Fowler, L. D.; Park, S.-H.; Ringler, T. D., A multiscale nonhydrostatic atmospheric model using centroidal Voronoi tesselations and C-grid staggering, Mon. Weather Rev., 140, 9, 3090-3105 (2012)
[18] Vanderzee, E.; Hirani, A. N.; Guoy, D.; Ramos, E., Well-centered planar triangulation - an iterative approach, (Proceedings of the 16th International Meshing Roundtable (2008), Springer), 121-138 · Zbl 1134.65330
[19] Vanderzee, E.; Hirani, A. N.; Guoy, D.; Ramos, E. A., Well-centered triangulation, SIAM J. Sci. Comput., 31, 6, 4497-4523 (2010) · Zbl 1253.65030
[20] Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms, SIAM Rev., 41, 4, 637-676 (1999) · Zbl 0983.65021
[21] Du, Q.; Gunzburger, M., Grid generation and optimization based on centroidal Voronoi tessellations, Appl. Math. Comput., 133, 2, 591-607 (2002) · Zbl 1024.65118
[22] Alliez, P.; Cohen-Steiner, D.; Yvinec, M.; Desbrun, M., Variational tetrahedral meshing, (Transactions on Graphics (TOG), vol. 24 (2005), ACM), 617-625
[23] Chen, L.; Xu, J.-C., Optimal Delaunay triangulations, J. Comput. Math., 299-308 (2004) · Zbl 1048.65020
[24] Chen, L.; Holst, M., Efficient mesh optimization schemes based on optimal Delaunay triangulations, Comput. Methods Appl. Mech. Eng., 200, 9, 967-984 (2011) · Zbl 1225.65113
[25] Mullen, P.; Memari, P.; de Goes, F.; Desbrun, M., HOT: Hodge-optimized triangulations, ACM Trans. Graph., 30, 4, 103 (2011)
[26] Goes, F.d.; Memari, P.; Mullen, P.; Desbrun, M., Weighted triangulations for geometry processing, ACM Trans. Graph. (TOG), 33, 3, 28 (2014)
[27] Walton, S.; Hassan, O.; Morgan, K., Advances in co-volume mesh generation and mesh optimisation techniques, Comput. Struct., 181, 70-88 (2017)
[28] Walton, S.; Hassan, O.; Morgan, K., Reduced order mesh optimisation using proper orthogonal decomposition and a modified cuckoo search, Int. J. Numer. Methods Eng., 93, 5, 527-550 (2013) · Zbl 1352.65156
[29] Walton, S.; Hassan, O.; Morgan, K., Selected engineering applications of gradient free optimisation using cuckoo search and proper orthogonal decomposition, Arch. Comput. Methods Eng., 20, 2, 123-154 (2013)
[30] Jacobsen, D.; Gunzburger, M.; Ringler, T.; Burkardt, J.; Peterson, J., Parallel algorithms for planar and spherical Delaunay construction with an application to centroidal Voronoi tessellations, Geosci. Model Dev., 6, 4, 1353-1365 (2013)
[31] Ringler, T.; Ju, L.; Gunzburger, M., A multiresolution method for climate system modeling: application of spherical centroidal Voronoi tessellations, Ocean Dyn., 58, 5-6, 475-498 (2008)
[32] J.R. Shewchuk, Lecture notes on geometric robustness, Interpolation, Conditioning, and Quality Measures. In Eleventh International Meshing Roundtable.; J.R. Shewchuk, Lecture notes on geometric robustness, Interpolation, Conditioning, and Quality Measures. In Eleventh International Meshing Roundtable.
[33] Perot, B., Conservation properties of unstructured staggered mesh schemes, J. Comput. Phys., 159, 1, 58-89 (2000) · Zbl 0972.76068
[34] Peixoto, P. S.; Barros, S. R., On vector field reconstructions for semi-Lagrangian transport methods on geodesic staggered grids, J. Comput. Phys., 273, 185-211 (2014) · Zbl 1351.86005
[35] Peixoto, P. S., Accuracy analysis of mimetic finite volume operators on geodesic grids and a consistent alternative, J. Comput. Phys., 310, 127-160 (2016) · Zbl 1349.76376
[36] Freitag, L. A.; Ollivier-Gooch, C., Tetrahedral mesh improvement using swapping and smoothing, Int. J. Numer. Methods Eng., 40, 21, 3979-4002 (1997) · Zbl 0897.65075
[37] Klingner, B. M.; Shewchuk, J. R., Aggressive tetrahedral mesh improvement, (Proceedings of the 16th International Meshing Roundtable (2008), Springer), 3-23 · Zbl 1238.65011
[38] Parthasarathy, V. N.; Graichen, C. M.; Hathaway, A. F., A Comparison of tetrahedron quality measures, Finite Elem. Anal. Des., 15, 3, 255-261 (1994)
[39] Shewchuk, J., What is a Good Linear Finite element? Interpolation, Conditioning, Anisotropy, and Quality Measures (2002), University of California at Berkeley, 70 pp
[40] Gosselin, S.; Ollivier-Gooch, C. F., Tetrahedral mesh generation using Delaunay refinement with non-standard quality measures, Int. J. Numer. Methods Eng., 87, 8, 795-820 (2011) · Zbl 1242.65257
[41] Lawson, C. L., Software for \(C^1\) surface interpolation, (Rice, J. R., Mathematical Software III (1977), Academic Press: Academic Press New York), 161-194 · Zbl 0407.68033
[42] Engwirda, D., JIGSAW(GEO): unstructured grid generation for geophysical modelling (2017)
[43] Amante, C.; Eakins, B. W., ETOPO1 1 arc-Minute Global Relief Model: Procedures, Data Sources and Analysis (2009), US Department of Commerce, National Oceanic and Atmospheric Administration, National Environmental Satellite, Data, and Information Service, National Geophysical Data Center, Marine Geology and Geophysics Division Colorado
[44] Engwirda, D.; Ivers, D., Off-centre Steiner points for Delaunay-refinement on curved surfaces, Comput. Aided Des., 72, 157-171 (2016)
[45] Persson, P.-O., Mesh size functions for implicit geometries and PDE-based gradient limiting, Eng. Comput., 22, 2, 95-109 (2006)
[46] Chen, Z.; Wang, W.; Lévy, B.; Liu, L.; Sun, F., Revisiting optimal Delaunay triangulation for 3D graded mesh generation, SIAM J. Sci. Comput., 36, 3, A930-A954 (2014) · Zbl 1298.49049
[47] Cheng, S. W.; Dey, T. K.; Shewchuk, J. R., Delauay Mesh Generation (2013), Taylor & Francis: Taylor & Francis New York
[48] Boissonnat, J. D.; Devillers, O.; Pion, S.; Teillaud, M.; Yvinec, M., Triangulations in CGAL, Comput. Geom. Theory Appl., 22, 1-3, 5-19 (2002) · Zbl 1016.68138
[49] Yee, K., Numerical solution of initial boundary value problems involving Maxwell’s equations in isotropic media, IEEE Trans. Antennas Propag., 14, 3, 302-307 (1966) · Zbl 1155.78304
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.