Automatic unstructured mesh generation algorithms have lent themselves more readily to triangle and tetrahedral meshing. As a result, most of the literature and software are triangle and tetrahedral. In spite of this, there is a significant group of literature that focuses on unstructured quad[34] and hexahedral[35] methods. Unstructured quad and hex meshing software have also become widely available in recent years. Unlike triangle and tetrahedral methods, extension from a 2D quadrilateral algorithm to a 3D hexahedral method is not generally straightforward.

3.1 Mapped Meshing

When the geometry of the domain is applicable, quad or hex mapped meshing[36] will generally produce the most desirable result. Although mapped meshing is considered a structured method, it is quite common for unstructured codes to provide a mapped meshing option. For mapped meshing to be applicable, opposite edges of the area to be meshed must have equal numbers of divisions. In 3D, each opposing face of a topological cube must have the same surface mesh. This can often be impossible for an arbitrary geometric configuration or can involve considerable user interaction to decompose geometry into mapped meshable regions and assign boundary intervals. In order to reduce human interaction, research has be done in recent years through the CUBIT [37] project at Sandia National Labs to automatically recognize features [38] and decompose geometry[39] into separate mapped meshable areas and volumes. Work has also been done to automate interval assignments[40].

Another category of mapped meshing, also developed as part of the CUBIT[37] project is referred to as sub-mapping[41]. This method, rather than decomposing the geometry directly, determines an appropriate virtual decomposition based on corner angles and edge directions. The separate map-meshable regions are then meshed separately. This method is suitable for blocky shapes and volumes that have well defined corners and cube-like regions.

Sweeping, sometimes referred to as 2 1/2-D meshing, is another class of mapped hexahedral meshing. A quadrilateral mesh can be swept through space along a curve. Regular layers of hexahedra are formed at specified intervals using the same topology as the quadrilateral mesh. This technique can be generalized to mesh certain classes of volumes by defining so-called source and target surfaces. Provided the source and target surface have similar topology and the surfaces are connected by a set of map-meshable surfaces, the quad elements of the source area can be swept through the volume to generate hexahedra as shown in Figure 5. Care must be taken in locating internal nodes during the sweeping process and several papers [42][43] have been presented addressing this issue.

Figure 5. Hex elements generated by sweeping

Blacker[44] generalizes and extends the applicability of sweeping when he introduces the Cooper Tool. The Cooper tool allows for multiple source and target surfaces while still requiring a single sweep direction. With this tool, the topology is allowed to branch or split along the sweep direction. In addition, the topology of source and target surfaces are not required to be similar. With these requirements relaxed, a greater subset of geometry may be meshed with generally very high quality elements. The cooper tool is provided as part of the Fluent pre-processor, Gambit[45].

3.2 Unstructured Quad Meshing

Unstructured quadrilateral meshing algorithms can, in general, be grouped into two main categories: direct and indirect approaches. With an indirect approach, the domain is first meshed with triangles. Various algorithms are then employed to convert the triangles into quadrilaterals. With a direct approach, quadrilaterals are placed on the surface directly, without first going through the process of triangle meshing.

3.2.1 Indirect Methods

One of the simplest methods for indirect quadrilateral mesh generation includes dividing all triangles into three quadrilaterals, as shown in Figure 6. This method guarantees an all-quadrilateral mesh, but a high number of irregular nodes are introduced into the mesh resulting in poor element quality. An alternate algorithm is to combine adjacent pairs of triangles to form a single quadrilateral as shown in Figure 7. While the element quality increases using this method, a large number of triangles may be left.

Figure 6. Quad mesh generated by splitting each triangle into three quads

Figure 7. Quad-dominant mesh generated by combining triangles.

The triangle combining method can be improved, if some care is taken in the order in which triangles are combined. In an effort to maximize the number of quadrilaterals, Lo[46] defined an algorithm that suggested several heuristic procedures for the order in which triangles could be combined. The result is a quad-dominant mesh containing a minimal number of triangles. Johnston [47] proposes additional local element splitting and swapping strategies to increase the number and quality of quads.

Lee[48] later enhances Lo's [46] strategy by including local triangle splitting. In addition, an advancing front approach is used over the initial triangles. An initial set of fronts is defined consisting of the edges of triangles at the boundary of the domain. Triangles are systematically combined at the front, advancing towards the interior of the area. Each time a set of triangles is combined the front advances. The front always defines the division between quadrilaterals already formed and triangles yet to be combined. With this technique, Lee is able to guarantee an all-quadrilateral mesh, provided the initial number of edges on the boundary is even.

