1. Introduction
  2. Boundary-Conforming Coordinate Systems
  3. Transformation Relations
  4. Numerical Implementation
  5. Truncation Error
  6. Elliptic Generation Systems
  7. Parabolic and Hyperbolic Generation Systems
  8. Algebraic Generation Systems
  9. Orthogonal Systems
    1. General Formulation
    2. Two-Dimensional Orthogonal Coordinates
      1. Conformal systems
      2. Other systems
      3. Systems based on first-order equations
    3. Three-Dimensional Orthogonal Coordinates
    4. Nearly-Orthogonal Systems
  10. Conformal Mapping
  11. Adaptive Grids
  12. Appendix A
    Appendix B
    Appendix C

    Downloadable Version (PDF)
Numerical Grid Generation
Foundations and Applications
By: Joe E. Thompson, Z.U.A. Warsi and C. Wayne Mastin


          Orthogonal coordinate systems produce fewer additional terms in transformed partial differential equations, and thus reduce the amount of computation required. Also, as has been noted in Chapter V, severe departure from orthogonality will introduce truncation error in difference expressions. A general discussion of orthogonal systems on planes and curved surfaces is given in Ref. [42], and various generation procedures are surveyed in Ref. [42] and Ref. [1].

          In numerical solutions, the concept of numerical orthogonality, i.e., that the off-diagonal metric coefficients vanish when evaluated numerically, is usually more important than strict analytical orthogonality, especially when the equations to be solved on the system are in the conservative law form.

          There are basically two types of orthogonal generation systems, those based on the construction of an orthogonal system from a non-orthogonal system, and those involving field solutions of partial differential equations. The first approach involves the construction of orthogonal trajectories on a given non-orthogonal system. Here one set of coordinate lines of the non-orthogonal system is retained, while the other set is replaced by lines emanating from a boundary and constructed by integration across the field so as to cross each line of the retained set orthogonally. Control of the line spacing is exercised through the generation of the non-orthogonal system and through the point distribution on the boundary from which the trajectories start. The point distributions on only three of the four boundaries can be specified. Several methods for the construction of orthogonal trajectories are discussed in Ref. [42] and Ref. [1]. If point distributions are to be specified on all boundaries, the field approach must be taken, and it is to this approach that this chapter is primarily directed.

1. General Formulation

          The characteristic criterion for orthogonal coordinates is the vanishing of the off-diagonal elements of the metric tensor, i.e., gij = gij = 0 for ij. Thus the Jacobian of the transformation is simply


For brevity, writing

it is easy to show from Eq. (III-74) that


The general differential equations satisfied in the transformed region are, from Eq. (VI-10),


Substituting Eq. (2) in (3) for the Laplacians, these grid generation equations take the following simpler form for an orthogonal system:


where is the cartesian coordinate vector.

          On the other hand, starting from Eq. (2), by writing

and using the chain rule of differentiation, we get the generation equations in the physical region as


          Another fundamental set of equations for orthogonal coordinates are known as Lame's equations, stated as


where (i,j,k) are cyclic. Equations (6) express essentially the condition that the curvilinear coordinates are to be introduced in an Euclidean space. (cf. Ref. [27]). In three dimensions, Eq. (6) represents six equations, although thereare only three distinct metric coefficients, h1,h2,h3.

          In summary the equations (2), (4), (5) and (6), together with the vanishing of the off-diagonal metric elements, are the fundamental equations which any orthogonal coordinate system must satisfy.

2. Two-Dimensional Orthogonal Coordinates

          The fundamental equations for two-dimensional orthogonal coordinates are collected below as a particular case of the equations (2) - (6):

I. Transformed plane: g12=0 and (7a)
II. Physical plane: g12=0 and (8a)
Also, the Laplacians (2) take the simple forms

          Considering Eq. (7a) and (8a), either of which provide the orthogonality condition, it is a straightforward matter to conclude that there exists a positive function F such that


and the Eq. (7a) is identically satisfied. In the same manner, from Eq. (8a),


It is obvious that the positive function F is related to the grid aspect ratio:


The choice of the sign in Eq. (10) and (11) follows from the right-handedness of the system 1,2.

          Introducing (12) into Eq. (7b), while using Eq. (9), we get


