CFD Online Logo CFD Online URL
Home > Wiki > Structured mesh generation

Structured mesh generation

From CFD-Wiki

Jump to: navigation, search
Mesh classification
Structured mesh generation
Unstructured mesh generation
Special topics

<< Mesh Classification | Structured Mesh Generation | Unstructured 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. The best basic refence on this topic is the book of Thompson, Warsi, and Mastin[1]. There are more recent texts available, but this is the classic book on the subject, and it is available online here.


Algebraic Grid Generation

The simplest way to obtain a grid would be to specify the grid coordinates \vec{x} as the result of some vector function, or


where \vec{\xi} 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 \vec{s}, 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. Consider a line segment joining two points \vec{x}_1 and \vec{x}_2 together. The segment can be expressed as the linear form

\vec{x}(s)=s(\vec{x}_2 - \vec{x}_1) + \vec{x}_1,\ \ s\in [0,1].

Similar expressions are possible for other curves connecting the two points. 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

\vec{x}(s)=\vec{P}_0 (1-s)^3 + 3\vec{P}_1 s (1-s)^2 + 3 \vec{P}_2 s^2 (1-s) + \vec{P}_3 s^3,

where the P_i's are the control points and again s\in [0,1].

By changing the functional expression for s, we can change the grid distribution along the line segement. These functions are often referred to as stretching functions, and there are many choices available. The simplest choice is a uniform distribution, in which we set

s(\xi)= \frac{\xi}{I},

where \xi\in[0,I]. For cases in which grid clustering is desired, the hyperbolic trigonometric functions such as the hyperbolic tangent are a popular choice. A simple one-parameter hyperbolic tangent stretching function is defined by

s\left(\xi\right) = 1 + \frac{\tanh\left[\delta\left(\xi/I-1\right)\right]}{\tanh\left(\delta\right)},

where \delta is the stretching factor and \xi\in[0,I]. 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 [2]. 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 \Delta s. This can be taken to mean that s(1)=\Delta s or that ds/d\xi (1) = \Delta s. Vinokur's procedure guarantees the latter.

A related double-sided stretching function (that gives symmetric spacings about \xi=I/2) is given by

u\left(\xi\right) = \frac{1}{2}\left[1 + \frac{\tanh\left[\delta\left(\xi/I-1/2\right)\right]}{\tanh\left(\delta/2\right)}\right].

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: \Delta s_1 and \Delta s_2. Vinokur gives such a function, first defining

A=\frac{\sqrt{\Delta s_2}}{\sqrt{\Delta s_1}},\ \ B=\frac{1}{I\sqrt{\Delta s_2\Delta s_1}}.

The stretching factor \delta is found from the solution of the transcendental equation

 \frac{\sinh\left(\delta\right)}{\delta} = B.

The final grid distribution is then given by

s\left(\xi\right)=\frac{u\left(\xi\right)}{A + (1-A)u\left(\xi\right)}.

Again, Vinokur's procedure ensures that the derivative conditions ds/d\xi (1) = \Delta s_1 and ds/d\xi (I) = \Delta s_2, and not the grid spacings obtained in the direct evaluation of the stretching function.

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.

MG boundary.png

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

\ \vec{x}_{i,j} = \frac{\vec{x}_{i+1,j}+\vec{x}_{i-1,j}+\vec{x}_{i,j+1}+\vec{x}_{i,j-1}}{4}

An initial grid is shown below in (a), and the resulting grid (after iterations) is shown in (b).

MG initial final.png

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.

Grid Marching Methods

Other Techniques

Stretched grid method


  1. Thompson, Joe F., Warsi, Z.U.A., and Mastin, C. Wayne, Numerical Grid Generation, Elsevier Science Publishers, 1985
  2. Vinokur, Marcel, On One-Dimensional Stretching Functions for Finite-Difference Calculations, Journal of Computational Physics. 50, 215, 1983.

<< Mesh Classification | Structured Mesh Generation | Unstructured Mesh Generation>>

My wiki