A mesh is a representation of a larger geometric domain by smaller discrete cells. Meshes are commonly used to compute solutions of partial differential equations and render computer graphics, and to analyze geographical and cartographic data. A mesh partitions space into elements (or cells or zones) over which the equations can be solved, which then approximates the solution over the larger domain. Element boundaries may be constrained to lie on internal or external boundaries within a model. Higher-quality (better-shaped) elements have better numerical properties, where what constitutes a "better" element depends on the general governing equations and the particular solution to the model instance.
Common cell shapes
Two-dimensional
There are two types of two-dimensional cell shapes that are commonly used. These are the triangle and the quadrilateral. Computationally poor elements will have sharp internal angles or short edges or both.
Triangle This cell shape consists of 3 sides and is one of the simplest types of mesh. A triangular surface mesh is always quick and easy to create. It is most common in unstructured grids.
Quadrilateral This cell shape is a basic 4 sided one as shown in the figure. It is most common in structured grids. Quadrilateral elements are usually excluded from being or becoming concave.
Three-dimensional
The basic 3-dimensional element are the tetrahedron, quadrilateral pyramid, triangular prism, and hexahedron. They all have triangular and quadrilateral faces. Extruded 2-dimensional models may be represented entirely by the prisms and hexahedra as extruded triangles and quadrilaterals. In general, quadrilateral faces in 3-dimensions may not be perfectly planar. A nonplanar quadrilateral face can be considered a thin tetrahedral volume that is shared by two neighboring elements.
Tetrahedron A tetrahedron has 4 vertices, 6 edges, and is bounded by 4 triangular faces. In most cases a tetrahedral volume mesh can be generated automatically.
Pyramid A quadrilaterally-based pyramid has 5 vertices, 8 edges, bounded by 4 triangular and 1 quadrilateral face. These are effectively used as transition elements between square and triangular faced elements and other in hybrid meshes and grids.
Triangular prism A triangular prism has 6 vertices, 9 edges, bounded by 2 triangular and 3 quadrilateral faces. The advantage with this type of layer is that it resolves boundary layer efficiently.
Hexahedron A cuboid, a topological cube, has 8 vertices, 12 edges, and 6 quadrilateral faces, making it a type of hexahedron. In the context of meshes, a cuboid is often called a hexahedron, hex, or brick. For the same cell amount, the accuracy of solutions in hexahedral meshes is the highest. The pyramid and triangular prism zones can be considered computationally as degenerate hexahedrons, where some edges have been reduced to zero. Other degenerate forms of a hexahedron may also be represented.
Advanced Cells (Polyhedron) A polyhedron (dual) element has any number of vertices, edges and faces. It usually requires more computing operations per cell due to the number of neighbours (typically 10). Though this is made up for in the accuracy of the calculation.
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, since the neighbourhood relationships are defined by storage arrangement. Some other advantages of structured grid over unstructured are better convergence and higher resolution.
Unstructured grids An unstructured grid is identified by irregular connectivity. It cannot easily be expressed as a two-dimensional or three-dimensional array in computer memory. This allows for any possible element that a solver might be able to use. Compared to structured meshes, for which the neighborhood relationships are implicit, this model can be highly space inefficient since it calls for explicit storage of neighborhood relationships. The storage requirements of a structured grid and of an unstructured grid are within a constant factor. These grids typically employ triangles in 2D and tetrahedral in 3D.
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.
Mesh quality A mesh is considered to have higher quality if a more accurate solution is calculated more quickly. Accuracy and speed are in tension. Decreasing the mesh size always increases the accuracy but also increases computational cost. Accuracy depends on both discretization error and solution error. For discretization error, a given mesh is a discrete approximation of the space, and so can only provide an approximate solution, even when equations are solved exactly. (In computer graphics ray tracing, the number of rays fired is another source of discretization error.) For solution error, for PDEs many iterations over the entire mesh are required. The calculation is terminated early, before the equations are solved exactly. The choice of mesh element type affects both discretization and solution error. Accuracy depends on both the total number of elements, and the shape of individual elements. The speed of each iteration grows (linearly) with the number of elements, and the number of iterations needed depends on the local solution value and gradient compared to the shape and size of local elements.
Solution precision A coarse mesh may provide an accurate solution if the solution is a constant, so the precision depends on the particular problem instance. One can selectively refine the mesh in areas where the solution gradients are high, thus increasing fidelity there. Accuracy, including interpolated values within an element, depends on the element type and shape.
… excerpt ends here. Continue reading the full article.
