Structured mesh generation
The simplest algorithms directly compute nodal placement from some given function. These algorithms are referred to as algebraic algorithms. Many of the algorithms for the generation of structured meshes are descendents of "numerical grid generation" algoritms, in which a differential equation is solved to determine the nodal placement of the grid. In many cases, the system solved is an elliptic system, so these methods are often referred to as elliptic methods.
Algebraic Grid Generation
The simplest way to obtain a grid would be to specify the grid coordinates as the result of some vector function, or
where is the "index" vector, sometimes referred to as a computational coordinate. For our purposes here the entries of the computational coordinate will range from zero to a maximum. If such a function can be found for a given geometry, then the actual generation of gridpoints is straightforward. The problem, however, is that the determination of the function is not neccessarily that easy. In practice, it is sometimes easier to add an intermediate parametric space, denoted by , in between the physical space representation of the grid and the computational space representation of the grid:
The entries in the computational coordinate are taken from the unit interval. This representation can help simplify matters, especially in the one dimensional case.
Many mesh generation systems (both structured and unstructured) require the generation of boundary grids before interior cells can be generated. This is an area in which algebraic grid generation is ideal - typically, we want to specify boundary edge point distributions quickly, with a minimum of complexity, and a high degree of repeatability. These functions are often referred to as stretching functions, with hyperbolic trigonometric functions such as the hyperbolic tangent as a popular choice. A simple one-parameter hyperbolic tangent stretching function is defined by
where is the stretching factor and . This function partitions the unit interval and allows the specification of a single location. This sort of distribution is good for wall-normal grid distribution in viscous flows. This distribution is due to Vinokur [REF?]. Vinokur's procedure for the determination of the proper stretching factor to obtain desired spacings uses the derivatives of the stretching functions. Suppose we wish for our first grid spacing to be . This can be taken to mean that or that . Vinokur's procedure guarantees the latter.
A related double-sided stretching function (that gives symmetric spacings about ) is given by
This function is good for duct flows, such as turbulent channel flow. In situations in which different grid spacings are desired, a stretching function can be constructed that has specified spacings at both ends: and . Vinokur gives such a function, first defining
The stretching factor is found from the solution of the transcendental equation
The final grid distribution is then given by
Again, Vinokur's procedure ensures that the derivative conditions and , and not the grid spacings obtained in the direct evaluation of the stretching function. To compute the actual gridpoints in practice, we need to express the grid edge in terms of a parameter. For example, a line segment between two points and can be expressed as
We can then use any of the above streching functions to generate a properly spaced grid on the given line segment. Other parametric forms are available as well. Of particular interest is the cubic Bézier curve, which allows the specification of direction and location at both endpoints and can be written as
where the 's are the control points.
For the generation of interior cells, algebraic techniques are also available, most usually in the form of interpolation between boundary faces.
Elliptic Grid Generation
The oldest numerical grid generation techniques are based upon the solution of elliptic PDE's. Typically, a Poission-type equation is solved given the boundary grid distribution to generate interior nodal points. The solution domain is often topologically equivalent to a cube in 3D and a square in 2D. Consider the solution domain shown below with the indicated boundary resolution.
The simplest technique we could use here would be a solution of the Laplace equation using the standard second order finite difference stencil. This approach simplies into a form that is easily solved using Jacobi or Gauss-Seidel iterative techniques:
with Dirichlet boundary conditions is discretized as
An initial grid is shown below in (a), and the resulting grid (after iterations) is shown in (b).
Note that the grid spacing near the curved section increases and then decreases as we move left to right, and that grid lines near the left and right boundaries are not very orthogonal. These issues are reasons that production grid generation techniques are usually more complicated. The addition of control functions allows for better grid clustering properties, which will be necessary for viscous flow simulations.