A constructive approach to constrained hexahedral mesh generation

Mitchell proved that a necessary and sufficient condition for the existence of a topological hexahedral mesh constrained to a quadrilateral mesh on the sphere is that the constraining quadrilateral mesh contains an even number of elements. Mitchell’s proof depends on Smale’s theorem on the regularity of curves on compact manifolds. Although the question of the existence of constrained hexahedral meshes has been solved, the known solution is not easily programmable; indeed, there are cases, such as Schneider’s Pyramid, that are not easily solved. Eppstein later utilized portions of Mitchell’s existence proof to demonstrate that hexahedral mesh generation has linear complexity. In this paper, we demonstrate a constructive proof to the existence theorem for the sphere, as well as assign an upper-bound to the constant of the linear term in the asymptotic complexity measure provided by Eppstein. Our construction generates 76 × n hexahedra elements within the solid where n is the number of quadrilaterals on the boundary. The construction presented is used to solve some problems posed by Schneiders and Eppstein. We will also use the results provided in this paper, in conjunction with Mitchell’s Geode-Template, to create an alternative way of creating a constrained hexahedral mesh. The construction utilizing the Geode-Template requires 130 × n hexahedra, but will have fewer topological irregularities in the final mesh.