Keywords: hexahedral mesh generation, unstructured mesh generation, algorithmic approaches, mesh quality, mesh optimization, smoothing, quadrilateral surface meshes, mesh topology, hybrid meshes, applications in biomechanics.

n a wide range of applications of numerical simulations by means of the finite element method (FEM) the generation of hexahedral meshes is highly desirable. However, in spite of enormous research efforts, the robust generation of such meshes with an acceptable quality is still a challenge for complex domains.

The purpose of this paper is to give a short overview of the state-of-the-art in hexahedral mesh generation. We review the most influential approaches which have been developed over the last years and discuss their strengths and limitations. We focus on scientific developments and do not review commercial products.

Owen [1] and Schneiders [2] gave surveys on unstructured mesh generation technology and quadrilateral and hexahedral element meshes, respectively, and Tautges [3] recently presented a survey on the generation of hexahedral meshes with emphasis to assembly geometries. For much more material, online information, and data bases on meshing literature see [4] and [5].

In this paper, we reserve the term mesh generation to unstructured mesh generation, whereas grid generation refers to the generation of structured meshes (which require the same node degree for all interior mesh vertices). We also distinguish between combinatorial and geometric meshes and polyhedral subdivisions. A combinatorial hexahedral mesh is merely a decomposition of the given domain into an abstract (cell) complex of combinatorial cubes but without an explicit embedding into space. Combinatorial meshes are important for the study of mesh existence but they are sometimes also used as a first step in the mesh generation process. In contrast, a geometric hexahedral mesh is an embedded cell complex of hexahedra. Here, each hexahedron is bounded by possibly warped quadrilaterals. Finally, a polyhedral subdivision requires a partition of the given domain into polytopes, i.e., cubes with flat facets. These meshes are the main focus of work in computational geometry, but not used much in practice as very difficult or even impossible to generate.

We first discuss the minimal requirements for valid meshes and mesh quality issues. Then we state several criteria for the comparison of meshing algorithms. This serves as a basis for the main section, where we review and compare the different approaches for hexahedral mesh generation which have been developed over the last decade(s) in view of these criteria. We categorize the different approaches into five groups:

1. Approaches for restricted classes of shapes. This includes mapping, templates, sweeping and its generalizations.
2. Decomposition-based approaches. Here we subsume manual decomposition, feature recognition based decomposition, virtual decomposition, and decomposition based on the embedded Voronoi graph.
3. Advancing front based methods like plastering.
4. Indirect approaches, which convert some other mesh. This includes grid-based methods and the conversion of tetrahedral meshes into hybrid meshes.
5. Direct approaches working with the combinatorial dual. Whisker weaving and successive dual cycle elimination belong to this class of methods.

As most approaches for volume meshing rely on high quality surface meshes, we also briefly touch upon quadrilateral surface meshing and the suitability of these methods for volume meshing. Moreover, we also discuss mesh improvement procedures. This includes mesh embedding and smoothing on the one hand, and structural changes of the mesh by means of flipping operations on the other hand.

We briefly touch upon examples for applications of hexahedral mesh generation. In particular, we review a case study in the field of biomechanics where parts of human bones have been meshed by hexahedra and successfully applied to a FEM analysis.

Finally, we conclude with some remarks on remaining challenges and perspectives for future research and development.

1

S. Owen. A survey of unstructured mesh generation technology. Proceedings of the 7th International Meshing Roundtable, pp. 239-267, http://www.andrew.cmu.edu/user/sowen/survey, 1998.

2

R. Schneiders. Quadrilateral and hexahedral element meshes. In J. F. Thompson, B. K. Soni, and N. P. Weatherill, editors," Chapter 21, Handbook of Grid Generation". CRC Press, 1999.

3

T. J. Tautges. The generation of hexahedral meshes for assembly geometry: survey and progress. "International Journal for Numerical Methods in Engineering", 50:2617-2642, 2001. doi:10.1002/nme.139

4

R. Schneiders. Information on finite element mesh generation. Available online at http://www-users.informatik.rwth-aachen.de/roberts/meshgeneration.html.

5

S. Owen. Meshing research corner. http://www.andrew.cmu.edu/user/sowen/mesh.html.

purchase the full-text of this chapter (price £20)

go to the previous chapter
go to the next chapter
return to the table of contents
return to the book description
purchase this book (price £90 +P&P)