Generation of Quadrilateral Meshes

A variety of approaches for the generation of quadrilateral meshes have been developed over the past decades. The most common and recent techniques are described in this section.

An early approach to the creation of quadrilateral meshes, called the multiblock method, is based on a mapped meshing [12]. 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. Some more recent algorithms try to automate the procedure of the geometry splitting using the medial-axes technique [30,34] combined with some heuristic rules. The quality of elements is typically dependent on the quality of the decomposition. A significant disadvantage of the mapped meshing algorithms resides in a limited flexibility of the mesh density control. In order to ensure the mesh conformity at block interfaces, the same division (often propagating through the entire region) must be used in neighbouring blocks. Therefore many additional blocks have to be created in order to accommodate changes in the element size from block to block.

The paving algorithm [24,25], which belongs to the family of the advancing front techniques, is a very powerful method for the generation of quadrilateral meshes. The main difference in comparison with the AFT for the generation of triangular meshes consists in the fact that the whole layer of elements is constructed along portions of the front at a time. Moreover, seams and wedges have to be used to resolve a conforming mesh closure in areas where layers would overlap or coincide with the boundary.

Another grid-based approach for the generation of quadrilateral meshes is suggested in [68]. A tree structure is built in the interior of the domain to be discretized. A quadtree-like structure (namely the ``9-tree'') is chosen in order to enable use of templates for an easy construction of the conforming quadrilateral 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 the 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 [32] forms the quadrilateral elements by merging two adjacent and consecutively created triangular elements during the mesh generation based on the AFT. The standard AFT is employed with some modifications concerning the ideal position of the offset node with respect to the quality of the quadrilaterals. A special attention is also paid to the front splitting because each of the subfronts must possess an even number of segments after the second triangle, completing a quadrilateral, is introduced into the mesh.

A similar approach is adopted in [89] which further simplifies the technique introduced in [32] by allowing to generate triangular elements in all situations when creation of a quadrilateral would be difficult (typically in mesh transition zones and front closure zones). Since a large number of triangular elements might be present in such a mixed mesh, an optimization process is applied. In this process, the weighted Laplacian smoothing is combined with the topological cleanup, attempting to remove some of the triangles and to optimize the connectivity of the mesh. The optimized mesh is then subjected to a one-level refinement thus eliminating all the remaining triangular elements.

The most recent strategy for the generation of quadrilateral meshes is based on the spatial twist continuum [71]. Instead of creating directly the quadrilateral mesh in terms of an array of nodes and an appropriate element connectivity, a dual representation is initially built. This dual representation is based on the topology of the quadrilateral mesh and works with chords passing through opposite edges of the quadrilateral element and intersecting at its centroid. Once an admissible mesh topology is created, the nodes are established and the standard representation of the quadrilateral mesh is recovered.

Some indirect methods for the creation of quadrilateral meshes are based on the postprocessing of a triangular mesh [19,28,37,47,48,61]. The most simple approach, using the fact that a triangle may be split into three quadrilaterals, 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 the elimination of remaining triangles. The elimination is most commonly done by a one-level refinement of created quadrilaterals, remaining triangles and pentagons (optionally formed by a remaining triangle and a neighbouring quadrilateral). Another very recent indirect method, called ``quad-morphing'' [76], is based on systematic transformations of a set of triangles of a background triangular mesh into quadrilaterals. The order of the transformations is controlled by the advancing front approach, which ensures a nice alignment of the quadrilateral elements with the boundary. Moreover, the position of nodes in the local neighbourhood of the currently created quadrilateral are perturbated to further improve the shape of the elements. The background (initially triangular, later mixed) mesh is kept topologically valid throughout the whole process, which avoids the necessity of expensive intersection checks, typical for direct techniques.

*Daniel Rypl
2005-12-07*