Efficiently Hex-Meshing Things with Topology

A topological quadrilateral mesh (Q) of a connected surface in (mathbb {R}^3) can be extended to a topological hexahedral mesh of the interior domain (varOmega ) if and only if (Q) has an even number of quadrilaterals and no odd cycle in (Q) bounds a surface inside (varOmega ) . Moreover, if such a mesh exists, the required number of hexahedra is within a constant factor of the minimum number of tetrahedra in a triangulation of (varOmega ) that respects (Q) . Finally, if (Q) is given as a polyhedron in (mathbb {R}^3) with quadrilateral facets, a topological hexahedral mesh of the polyhedron can be constructed in polynomial time if such a mesh exists. All our results extend to domains with disconnected boundaries. Our results naturally generalize results of Thurston, Mitchell, and Eppstein for genus-zero and bipartite meshes, for which the odd-cycle criterion is trivial.