Since all operations are local, indirect methods have the advantage of being very fast. Global intersection checks are not necessary as is required with some forms of direct methods. The drawback to indirect methods is that there are typically many irregular nodes left in the mesh. Even if few irregular nodes exist, there is no guarantee that the elements will align with the boundary, a desirable property for some applications. Some of the irregular nodes can be reduced, and hence element quality increased by performing topological clean-up operations (discussed later).

Another method recently introduced by the author, known as Quad Morphing[49] also utilizes an advancing front approach to convert triangles to quads, but is able to significantly reduce the number of irregular nodes in the mesh. With this approach, local edge swaps are performed and additional nodes introduced in order to ensure boundary alignment and orthogonality. Any number of triangles may be deleted to create a single quad.

3.2.2 Direct Methods

Many methods for direct generation of quad meshes have been proposed. Among these methods, there appears to be two main categories. The first are methods that rely on some form of decomposition of the domain into simpler regions than can be resolved by one of a series of templates. The second category are those that utilize a moving front method for direct placement of nodes and elements.

3.2.2.1 Quad Meshing by Decomposition

The quad-tree decomposition technique proposed by Baehmann [50] is among the first methods utilizing decomposition of the area for quadrilateral meshing. After an initial decomposition of the 2D space into a quad-tree based on local feature sizes, quadrilateral elements are fitted into the quad-tree leaves, adjusting nodes in order to conform to the boundary.

Talbert[51] later introduces another decomposition technique. With this approach, the domain is recursively subdivided into simple polygonal shapes. The resulting polygons satisfy a limited number of templates into which quadrilateral elements are inserted. Chae[52] has recently proposed enhancements to Talbert's algorithm with similar work presented by Nowottny[53].

Quadrilateral meshing utilizing a medial axis decomposition of the domain was first introduced by Tam[54]. The medial axis can be thought of as a series of lines and curves generated from the midpoint of a maximal circle as it is rolled through the area (Figure 8). Having decomposed the area into simpler regions, sets of templates are then employed to insert quadrilaterals into the domain. Linear programming techniques are used in order to maintain compatibility of element divisions between adjoining regions of the domain.

Figure 8. Decomposition of an area using the medial axis

Joe[55] also utilizes decomposition algorithms to decompose the area into convex polygons. Using techniques previously developed for triangle mesh generation[56], Joe constructs a boundary constrained quadrilateral mesh within each convex sub-domain of the area.

3.2.2.2 Advancing Front Quad Meshing

Zhu[57] is among the first to propose a quadrilateral meshing algorithm using an advancing front approach. Starting with an initial placement of nodes on the boundary, individual elements are formed by projecting edges towards the interior. Two triangles are formed using traditional triangle advancing front methods and then combined to form a single quadrilateral.

The paving algorithm introduced by Blacker and Stephenson [58], presents a method for forming complete rows of elements starting from the boundary and working in. Methods for projection of nodes, handling of special geometric situations and intersection of opposing fronts are discussed. Cass[59] further developed paving, by generalizing the method for three-dimensional surfaces. White[60] recently proposed enhancements to the paving algorithm suggesting individual placement of elements rather than complete rows. The paving algorithm is currently implemented as part of the CUBIT [37] software as well as several commercial packages including MSC Patran [61]and Fluent's Gambit [45] software.

3.3 Unstructured Hex Meshing

Similar to quadrilateral meshing, there are both direct and indirect methods for unstructured hex meshing.

3.3.1 Indirect Methods

Indirect methods, although not in wide use have been proposed for some applications[62]. Provided a solid can be tet meshed, each tetrahedron can be subdivided into four hexahedra as shown in Figure 9. Most finite element analysts, because of the poor element quality that will in general result, have rejected this solution.

Figure 9. Decomposition of a tetrahedron into four hexahedra

An equivalent indirect hexahedral mesh generation scheme that will combine tetrahedra, similar to combining triangles to form quadrilaterals has not been presented in the literature. The simplest tetrahedralization of a cube will contain five tetrahedra. An indirect method that combines tets to form hexes would therefore need to look for combinations of five or more tetrahedra to form a single hexahedra. This problem to date has not proved a reasonable nor tractable method for mesh generation.

3.3.2 Direct Methods

There are currently four distinct strategies proposed for unstructured all-hex mesh generation that are predominant in the literature:

grid-based
medial surface
plastering
whisker weaving

3.3.2.1 Grid-Based

The grid-based approach, proposed by Schneiders[63] involves generating a fitted three dimensional grid of hex elements on the interior of the volume. Hex elements are added at the boundaries to fill gaps where the regular grid of hexes does not meet flush with the surface. This method, while robust, tends to generate poor quality elements at the boundary of the volume. Hex elements will in general not be aligned with the boundary. The resulting mesh generated from the grid-based approach is also highly dependent upon the orientation of the interior grid of hex elements. In addition, element sizes must be approximately all the same. In recent work, Weiler[64] and Schneiders[65] have introduced modifications that allow for significant transition in element sizes utilizing an octree decomposition of the domain. Mesh generators based on the grid-based approach are available in the Hexar [66] software from Cray Research and in MARC's Mentat[67] software.

