By John Chawner

One could be forgiven for thinking the computational fluid dynamics (CFD) world has converted entirely to unstructured (or hybrid) meshing. Certainly, we contribute to that impression with our emphasis on anisotropic tetrahedral extrusion (T-Rex), our highly automated hybrid mesh generation technique with near-wall boundary layer resolution.

T-Rex and methods like it are filling a need. For example, the Klein bottle in Figure 1 is easily meshed using T-Rex. The method meets these combined requirements: rapid generation of a high quality mesh that resolves boundary layers, wakes and other flow features for realistic (i.e. complex) geometry. One might, therefore, infer that structured grids might not meet some of those requirements – otherwise, why bother with hybrid – and that would be correct. Structured grids have a reputation for taking a long time to generate.

On the other hand, structured grids give you two things that unstructured meshes may lack: quality and control. Because unstructured and hybrid meshing algorithms are highly automated you necessarily give up some control. The control afforded to you by structured grids ensure that you generate precisely the grid you need. Also, structured grids (or more specifically, hexahedral cells) are widely acknowledged to be superior to unstructured meshes (tet cells). A recent reminder comes from the Pointwise User Group Meeting 2013, at which a presenter made it abundantly clear that “choice of grid is an integral part of getting an accurate solution” for aeroacoustics, an application for which a structured grid was chosen (Figure 2).

Another example of the use of structured grids for aeroacoustic applications is the airfoil grid we generated for a test case from the 2nd workshop benchmark problems for airframe noise computations (BANC-II), shown in Figure 3.

There are several general advantages to using a structured grid:

- Time and memory. You can fill the same volume with fewer hexes than tets, thereby lowering the cell count and your CFD computation time and memory usage. Structured grids generally have a different topology than unstructured grids, so it is difficult to make a direct cell count comparison. At its simplest, each hexahedron can be decomposed into 5 tetrahedra that share its edges, giving a 5:1 reduction in cell count for the same flowfield resolution. The benefit to reducing cell count becomes very apparent when generating a mesh with a wide variation in resolved length scales; you will use many more tets than you would hexes.
- Resolution. Flow of a fluid will often exhibit strong gradients in one direction with milder gradients in the transverse directions (e.g. boundary layers, shear layers, wakes). In these instances, high quality cells are easily generated on a hex grid with high aspect ratio (on the order of one thousand or more). It is much more difficult to generate accurate CFD solutions on highly stretched tetrahedra. (Plus, not all stretched tets are equal depending on the maximum included angles.)
- Alignment. CFD solvers converge better and can produce more accurate results when the grid is aligned with the predominant flow direction. Alignment in a structured grid is achieved almost implicitly because grid lines follow the contours of the geometry (as does the flow), whereas there's no such alignment in an unstructured mesh.
- Definable normals. Application of boundary conditions and turbulence models work well when there is a well-defined computational direction normal to a feature such as a wall or wake. Transverse normals are easily defined in a structured grid.

These last two bullet points are why boundary layers are best modeled in an unstructured mesh with prism layers: they provide structure in the direction away from the wall.

For good comparisons of the performance of structured and unstructured grids, you should review the extensive body of results accumulated by AIAA's Drag Prediction Workshop [Reference 1] and AIAA's High Lift Prediction Workshop [Reference 2], among others.

The good news is that Pointwise has an extensive suite of structured grid technology dating back to 1984 and the birth of its predecessor, Gridgen. In fact, structured grids should be viewed in equal light with Pointwise's other meshing tools in terms of breadth of applicability and depth of capability.

Rather than delving into the issue of quantifying why and how structured grids may be better than unstructured (a topic for another article), this article will review and highlight Pointwise's capabilities in structured grid generation.

