Combinatorial techniques for hexahedral mesh generation

Verhetsel, Kilian [UCL]

Hexahedral meshes are used in engineering and computer graphics to describe complex geometric shapes by subdividing them into cube-like cells. Hexahedral meshes are widely considered advantageous over tetrahedral meshes, in terms of efficiency or their ability to align elements to relevant geometric features. Nonetheless, they have proven difficult to generate automatically for the wide range of geometric models used in industrial applications. This thesis uses combinatorial and topological techniques to answer long-standing theoretical questions pertaining to the generation of hexahedral meshes. Namely, search algorithms exploring the space of possible topological meshes are used to find small hexahedral meshes with a given boundary, typically less than 70 hexahedra in the entire mesh. The special case of topological balls is treated separately, using shellings to more efficiently construct hexahedral meshes. These algorithms are fast enough to compute hexahedral meshes for all quadrangulated spheres with up to 20 faces. This yields an explicit construction showing that any quadrangulated sphere with n faces can be filled by a topological mesh containing up to 78n hexahedra. This new bound improves previous results requiring up to 5396n hexahedra. Furthermore, the indirect generation of hex-dominant meshes by combining tetrahedra into hexahedra is shown to be computationally intractable, justifying the existing use of heuristics for this problem. These algorithms are also used in the construction of the first geometric meshes with planar faces for two difficult test cases for hexahedral mesh generation: the 8-quadrangle tetragonal trapezohedron, and a 16-quadrangle polyhedron known as Schneiders' pyramid.