3.3.2.2 Medial Surface

Medial surface methods[68] [69][70] involve an initial decomposition of he volume. As a direct extension of the medial axis method for quad meshing, the domain is subdivided by a set of medial surfaces, which can be thought of as the surfaces generated from the midpoint of a maximal sphere as it is rolled through the volume. The decomposition of the volume by medial surfaces is said to generate map meshable regions. A series of templates for the expected topology of the regions formed by the medial surfaces are utilized to fill the volume with hexahedra. Linear programming is used to ensure element divisions match from one region to another. This method, while proving useful for some geometry, has been less than reliable for general geometry. Robustness issues in generating the medial surfaces as well as providing for all cases of regions defined by the medial surfaces has proved to be a difficult problem. Medial surface methods are incorporated into the FEGS' CADFix [71] hexahedral mesh generator and within Solidpoint's Turbomesh [72] software.

3.3.2.3 Plastering

Plastering[73][74] is an attempt to extend the paving algorithm to three dimensions. With this method, elements are first placed starting with the boundaries and advancing towards the center of the volume as shown in Figure 10. A heuristic set of procedures for determining the order of element formation is defined. Similar to other advancing front algorithms, a current front is defined consisting of all quadrilaterals. Individual quads are projected towards the interior of the volume to form hexahedra. In addition, plastering must detect intersecting faces and determine when and how to connect to pre-existing nodes or to seam faces. As the algorithm advances, complex interior voids may result, which in some cases are impossible to fill with all-hex elements. Existing elements, already placed by the plastering algorithm must sometimes be modified in order to facilitate placement of hexes towards the interior.

Figure 10. Plastering process forming elements at the boundary.

Currently, the plastering algorithm has not been proven to be reliable on a large class of problems. Although in many cases, several layers of hex elements may be successfully placed on the boundary of the volume, intersection and closure procedures are less than reliable. Sandia's CUBIT[37] project is continuing research on plastering and makes it available in their software.

3.3.2.4 Whisker Weaving

Whisker weaving, first introduced by Tautges and Blacker [75], is based on the concept of the spatial twist continuum (STC) [76]. Tautges describes the STC as the dual of the hexahedral mesh, represented by an arrangement of intersecting surfaces which bisect hexahedral elements in each direction. Figure 11 shows a simple representation of the twist planes of the STC defined for a volume composed of only two hexahedra.

The principal behind whisker weaving is to first construct the STC or dual of the hex mesh. With a complete STC, the hex elements can then be fitted into the volume using the STC as a guide. This is done by beginning with a topological representation of the loops formed by the intersection of the twist planes with the surface. The loops can be easily determined from an initial quad mesh of the surface. The objective of the whisker weaving algorithm is to determine where the intersections of the twist planes will occur within the volume. Since this is done topologically, there are no actual intersection calculations performed. Once a valid topological representation of the twist planes has been achieved, hexes are then formed inside the volume. One hex is formed wherever three twist planes converge.

The whisker weaving algorithm has achieved some success, but has yet to prove itself as robust and reliable for a wide variety of problems.

Figure 11. The STC composed of four twist planes, for a solid composed of two hexahedra

3.4 Hex-Dominant Methods

Since most methods for all-hex meshing appear to be less than robust, some researchers have proposed using a mixed hexahedra/tetrahedra mesh. A hex-dominant approach appears to be satisfactory in many cases. One simple approach introduced by the author[77] is to manually subdivide the geometry into regions that will readily accept a mapped mesh and those that are more geometrically complex. Within the complex regions a tet mesh is defined. Wherever the tet elements interface directly with hex elements, a pyramid shaped element may be formed. This option is provided with the ANSYS[31] mesh generation software.

Tuchinsky[78] recently proposed an algorithm for combining both plastering and tetrahedral meshing technologies. Using the plastering algorithm, hex elements are advanced as far as possible into the volume. The remaining voids within the volume are then filled with tetrahedra. The user also has the option of forming pyramid shaped elements at the interface between hex and tet elements. The CUBIT[37] software now provides an option to allow a hex-dominant mesh.

Min[79] also presents a similar method for hex-dominant meshing, utilizing offset geometry from the boundaries in order to form layers of hexes. After a series of shrunken shells have been advanced towards the interior of the volume, the remainder of the volume is filled with tetrahedra. In addition to tets and hexes, Min introduces pyramid and wedge shaped elements where applicable.

Back to Tet/Tri Methods.

Go to Introduction.

Continue to Surface Meshing.

sjowen@sandia.gov