Grid generation is often quoted as the most important and most time consuming part of CFD analysis. The quality of the grid plays a direct role on the quality of the analysis, regardless of the flow solver used. Additionally, the solver will be more robust and efficient when using a well constructed mesh. With this in mind, it is important for the CFD analyst to know and understand all of the various grid generation methods. Only by knowing all the methods can he or she select the right tool to solve the problem at hand. In this article, I will describe the current state of the art in CFD grid generation. I will restrict myself to methods which are currently available in production software and in widespread use and I will describe the strengths and weaknesses of each.

  



Structured Grid Methods
Structured grid methods take their name from the fact that the grid is laid out in a regular repeating pattern called a block. These types of grids utilize quadrilateral elements in 2D and hexahedral elements in 3D in a  computationally rectangular array. Although the element topology is fixed, the grid can be shaped to be body fitted through stretching and twisting of the block. Really good structured grid generators utilize sophisticated elliptic equations to automatically optimize the shape of the mesh for orthogonality and uniformity.
It used to be that structured meshes could only consist of one block. The user was forced to make due with just one block and various cell flagging schemes were used to "turn off" portions of the block to model obstructions. Later, multiblock structured grid generation schemes were developed which allow several blocks to be connected together to construct the whole domain. Over the years, several block to block connection methods have evolved. These include point to point, where the blocks must match topologically and physically at the boundary, many points to one point, where the blocks must be topologically similar, but not the same at the boundary, and arbitrary connections, where the blocks must be physically similar at the boundary, but can have significant topology differences. While multiblock grids give the user more freedom in constructing the mesh, the block connection requirements can be restricting and are often difficult to construct. Additionally, the various degrees of block connectivity freedom come at the expense of solution accuracy and solver robustness.

There is another structured grid method which seeks to avoid the problems associated with block connections. Chimera or overset grid methods allow the individual blocks to conform to the physical boundaries, but be free form and overlapping at the block connections. Sophisticated post processing programs are run on the overlapping mesh to determine "hole cutting" locations and interpolation factors around block boundaries. What these methods gain in user convenience, they usually give up in solution accuracy. However, these methods can be enablers for geometries which would be too daunting a task with conventional methods (modeling helicopters with moving rotor blades and aircraft store separation are cases in point).

Structured grids enjoy a considerable advantage over other grid methods in that they allow the user a high degree of control. Because the user places control points and edges interactively, he has total freedom when positioning the mesh. In addition, hexahedral and quadrilateral elements, which are very efficient at filling space, support a high amount of skewness and stretching before the solution will be significantly effected. This allows the user to naturally condense points in regions of high gradients in the flowfield and expand out to a less dense packing away from these areas. Also, because the user interactively lays out the elements, the grid is most often flow-aligned, thereby yielding greater accuracy within the solver. Structured block flow solvers typically require the lowest amount of memory for a given mesh size and execute faster because they are optimized for the structured layout of the grid. Lastly, post processing of the results on a structured block grid is typically a much easier task because the logical grid planes make excellent reference points for examining the flow field and plotting the results.

The major drawback of structured block grids is the time and expertise required to lay out an optimal block structure for an entire model. Often this comes down to past user experience and brute force placement of control points and edges. Some geometries, eg. shallow cones and wedges, do not lend themselves to structured block topologies. In these areas, the user is forced to stretch or twist the elements to a degree which drastically affects solver accuracy and performance. Grid generation times are usually measured in days if not weeks.

