Grid Generation Methods

This second edition is significantly expanded by new material that discusses recent advances in grid generation technology based on the numerical solution of Beltrami and diffusion equations in control metrics. It gives a more detailed and practice-oriented description of the control metrics for providing the generation of adaptive, field-aligned, and balanced numerical grids. Some numerical algorithms are described for generating surface and domain grids. Applications of the algorithms to the generation of numerical grids with individual and balanced properties are demonstrated. Grid generation codes represent an indispensable tool for solving field problems in nearly all areas of applied mathematics and computational physics. The use of these grid codes significantly enhances the productivity and reliability of the numerical analysis of problems with complex geometry and complicated solutions. The science of grid generation is still growing fast; new developments are continually occurring in the fields of grid methods, codes, and practical applications. Therefore there exists an evident need of students, researchers, and practitioners in applied mathematics for new books which coherently complement the existing ones with a description of new developments in grid methods, grid codes, and the concomitant areas of grid technology. The objective of this book is to give a clear, comprehensive, and easily learned description of all essential methods of grid generation technology for two major classes of grids: structured and unstructured. These classes rely on two somewhat opposite basic concepts. The basic concept of the former class is adherence to order and organization, while the latter is prone to the absence of any restrictions. The present monograph discusses the current state of the art in methods of grid generation and describes new directions and new techniques aimed at the enhancement of the efficiency and productivity of the grid process. The emphasis is put on mathematical formulations, explanations, and examples of various aspects of grid generation. Special attention is paid to a review of those promising approaches and methods which have been developed recently and/or have not been sufficiently covered in other monographs. In particular, the book includes a stretching method adjusted to the numerical solution of singularly perturbed equations having large scale solution variations, e.g. those modeling high-Reynolds-number flows. A number of functionals related to conformality, orthogonality, energy, and alignment are described. The book includes differential and variational techniques for generating uniform, conformal, and harmonic coordinate transformations on hypersurfaces for the development of a comprehensive approach to the construction of both fixed and adaptive grids in the interior and on the boundary of domains in a unified manner. The monograph is also concerned with the description of all essential grid quality measures such as skewness, curvature, torsion, angle and length values, and conformality. Emphasis is given to a clear style and new angles of consideration where it is not intended to include unnecessary abstractions. The major area of attention of this book is structured grid techniques. However, the author has also included an elementary introduction to basic unstructured approaches to grid generation. A more detailed description of unstructured grid techniques can be found in {\it Computational Grids: Adaptation and Solution Strategies} by G.F. Carey (1997), {\it Delaunay Triangulation and Meshing} by P.-L. George and H. Borouchaki (1998), and {\it Mesh Generation Application to Finite Elements} by P.J. Frey and P.-L. George (2008). Since grid technology has widespread application to nearly all field problems, this monograph may have some interest for a broad range of readers, including teachers, students, researchers, and practitioners in applied mathematics, mechanics, and physics. The first chapter gives a general introduction to the subject of grids. There are two fundamental forms of mesh: structured and unstructured. Structured grids are commonly obtained by mapping a standard grid into the physical region with a transformation from a reference computational domain. The most popular structured grids are coordinate grids. The cells of such grids are curvilinear hexahedrons, and the identification of neighboring points is done by incrementing coordinate indices. Unstructured grids are composed of cells of arbitrary shape and, therefore, require the generation of a connectivity table to allow the identification of neighbors. The chapter outlines structured, unstructured, and composite grids and delineates some basic approaches to their generation. It also includes a description of various types of grid topology and touches on certain issues of big grid codes. Chapter 2 deals with some relations, necessary only for grid generation, connected with and derived from the metric tensors of coordinate transformations. As an example of an application of these relations, the chapter presents a technique aimed at obtaining conservation-law equations in new fixed or time-dependent coordinates. In the procedures described, the deduction of the expressions for the transformed equations is based only on the formula for differentiation of the Jacobian . Very important issues of grid generation, connected with a description of grid quality measures in forms suitable for formulating grid techniques and efficiently analyzing the necessary mesh properties, are discussed in Chap. 3. The definitions of the grid quality measures are based on the metric tensors and on the relations between the metric elements considered in Chap. 2. Special attention is paid to the invariants of the metric tensors, which are the basic elements for the definition of many important grid quality measures. Clear algebraic and geometric interpretations of the invariants are presented. Equations with large variations of the solution, such as those modeling high-Reynolds-number flows, are one of the most important areas of the application of adaptive grids and of demonstration of the efficiency of grid technology. The numerical analysis of such equations on special grids obtained by a stretching method has a definite advantage in comparison with the classical analytic expansion method in that it requires only a minimum knowledge of the qualitative properties of the physical solution. The fourth chapter is concerned with the description of such stretching methods aimed at the numerical analysis of equations with singularities. The first part of Chap. 4 acquaints the reader with various types of singularity arising in solutions to equations with a small parameter affecting the higher derivatives. The solutions of these equations undergo large variations in very small zones, called boundary or interior layers. The chapter gives a concise description of the qualitative properties of solutions in boundary and interior layers and an identification of the invariants governing the location and structure of these layers. Besides the well-known exponential layers, three types of power layer which are common to bisingular problems having complementary singularities arising from reduced equations, are described. Such equations are widespread in applications, for example, in gas dynamics. Simple examples of one- and two-dimensional problems which realize different types of boundary and interior layers are demonstrated, in particular, the exotic case where the interior layer approaches infinitely close to the boundary as the parameter tends to zero, so that the interior layer turns out to be a boundary layer of the reduced problem. This interior layer exhibits one more phenomenon: it is composed of layers of two basic types, exponential on one side of the center of the layer and power-type on the other side. The second part of Chap. 4 describes a stretching method based on the application of special nonuniform stretching coordinates in regions of large variation of the solution. The use of stretching coordinates is extremly effective for the numerical solution of problems with boundary and interior layers. The method requires only a very basic knowledge of the qualitative properties of the physical solution in the layers. The specification of the stretching functions is given for each type of basic singularity. The functions are defined in such a way that the singularities are automatically smoothed with respect to the new stretching coordinates. The chapter ends with the description of a procedure to generate intermediate coordinate transformations which are suitable for smoothing both exponential and power layers. The grids derived with such stretching coordinates are often themselves well adapted to the expected physical features. Therefore, they make it easier to provide dynamic adaptation by taking part of the adaptive burden on themselves. The simplest and fastest technique of grid generation is the algebraic method based on transfinite interpolation. Chapter 5 describes formulas for general unidirectional transfinite interpolations. Multidirectional interpolation is defined by Boolean summation of unidirectional interpolations. The grid lines across block interfaces can be made completely continuous by using Lagrange interpolation or to have slope continuity by using the Hermite technique. Of central importance in transfinite interpolation are the blending functions (positive univariate quantities depending only on one chosen coordinate) which provide the matching of the grid lines at the boundary and interior surfaces. Detailed relations between the blending functions and approaches to their specification are discussed in this chapter. Examples of various types of blending function are reviewed, in particular, the functions defined through the basic stretching coordinate transformations for singular layers described in Chap. 4. These transformations are dependent on a small parameter so that the resulting grid automatically adjusts to the respective physical parameter, e.g. viscosity, Reynolds number, or shell thickness, in practical applications. The chapter ends with a description of a procedure for generating triangular, tetrahedral, or prismatic grids through the method of transfinite interpolation. Chapter 6 is concerned with grid generation techniques based on the numerical solution of systems of partial differential equations. Generation of grids from these systems of equations is largely based on the numerical solution of elliptic, hyperbolic, and parabolic equations for the coordinates of grid lines which are specified on the boundary segments. The elliptic and parabolic systems reviewed in the chapter provide grid generation within blocks with specified boundary point distributions. These systems are also used to smooth algebraic, hyperbolic, and unstructured grids. A very important role is currently played in grid codes by a system of Poisson equations defined as a sum of Laplace equations and control functions. This system was originally considered by Godunov and Prokopov and further generalized, developed, and implemented for practical applications by Thompson, Thames, Mastin, and others. The chapter describes the properties of the Poisson system and specifies expressions for the control functions required to construct nearly orthogonal coordinates at the boundaries. Hyperbolic systems are useful when an outer boundary is free of specification. The control of the grid spacing in the hyperbolic method is largely performed through the specification of volume distribution functions. Special hyperbolic and elliptic systems are presented for generating orthogonal and nearly orthogonal coordinate lines, in particular, those proposed by Ryskin and Leal. The chapter also reviews some parabolic and high-order systems for the generation of structured grids. Effective adaptation is one of the most important requirements put on grid technology. The basic aim of adaptation is to increase the accuracy and productivity of the numerical solution of partial differential equations through a redistribution of the grid points and refinement of the grid cells. Chapter 7 describes some basic techniques of dynamic adaptation. The chapter starts with the equidistribution method, first suggested in difference form by Boor and further applied and extended by Dwyer, Kee, Sanders, Yanenko, Liseikin, Danaev, and others. In this method, the lengths of the cell edges are defined through a weight function modeling some measure of the solution error. An interesting fact about the uniform convergence of the numerical solution of some singularly perturbed equations on a uniform grid is noted and explained. The chapter also describes adaptation in the elliptic method, performed by the control functions. Features and effects of the control functions are discussed and the specification of the control functions used in practical applications is presented. Approaches to the generation of moving grids for the numerical solution of nonstationary problems are also reviewed. The most important feature of a structured grid is the Jacobian of the coordinate transformation from which the grid is derived. A method based on the specification of the values of the Jacobian to keep it positive, developed by Liao, is presented. Chapter 8 reviews the developments of variational methods applied to grid generation. Variational grid generation relies on functionals related to grid quality: smoothness, orthogonality, regularity, aspect ratio, adaptivity, etc. By the minimization of a combination of these functionals, a user can define a compromise grid with the desired properties. The chapter discusses the variational approach of error minimization introduced by Morrison and further developed by Babu\^{s}ka, Tihonov, Yanenko, Liseikin, and others. Functionals for generating uniform, conformal, quasiconformal, orthogonal, and adaptive grids, suggested by Brackbill, Saltzman, Winslow, Godunov, Prokopov, Yanenko, Liseikin, Liao, Steinberg, Knupp, Roache, and others are also presented. A variational approach using functionals dependent on invariants of the metric tensor is also considered. The chapter discusses a new variational approach for generating harmonic maps through the minimization of energy functionals, which was suggested by Dvinsky. Several versions of the functionals from which harmonic maps can be derived are identified. Methods developed for the generation of grids on curves and surfaces are discussed in Chap. 9. The chapter describes the development and application of hyperbolic, elliptic, and variational techniques for the generation of grids on parametrically defined curves and surfaces. The differential approaches are based on the Beltrami equations proposed by Warsi and Thomas, while the variational methods rely on functionals of surface grid quality measures. The chapter includes also a description of the approach to constructing conformal mappings on surfaces developed by Khamaysen and Mastin. Chapter 10 is devoted to the author variant of the implementation of an idea of Eiseman for generating adaptive grids by projecting quasiuniform grids from monitor hypersurfaces. The monitor hypersurface is formed as a surface of the values of some vector function over the physical geometry. The vector function can be a solution to the problem of interest, a combination of its components or derivatives, or any other variable quantity that suitably monitors the way that the behavior of the solution influences the efficiency of the calculations. For the purpose of commonality a general approach based on differential and variational methods for the generation of quasiuniform grids on arbitrary hypersurfaces is considered. The variational method of generating quasiuniform grids, developed by the author, is grounded on the minimization of a generalized functional of grid smoothness on hypersurfaces, which was introduced for domains by Brackbill and Saltzman. The chapter also includes an expansion of the method by introducing more general control metrics in the physical geometry. The control metrics provide efficient and straightforwardly defined conditions for various types of grid adaptation, particularly grid clustering according to given function values and/or gradients, grid alignment with given vector fields, and combinations thereof. Using this approach, one can generate both adaptive and fixed grids in a unified manner, in arbitrary domains and on their boundaries. This allows code designers to merge the two tasks of surface grid generation and volume grid generation into one task while developing a comprehensive grid generation code. The subject of unstructured grid generation is discussed in Chap. 11. Unstructured grids may be composed of cells of arbitrary shape, but they are generally composed of triangles and tetrahedrons. Tetrahedral grid methods described in the chapter include Delaunay procedures and the advancing-front method. The Delaunay approach connects neighboring points (of some previously defined set of nodes in the region) to form tetrahedral cells in such a way that the sphere through the vertices of any tetrahedron does not contain any other points. In the advancing-front method, the grid is generated by building cells one at a time, marching from the boundary into the volume by successively connecting new points to points on the front until all the unmeshed space is filled with grid cells. The book ends with a list of references. The author is greatly thankful to G. Liseikin who prepared the text of the manuscript in {\LaTeX} code. Thanks go as well to G. Lukas for correcting the author`s English. The author is very grateful for the helpful suggestions in the comments for Chaps 1, 3, and 11 made by E. Ivanov, a leading expert in up-to-date codes, grid quality measures, and methods for unstructured grid generation. The author is also greatly obliged to the researchers who responded to his requests and sent him their papers, namely, T.J. Baker, D.A. Field, E. Ivanov, P. Knupp, G. Liao, M.S. Shephard, N.P. Weatherill, and P.P. Zegeling. The work over the book was supported in part by an Integrated Grant of the Siberian Branch of the Russian Academy of Sciences (2009-2011): Award No 94. Specifically, the efforts related to computing figures of grids made by A. Kharitonchick, A. Kofanov, Yu. Likhanova, and I. Vaseva, whom the author thanks very much, were remunerated by payments from this grant.