Grid Generation
Summary
Grid generation is an essential aspect of all numerical methods that employ finite differences, finite volumes and finite elements for the solution of partial differential equations (PDE). Shortly, it consists in dividing bounded or unbounded flow domains into elements (triangles, quadrilaterals, polygons in 2-D; tetraedrons, parallelepipeds, n-edrons, etc.) called cells.
The problem is a non-trivial one, and requires a considerable amount of time. Development of a grid generation system requires years of work.
Figure 1: 3-D structured grid for external aerodynamics
Importance of the Subject
The topic of grid generation has become a field on its own in the increasigly vast field of computational fluid dynamics (CFD). A short selection of publications for reference is given below. Some general considerations regarding suitable methods and their role in CFD are the following:
-
Almost any method works on a good grid, whereas the bad methods only work on good grids;
-
If one had enough resolution (e.g. enough points), then the grid quality would be of minor importance, provided that some basic requirements are satisfied; if the grid is necessarily coarse, then its quality becomes essential;
-
A good grid can accelerate the convergence of the solution, while a bad grid can even lead to a divergent iteration history.
Conceptual Problems
There are a number of conceptual problems that must be addressed when choosing a grid generation system for a particular problem:
- Open or closed flow domain
- Domain topology (C, H, O, and combinations therein)
- Single or multiple (single- of multi-block)
- block-interface type for multi-block (continuous ?)
- Overlapping (ex. chimera type) or non-overlapping
- Algebraic or from differential equations
- Structured or unstructured
- Fixed or fully-adaptive
- Two- or three dimensional
Fig. 2. below shows some typical multi-block interfaces (for structured grids). The most common interface is the full matching (top left). The other systems require interpolation of fluid dynamic quantities at non-matching points.
 |
 |
 |
 |
