Efficiently hex-meshing things with topology (Q471135)

This paper provides a complete solution to the topological hex-meshing problem, generalizing the results for manifolds of genus zero and bipartite meshes of \textit{W. P. Thurston}, ``Hexahedral decomposition of polyhedra'', Posting to Sci. Math. (1993). {\texttt{http://www.ics.uci.edu/~eppstein/gina/Thurston-hexahedra.html}}], \textit{S. A. Mitchell} [A characterization of the quadrilateral meshes of a surface which admit a compatible hexahedral mesh of the enclosed volume. In: Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 1046, 456--476. Springer, Berlin (1996)], and \textit{D. Eppstein} [Comput. Geom. 12, No. 1--2, 3--16 (1999; Zbl 0922.68120)]. In this setting, the input quadrilaterals and output hexahedra are not necessarily convex polygons or polyhedra, but rather topological disks and balls satisfying natural conditions on the intersections pattern. The main result of the paper is the following: Consider a compact connected domain \(\Omega\subset\mathbb{R}^3\) whose boundary \(\partial\Omega\) is a (possibly disconnected) 2-dimensional manifold. Let \(Q\) be a topological quadrilateral mesh of \(\partial\Omega\) with an even number of facets. Moreover, assume that in the case \(Q\) has more than one connected component, each of them consists of an even number of facets. Then the following statements are equivalent: (1) There exists a topological hexahedral mesh of \(\Omega\) whose boundary is \(Q\); (2) Every subgraph of \(Q\) that is the boundary of a (possibly self-intersecting) surface inside \(\Omega\) has an even number of edges; (3) The dual graph \(Q^*\) of \(Q\) is the boundary of an immersed surface in \(\Omega\). The equivalence (2)\(\Leftrightarrow\)(3) is proved in Lemma 1 using homological arguments; (1)\(\Rightarrow\)(3) follows from the properties of the dual of a hexahedral mesh; (3)\(\Rightarrow\)(1) is proved in two different ways that cover, respectively, Section 4 and 5. The first proof is by steps: Lemma 3 claims that if \(Q^*\) is the boundary of a surface in \(\Omega\), then this surface is an immersion into \(\Omega\); Lemma 4 ensures that such a surface immersion can be refined to the dual of a hexahedral mesh bounded by \(Q\). The second proof is constructive and leads directly to an algorithm for the construction (when it is possible) of a hexahedral mesh of \(\Omega\) given \(Q\) as input. The author shows that, in both the situations, i.e. when the hexahedral mesh exists or not, the output, i.e. a hexahedral mesh of \(\Omega\) or an answer stating that no such mesh exists, are computable in polynomial time. Section 6 is devoted to some implications on the desirable solution of the geometrical hex-meshing problem by virtue of the results obtained under the weaker conditions used in this paper.