Variational method for untangling and optimization of spatial meshes. (English) Zbl 1302.65265
Summary: A variational method that can provably construct 3D quasi-isometric mappings between domains of a complex shape is introduced. A local maximum principle for polyconvex mesh element distortion measures is formulated. It allows us to control the invertibility and distortion bounds for non-simplicial elements in the minimization process. A simple and efficient technique for construction of boundary orthogonal meshes suggested in V. A. Garanzha [Comput. Math. Math. Phys. 40, 1617–1637 (2000; Zbl 1004.65131)] is applied to the construction of hexahedral meshes and thick prismatic mesh layers around complex shapes. The mesh untangling technique, which is a generalization of the penalty method suggested in V. A. Garanzha and I. E. Kaporin [Comput. Math. Math. Phys. 39, No. 9, 1426–1440 (1999); translation from Zh. Vychisl. Mat. Mat. Fiz. 39, No. 9, 1489–1503 (1999; Zbl 0977.65111)], is verified on a wide set of challenging test problems. Another untangling technique based on theoretical ideas from S. A. Ivanenko [Adaptive-harmonic grids. Moskva: Vychislitel’nyj Tsentr RAN. 182 p. (1997; Zbl 0945.65523)] is implemented and tested. It provably constructs admissible meshes using a finite number of minimization steps. A minimization technique for the mesh distortion functional is described. The approach is based on the global gradient search technique with preconditioning and domain decomposition for local mesh optimization and untangling. Application areas for explicit and implicit minimization methods are evaluated.
MSC:
| 65N50 | Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs |
Keywords:
variational mesh generation; mesh untangling; barrier functional; quasi-isometric mapping; polyconvexitySoftware:
LOGOSReferences:
| [1] | Crowley, W. P., An Equipotential Zoner on a Quadrilateral Mesh (1962), Memo, Lawrence Livermore National Lab |
| [2] | Winslow, A. M., Numerical solution of the quasilinear Poisson equation in a nonuniform triangle mesh, J. Comput. Phys., 2, 149-172 (1967) · Zbl 0254.65069 |
| [3] | Brackbill, J. U.; Saltzman, J. S., Adaptive zoning for singular problems in two dimensions, J. Comput. Phys., 46, 342-368 (1982) · Zbl 0489.76007 |
| [4] | Jacquotte, O-P., A mechanical model for a new mesh generation method in computational fluid dynamics, Comput. Methods Appl. Mech. Engrg., 66, 323-338 (1988) · Zbl 0619.76029 |
| [5] | Ivanenko, S. A., Construction of nondegenerate grids, Comput. Math. Math. Phys., 28, 5, 141-146 (1988) · Zbl 0695.65070 |
| [6] | Liseikin, V. D., On the construction of regular grids on \(n\)-dimensional surfaces, Comput. Math. Math. Phys., 31, 11, 47-57 (1991) · Zbl 0785.65108 |
| [7] | Liseikin, V. D., Grid Generation Methods (1999), Springer: Springer Berlin, Heidelberg, New York · Zbl 0949.65098 |
| [8] | Knupp, P. M., Achieving finite element mesh quality via optimization of the Jacobian matrix norma nd associated quantities. Part I a framework for surface mesh optimization, Int. J. Numer. Methods Eng., 48, 3, 401-420 (2000) · Zbl 0964.65140 |
| [9] | Knupp, P. M., Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities. Part II a framework for volume mesh optimization and the condition number of the Jacobian matrix, Int. J. Numer. Methods Eng., 48, 8, 1165-1185 (2000) · Zbl 0990.74069 |
| [10] | Knupp, P., Algebraic mesh quality metrics, SIAM J. Sci. Comput., 23, 193-218 (2001) · Zbl 0996.65101 |
| [11] | Knupp, P. M., A method for hexahedral mesh shape optimization, Int. J. Numer. Methods Eng., 58, 2, 319-332 (2003) · Zbl 1035.65020 |
| [12] | Freitag, L. A.; Knupp, P. M., Tetrahedral mesh improvement via optimization of the element condition number, Int. J. Numer. Methods Eng., 53, 1377-1391 (2002) · Zbl 1112.74512 |
| [13] | Liseikin, V. D., Grid Generation Methods (2010), Springer-Verlag: Springer-Verlag Berlin, Heidelberg, New York · Zbl 1196.65158 |
| [14] | (Thompson, J. F.; Soni, B. K.; Weatherill, N., Handbook of Grid Generation (1998), CRC Press) · Zbl 0980.65500 |
| [15] | Beg, M. F.; Miller, M. I.; Trouve, A.; Younes, L., Computing large deformation metric mappings via geodesics flows of diffeomorphisms, Int. J. Comput. Vis., 61, 2, 139-157 (2005) · Zbl 1477.68459 |
| [16] | Trouve, A., An Approach of Pattern Recognition through Infinite Dimensional Group Action, Research Report LMENS-95-9 (1995) |
| [17] | Rumpf, M., A variational approach to optimal meshes, Numer. Math., 72, 4, 523-540 (1996) · Zbl 0863.65075 |
| [20] | Riemslagh, K.; Vierendeels, J.; Dick, E., Two-dimensional incompressible Navier-Stokes calculations in complex-shaped moving domains. A celebration of the sixty-fifth anniversary of Pieter J. Zandbergen: teacher and research leader in applied mathematics, J. Engrg. Math., 34, 1-2, 57-73 (1998) · Zbl 0917.76065 |
| [21] | Garanzha, V. A.; Kaporin, I. E., Regularization of the barrier variational method for constructing computational grids, Comput. Math. Math. Phys., 39, 9, 1426-1440 (1999) · Zbl 0977.65111 |
| [22] | Freitag, L. A.; Plassmann, P., Local optimization-based simplicial mesh untangling and improvement, Int. J. Numer. Methods Eng., 49, 1-2, 109-125 (2000) · Zbl 0962.65098 |
| [23] | Knupp, P. M., Hexahedral and tetrahedral mesh untangling, Eng. Comput., 17, :261-268 (2001) · Zbl 0983.68564 |
| [24] | Garanzha, V. A., Maximum norm optimization of quasi-isometric mappings, Numer. Linear Algebra Appl., 9, 6-7, 493-510 (2002) · Zbl 1071.65094 |
| [25] | Branets, L. V.; Garanzha, V. A., Distortion measure for trilinear mapping. Application to 3-D grid generation, Numer. Linear Algebra Appl., 9, 6-7, 511-526 (2002) · Zbl 1071.65555 |
| [26] | Escobar, J. M.; Rodriguez, E.; Montenegro, R.; Montero, G.; Gonsalez-Yuste, J. M., Simultaneous untangling and smoothing of tetrahedral meshes, Comput. Methods Appl. Mech. Eng., 192, 2775-2787 (2003) · Zbl 1037.65126 |
| [27] | Vachal, P.; Garimella, R. V.; Shashkov, M. J., Untangling of 2D meshes in ALE simulations, J. Comput. Phys., 196, 2, 627-644 (2004) · Zbl 1109.76332 |
| [28] | Lopez, E. J.; Nigro, N. M.; Storti, M. A., Simultaneous untangling and smoothing of moving grids, Int. J. Numer. Methods Eng., 76, 7, 994-1019 (2008) · Zbl 1195.74312 |
| [29] | Danczyk, J.; Surech, K., Finite element analysis over tangled simplicial meshes: theory and implementation, Finite Elem. Anal. Des., 70-71, 57-67 (2013) · Zbl 1302.65251 |
| [30] | Godunov, S. K.; Gordienko, V. M.; Chumakov, G. A., Quasi-isometric parametrization of a curvilinear quadrangle and a metric of constant curvature, Siberian Adv. Math., 5, 2, 1-20 (1995) · Zbl 0861.53011 |
| [31] | Garanzha, V. A., The barrier method for constructing quasi-isometric grids, Comput. Math. Math. Phys., 40, 11, 1617-1637 (2000) · Zbl 1004.65131 |
| [32] | Garanzha, V. A., Quasi-isometric surface parameterization, Appl. Numer. Math., 55, 3, 295-311 (2005) · Zbl 1081.65021 |
| [33] | Garanzha, V. A.; Kaporin, I. E., On the convergence of a gradient method for the minimization of functionals in the theory of elasticity with finite deformations and for the minimization of barrier grid functionals, Comput. Math. Math. Phys., 45, 8, 1400-1415 (2005) · Zbl 1091.74019 |
| [34] | Garanzha, V. A., Polyconvex potentials, invertible deformations and thermodynamically consistent formulation of nonlinear elasticity equations, Comp. Math. Math. Phys., 50, 9, 1561-1587 (2010) · Zbl 1224.74003 |
| [35] | Floater, M. S.; Hormann, K., Surface parameterization: a tutorial and survey. advances in multiresolution for geometric modelling, Math. Vis., 157-186 (2005) · Zbl 1065.65030 |
| [36] | Jacquotte, O.-P., Grid optimization methods for quality improvement and adaptation, (Thompson, J. F.; Soni, B. K.; Weatherill, N., Handbook of Grid Generation (1998), CRC Press), Section 33 |
| [37] | Shontz, S. M.; Vavasis, S. A., A robust solution procedure for hyperelastic solids with large boundary deformation, Eng. Comput., 28, 2, 135-147 (2012) |
| [38] | Ball, J. M., Convexity conditions and existence theorems in nonlinear elasticity, Arch. Ration. Mech. Anal., 63, 337-403 (1977) · Zbl 0368.73040 |
| [39] | Ball, JM., Global invertibility of Sobolev functions and the interpenetration of matter, Proc. Roy. Soc. Edinburgh., 88A., 315-328 (1981) · Zbl 0478.46032 |
| [40] | Liu, A.; Joe, B., On the shape of tetrahedra from bisection, Math. Comput., 63, 141-154 (1994) · Zbl 0815.51016 |
| [41] | Sastry, S. P.; Shontz, S. M.; Vavasis, S. A., A log-barrier method for mesh quality improvement, (Proceedings of the 20th International Meshing Roundtable (2011), Springer), 329-346 |
| [42] | Sastry, S. P.; Shontz, S. M.; Vavasis, S. A., A log-barrier method for mesh quality improvement and untangling, Eng. Comput. (November 2012), Published online ahead of print |
| [43] | Ivanenko, S. A., Grid generation with cell shape control, Comp. Math. Math. Phys., 40, 11, 1662-1684 (2000) · Zbl 1004.65130 |
| [44] | Vavasis, S. A., A Bernstein-Bezier Sufficient Condition for Invertibility of Polynomial Mapping Functions, Research Report CoRR cs.NA/0308021 (2003) |
| [45] | Farin, G., Curves and Surfaces for Computer-aided Geometric Design (1997), Academic Press · Zbl 0919.68120 |
| [47] | Kim, J.; Panitanarak, T.; Shontz, S. M., A multiobjective mesh optimization framework for mesh quality improvement and mesh untangling, Internat. J. Numer. Methods Engrg., 94, 1, 20-42 (2013) · Zbl 1352.65611 |
| [49] | Charakhchyan, A. A.; Ivanenko, S. A., A variational form of the Winslow grid generator, J. Comput. Phys., 136, 385-398 (1997) · Zbl 0887.65118 |
| [50] | Branets, L.; Carey, G. F., Extension of a mesh quality metric for elements with a curved boundary edge or surface, J. Comp. Inf. Sci. Eng., 5, 4 (2005) |
| [51] | Ball, J. M., Some open problems in elasticity, (Geometry, Mechanics, and Dynamics (2002), Springer: Springer New York), 3-59 · Zbl 1054.74008 |
| [52] | Utyuzhnikov, S. V.; Rudenko, D. V., An adaptive moving mesh method with application to nontstationary hypersonic flows in the atmosphere, Proc. Inst. Mech. Eng. G, 222, 5, 661-671 (2008) |
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.
