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 in 2D or in 3D for some real numbers dx, dy, and dz representing the grid spacing.
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 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
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
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:
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 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 , 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 and 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
By changing the functional expression for , 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 . 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 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. 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 . This can be taken to mean that or that . Vinokur’s procedure guarantees the latter.
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: and . Vinokur gives such a function, first defining
The final grid distribution is then given by
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.
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.
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.
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 times the Euclidean distance between them.