Generation of Quadrilateral and Hexahedral Meshes

The early approach to creation of quadrilateral or hexahedral meshes, called the multiblock method, is based on a mapped meshing. The domain to be discretized is divided into blocks which are then meshed separately using the parametric space mapping, transfinite mapping, or other algebraic or variational techniques. Although the mesh of individual blocks can be regarded as structured, the global mesh is generally unstructured because of the unstructured decomposition into blocks. This technique is not automatic in that the analyst must decompose manually the geometry into blocks that map well into the parametric space, and it is therefore suitable for a skilled analyst with a significant expertise especially when 3D domains are under consideration. In fact, this semi-automatic mesh generation technique is currently the mainstay of commercially available mesh generators. The quality of elements is typically dependent on the quality of the decomposition. Some more recent algorithms try to automate the procedure of geometry splitting using the medial-axes and medial-surface techniques combined with some heuristic rules. However, automatic decomposition of a complex domain into mappable regions seems to be a non-trivial task [20,70,74,109,121]. Significant disadvantage of the mapped meshing algorithms resides in a limited flexibility of the mesh size control. In order to ensure the mesh conformity at the block interfaces the same division (often propagating through the entire volume) must be used in neighbouring blocks. Therefore many additional blocks have to be created in order to accommodate changes in the desired element size from block to block. Also when used in the adaptive analysis, each time a new decomposition must be created to enable generation of meshes of a required density.

Another technique offering hexahedral meshes, often called 2.5D meshing, is based on the extrusion of a quadrilateral mesh in the third dimension. The directions of the extrusion of separate parts can be generally different (2.75D meshing), thus quite complex meshes can be formed [158]. Also this technique suffers from an insufficient control of the mesh density. Moreover, its semi-automatic nature makes it inappropriate for use in the adaptive analysis.

The paving [53,54] and plastering [47,85] algorithms, which belong to the family of advancing front techniques, are the most promising methods for generation of quadrilateral and hexahedral meshes. While the paving is being successfully used for creation of quadrilateral meshes, its 3D extension, called plastering, is still subjected to an intensive research because of its enormous algorithmic complexity. The main difference in comparison with the advancing front technique for generation of triangular and tetrahedral meshes consists in the fact that the whole layer of elements is constructed along the front at a time and that seams and wedges have to be used to resolve a conforming mesh closure in areas where layers would overlap or coincide with the boundary.

The method described in [154] uses a grid-based approach. Initially, a structured grid is built around the domain. The outer nodes of the minimal set of grid cells containing a part of the boundary surface are projected onto the boundary surface creating the surface map. The grid is then locally refined or coarsened to comply with the user-defined mesh size specification. All the nodes are then subjected to a constrained relaxation with the aim to improve the quality of the elements. The basic disadvantage of this methodology lies in its incapability to handle multiple regions and multiple material domains. Also the deviation of the mesh from the original geometry together with a relatively large computational time are considered to be a drawback.

Another grid-based approach for generation of quadrilateral and hexahedral meshes has been suggested in [152,153]. A tree structure is built in the interior of the domain to be discretized. A quadtree-like (namely the ``9-tree'') and octree-like (namely the ``27-tree'') structures have been chosen in order to allow an easy construction of a conforming quadrilateral and hexahedral mesh in the interior. The boundary region mesh is generated by adapting the interior mesh to the boundary using an isomorphism technique. This can potentionally lead to creation of poor quality elements. The other handicaps of this algorithm reside in a limited flexibility of the mesh density control (typical for tree-based approaches) and in the inability to handle domains with internal faces (multiple regions and multiple material domains).

The algorithm proposed in [72] forms the quadrilateral elements by merging two neighbouring triangular elements during the mesh generation based on the advancing front technique. The standard advancing front technique is employed with some modifications concerning the ideal position of the offset node with respect to the quality of the quadrilaterals. Note also that when splitting the front each of the subfronts must possess an even number of segments after the second triangle, completing a quadrilateral, has been introduced into the mesh.

Some methods for the creation of quadrilateral and hexahedral meshes are based on the postprocessing of a triangular or tetrahedral mesh [35,63,78,105,106]. The simplest approach, using the fact that a triangle may be split into 3 quadrilaterals and a tetrahedron into 4 hexahedrons, yields highly unstructured meshes of a rather poor quality. Therefore advanced algorithms for the conversion of a triangular mesh into a quadrilateral mesh have been developed. These algorithms are based on merging appropriate couples of neighbouring triangles into well-shaped quadrilaterals and on elimination of the remaining triangles. The elimination is most commonly done by one-level refinement of created quadrilaterals, remaining triangles and pentagons (optionally formed by a remaining triangle and a neighbouring quadrilateral). The attempts to apply a similar methodology to the conversion of a tetrahedral mesh into a hexahedral mesh have failed for two reasons. Firstly, only a very small percentage of good quality hexahedrons are obtained via the direct merging and secondly, a one-level refinement mechanism for pyramids (resulting together with wedges from the merging) is not available.

*Daniel Rypl
2005-12-07*