A structured grid (aka mapped mesh) is one in which the cells (quadrilaterals for a surface grid, hexahedra for a volume grid) are arranged in an I×J (or I×J×K) array where I, J, and K are known as the grid's dimensions. The term “structured” refers to the structure provided to the cells' organization within that array such that a cell's neighbors are known implicitly. In other words, the point at (i,j,k) has neighbors at (i+1,j,k), (i-1,j,k), etc. This structure contrasts with an unstructured mesh in which a connectivity table has to be maintained and queried to find any point's neighbors.

In fact, structure is the source of one of the benefits of structured grids in terms of computational performance. Finding neighbors directly (via the structure) is much faster and uses less memory than having to look them up in a table (i.e. unstructured).

The best - and freely available - online reference for structured grid generation is the classic text by Joe Thompson et al, Numerical Grid Generation: Foundations and Applications [Reference 3].

There are many mathematical methods with which structured grids can be generated. Pointwise's suite, though not comprehensive, provides a broad range of capability that can be applied to virtually any type of geometry.

Note that the use of structured grids implies that the distribution of boundary points has been performed in a manner such that dimensions (number of grid points) of opposite boundaries are identical. Domains (surface grids) will have four boundaries (edges) and blocks (volume grids) will have six boundaries (faces). These topological considerations won't be discussed in what follows, only the grid methods themselves.

Algebraic methods in Pointwise serve two purposes. First, they initialize the grid in every domain and block. That grid will be sufficient (in terms of cell quality) for many geometries. In other cases, this algebraic grid serves as the starting point for elliptic PDE methods (described below).

Transfinite interpolation (TFI) is a very simple set of algebraic equations (i.e. the solution is not iterative) that is based on the solution of a boundary value problem. In other words, the location of each interior grid point is computed based on the locations of the grid's boundary points.

TFI is applied automatically in Pointwise to initialize structured surface and volume grids, domains and blocks respectively. Because TFI is a relatively fast computation (an 88x88x88 block takes only a second to TFI on a laptop), it isn't actually applied to a block until that block's grid points are needed (e.g. mesh quality examination, export), thereby minimizing memory usage.

Cell quality in a TFI'd grid is influenced by the choice of interpolants. You have three interpolant choices in Pointwise.

- Arc length. By default, Pointwise uses arc-length based interpolants that result in a grid that mimics the distribution of boundary points.
- Polar. For surface grids that need to be shaped like a surface of revolution (i.e. farfield boundaries), you can apply polar interpolants. Given an axis of revolution, the grid's boundary coordinates are mapped to a cylindrical coordinate system, TFI is applied, and the grid points' (x,y,z) coordinates are obtained from the inverse mapping. This method means you won't need CAD surfaces to define outer boundaries.
- Linear. Primarily for historical reasons, linear interpolants are also available.

When surface grids are generated, it's vital that they conform to the CAD model where appropriate. When Pointwise detects that a domain's boundaries all lie on the same surface in the CAD model, it applies Parametric TFI in which the interpolation is performed in the CAD surface's (u,v) parametric coordinates, which ensures that each of the domain's grid points lies precisely on the CAD model. In other words, because (u,v) is known at each of the boundary points, the TFI method interpolates those (u,v) coordinates onto the grid's interior. Evaluating the CAD surface at each interpolated (u,v) location yields the grid's (x,y,z) coordinates.

In more general cases, Pointwise can detect where the surface grid's boundary points lie “close enough” to a CAD surface (usually via a boundary shared with another CAD surface), and will fit them to that surface before applying Parametric TFI with the same result: grid points that all lie precisely on the CAD geometry.

It's perhaps a bit ironic that the use of elliptic partial differential equations (PDEs) for meshing was originally developed for unstructured meshes by Winslow in the late 1960s [Reference 4]. These methods involve iterative solution of an elliptic PDE with right hand side terms (control functions) that influence various aspects of the grid's cell quality.

You will likely run the Solve command on at a least a few of the domains and blocks in most grids you generate for the simple reason that the improvements in smoothness, clustering and orthogonality relative to the TFI grid are substantial and will improve your flow solver's convergence and solution accuracy.

