Most of the research on the development of fully automatic unstructured mesh generators has been concentrated on various triangulation schemes. Their advantage lies in the fact that simplicial elements (triangles and tetrahedrons) are most suitable to discretize domains of arbitrary complexity, particularly when locally graded meshes are needed. In the past, a wide class of algorithms for generation of triangular and tetrahedral meshes has been established, among which three basic strategies -- the tree-based approach, advancing front technique, and Delaunay triangulation -- have proved particularly successful. Currently, the dominating activity is focused on the development of methods for generation of quadrilateral and hexahedral meshes. This effort is driven, first of all, by the fact that quadrilateral and hexahedral elements are much more popular in the engineering analysis community because of their favourable features from the computational point of view. Although a variety of approaches for generation of quadrilateral meshes has been developed so far, only few algorithms for generation of hexahedral meshes (which are algorithmically much more complex) have been established.

The early approach to creation of quadrilateral meshes, called multiblock method, is based on a mapped meshing [1]. 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 geometry splitting using the medial-axes techniques [2] combined with some heuristic rules. The quality of elements is typically dependent on the quality of the decomposition. 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 element size from block to block.

The paving algorithm [3,4], which belongs to the family of advancing front techniques, is a very powerful method for generation of quadrilateral meshes. The main difference in comparison with the advancing front technique for generation of triangular meshes consists in the fact that the whole layer of elements is constructed along the portions of 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.

Another grid-based approach for generation of quadrilateral meshes has been suggested in [5]. A tree structure is built in the interior of the domain to be discretized. A quadtree-like (namely the ``9-tree'') structure has been chosen in order to allow an easy construction of a 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 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 [6] forms the quadrilateral elements by merging two adjacent 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.

The most recent strategy for generation of quadrilateral mesh is based on spatial twist continuum. Instead of creating directly the quadrilateral mesh, a dual representation is initially built. This dual representation works with chords passing through opposite edges of a quadrilateral and intersect at the quadrilateral centroid.

Some indirect methods for the creation of quadrilateral meshes are based on the postprocessing of a triangular mesh [7,8,9]. The most simple approach, using the fact that a triangle may be split into 3 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 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). Another indirect method, called ``quad-morphing'' [10], is based on systematic transformations of set of triangles into quadrilaterals. The order of the transformations is controlled by the advancing front approach, which ensures nice alignment of the quadrilateral elements with the boundary. However, the background triangular mesh, that is kept topologically valid throughout the whole process, avoids the necessity of expensive intersection checks, typical for direct techniques.

The present paper describes a method for generation of quadrilateral meshes using an advancing front triangular mesh generator working directly on 3D surface and subjected only to minor modifications. Initially, a mixed mesh is generated in which quadrilateral elements are formed by merging two adjacent and consecutively created triangles. This approach actually further simplifies the technique introduced in [6] 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 the initial 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 one-level refinement thus eliminating all the remaining triangular elements.

The paper is organized as follows. In Section 2, the 3D surface representation is briefly described. Section 3 explains the utilization of octree data structure. The mixed mesh generation strategy is outlined in Section 4, where the triangular kernel and its modifications for quadrilateral generation are described. Section 5 deals with the adopted mesh optimization strategy, namely the Laplacian smoothing and topological cleanup. In Section 6, the one-level refinement process yielding the final quadrilateral mesh is depicted. The performance of the algorithm is presented on several examples in Section 7. The paper ends with concluding remarks in Section 8.

*Daniel Rypl
2005-12-03*