Efficiently hex-meshing things with topology

DOI10.1007/S00454-014-9624-3MaRDI QIDQ471135zbMATH OpenOpenAlexFDO

Publication date 14 November 2014

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-014-9624-3

computational topology cube complexes homology mesh generation

General low-dimensional topology (57M99) General topology of complexes (57Q05) Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs (65N50) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

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.

Recommendations

Cites work

Cited in

(11)

Describes a project that uses

Uses Software

This page was built for publication: Efficiently hex-meshing things with topology

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q471135)