Pointwise uses a unique implementation of the control functions whereby they are split into those that influence the grid on the interior and those that influence the grid near the boundaries.

- Laplace. The right hand side (RHS) terms of the elliptic PDE are set to zero, resulting in a maximization of smoothness but without any control over clustering.
- Thomas-Middlecoff. This formulation of the RHS terms provides a smooth variation of cell sizes on the grid's interior that mimics the cell sizes on its boundaries. This is the default control function.
- Fixed Grid. This relatively subtle technique extracts control functions from the existing grid, smoothes them, and applies them to the grid. It helps remove kinks from grids that are otherwise sufficient.

There is one very good reason for applying a boundary control function to your grid: controlling the cell spacing and orthogonality at the boundaries. It should be clear that having grid lines emanate orthogonally from solid walls is a desirable property (for boundary conditions and turbulence models), as is the ability to control the height of the first cell (for Y+ clustering requirements). Those attributes are the purpose of the boundary control functions which come in two basic formulations:

- von Lavante/Hilgenstock/White. This sequentially poly-authored formulation is the default method because it achieves the desired constraints precisely at the price of being potentially and slightly unstable in the numerical solution of the PDEs.
- Steger-Sorenson. This classic formulation of the boundary control functions tends to be more stable at the price of not matching the constraints exactly. (In other words, in highly concave regions the first grid point off the wall may be slightly farther away from the wall than specified.)

The descriptions above mention “constraints.” These constraints are definitions of exactly how you desire the wall spacing and orthogonality to be computed. Without going into too much detail, constraint types include

- Interpolated. The constraints on the boundary are interpolated from the ends of the boundary (default).
- Current Grid. The constraints are obtained from the current grid.
- Adjacent Grid. The constraints are obtained from an adjacent grid via a shared boundary. This is good for ensuring smoothness and continuity across a grid boundary.
- User Specified. Enter whatever values you desire.

Each grid boundary in the grid can use a different control function formulation.

For completeness' sake, it's worth mentioning that you also have a choice of boundary condition to be applied to each boundary of the grid.

- Fixed. Boundary points remain fixed in space (default).
- Float. The boundary points float with the solution of the PDE.
- Orthogonal. Whereas boundary control functions leave boundary points fixed and influence the near-boundary grid, you may choose to have boundary points slide along the boundary shape to achieve orthogonality.

When applying the Solve command (or “smoothing” the grid as the operation is commonly known), the elliptic PDEs are solved iteratively using either a multigrid (default) or a pointwise, successive over-relaxation (SOR) algorithm. Each algorithm has several tunable parameters that influence the rate of convergence of the solution. What you must keep in mind is that convergence of these PDEs means nothing. There's no guarantee that the “converged” grid will be better than one that's partially converged. The point is to run the solver sufficiently to achieve in the grid the desirable attributes of smoothness, clustering and orthogonality. Mesh quality can be quantified using the Examine command, but that's a topic for another article.

As is the case for TFI, it's vital that surface meshes remain constrained to the CAD model even while being smoothed. Fortunately, the elliptic PDE solver also uses parametric techniques like TFI does in which the grid is smoothed in the CAD surface's (u,v) parametric space ensuring grid adherence to the CAD model.

But as you know, grid topology is independent of CAD topology and one grid may span several CAD surfaces (see Figure 6), making the parametric solver unusable because a single consistent (u,v) mapping can't be obtained. Fortunately, Pointwise's elliptic solver is coupled with grid point projection to the CAD model to provide coverage when the parametric technique isn't available. For each iteration of the elliptic PDEs, each grid point can be projected onto the CAD model.

One of the attributes for the elliptic solver for surfaces is Shape, which can be Free (float in 3D space), Fixed (maintain current shape), or Database (CAD model) constrained. For the latter, you have the choice of which CAD surfaces the grid should be projected onto (Pointwise can figure that out for you) and the type of projection:

- Closest Point (default)
- Linear. A ray cast in a direction chosen by the user
- Cylindrical. Outward projection from an axis
- Spherical. Outward projection from a point

Up to this point, we have been describing boundary value problems. Pointwise also contains a class of structured grid methods that are initial value problems: given a grid along a boundary (the initial value), a grid is created by extruding from that boundary. Extrusion methods are very powerful and can create some great grids as illustrated in Figure 8, a single structured grid extruded around a multi-element airfoil.

Extrusion methods are limited in their application because you only have control over one boundary (the initial boundary, often called the extrusion front or just front). One common use for extrusion is with grids that extend to the farfield where that outer boundary shape need not be stringently defined. Another very popular usage of extrusion methods is for overset grids.

Extrusion in Pointwise consists of two subclasses of methods, algebraic and hyperbolic PDE:

- Algebraic. Using a set of simple algebraic equations, a grid is created by sweeping a lower order grid along a line, along a vector, or around an axis. Figure 9 demonstrates how these methods can be used to create complex shapes.
- Hyperbolic PDE. The grid generation equations are recast as hyperbolic PDE and a solution is obtained by marching outward from the initial grid.

The hyperbolic PDE technique for structured grid extrusion is significantly more sophisticated than the algebraic methods. The PDEs are cast in terms of the marching direction (typically orthogonal to the extrusion front) and the step size with various controls on each attribute. As listed below.

- Step Size. In addition to specifying the height of the first grid cell, you can control how rapidly it grows and place limits on its minimum and maximum size.
- Smoothing. Four different types of tunable smoothing parameters are available. (These are necessary because numerical solutions to hyperbolic PDEs can be a little finicky.)
- Quality criteria. You can specify limits on grid quality attributes like cell skewness and aspect ratio or even a total height of the extrusion layer. The extrusion stops when those criteria are met.

Even though the hyperbolic PDEs only give you control over the initial front, you can apply boundary conditions to the extrusion to influence its behavior. For overset grid applications the main (and default) boundary condition is splay with which you can influence how widely the sides of the extrusion splay outward as the extrusion proceeds. As you can imagine, this is good for overset grids as it ensures sufficient overlap between adjacent grids for the interpolation to proceed. Other boundary conditions include:

- Database constrained. The boundary will follow the contours of the CAD model.
- Adjacent grid. The boundary will match point-to-point with an existing grid.
- Symmetry
- Constant X, Y, or Z

Based on descriptions of the previous methods, it will not surprise you to learn that the hyperbolic PDE technique also has built-in capabilities to ensure that surface grids adhere to the CAD model where appropriate. A unique feature of Pointwise's implementation of hyperbolic PDE methods is the ability to extrude a surface while keeping it constrained to CAD surfaces. The grid in Figure 10 for a notional space vehicle was extruded using the hyperbolic PDE method from a single curve that wraps around the cross section at the base of the wings. After each point is extruded via the PDE solution it is projected onto the CAD model.

Hopefully, after reading this you will understand how Pointwise provides a great breadth of capability in its structured grid generation methods, enabling you to use structured grids in your simulations. One point to remember is that by using grid generation methods that are sufficiently broad in their applicability, you don't have to use grid topology as a crutch to achieve your desired results.

Structured grids will continue to be used in CFD for a long time to come and we plan to continue adding new capabilities to Pointwise to make them even more amenable to your work.

Give Pointwise a try and find out if a structured grid is a good fit for your application. A no-cost, no-obligation trial is available. Just click the button below to get started.

- http://aaac.larc.nasa.gov/tsab/cfdlarc/aiaa-dpw/
- http://hiliftpw.larc.nasa.gov/
- http://www.erc.msstate.edu/publications/gridbook/
- Winslow, A.M.: Numerical Solution of the Quasilinear Poisson Equations in a Nonuniform Triangle Mesh, Journal of Computational Physics 2, 149-172 (1967)