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
    1. Hyperbolic Grid Generation
    2. Parabolic Grid Generation
  8. Algebraic Generation Systems
  9. Orthogonal Systems
  10. Conformal Mapping
  11. Adaptive Grids
  12. Appendix A
    Appendix B
    Appendix C

    Downloadable Version (PDF)
Numerical Grid Generation
Foundations and Applications


          It is also possible to base a grid generation system on hyperbolic or parabolic partial differential equations, rather than elliptic equations. In each of these eases the grid is generated by numerically solving the partial differential equations, marching in the direction of one curvilinear coordinate between two boundary curves in two dimensions, or between two boundary surfaces in three dimensions. In neither case can the entire boundaries of a general region be specified -- only the elliptic equations allow that.

          The parabolic system can be applied to generate the grid between the two boundaries of a doubly-connected region with each of these boundaries specified. The hyperbolic case, however, allows only one boundary to be specified, and is therefore of interest only for use in calculation on physically unbounded regions where the precise location of a computational outer boundary is not important. Both parabolic and hyperbolic grid generation systems have the advantage of being generally faster than elliptic generation systems, but, as just noted, are applicable only to certain configurations. Hyperbolic generation systems can be used to generate orthogonal grids.

1. Hyperbolic Grid Generation

          In two dimensions the condition of orthogonality is simply


If either the cell area, or the cell diagonal length (squared), g11 + g22, is a specified function of the curvilinear coordinates, i.e.,


then the system consisting of Eq. (1) and either (2a) or (2b), as appropriate, is hyperbolic.

          A hyperbolic generation system based on Eq. (1) and (2a) is constructed as follows (cf. Ref. [28-29]). Eq. (1) and (2a) become, with 1 = , 2 = , x1 = x, x2 = y,


where the cell volume distribution, V(,), is specified. This system is hyperbolic and therefore a non-iterative marching solution can be constructed proceeding in one coordinate direction, say , away from a specified boundary.

          The equations are first locally linearized about a known solution denoted x°, y°. Thus



Then with second-order central differences for the -derivatives and first-order backward differences for the derivatives we have, with = i and = j,


with iij=i+1,j - ij and j=ij - i,j-1 and where A and B, and V° in , are evaluated at j, and the last term is an added fourth-order dissipation term for stability. With and evaluated using central differences at j, and can be evaluated by simulatenous solution of Eq. (3a) and (3b). Eq. (5) then is a 2x2 block tridiagonal equation which is solved on each successive -line, proceeding away from the specified boundary, to generate the grid.

          The cell volume distribution in the field is controlled by the specified function, V(,). One form of this specification is as follows. Let points be distributed on a circle having a perimeter equal to that of the specified boundary at the same are length distribution as on that boundary. Then specify a radial distribution of concentric circles about this circle according to some distribution function, e.g., the hyperbolic tangent discussed in Chapter VIII. Then use the volume distribution from this unequally-spaced cylindrical coordinate system as V(,), with corresponding to the points around the circle, (), and corresponding to the radial distribution r(). An example of grids generated by this procedure follows:

          The specification of the cell volume prevents the coordinate system from overlapping even above a concave boundary. In this case the line spacing will expand rapidly away from the boundary in order to keep the cell volume from vanishing, as in the Following figure.

Although this prevents overlap, the rapid expansion that occurs can lead to problems with truncation error in some eases. This approach is extendable to 3-D with the coordinate lines emanating from the boundary being orthogonal to the other two coordinates, but the latter two lines not being orthogonal. There apparently is no system, hyperbolic or elliptic, that will give complete orthogonality in 3-D.

          This hyperbolic grid generation system is faster than the elliptic generation systems by one or two orders of magnitude, the computational time required being equivalent to about that for one iteration in a solution of the elliptic system. The specification of the cell volume distribution avoids the grid line overlapping that otherwise can occur with concave boundaries in a method involving projection away from a boundary. The grid may, however, be somewhat distorted when concave boundaries are involved. The cell volume specification also allows control of the gird line spacing, of course, as in the upper part of the second figure on p. 275, but again concave boundaries may cause the intended spacing to occur in the wrong coordinate direction, as in the lower part of this figure, since it is only the volume, and not the spacing in the two separate coordinate directions, that is controlled. As has been noted, the grid is constructed to be orthgonal.

          The hyperbolic generation system is not as general as the elliptic systems, however, since the entire boundary of the region cannot be specified. As noted above, boundary slope discontinuities are propagated into the field, so that the metric elements will be discontinuous along coordinate lines emanating from boundary slope discontinuities. Finally, since hyperbolic partial differential equations can have shock-like solutions in some circumstances, it is possible for very unsuitable grids to result with some specifications of boundary point and cell volume distributions. This is in contrast with the elliptic generation systems which tend to emphasize smoothness because of the nature of elliptic partial differential equations.

2. Parabolic Grid Generation

          Parabolic grid generation sytems may be constructed by modifying elliptic generation systems so that the second derivatives in one coordinate direction do not appear. The solution then can be marched away from a boundary in much the same manner as described above for the hyperbolic systems. Here, however, some influence of the other boundary toward which the marching progresses is retained in the equations.

          In Ref. [30] such a parabolic generation system is formed essentially by first representing all derivatives in an elliptic generation system with second-order central differences and then replacing all values on the forward line in one coordinate direction, say = j+1, with values specified in some manner in terms of the values on the preceeding lines and specified values on the outer boundary. This reduces the difference equations to a set of 2x2 block tridiagonal equations to be solved on each coordinate line in succession, proceeding away from a specified boundary. Control of the coordinate line spacing can be achieved by certain control functions that are drawn from some analogy with the elliptic system. It is possible to use the functional specification of the forward values to cause the grid to be nearly-orthogonal.

          The parabolic generation system is also faster than the elliptic generation systems to the same degree as is the hyperbolic system, since again only a succession of tridiagonal solutions is required. The functional specification of the forward values, with an influence of an outer boundary, introduces a smoothing effect from this second boundary not present in the hyperbolic system. Orthogonality is not achieved as directly as with the hyperbolic system, however. The forms of the forward value specification, and of the control functions, have not yet been well-developed.