3.1.2 Quadrilateral and Hexahedral Mesh Generation

Due to their topology, quadrilateral and hexahedral meshes are naturally related to regular grids. Meshes, which are topologically equivalent to a regular grid, are called structured. Structured mesh generation algorithms play an important role for all-quad and all-hex meshes [44]. Simplex meshes can also be structured, but they are far less common than structured quadrilateral or hexahedral meshes. However, due to their topological inflexibility, structured meshes are not covered in this thesis.

One of the first algorithms published, which generates unstructured all-quad 2D meshes, is called Paving [134]. Paving is based on an advancing front approach and therefore requires the geometry to be represented as a line mesh. Another popular method for creating quadrilateral meshes uses a triangle mesh and morphs the triangles into quadrilaterals [40][122]. A technique called sweeping can be used to generate a hexahedral mesh based on a quadrilateral mesh of the boundary [106]. When using sweeping, two opposing sides of the geometry are selected. A quad mesh is generated for both sides, and these quad meshes are extruded to a hexahedral mesh. Similar to simplex mesh generation, grid overlay methods using a regular grid (or a quad- or octtree) have also been developed for all-quad and all-hex mesh generation [113][138]. Lately, methods using frame fields were proposed for quadrilateral and hexahedral mesh generation [100][101].