Nondegeneracy tests for hexahedral cells

doi:10.1016/j.cma.2011.01.014

Computer Methods in Applied Mechanics and Engineering

Volume 200, Issues 17–20, 1 April 2011, Pages 1649-1658

https://doi.org/10.1016/j.cma.2011.01.014 Get rights and content

Abstract

The aims of the paper are to consider the nondegeneracy requirement for computational grids and to analyze eight tests used to check the nondegeneracy of hexahedral cells. The paper starts with consideration of nondegeneracy requirement and formulation of definitions and common theorems utilized for estimation of nondegeneracy of grids both structured and unstructured. Then hexahedral cells are introduced and sufficient nondegeneracy conditions (Ushakova, 2000) for them are given. Sufficient nondegeneracy conditions are 27 inequalities for 32 tetrahedral volumes. Besides sufficient nondegeneracy conditions other conditions are applied as nondegeneracy tests in grid generation theory and practice. Considered nondegeneracy tests are the checks for positivity of different values. Tests 1, 2, 3, 4, 5, 6 check the positivity of 8, 10, 24, 32, 58, 48 tetrahedral volumes, correspondingly. Test 7 verifies the positivity of the volume of a cell. Test 8 checks the positivity of the Jacobian of the mapping used for generation of a cell. The check is performed at the corners of a cell and hex center. Tests 1, 7, 8 are often used in commercial packages. For the most part, nondegeneracy tests are not sufficient nondegeneracy conditions, however they are used for the purpose of constructing nondegenerate grids and, some times, instead of sufficient nondegeneracy conditions. The effectiveness and reliability of such substitutions are investigated in special numerical experiments with random numbers. In the numerical experiment for each test, hexahedral cells are generated randomly. Results of such experiments are the following. Among eight tests, test 2 is considered the best since it verifies the volumes of only 10 tetrahedra for positiveness, guarantees the nondegeneracy in most of cases (68.7% randomly generated hexahedral cells satisfying test 2) and covers a wide class of cells (about 60% of nondegenerate cells). Tests 1, 3, 4, 5, 6, 7, 8 have success in 31.7%, 83.1%, 100%, 100%, 39.5%, 0.2%, 34% of cases and cover 100%, 7.9%, 7.9%, 4.2%, 59.5%, 100%, 100% of nondegenerate cells, correspondingly. Because of high rate of success, tests 3, 4, 5 also can be used for grid generation purpose. All tests are illustrated by the examples of structured grids.

Introduction

Computational grids and grid generation methods are one of the tools using for mathematical simulation of physical field phenomena and processes. The main requirement to a grid is its nondegeneracy. This requirement is very important, since the physical phenomenon cannot be described with required accuracy on degenerate grids. In this case, systems of algebraic equations, replacing an initial differential problem, are ill conditioned. Thus, nondegeneracy of a grid is one of chief aims of the grid generation algorithm, and both a mathematician developing a grid generation method and a practicing engineer must care about this. Among other requirements influential in accuracy of the solution of a problem (we mean mainly the case of structured grids), the requirements usually considered are: smoothness of grid lines, closeness of a grid to uniform and orthogonal grid, and adaptation to the solution of a physical problem [16]. In the present paper, we will not concern these requirements but investigate only the requirement of nondegeneracy, since, despite of significance, the problem of nondegeneracy is stated not in all researches on constructing grids, and discussion of this question is often omitted. We shall examine nondegeneracy of grids using the main instrument for its construction — the mapping approach. According to this approach the computational grids both structured and unstructured (and their cells) in the domains of complicated geometrical forms are usually constructed by a continuous mapping of an auxiliary domain of a simpler form into the domain of a complicated form. We shall start with formalization of nondegeneracy requirement and formulation of definitions and some general theorems which can be used to estimate nondegeneracy of grids (see Section 2 and Appendix).