which forms the basic generation system for plane orthogonal coordinates. Though the generating equations (7b) and (13) are completely equivalent, nevertheless, the apparent difference in their structures must be taken into consideration to decide about the type of boundary conditions for their solution.

          With Eq. (7b) as the generating system then the two options are: (i) Specify F=h2/h1 as a known function of 1,2. This case covers the cases F= and where =constant. For any constant , Eq. (9) reduce to the Laplace equations 21=0, 22=0, and Eq. (7b) becomes


For =1, the coordinates 1,2 are isothermic, i.e., h2=h1, and so are conformal. Cases in which 1 have also been considered, and specific references are given in Ref. [1]. It is also of interest to state that starting from a conformal system (1,2), yet another system (1,2) can be established by transforming the Laplace equations 21=0, 22=0, such that 1 and is a product of a function of 1 and a function of 2. (cf. Ref. [1]). (ii) The other option is to calculate F iteratively. In this case the field values of F are updated by iteratively changing its values at the boundaries under the orthogonality condition g12=0.

          With Eq. (13) as the generating system, the two Laplacians 21 and 22 have to be specified. Following the nonorthogonal case, let


where P1,....,Q2 are arbitrary specified functions of 1,2. Using Eqs. (9) and (12) one can rewrite these equations as


Thus if P1,....,Q2 are specified, the above equations provide a way to determine F. (Using the condition

one can establish a fourth order algebraic equation in F.) It is therefore concluded that the use of Eq. (13) with P1,....,Q2 specified is equivalent to using Eq. (7b) in which F has explicitly been specified.

          The above noted considerations are important in deciding about the type of boundary data needed for the solution of either Eq. (7b) or Eq. (13). The solution of Eq. (7b) with specified F, or the solution of Eq. (13) with specified P1,....,Q2, does not allow an arbitrary point distribution on the domain boundaries. The reason for this as follows: For example, on a boundary segment 2==constant if x1(1,) is prescribed, then from Eq. (10) the normal derivative becomes available. If in addition to x1(1, one also specifies x2(1, which amounts to specifying the complete boundary point distribution, then the problem becomes overdetermined. Thus for the cases under consideration, specification of the complete boundary point distribution is not possible. That is, Eq. (7b) with F specified, or Eq. (13) with specified P1,,....,Q2, cannot be solved when the complete boundary point distribution is prescribed. The appropriate boundary conditions for such problems are discussed in the context of conformal coordinates in Section A.

          The specification of the complete boundary point distribution is possible in the case when Eq. (7b) is solved without specifying F. An iterative approach can be used to update the values of F based on the changed values at the boudnaries. (cf. Section B).

A. Conformal systems

          Considering first conformal systems, i.e., with h2=h1 and F=1, the basic equations from (9a,b) are


          Let the domain in which the conformal coordinates are to be generated be bounded by a piecewise-smooth curve on which s is the arc length and n the outward normal. The Cauchy-Riemann equations (17b) on the boundary take the form


          Referring to the figure below, let the curves 1 and 2 be those portions on which 1=constant, and the curves 3 and 4 be those on which 2=constant. From Eq. (18) we readily find that on 1 and 2 the condition , and on 3 and 4 the condition , are to be imposed, where the subscript n indicates the normal derivative.

Therefore, for the generation of conformal coordinates, the properly posed boundary value problems are

on 1 and 2: 1 = , 1 = , respectively
on 3 and 4: (19)

on 1 and 2:
on 3 and 4: 2 = , 2 = , respectively (20)

          In the transformed plane the governing equations for conformal coordinates are obtained from (13):


Taking 1 and 2 as monotonically increasing parameters having the ranges, 1, 2, the given equations of the curves 1, 2, 3, 4, respectively, can be expressed .in parametric form as


          The specification of the boundary data in the form of (21) should at best be regarded as a statement of the problem, rather than as a procedure, since the exact boundary point-distribution in this form is not possible a'priori. To develop the procedure itself we regard the specification in (22) as an initial guess. However, this type of specification produces an overdetermined situation. For example, if on 1 both x1(, 2) and x2(, 2) are specified, then from the first equation in (21b), can be calculated on this boundary. Thus both

become specified, which makes the problem overdetermined. Following this logic, we can isolate the proper arbitrarily specifed boundary values for Eq. (21) as follows: specifying x1(, 2) on 1, x1(, 2) on 2, x2(1, ) on 3, and x2(1, ) on 4. Thus, for the x1-equation the normal derivative conditions on 3 and 4 are provided by the second equation in (21b) through the specified x2 values. Similarly, for the x2-equation the normal derivative conditions on 1 and 2 are provided by the second equation in (21b) through the specified x1-values.

          In any numerical procedure, the values of x1 are determined by integration through the formula


and these values in turn give the new values of x2 through the exact functional relations between x1 and x2 for these curves. Similarly, the values of x2 are calculated by the formula


and then the new values of x1 are determined by the functional relations between x1 and x2 for these curves. Further discussion of conformal systems is given in Chapter X.

B. Other systems

          For general orthogonal systems, the basic equations for x1 and x2 remain Eq. (13). As noted earlier, the other constraint besides orthogonality (g12=O) is now to specify the function F defined in Eq.(12), which is the ratio of the scale factors, i.e., the grid aspect ratio. One approach is to specify the function F explicitly, in which case, as with the conformal coordinates, it is not possible to specify an arbitrary point distribution on the boundaries. The set of equations in (7a) must be used to find the proper x1 and x2 values by integration on the appropriate boundaries. Another alternative is to specify an arbitrary point distribution on the boundaries, and leave the function F to be determined iteratively in the course of the solution for the grid. This is done in a manner similar to that used in the GRAPE code, discussed in Chapter VI, with new boundary values of the function F being calculated from the present iterate for the coordinates. The function F in the field is then determined from these boundary values by either transfinite interpolation or as the solution of Laplace's equations, the former being found preferable in the cases considered. (With more distorted boundaries the Laplace solution might be more reliable than the interpolation.) Different forms of interpolation, or an equation other than the Laplace, for the determination of the control function in the field would allow some control of coordinate line spacing in the field. However, since only a single control function is involved, it is not possible to exercise control of the coordinate line spacing in the field in both directions.

          Another approach in which the boundary point distribution can only be fixed in a specified manner is to take the basic generation equation to be Eq. (7c) which for conformal coordinates (h2=h1) takes the form


where P=2 ln(h1). An exact solution of Eq. (25) can be obtained if appropriate values of P are known at the boundaries. The important problem then becomes the choice of those points at the inner and outer boundaries which can be put in orthogonal correspondence with one another. This can be accomplished if the 1-coordinate, both at the inner and outer boundaries is selected to satisfy the Laplace equation 21=0. This condition can be satisfied by taking 1 as the angle traced out by the common radii of those concentric circles which are the conformal maps of the contours in the physical plane. The solution of Eq. (25) under these conditions then can be used to generate non-conformal coordinates by a coordinate transformation of the other coordinate 2.

          An orthogonal grid can be generated by solving the Laplace equations (21a) provided that the boundary point distribution is compatible. Since a conformal mapping generates an orthogonal grid, a compatible boundary point distribution can be obtained by conformally mapping the boundary contour as follows (cf. Ref. [43]): Consider an open physical boundary contour

where and are to be lines of constant 2, while and a connecting line to be generated are to be lines of constant 1.

          Each point of the set that defines this contour is successively mapped onto the real axis in the complex plane by a hinge point transformation (such a transformation has the effect of mapping one point onto the real axis while points already on the real axis remain there):

The straight line on the real axis is then mapped conformally onto an open rectangle in the complex plane:

Points are then placed as desired along the sides and of this rectangle, these points on and being assigned successive integer values of 1 and 2, respectively. (This placement of points on these two sides is arbitrary and may be done by any distribution function desired.) The key to the construction of a compatible boundary point distribution is then that the points on the other sides of the rectangle, i.e., and , are placed with the same distributions chosen for and . The points in the physical plane that correspond to these boundary points on the rectangle in the complex plane are then determined by exponential spline interpolation among the values at the original set of points defining the contour, except for the open side of the rectangle where the points in the conformal transformations. Finally the orthogonal grid is generated by solving the Laplace equations (21a) with this fixed boundary point distribution.

C. Systems based on first-order equations

          Equations (10) are formally related to the Cauchy-Riemann equations (with F=1), but otherwise form a set of first order nonlinear partial differential equations. In order to preserve the orientation of coordinates, the sign of F is taken to be positive throughout the domain. For certain choices of the function F the system is hyperbolic, and the complete initial-value problem is then


Here = o is the given body contour, and, unlike the elliptic problem, the data on another boundary cannot be specified.

          This system may be shown to exhibit the following important properties:

(i). First, g22 in principle can be expressed as a function of g11. <.p> (ii) Because of (i), F > 0 is a function of 1,2, and g11, i.e.,

          For brevity, writing

          we have

(iii). For a well-posed initial value problem the system of equations in (26) must be hyperbolic.

          A test for the well-posedness is that small perturbations produce small effects. Using this test, for Eqs. (26) to be hyperbolic, the function f(z), defined as

must be a strictly decreasing function of z.

3. Three-Dimensional Orthogonal Coordinates

          The problem of three-dimensional orthogonal coordinate generation, though of much importance in many practical problems, has received little attention in comparison to its two-dimensional counterpart. The reason is not so much in the complicated form of the governing equations but rather in the prescription of the boundary conditions and in their numerical implementation.

          Orthogonality in three dimensions is difficult to achieve, and only exists when the coordinate lines on the bounding surfaces follow lines of curvature, i.e., lines in the direction of maximum or minimum curvature of the surface. Therefore, three dimensional orthogonal coordinates will not be available in most cases with nontrivial geometry. It is possible, however, to have the system locally orthogonal at boundaries, and/or to have orthogonality of surface coordinates.

          The governing equations for generation of orthogonal coordinates are obtained in a straightforward manner and have been listed above as Eq. (4) - (6). The set of equations which are to be solved for x1,x2,x3 and h1,h2,h3 has Eq. (4) and (6). The set (6) has six equations for the three unknowns. On the other hand, without imposing the orthogonality condition, gij = 0 (ij), there are six equations for the determination of six unknowns. Thus the orthogonality does not reduce the number of the equations which govern the distribution of the metric coefficients, and it would be wrong to try to select a set of three equations out of the available six.

4. Nearly-Orthogonal Systems

          Since a part of the truncation error is decreased as the grid becomes more orthogonal, it is of interest to generate grids which are "nearly-orthogonal". Such grids do not approximate orthogonality sufficiently well, however, for the terms arising from nonorthogonality in transformation relations to be dropped. The generation of nearly-orthogonal grids naturally follows some of the procedures discussed above in this chapter, but with the conditions for orthogonality only partially satisfied. Several procedures are discussed in Ref. [1] and Ref. [42].

          A simple procedure for generating a nearly-orthogonal system from a nonorthogonal system is to first generate curves of a nonorthogonal system by connecting points obtained by any specified distribution function along straight lines connecting boundary points on two arbitrary closed boundaries. Coordinate lines connecting points on each succeeding pair of curves from the original coordinate system then are constructed as follows: At selected points on the inner curve, normals are constructed, and the points of intersection with the next curve outward are determined. Normal directions form the intersection point are determined and translated to the original point in the inner curve. Then a second point on the outer curve is determined as before. Finally, the new coordinate lines are constructed as straight lines joining the selected points on the inner curve with points located halfway between the corresponding pair of points on the outer curve located as described above. The resulting lines will not actually be orthogonal to either the inner or outer curve, and the slopes of these lines will, in fact, be discontinuous at each curve. The observed departures from orthgonality, however, have been small and the departure may be made arbitrarily small by the addition of more curves. Since the procedure is applied successively between pairs of coordinate lines, concave bodies can be treated as well.


1. The unit tangent vector on a curve C defined in the parametric form = (s), with s as the arc length along C, is given by =d/ds. Let C be a plane curve in the xy-plane having as the unit normal vector. Using the condition and the convention that (,,), in the order shown, form a right-handed triad of vectors, find the components of . Here is the constant unit vector along the z-axis.

2. Let (x,y) and (x,y) be the conformal coordinates in the xy-plane so that the Cauchy-Riemann equations

are satisfied. Consider the curve C defined in excercise 1 and the normal derivative operator

and show that the Cauchy-Riemann equations in the natural coordinates (s,n) are

3. Let F(i) be a scalar function of position and (i)=constant be a surface.

(a) Show that the unit normal vector to the surface =constant in curvilinear coordinates is given by

(b) Prove that the normal derivative of F on the surface =constant is

(c) In particular, for two-dimensional curvilinear coordinates show that

(d) Particularize the results in (c) for orthogonal curvilinear coordinates. Write the partial derivative operator for orthogonal coordinates.

4. Consider Eq. (26) of this chapter, which form a system of first-order partial differential equations for two-dimensional orthogonal coordinates. It was stated subsequently that these equations form a hyperbolic system if the initial value problem is well-posed. To prove this assertion consider the perturbed state x+x, y+y, F(,,z+z), where . Retaining only the first order terms, develop a system of algebraic equations in (x),(y), (x), (y), and show that the resulting matrix has eigenvalues given by

2 = -F(F + zFz)

Show from the preceding result that the eigenvalues are real only when zF is a strictly decreasing function of z.