Structure Grid:

A regular grid is a tessellation of n-dimensional Euclidean space by congruent  parallel topes  (e.g. bricks). Grids of this type appear on graph paper and may be used in finite element analysis as well as finite volume methods and finite difference methods. Since the derivatives of field variables can be conveniently expressed as finite differences, structured grids mainly appear in finite difference methods. Unstructured grids offer more flexibility than structured grids and hence are very useful in finite element and finite volume methods.

Each cell in the grid can be addressed by index (i, j) in two dimensions or (i, j, k) in three dimensions, and each vertex has coordinates clip_image001 in 2D or clip_image002 in 3D for some real numbers dx, dy, and dz representing the grid spacing.

Related grids:

A Cartesian grid is a special case where the elements are unit squares or unit cubes, and the vertices are integer points.

A rectilinear grid is a tessellation by rectangles or parallelepipeds that are not, in general, all congruent to each other. The cells may still be indexed by integers as above, but the mapping from indexes to vertex coordinates is less uniform than in a regular grid. An example of a rectilinear grid that is not regular appears on logarithmic scale graph paper.

A curvilinear grid or structured grid is a grid with the same combinatorial structure as a regular grid, in which the cells are quadrilaterals or cuboids rather than rectangles or rectangular parallelepipeds.


Fig: Cartesian Grid and Regular Grid


Fig: Rectilinear Grid and Curvilinear Grid

Classification of grids

Structured grids:

Structured grids are identified by regular connectivity. The possible element choices are quadrilateral in 2D and hexahedra in 3D. This model is highly space efficient, i.e. since the neighbourhood relationships are defined by storage arrangement.


Fig: Structured Grid

Unstructured grids:

An unstructured grid is identified by irregular connectivity. It cannot easily be expressed as a two dimensional or three dimensional arrays in computer memory. This allows for any possible element that a solver might be able to use. Compared to structured meshes, this model can be highly space inefficient since it calls for explicit storage of neighbourhood relationships. These grids typically employ triangles in 2D and tetrahedral in 3D.

Fig: Unstructured Grid

Hybrid grids:

A hybrid grid contains a mixture of structured portions and unstructured portions. It integrates the structured meshes and the unstructured meshes in an efficient manner. Those parts of the geometry that are regular can have structured grids and those that are complex can have unstructured grids. These grids can be non-conformal which means that grid lines don’t need to match at block boundaries.

Generation of structured Grid:

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 descendent of “numerical grid generation” algorithms, 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 clip_image001[7] as the result of some vector function, or


where clip_image003[7] 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 grid points is straightforward. The problem, however, is that the determination of the function is not necessarily that easy. In practice, it is sometimes easier to add an intermediate parametric space, denoted by clip_image004[7], 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 clip_image006 and clip_image007 together. The segment can be expressed as the linear form


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


where the clip_image002[9]‘s are the control points and again clip_image003[9].

By changing the functional expression for clip_image004[9], we can change the grid distribution along the line segment. 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


where clip_image006[5]. 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


where clip_image008[5] is the stretching factor and clip_image006[6]. 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. Vinokur’s procedure for the determination of the proper stretching factor to obtain desired spacing’s uses the derivatives of the stretching functions. Suppose we wish for our first grid spacing to be clip_image009. This can be taken to mean that clip_image010 or that clip_image011. Vinokur’s procedure guarantees the latter.

A related double-sided stretching function (that gives symmetric spacing’s about clip_image012) is given by


This function is good for duct flows, such as turbulent channel flow. In situations in which different grid spacing are desired, a stretching function can be constructed that has specified spacing at both ends: clip_image014 and clip_image015. Vinokur gives such a function, first defining


The stretching factor clip_image008[6] 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 clip_image019 and clip_image020, and not the grid spacing’s 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 Poisson-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 simplify 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.

Unstructured grid:


Fig: Example of unstructured grid for a finite element analysis mesh.

An unstructured (or irregular) grid is a tessellation of a part of the Euclidean plane or Euclidean space by simple shapes, such as triangles or tetrahedral, in an irregular pattern. Grids of this type may be used in finite element analysis when the input to be analysed has an irregular shape.

Unlike structured grids, unstructured grids require a list of the connectivity which specifies the way a given set of vertices make up individual elements.

Ruppert’s algorithm is often used to convert an irregularly shaped polygon into an unstructured grid of triangles.

In addition to triangles and tetrahedral, other commonly used elements in finite element simulation include quadrilateral (4-noded) and hexahedral (8-noded) elements in 2D and 3D, respectively. One of the most commonly used algorithms to generate unstructured quadrilateral grid is “Paving However, there is no such commonly used algorithm for generating unstructured hexahedral grid on a general 3D solid model. “Plastering” is a 3D version of Paving, but it has difficulty in forming hexahedral elements at the interior of a solid.

Delany Triangulation:

A Delaunay triangulation for a set P of points in a plane is a triangulation DT (P) such that no point in P is inside the circumcircle of any triangle in DT (P). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid skinny triangles. For a set of points on the same line there is no Delaunay triangulation (the notion of triangulation is degenerate for this case). For four or more points on the same circle (e.g., the vertices of a rectangle) the Delaunay triangulation is not unique: each of the two possible triangulations that split the quadrangle into two triangles satisfies the “Delaunay condition”, i.e., the requirement that the circumcircles of all triangles have empty interiors.

By considering circumscribed spheres, the notion of Delaunay triangulation extends to three and higher dimensions. Generalizations are possible to metrics other than Euclidean. However in these cases a Delaunay triangulation is not guaranteed to exist or be unique.



Fig: Example steps

Let n be the number of points and d the number of dimensions.

· The union of all simplifies in the triangulation is the convex hull of the points.

· The Delaunay triangulation contains O(n[d/2] ) simplifies.

· In the plane (d = 2), if there are b vertices on the convex hull, then any triangulation of the points has at most 2n − 2 − b triangles, plus one exterior face.

· In the plane, each vertex has on average six surrounding triangles.

· In the plane, the Delaunay triangulation maximizes the minimum angle. Compared to any other triangulation of the points, the smallest angle in the Delaunay triangulation is at least as large as the smallest angle in any other. However, the Delaunay triangulation does not necessarily minimize the maximum angle.

· A circle circumscribing any Delaunay triangle does not contain any other input points in its interior.

· If a circle passing through two of the input points doesn’t contain any other of them in its interior, then the segment connecting the two points is an edge of a Delaunay triangulation of the given points.

· Each triangle of the Delaunay triangulation of a set of points in d-dimensional spaces corresponds to a facet of convex hull of the projection of the points onto a (d + 1)-dimensional paraboloid, and vice versa.

· The closest neighbour b to any point p is on an edge bp in the Delaunay triangulation since the nearest neighbour graph is a subgraph of the Delaunay triangulation.

· The Delaunay triangulation is a geometric spanner: the shortest path between two vertices, along Delaunay edges, is known to be no longer than clip_image028 times the Euclidean distance between them.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s