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.
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.
Reviewer: Barbara Di Fabio (Bologna)
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 |
Citations:
Zbl 0922.68120References:
| [1] | 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 |
| [2] | Aitchison, I.R., Matsumoto, S., Rubinstein, J.H.: Immersed surfaces in cubed manifolds. Asian J. Math. 1(1), 85-95 (1997) · Zbl 0935.57033 |
| [3] | Babson, E.K., Chan, C.S.: Counting faces of cubical spheres modulo two. Discret. Math. 212(3), 169-183 (2000) · Zbl 0947.52004 · doi:10.1016/S0012-365X(99)00285-X |
| [4] | Banchoff, T.F.: Triple points and surgery of immersed surfaces. Proc. Am. Math. Soc. 46(3), 407-413 (1974) · Zbl 0309.57017 · doi:10.1090/S0002-9939-1974-0377897-1 |
| [5] | Berge, C.: Théorie des graphes et ses applications. Dunod, Paris (1958). English translation in [6] · Zbl 0214.50804 |
| [6] | Berge, C.: The Theory of Graphs. Dover Publications, New York (2001). English translation of [5] · Zbl 0993.05001 |
| [7] | Bern, M.: Compatible triangulations. In: Proceedings of the 9th Annual Symposium on Computational Geometry, pp. 281-288 (1993) |
| [8] | 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 [9] |
| [9] | Bern, M., Eppstein, D., Erickson, J.: Flipping cubical meshes. Eng. Comput. 18, 173-187 (2002). Full version of [8] |
| [10] | Billera, L.J., Sturmfels, B.: Fiber polytopes. Ann. Math. 135(3), 527-549 (1992) · Zbl 0762.52003 · doi:10.2307/2946575 |
| [11] | Bing, R.H.: Locally tame sets are tame. Ann. Math. 59, 145-158 (1954) · Zbl 0055.16802 · doi:10.2307/1969836 |
| [12] | Bing, R.H.: An alternative proof that 3-manifolds can be triangulated. Ann. Math. 69, 37-65 (1959) · Zbl 0106.16604 · doi:10.2307/1970092 |
| [13] | 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 |
| [14] | Bunch, J.R., Hopcroft, J.E.: Triangular factorization and inversion by fast matrix multiplication. Math. Comput. 28(125), 231-236 (1974) · Zbl 0276.15006 · doi:10.1090/S0025-5718-1974-0331751-8 |
| [15] | 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) |
| [16] | Carbonera, C.D., Shepherd, J.F.: A constructive approach to constrained hexahedral mesh generation. Eng. Comput. 26(4), 341-350 (2010) · doi:10.1007/s00366-009-0168-8 |
| [17] | Carter, J.S.: Extending immersions of curves to properly immersed surfaces. Topol. Appl. 40(3), 287-306 (1991) · Zbl 0753.57019 · doi:10.1016/0166-8641(91)90111-X |
| [18] | Carter, J.S.: Extending immersed circles in the sphere to immersed disks in the ball. Commun. Math. Helv. 67, 337-348 (1992) · Zbl 0766.57018 · doi:10.1007/BF02566506 |
| [19] | Chazelle, B.: Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm. SIAM J. Comput. 13(3), 488-507 (1984) · Zbl 0545.68031 · doi:10.1137/0213031 |
| [20] | Chazelle, B., Palios, L.: Triangulating a nonconvex polytope. Discrete Comput. Geom. 5, 505-526 (1990) · Zbl 0701.68038 · doi:10.1007/BF02187807 |
| [21] | Chazelle, B., Shouraboura, N.: Bounds on the size of tetrahedralizations. Discrete Comput. Geom. 14, 429-444 (1995) · Zbl 0841.68119 · doi:10.1007/BF02570716 |
| [22] | 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 · doi:10.1007/BF02570475 |
| [23] | 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 |
| [24] | 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) |
| [25] | Dey, T.K., Li, K., Sun, J., Cohen-Steiner, D.: Computing geometry-aware handle and tunnel loops in 3D models. ACM Trans. Graph. 27(3), 1-9 (2008). Proceedings of SIGGRAPH 2008 · doi:10.1145/1360612.1360644 |
| [26] | Edelsbrunner, H., Harer, J.L.: Computational Topology: An Introduction. American Mathematical Society, Providence, RI (2010) · Zbl 1193.55001 |
| [27] | Eppstein, D.: Linear-complexity hexahedral mesh generation. Comput. Geom. Theory Appl. 12, 3-16 (1999) · Zbl 0922.68120 · doi:10.1016/S0925-7721(98)00032-7 |
| [28] | 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 |
| [29] | 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 [65] |
| [30] | Fedorov, E.S.: Elemente der gestaltenlehre. Z. Kryst. Mineral. 21, 679-694 (1893) |
| [31] | Folwell, N.T., Mitchell, S.A.: Reliable whisker weaving via curve contraction. Eng. Comput. 15(3), 292-302 (1999) · Zbl 0958.65509 · doi:10.1007/s003660050024 |
| [32] | Francis, G.K.: Titus’ homotopies of normal curves. Proc. Am. Math. Soc. 30, 511-518 (1971) · Zbl 0223.57015 |
| [33] | Funar, L.: Cubulations, immersions, mappability and a problem of Habegger. Ann. Sci. École Norm. Supér. 32(5), 681-700 (1999) · Zbl 0934.57027 |
| [34] | Funar, L.; Nencka, H. (ed.), Cubulations mod bubble moves, No. 223, 29-43 (1999), Providence, RI · Zbl 0941.57023 · doi:10.1090/conm/233/03424 |
| [35] | Funar, L.: Surface cubications mod flips. Manuscr. Math. 125, 285-307 (2008) · Zbl 1144.05022 · doi:10.1007/s00229-007-0149-4 |
| [36] | Hass, J., Hughes, J.: Immersions of surfaces in 3-manifolds. Topology 24(1), 97-112 (1985) · Zbl 0527.57020 · doi:10.1016/0040-9383(85)90048-5 |
| [37] | Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge, UK (2002). http://www.math.cornell.edu/ hatcher/AT/ATpage.html · Zbl 1044.55001 |
| [38] | Ibarra, O.H., Moran, S., Hui, R.: A generalization of the fast LUP matrix decomposition algorithm and applications. J. Algorithms 3(1), 45-56 (1982) · Zbl 0492.65024 · doi:10.1016/0196-6774(82)90007-4 |
| [39] | Jockusch, W.: The lower and upper bound problems for cubical polytopes. Discrete Comput. Geom. 9, 159-163 (1993) · Zbl 0771.52005 · doi:10.1007/BF02189315 |
| [40] | 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 |
| [41] | Lackenby, M.: The volume of hyperbolic alternating link complements. Proc. Lond. Math. Soc. 88, 204-224 (2004) · Zbl 1041.57002 · doi:10.1112/S0024611503014291 |
| [42] | Ledoux, F., Shepherd, J.F.: Topological modifications of hexahedral meshes via sheet operations: a theoretical study. Eng. Comput. 26(4), 433-447 (2010) · doi:10.1007/s00366-009-0145-2 |
| [43] | Micali, S., Vazirani, V.V.: An \[O(\sqrt{v}\cdot |E|)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) |
| [44] | 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 |
| [45] | 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 |
| [46] | Moise, E.E.: Affine structures in 3-manifolds, V. The triangulation theorem and Hauptvermutung. Ann. Math. 56, 96-114 (1952) · Zbl 0048.17102 · doi:10.2307/1969769 |
| [47] | Moise, E.E.: Affine structures in 3-manifolds, VIII. Invariance of the knot-type; local tame embedding. Ann. Math. 59, 159-170 (1954) · Zbl 0055.16804 · doi:10.2307/1969837 |
| [48] | Müller-Hannemann, M.: Hexahedral meshing by successive dual cycle elimination. Eng. Comput. 15(3), 269-279 (1999) · Zbl 0958.65507 · doi:10.1007/s003660050022 |
| [49] | Müller-Hannemann, M.: Shelling hexahedral complexes for mesh generation. J. Graph Algorithms Appl. 5(5), 59-91 (2001) · Zbl 0985.68083 · doi:10.7155/jgaa.00040 |
| [50] | 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 · doi:10.1016/S0925-7721(01)00053-0 |
| [51] | Murdoch, P., Benzley, S., Blacker, T., Mitchell, S.A.: 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 · doi:10.1016/S0168-874X(97)81956-7 |
| [52] | Nakamoto, A.: Diagonal transformations and cycle parities of quadrangulations on surfaces. J. Comb. Theory Ser. B 67, 202-211 (1996) · Zbl 0857.05024 · doi:10.1006/jctb.1996.0041 |
| [53] | Nakamoto, A.: Diagonal transformations in quadrangulations of surfaces. J. Graph Theory 21, 289-299 (1996) · Zbl 0854.05038 · doi:10.1002/(SICI)1097-0118(199603)21:3<289::AID-JGT3>3.0.CO;2-M |
| [54] | 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 · doi:10.1006/jctb.1997.1730 |
| [55] | Nowik, T.: Complexity of planar and spherical curves. Duke J. Math. 148(1), 107-118 (2009) · Zbl 1163.57014 · doi:10.1215/00127094-2009-022 |
| [56] | Papakyriakopoulos, C.D.: On Dehn’s lemma and the asphericity of knots. Ann. Math. 66, 1-26 (1957) · Zbl 0078.16402 · doi:10.2307/1970113 |
| [57] | 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 |
| [58] | Price, M.A., Armstrong, C.G.: Hexahedral mesh generation by medial surface subdivision: Part II. Solids with flat and concave edges. Int. J. Numer. Methods Eng. 40(1), 111-136 (1997) · doi:10.1002/(SICI)1097-0207(19970115)40:1<111::AID-NME56>3.0.CO;2-K |
| [59] | Purcell, J.S.: Volumes of highly twisted knots and links. Algebr. Geom. Topol. 7, 93-108 (2007) · Zbl 1135.57005 · doi:10.2140/agt.2007.7.93 |
| [60] | 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 |
| [61] | Schneiders, R.: Open problem (1995). http://www-users.informatik.rwth-aachen.de/ roberts/open.html. Accessed 1 Aug 2013 |
| [62] | Schneiders, R.: A grid-based algorithm for the generation of hexahedral element meshes. Eng. Comput. 12, 168-177 (1996) · doi:10.1007/BF01198732 |
| [63] | 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 |
| [64] | Schwartz, A., Ziegler, G.M.: Construction techniques for cubical complexes, odd cubical 4-polytopes, and prescribed dual manifolds. Exp. Math. 13(4), 385-413 (2004) · Zbl 1110.52015 · doi:10.1080/10586458.2004.10504548 |
| [65] | Senechal, M., Galiulin, R.V.: An introduction to the theory of figures: the geometry of E. S. Fedorov. Struct. Topol. 10, 5-22 (1984) · Zbl 0557.52010 |
| [66] | Shepherd, J.F., Johnson, C.R.: Hexahedral mesh generation constraints. Eng. Comput. 24(3), 195-213 (2008) · doi:10.1007/s00366-008-0091-4 |
| [67] | Suzuki, T., Takahashi, S., Shepherd, J.F.: An interior surface generation method for all-hexahedral meshing. Eng. Comput. 26(3), 303-316 (2010) · doi:10.1007/s00366-009-0159-9 |
| [68] | Thurston, W.P.: Hexahedral decomposition of polyhedra. Posting to Sci. Math. (1993). http://www.ics.uci.edu/ eppstein/gina/Thurston-hexahedra.html |
| [69] | Thurston, B., Thurston, D.: Complexity of random knot with vertices on sphere. MathOverflow (2011). http://mathoverflow.net/questions/54417 |
| [70] | Vazirani, V.V.: A theory of alternating paths and blossoms for proving correctness of the \[O(\sqrt{V}E)O\](\sqrt{V}E) general graph maximum matching algorithm. Combinatorica 14(1), 71-109 (1994) · Zbl 0806.05058 · doi:10.1007/BF01305952 |
| [71] | Vazirani, V.V.: A proof of the MV matching algorithm (2014). http://www.cc.gatech.edu/ vazirani/new-proof.pdf. Unpublished manuscript |
| [72] | Whitney, H.: On regular closed curves in the plane. Compos. Math. 4, 276-284 (1937) · JFM 63.0647.01 |
| [73] | Whitney, H.: The singularities of a smooth n-manifold in \[(2n-1)\](2n-1)-space. Ann. Math. 45(2), 247-293 (1944) · Zbl 0063.08238 · doi:10.2307/1969266 |
| [74] | Yamakawa, S., Shimada, K.: HEXHOOP: modular templates for converting a hex-dominant mesh to an ALL-hex mesh. Eng. Comput. 18, 211-228 (2002) · doi:10.1007/s003660200019 |
| [75] | 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