Visualization Issues
Once the grid has been generated, it must be visualized to check for errors (they come in an infinite variety). For 3-D grids this is a particular difficult stage, where a computer animated image, or a CAD-based system is absolutely essential, and this is proven by the fact that the most sophisticated systems currently available come with visualization facilities. Minor errors can be fixed with ad hoc post- processing, going under the definition of grid smoothing.
Input Requirements
Given the complexity of the problem just outlined, one can argue also on the amount of user input required. Some methods excel for the amount of data that must be set (for example a multi-block structured grid, requiring point bunching on all sides).
Unstructured grids have been sometimes preferred on the structured counterparts because grids - also in complex domains - can be generated more automatically.
How about the grid quality then ? - If the code runs, do not fix it, otherwise repeat the fundamental steps.
Grid Generation Methods
Below it is described a set of algebraic and differential methods that makes up the bulk
of the available methods.
Algebraic methods are based on coordinate transformation equations in a physical
domain. In their most simple form they are Lagrange and Hermite transformations (are
called shearing transformations). Some methods are based on interpolation schemes in
multi-dimensions.
Transfinite interpolation (Eriksson, 1982), and multi- surface
transformation (Eiseman, 1985) produce good grids for closed domains. Integration of
the methods with additional control on the boundary values and elliptic smoothing
(see further down) give efficient grid generation systems (for example ICEM/CFD,
GridPro)
These methods in their most developed form allow some control on the values of the
derivatives at the boundary.
Elliptic methods are based on the solution of elliptic partial differential
equations with some conditions (called forcing terms) to force point
bunching. The problem is formulated via a set of Poisson equations (Thompson, 1977)
with forcing terms usually defined by the Thomas-Middlecoff terms (Thomas-Middlecoff,
1982), or by other appropriate control functions (Sorenson, 1995).
The solution of the system is iterative, for example with a Successive Over-
Relaxation (SOR) method. For large grids the computing time is considerable.
Elliptic systems produce very smooth grids (sometimes too smooth) and they can be used
to smooth out metric discontinuities in the transfinite interpolation systems
(for this purpose also a Laplace smoother will suffice).
Hyperbolic methods are based on the solution of partial differential equations
of hyperbolic type, that are solved marching outward from the domain boundaries.
The idea of using hyperbolic PDEs is very effective for external flows where the wall
boundaries (airfoil, wing, wing-body, etc.) are well defined, whereas the far field
boundary is left arbitrary. This situation also eliminates the need to specify point
distribution on some of the edges of the flow domain, and makes it more handy than
for example the transfinite interpolation methods.
In its basic formulation (Steger- Chaussee, 1980) the hyperbolic grid generator is
based on a condition of orthogonality, and a condition on the cell area. The method
can be integrated with grid line smoothing and orthogonality checks.
There are several algorithms for generating unstructured grids. The Delauney
triangulation method other Voronoi methods and the advancing front method are the
most popular, also among solution-adaptive systems, and they are the basis of some
commercial fluid dynamic codes (for example Star-CD, Rampant).
The field is in rapid
expansion, and there are schools of thought whether the unstructured approach
is better or worse than the structured approach to the solution of PDEs in fluid
dynamics.
Briefly, unstructured grids can be generated faster on most complex
domains, and exists for all domains. Mesh refinement can be done without
difficulties, also on a local basis and adaptively.
Storage of the grid data is no easy (it requires information on which node is
neighbor to which), it takes far more memory than in a structured sense, and
therefore hinders parallelizarion of computer codes.
All the methods described above make use of some empirical knowledge about the form
of the solution of the PDEs. This knowledge makes us force many points in regions of
large field gradients (for ex. boundary layers).
Better solutions could be obtained
if a first guess grid could be adapted in a time-marching numerical scheme to follow
exactly the evolution of the field gradients (a particular difficult problem is the
position of the shock wave in a transonic flow.)
Methods that can be used to follow the solution include: weight functions,
Poisson smoothing, electro-dynamic analogy. The major problem of the adaptivity
systems is that they must be built in the solver of the PDEs, and cannot be left out
as in the most popular approach.
For some problems of particular difficult nature scientists have developed hybrid
methods that feature both structured and unstructured zones. These methods are the
chimera technique and the hybrid structured/ unstructured technique.
The chimera
approach consists in building partially overlapping blocks. Boundary conditions need
to be exchanged at the interface between domains and this is usually done through
some form of interpolation.
The hybrid scheme takes advantage of both unstructured
and structured methods by applying structured body fitted coordinates to the body
and unstructured networks in the outer boundaries.
Problems that require such a complex CFD approach include rotor/fuselage interaction
in a full rotorcraft simulation, propeller to fixed wing analysis, etc.
All grid generation processes (especially 3-D problems) start with a surface
definition. This definition is seldom an easy task. The input may consist of points,
lines, curves, splines, surface patches, etc.
All these items can be defined through a CAD system. Sometimes it is necessary to
spline, smooth and re-patch the input data. Some examples for 2-D airfoil problems
are shown in theexamples. Some grid generation systems come with their own facilities
(for ex. ICEM/Surf, widely used in automotive industry).
Presently there is no one method that fits all. Most still depends on the
quality of the CFD solution that can be achieved.
The characteristics of the block boundaries depend on the capabilities of the flow
solver. In the structured domain, algebraic methods have been preferred because
faster.
The most up-to-date methods have been embedded in sophisticated multi-disciplinary
tools that come with CAD/CAE interface, surface treatment techniques, complex
visualization tools, post-processing, etc. These tools allow multi-block structured.
The number of cells that can are necessary depends on the particular problem. Usually
a minimum number is easy to figure out. Most practical aerodynamic problems can be
solved with several million cells. The 10 million mark is current practical bound.
These sites are not part of the aerodyn.org domain. There is no guarantee nor control
over their content and availability.
Algebraic Methods
Elliptic Methods
Hyperbolic Methods
Unstructured Methods
Adaptive Grids
Other Methods
Surface Control
State-of-the-Art
Multi-Disciplinary Strategies
Problem Size
More on
On the Web
Selected References