Unstructured Grid Methods
Unstructured grid methods utilize an arbitrary collection of elements to fill the domain. Because the arrangement of elements have no discernible pattern, the mesh is called unstructured. These types of grids typically utilize triangles in 2D and tetrahedra in 3D. While there are some codes which can generate unstructured quadrilateral elements in 2D, there are currently no production codes which can generate unstructured hexahedral elements in 3D.  As with structured grids, the elements can be stretched and twisted to fit the domain. These methods have the ability to be automated to a large degree. Given a good CAD model, a good mesher can automatically place triangles on the surfaces and tetrahedra in the volume with very little input from the user. The automatic meshing algorithm typically involves meshing the boundary and then either adding elements touching the boundary (advancing front) or adding points in the interior and reconnecting the elements (Delaunay).
The advantage of unstructured grid methods is that they are very automated and, therefore, require little user time or effort. The user need not worry about laying out block structure or connections. Additionally, unstructured grid methods are well suited to inexperienced users because they require little user input and will generate a valid mesh under most circumstances. Unstructured methods also enable the solution of very large and detailed problems in a relatively short period of time. Grid generation times are usually measured in minutes or hours.

The major drawback of unstructured grids is the lack of user control when laying out the mesh. Typically any user involvement is limited to the boundaries of the mesh with the mesher automatically filling the interior. Triangle and tetrahedral elements have the problem that they do not stretch or twist well, therefore, the grid is limited to being largely isotropic, ie. all the elements have roughly the same size and shape. This is a major problem when trying to refine the grid in a local area, often the entire grid must be made much finer in order to get the point densities required locally. Another drawback of the methods are their reliance on good CAD data. Most meshing failures are due to some (possibly minuscule) error in the CAD model. Unstructured flow solvers typically require more memory and have longer execution times than structured grid solvers on a similar mesh. Post processing the solution on an unstructured mesh requires powerful tools for interpolating the results onto planes and surfaces of rotation for easier viewing.

Hybrid Grid Methods
Hybrid grid methods are designed to take advantage of the positive aspects of both structured and unstructured grids. Hybrid grids utilize some form of structured grid in local regions while using unstructured grid in the bulk of the domain.
Hybrid grids can contain hexahedral, tetrahedral, prismatic, and pyramid elements in 3D and triangles and quadrilaterals in 2D. The various elements are used according to their strengths and weaknesses. Hexahedral elements are excellent near solid boundaries (where flowfield gradients are high) and afford the user a high degree of control, but are time consuming to generate. Prismatic elements (usually triangles extruded into wedges) are useful for resolving near wall gradients, but suffer from the fact that they are difficult to cluster in the lateral direction due to the underlying triangular structure. In almost all cases, tetrahedral elements are used to fill the remaining volume. Pyramid elements are used to transition from hexahedral elements to tetrahedral elements. Many codes try to automate the generation of prismatic meshes by allowing the user to define the surface mesh and then marching off the surface to create the 3D elements. While very useful and effective for smooth shapes, the extrusion process can break down near regions of high curvature or sharp discontinuities.

Another type of hybrid grid is the quasi-structured or "cooper" grid method. While basically a form of the prismatic grid extrusion technique, the quasi-structured method does allow for some sophisticated forms of growing the 3D mesh using a sweeping concept within a CAD solid model.

The advantage of hybrid grid methods is that you can utilize the positive properties of structured grid elements in the regions which need them the most and use automated unstructured grid techniques where not much is happening in the flowfield. The ablity to control the shape and distribution of the grid locally is a powerful tool which can yield excellent meshes.

The disadvantage of hybrid methods is that they can be difficult to use and require user expertise in laying out the various structured grid locations and properties to get the best results. Hybrid methods are typically less robust than unstructured methods. The generation of the structured portions of the mesh will often fail due to complex geometry or user input errors. While the flow solver will use more resources than a structured block code, it should be very similar to an unstructured code. Post processing the flow field solution on a hybrid grid suffers from the same disadvantages as an unstructured grid. Grid generation times are usually measured in hours or days.

Summary
In this article I have outlined the various methods which are currently the state of the art in CFD grid generation. We have seen that the various methods are a trade-off between user control and automation. None of these methods will be ideal in all cases, it is up to the CFD analyst to recognize and understand these grid generation tools and use them appropriately.
Watch for a follow up article in which I will describe the available CFD meshing software packages in light of what we have learned in this article.