Then different nondegeneracy tests will be analyzed for a three-dimensional case. Especially in the three-dimensional case such tests are very important, since a visualization of three-dimensional grids is complicated. Such tests will be analyzed for hexahedral cells. In the three-dimensional case, hexahedral cells are widely used for constructing computational grids in numerical solving physical problems. Hexahedral cells are constructed by applying a trilinear smooth mapping and introduced in Section 3. Such cells were called ruled cells in [24]. These cells possess complex geometry (in the general case, they have nonflat ruled faces) and are associated with complicated nondegeneracy conditions [18], [25], [26] (see Section 4). Specifically, in the sufficient nondegeneracy conditions [18], [25], [26], we have to verify 27 conditions for 32 tetrahedral volumes. For a long time, for hexahedral cells there were no nondegeneracy conditions at all. For these reasons, an idea arose to replace the nondegeneracy conditions for hexahedral cells by simpler conditions which are not necessarily sufficient (we call them nondegeneracy tests) and to replace hexahedral cells by those of simpler shape, namely, by dodecahedral cells with flat faces (see, e.g., [2], [15]). This replacement was used primarily to substantiate and design numerical algorithms for various problems, including the computation of grids with hexahedral ruled cells. In connection with such substitutions, first, it is interesting and necessary to know whether the class of nondegenerate hexahedral cells coincides with that of nondegenerate dodecahedral cells. Second, it is also interesting and necessary to know what nondegeneracy tests can substitute nondegeneracy conditions [18], [25], [26] in computational practice. The answers to above questions are given in Section 5. Different nondegeneracy tests [2], [15], [22], [30], a test which can be suggested for tetrahedrons from [14] and some tests used in commercial packages are investigated in special numerical experiments with randomly generated hexahedrons.

Section snippets

Nondegeneracy requirement

We shall use the following formalization of nondegeneracy requirement [27]. We investigate the problem of nondegeneracy on the example of structured grids. In doing this, as already mentioned, we shall be guided by the mapping approach. According to this approach constructing a structured grid in the solution domain G of a physical problem, called the physical domain and having a complicated geometrical form in the common case, is carried out by means of a continuous mapping x to the domain G

Hexahedral ruled cells

The hexahedral ruled cell with the vertices $x_{i_{1} i_{2} i_{3}}$ , i₁, i₂, i₃ = 0, 1 (see Fig. 1(a)) is constructed by a trilinear mapping $x (ξ) = a_{000} + a_{100} ξ_{1} + a_{010} ξ_{2} + a_{001} ξ_{3} + a_{110} ξ_{1} ξ_{2} + a_{101} ξ_{1} ξ_{3} + a_{011} ξ_{2} ξ_{3} + a_{111} ξ_{1} ξ_{2} ξ_{3}$ of the unit cube P₀₀₀ = {ξ = (ξ₁, ξ₂, ξ₃) : 0 ⩽ ξ_l ⩽ 1, l = 1, 2, 3}. It maps vertices of the cube to vertices of the cell and edges of the cube to edges of the cell, specifies surfaces for faces of the cell (ruled surfaces of the second order or planes), and determines a hexahedral rule cell (see Fig. 1(a)). Vectors $a_{i_{1} i_{2} i}$

Sufficient nondegeneracy conditions

For a long time, in the three-dimensional case there were no nondegeneracy conditions at all. Analogously to the two-dimensional case to estimate the nondegeneracy of hexahedral cells the check of the positivity of the Jacobian of the trilinear mapping at corners of a cell (positivity of 8 tetrahedral volumes $α_{i_{1} i_{2} i_{3}}$ , see further (2)) was used. Then it was shown, for example, in [17] that the positivity of the Jacobian at the corners and even on edges does not guarantee nondegeneracy of a cell.

Discussion

First test used to check nondegeneracy of hexahedral cells was the positive values of the Jacobian at the corners of a cell or positivity of eight tetrahedral volumes $α_{i_{1} i_{2} i_{3}}$ (2). It was shown in [15], [17] that this test did not guarantee nondegeneracy of a cell.

Result

Then it was shown by a special numerical experiment with random numbers in [18], [25], [26], [27] that in less than 1/3 of cases (31.7%, see Table 1) when the Jacobian was positive at the corners of a cell the Jacobian was positive

Conclusion

