# zbMATH — the first resource for mathematics

Efficiently hex-meshing things with topology. (English) Zbl 1311.57032
This paper provides a complete solution to the topological hex-meshing problem, generalizing the results for manifolds of genus zero and bipartite meshes of W. P. Thurston, “Hexahedral decomposition of polyhedra”, Posting to Sci. Math. (1993). {http://www.ics.uci.edu/ eppstein/gina/Thurston-hexahedra.html}], 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 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.

##### MSC:
 57Q05 General topology of complexes 65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) 57M99 General low-dimensional topology
##### Software:
ReebHanTun; MathOverflow
Full Text:
##### References:
  Aitchison, IR; Rubinstein, JH; Donaldson, SK (ed.); Thomas, CB (ed.), An introduction to polyhedral metrics of non-positive curvature on 3-manifolds, No. 151, 127-161, (1990), Cambridge · Zbl 0735.57005  Aitchison, IR; Matsumoto, S; Rubinstein, JH, Immersed surfaces in cubed manifolds, Asian J. Math., 1, 85-95, (1997) · Zbl 0935.57033  Babson, EK; Chan, CS, Counting faces of cubical spheres modulo two, Discret. Math., 212, 169-183, (2000) · Zbl 0947.52004  Banchoff, TF, Triple points and surgery of immersed surfaces, Proc. Am. Math. Soc., 46, 407-413, (1974) · Zbl 0309.57017  Berge, C.: Théorie des graphes et ses applications. Dunod, Paris (1958). English translation in   Berge, C.: The Theory of Graphs. Dover Publications, New York (2001). English translation of   Bern, M.: Compatible triangulations. In: Proceedings of the 9th Annual Symposium on Computational Geometry, pp. 281-288 (1993)  Bern, M., Eppstein, D.: Flipping cubical meshes. In: Proceedings of the 10th International Meshing Roundtable, pp. 19-29 (2001). http://www.andrew.cmu.edu/user/sowen/abstracts/Be812.html. Preliminary version of   Bern, M., Eppstein, D., Erickson, J.: Flipping cubical meshes. Eng. Comput. 18, 173-187 (2002). Full version of   Billera, LJ; Sturmfels, B, Fiber polytopes, Ann. Math., 135, 527-549, (1992) · Zbl 0762.52003  Bing, RH, Locally tame sets are tame, Ann. Math., 59, 145-158, (1954) · Zbl 0055.16802  Bing, RH, An alternative proof that 3-manifolds can be triangulated, Ann. Math., 69, 37-65, (1959) · Zbl 0106.16604  Boy, W.: Über die Abbildung der projektiven Ebene auf eine im Endlichen geschlossene singularitätenfreie Fläche. Nachr. Ges. Wiss. Göttingen, pp. 20-33 (1901) · JFM 32.0677.02  Bunch, JR; Hopcroft, JE, Triangular factorization and inversion by fast matrix multiplication, Math. Comput., 28, 231-236, (1974) · Zbl 0276.15006  Carbonera, C.D., Shepherd, J.F.: On the existence of a perfect matching for 4-regular graphs derived from quadrilateral meshes. Technical Report UUSCI-2006-021. SCI Institute, University of Utah (2006)  Carbonera, CD; Shepherd, JF, A constructive approach to constrained hexahedral mesh generation, Eng. Comput., 26, 341-350, (2010)  Carter, JS, Extending immersions of curves to properly immersed surfaces, Topol. Appl., 40, 287-306, (1991) · Zbl 0753.57019  Carter, JS, Extending immersed circles in the sphere to immersed disks in the ball, Commun. Math. Helv., 67, 337-348, (1992) · Zbl 0766.57018  Chazelle, B, Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM J. Comput., 13, 488-507, (1984) · Zbl 0545.68031  Chazelle, B; Palios, L, Triangulating a nonconvex polytope, Discrete Comput. Geom., 5, 505-526, (1990) · Zbl 0701.68038  Chazelle, B; Shouraboura, N, Bounds on the size of tetrahedralizations, Discrete Comput. Geom., 14, 429-444, (1995) · Zbl 0841.68119  Csikós, B; Szűcs, A, On the number of triple points of an immersed surface with boundary, Manuscr. Math., 87, 285-293, (1995) · Zbl 0856.57028  Dey, T.K., Fan, F., Wang, Y.: An efficient computation of handle and tunnel loops via Reeb graphs. ACM Trans. Graph. 32(4) (2013). Proceedings of SIGGRAPH 2013. · Zbl 1305.68226  Dey, T.K., Li, K., Sun, J.: On computing handle and tunnel loops. In: IEEE Proceedings of International Conference on Cyberworlds, pp. 357-366 (2007)  Dey, TK; Li, K; Sun, J; Cohen-Steiner, D, Computing geometry-aware handle and tunnel loops in 3D models, ACM Trans. Graph., 27, 1-9, (2008)  Edelsbrunner, H., Harer, J.L.: Computational Topology: An Introduction. American Mathematical Society, Providence, RI (2010) · Zbl 1193.55001  Eppstein, D, Linear-complexity hexahedral mesh generation, Comput. Geom. Theory Appl., 12, 3-16, (1999) · Zbl 0922.68120  Erickson, J.: Efficiently hex-meshing things with topology. In: Proceedings of the 29th Annual Symposium on Computational Geometry, pp. 37-46 (2013) · Zbl 1305.68230  Fedorov, E.S.: Načala učeniya o figurah (Elements of the study of figures). Not. Imp. Petersb. Mineralog. Soc. 24, 1-279 (1885) (in Russian). Cited in   Fedorov, ES, Elemente der gestaltenlehre, Z. Kryst. Mineral., 21, 679-694, (1893)  Folwell, NT; Mitchell, SA, Reliable whisker weaving via curve contraction, Eng. Comput., 15, 292-302, (1999) · Zbl 0958.65509  Francis, GK, Titus’ homotopies of normal curves, Proc. Am. Math. Soc., 30, 511-518, (1971) · Zbl 0223.57015  Funar, L, Cubulations, immersions, mappability and a problem of habegger, Ann. Sci. École Norm. Supér., 32, 681-700, (1999) · Zbl 0934.57027  Funar, L; Nencka, H (ed.), Cubulations mod bubble moves, No. 223, 29-43, (1999), Providence, RI · Zbl 0941.57023  Funar, L, Surface cubications mod flips, Manuscr. Math., 125, 285-307, (2008) · Zbl 1144.05022  Hass, J; Hughes, J, Immersions of surfaces in 3-manifolds, Topology, 24, 97-112, (1985) · Zbl 0527.57020  Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge, UK (2002). http://www.math.cornell.edu/ hatcher/AT/ATpage.html · Zbl 1044.55001  Ibarra, OH; Moran, S; Hui, R, A generalization of the fast LUP matrix decomposition algorithm and applications, J. Algorithms, 3, 45-56, (1982) · Zbl 0492.65024  Jockusch, W, The lower and upper bound problems for cubical polytopes, Discrete Comput. Geom., 9, 159-163, (1993) · Zbl 0771.52005  Kirby, R.: Problems in low-dimensional topology. In: Kazez, W.H. (ed.) Geometric Topology (Part 2), AMS/IP Studies in Advanced Mathematics, vol. 2, pp. 35-473. American Mathematical Society, Providence, RI (1997). http://math.berkeley.edu/ kirby/problems.ps.gz  Lackenby, M, The volume of hyperbolic alternating link complements, Proc. Lond. Math. Soc., 88, 204-224, (2004) · Zbl 1041.57002  Ledoux, F; Shepherd, JF, Topological modifications of hexahedral meshes via sheet operations: a theoretical study, Eng. Comput., 26, 433-447, (2010)  Micali, S., Vazirani, V.V.: An $$O(\sqrt{v}· |E|)$$ algorithm for finding maximum mathing in general graphs. In: Proceedings of the 21st Annual Symposium on Foundations of Computer Science, pp. 17-27 (1980)  Mitchell, S.A.: 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, pp. 456-476. Springer, Berlin (1996) · Zbl 1380.65043  Mitchell, S.A.: The all-hex Geode-template for conforming a diced tetrahedral mesh to any diced hexahedral mesh. In: Proceedings of the 7th International Meshing Roundtable, pp. 295-305 (1998) · Zbl 0944.65534  Moise, EE, Affine structures in 3-manifolds, V. the triangulation theorem and hauptvermutung, Ann. Math., 56, 96-114, (1952) · Zbl 0048.17102  Moise, EE, Affine structures in 3-manifolds, VIII. invariance of the knot-type; local tame embedding, Ann. Math., 59, 159-170, (1954) · Zbl 0055.16804  Müller-Hannemann, M, Hexahedral meshing by successive dual cycle elimination, Eng. Comput., 15, 269-279, (1999) · Zbl 0958.65507  Müller-Hannemann, M, Shelling hexahedral complexes for mesh generation, J. Graph Algorithms Appl., 5, 59-91, (2001) · Zbl 0985.68083  Müller-Hannemann, M, Quadrilateral surface meshes without self-intersecting dual cycles for hexahedral mesh generation, Comput. Geom. Theory Appl., 22, 75-97, (2002) · Zbl 1016.68140  Murdoch, P; Benzley, S; Blacker, T; Mitchell, SA, The spatial twist continuum: a connectivity based method for representing all-hexahedral finite element meshes, Finite Elem. Anal. Des., 28, 137-149, (1997) · Zbl 0914.73049  Nakamoto, A, Diagonal transformations and cycle parities of quadrangulations on surfaces, J. Comb. Theory Ser. B, 67, 202-211, (1996) · Zbl 0857.05024  Nakamoto, A, Diagonal transformations in quadrangulations of surfaces, J. Graph Theory, 21, 289-299, (1996) · Zbl 0854.05038  Nakamoto, A; Ota, K, Diagonal transformations in quadrangulations and Dehn twists preserving cycle parities, J. Comb. Theory Ser. B, 69, 125-141, (1997) · Zbl 0874.05021  Nowik, T, Complexity of planar and spherical curves, Duke J. Math., 148, 107-118, (2009) · Zbl 1163.57014  Papakyriakopoulos, CD, On dehn’s lemma and the asphericity of knots, Ann. Math., 66, 1-26, (1957) · Zbl 0078.16402  Petit, J.P.: Le topologicon, Les aventures d’Anselme Lanturlu, vol. 12. Belin, Paris (1985). http://www.savoir-sans-frontieres.com/JPP/telechargeables/Francais/topologicon.htm  Price, MA; Armstrong, CG, Hexahedral mesh generation by medial surface subdivision: part II. solids with flat and concave edges, Int. J. Numer. Methods Eng., 40, 111-136, (1997)  Purcell, JS, Volumes of highly twisted knots and links, Algebr. Geom. Topol., 7, 93-108, (2007) · Zbl 1135.57005  Reiner, V; Billera, LJ (ed.); Björner, A (ed.); Greene, C (ed.); Simion, RE (ed.); Stanley, RP (ed.), The generalized baues problem, No. 38, 293-336, (1999), Cambridge · Zbl 0956.52011  Schneiders, R.: Open problem (1995). http://www-users.informatik.rwth-aachen.de/ roberts/open.html. Accessed 1 Aug 2013  Schneiders, R, A grid-based algorithm for the generation of hexahedral element meshes, Eng. Comput., 12, 168-177, (1996)  Schwartz, A.: Constructions of cubical polytopes. Ph.D. dissertation, Technical University, Berlin (2003). http://edocs.tu-berlin.de/diss/2004/schwartz_alexander.html · Zbl 1235.52003  Schwartz, A; Ziegler, GM, Construction techniques for cubical complexes, odd cubical 4-polytopes, and prescribed dual manifolds, Exp. Math., 13, 385-413, (2004) · Zbl 1110.52015  Senechal, M; Galiulin, RV, An introduction to the theory of figures: the geometry of E. S. fedorov, Struct. Topol., 10, 5-22, (1984) · Zbl 0557.52010  Shepherd, JF; Johnson, CR, Hexahedral mesh generation constraints, Eng. Comput., 24, 195-213, (2008)  Suzuki, T; Takahashi, S; Shepherd, JF, An interior surface generation method for all-hexahedral meshing, Eng. Comput., 26, 303-316, (2010)  Thurston, W.P.: Hexahedral decomposition of polyhedra. Posting to Sci. Math. (1993). http://www.ics.uci.edu/ eppstein/gina/Thurston-hexahedra.html  Thurston, B., Thurston, D.: Complexity of random knot with vertices on sphere. MathOverflow (2011). http://mathoverflow.net/questions/54417  Vazirani, VV, A theory of alternating paths and blossoms for proving correctness of the $$O(\sqrt{V}E)$$ general graph maximum matching algorithm, Combinatorica, 14, 71-109, (1994) · Zbl 0806.05058  Vazirani, V.V.: A proof of the MV matching algorithm (2014). http://www.cc.gatech.edu/ vazirani/new-proof.pdf. Unpublished manuscript  Whitney, H, On regular closed curves in the plane, Compos. Math., 4, 276-284, (1937) · JFM 63.0647.01  Whitney, H, The singularities of a smooth $$n$$-manifold in $$(2n-1)$$-space, Ann. Math., 45, 247-293, (1944) · Zbl 0063.08238  Yamakawa, S; Shimada, K, HEXHOOP: modular templates for converting a hex-dominant mesh to an ALL-hex mesh, Eng. Comput., 18, 211-228, (2002)  Yamakawa, S; Shimada, K, 88-element solution to schneiders’ pyramid hex-meshing problem, Int. J. Numer. Methods. Biomed. Eng., 26, 1700-1712, (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.