An analysis of nondegeneracy tests of all the types allows us to draw a conclusion that conditions from [2] (test 2) are the best in replacement of nondegeneracy conditions 1 and 2 from [18], [25], [26]. The test 2 verifies the volumes of only 10 tetrahedra for positiveness, covers a wide class of cells, and guarantees the nondegeneracy of hexahedral ruled cells in most cases. Note that all the types of conditions (except conditions [30] for grids given by Bernstein–Bezier polynomials, the

References (30)

B.N. Azarenok
A variational hexahedral grid generator with control metric
J. Comput. Phys.
(2006)
L.O. Chua et al.
Global homeomorphism of vector-valued functions
Math. Anal. Appl.
(1972)
J. Grandy
Conservative remapping and regions overlays by intersecting arbitrary polyhedra
J. Comput. Phys.
(1999)
P.M. Knupp
On the invertibility of isoparametric map
Comput. Methods Appl. Mech. Engrg.
(1990)
N.N. Anuchina et al.
Numerical simulation of 3D multi-component vortex flows by MAH-3 code
B.N. Azarenok
Conservative remapping on hexahedral meshes
N.A. Bobylev et al.
Several remarks on homeomorphisms
Mat. Zametki
(1996)
N.A. Bobylev, S.A. Ivanenko, A.V. Kazunin, On the piecewise homeomorphic mappings of the bounded domains and their...
N.A. Bobylev et al.
Piecewise smooth homeomorphisms of bounded domains and their applications to the theory of grids
Zh. Vychisl. Mat. Mat. Fiz.
(2003)
T.N. Bronina
Algorithm for constructing initial three-dimensional structured grids for the domains of revolution
Proc. Steklov Inst. Math. Suppl.
(2008)

K.G. Merkley, R.J. Meyers, Verde Users Manual Version 2.5....

J.K. Dukowicz, N.T. Padial, REMAP3D: a conservative three-dimensional remapping code, Los Alamos Report,...

G.M. Fikhtengol’ts, Fundamentals of Calculus, vol. 2, Nauka, Moscow,...

CSCMDO – Coordinate and sensitivity calculator for multi-disciplinary design optimization SYNOPSIS....

S.K. Godunov, A.V. Zabrodin, M.Ya. Ivanov, et al., Numerical Solution of Multidimensional Gas Dynamics Problems, Nauka,...

Cited by (13)

Non-stationary grid generation algorithm for deformed volumes of revolution
2023, Mathematics and Computers in Simulation
Citation Excerpt :
Usually the requirement of nondegeneracy for a grid (cell) coincides with nondegeneracy of the mapping used for grid (cell) construction. The grid (cell) is considered nondegenerate (see [5]), if the mapping used for its construction is one-to-one, onto (homeomorphism) and characterized by positive (nonvanishing) values of the Jacobian of the mapping (contained in the dominators of the coefficients of algebraic systems). If the mapping does not satisfy these conditions, the grid (cell) is considered degenerate.
The algorithm is designed for multi-component hydrodynamic simulation and for solving other physical and engineering problems. It is suggested for generating structured grids in the volume of revolution (main body) deformed by another volume of revolution (deforming body). In the deformation process, the deforming body is assumed infinitely stiff and strong (i.e. it does not deform, only the main body deforms). The algorithm is developed within the original variational approach for constructing optimal grids satisfying different requirements. The requirements of closeness of a grid to uniform and orthogonal are considered. The algorithm is performed on the basis of the grid generation technology elaborated earlier within the utilized approach for the volume of revolution. The volume of revolution is obtained by the rotation through 180° around an axis of a plane generatrix curve consisting of segments of straight lines and arcs of circles and ellipses. The technology is fully three-dimensional one and is not reduced to constructing rotational grids obtained by the rotation of two-dimensional grids around the axis. The developed algorithm represents the non-stationary procedure generating three-dimensional structured grids in domains with moving boundaries during which the form of the domain is changing from the volume of revolution to the desired deformed volume. The non-stationary algorithm is an iterative process where, at each stage, the deformation of a grid and then its optimization are carried out. Such algorithm allows to generate grids in very complex geometries. For this there is no need to describe the complex geometry of the deformed domain which is not obvious in the general case. It is necessary to do this only for the volumes of revolutions of the main and deforming bodies by the definition of generatrix curves for them which is essentially easier. It also permits to exclude some other stages of the traditional grid generation for the deformed volume such as generation of an initial grid. The algorithm is realized in the computer code written in $C + +$ . Examples of constructed grids are given.
Untangling all-hex meshes via adaptive boundary optimization
2022, Graphical Models
Citation Excerpt :
Inversion check We verify the inversion of a hexahedron by checking whether one of the eight corresponding tetrahedrons is inverse. However, [49] empirically studied this metric and found it insufficient. We would like to extend our method to support a more reliable metric for inversion check of hexahedrons.
We propose a novel method to untangle and optimize all-hex meshes. Central to this algorithm is an adaptive boundary optimization process that significantly improves practical robustness. Given an all-hex mesh with many inverted hexahedral elements, we first optimize a high-quality quad boundary mesh with a small approximation error to the input boundary. Since the boundary constraints limit the optimization space to search for the inversion-free meshes, we then relax the boundary constraints to generate an inversion-free all-hex mesh. We develop an adaptive boundary relaxation algorithm to implicitly restrict the shape difference between the relaxed and input boundaries, thereby facilitating the next step. Finally, an adaptive boundary difference minimization is developed to effectively and efficiently force the distance difference between the relaxed boundary and the optimized boundary of the first step to approach zero while avoiding inverted elements. We demonstrate the efficacy of our algorithm on a data set containing 1004 all-hex meshes. Compared to previous methods, our method achieves higher practical robustness.
Criteria for hexahedral cell classification
2018, Applied Numerical Mathematics
Citation Excerpt :
Almost all commercial grid generators have some tools to estimate the quality of constructed grids. However they do not have both the reliable tools for estimation of nondegeneracy of grids (see [29]) and the special criteria for determining the types of degeneration or the types of nondegenerate cells. Usually, a quality metric is a real number assigned to a cell and defined by its vertex coordinates.
The aim of the paper is to give the numerical criteria for classification of different types of hexahedral cells which can emerge in a three-dimensional structured grid generation. In general, computational grids and their cells have to be nondegenerate, however, in practice, situations arise in which degenerate grids are used and computed. In these cases, to prevent lost of accuracy, special strategies must be chosen both in grid generation and physical phenomenon solution algorithms. To determine which cells need a modification in above strategies, degenerate cells have to be detected. The criteria are suggested for hexahedral cells constructed by a trilinear mapping of the unit cube. All hexahedral cells are divided into nondegenerate and degenerate. Among nondegenerate hexahedral cells, cells exotic in shape are singled out as inadmissible. Degenerate cells are divided into pyramids, prisms and tetrahedrons—types of cells which can be admissible in grid generation and solution algorithms. Inadmissible types of degenerations are also considered. An algorithm for testing three-dimensional structured grids according to suggested criteria is described. Both results of testing and examples of different types of cells are demonstrated. In conclusion, recommendations for structured grid generation with the purpose to exclude undesirable types of cells are given.
Robust and efficient validation of the linear hexahedral element
2017, Procedia Engineering
Checking mesh validity is a mandatory step before doing any finite element analysis. If checking the validity of tetrahedra is trivial, checking the validity of hexahedral elements is far from being obvious. In this paper, a method that robustly and efficiently compute the validity of standard linear hexahedral elements is presented. This method is a significant improvement of a previous work on the validity of curvilinear elements [1]. The new implementation is simple and computationally efficient. The key of the algorithm is still to compute Bézier coefficients of the Jacobian determinant. We show that only 20 Jacobian determinants are necessary to compute the 27 Bézier coefficients. Those 20 Jacobians can be efficiently computed by calculating the volume of 20 tetrahedra. The new implementation is able to check the validity of about 6 million hexahedra per second on one core of a personal computer. Through the paper, all the necessary information is provided that allow to easily reproduce the results, i.e. write a simple code that takes the coordinates of 8 points as input and outputs the validity of the hexahedron.
On the development of the variational approach to the generation of optimal grids (a survey)
2023, Trudy Instituta Matematiki i Mekhaniki UrO RAN
Up to 58 Tets/Hex to untangle Hex meshes
2022, arXiv

View all citing articles on Scopus

^☆: This work was partially supported by the Russian Foundation for Basic Research (projects 09-01-00173 and 11-01-00063) and the project of oriented fundamental research of the Ural Branch of RAS.

View full text

Nondegeneracy tests for hexahedral cells☆

Abstract

Introduction

Section snippets

Nondegeneracy requirement

Hexahedral ruled cells

Sufficient nondegeneracy conditions

Discussion

Result

Conclusion

J. Comput. Phys.

Math. Anal. Appl.

J. Comput. Phys.

Comput. Methods Appl. Mech. Engrg.

Numerical simulation of 3D multi-component vortex flows by MAH-3 code

Conservative remapping on hexahedral meshes

Several remarks on homeomorphisms

Mat. Zametki

Piecewise smooth homeomorphisms of bounded domains and their applications to the theory of grids

Zh. Vychisl. Mat. Mat. Fiz.

Algorithm for constructing initial three-dimensional structured grids for the domains of revolution

Proc. Steklov Inst. Math. Suppl.