“Finding hexahedrizations for small quadrangulations of the sphere” by Verhetsel, Pellerin and Remacle
Conference:
Type(s):
Title:
- Finding hexahedrizations for small quadrangulations of the sphere
Session/Category Title: Meshing
Presenter(s)/Author(s):
Abstract:
This paper tackles the challenging problem of constrained hexahedral meshing. An algorithm is introduced to build combinatorial hexahedral meshes whose boundary facets exactly match a given quadrangulation of the topological sphere. This algorithm is the first practical solution to the problem. It is able to compute small hexahedral meshes of quadrangulations for which the previously known best solutions could only be built by hand or contained thousands of hexahedra. These challenging quadrangulations include the boundaries of transition templates that are critical for the success of general hexahedral meshing algorithms.The algorithm proposed in this paper is dedicated to building combinatorial hexahedral meshes of small quadrangulations and ignores the geometrical problem. The key idea of the method is to exploit the equivalence between quad flips in the boundary and the insertion of hexahedra glued to this boundary. The tree of all sequences of flipping operations is explored, searching for a path that transforms the input quadrangulation Q into a new quadrangulation for which a hexahedral mesh is known. When a small hexahedral mesh exists, a sequence transforming Q into the boundary of a cube is found; otherwise, a set of pre-computed hexahedral meshes is used.A novel approach to deal with the large number of problem symmetries is proposed. Combined with an efficient backtracking search, it allows small shellable hexahedral meshes to be found for all even quadrangulations with up to 20 quadrangles. All 54, 943 such quadrangulations were meshed using no more than 72 hexahedra. This algorithm is also used to find a construction to fill arbitrary domains, thereby proving that any ball-shaped domain bounded by n quadrangles can be meshed with no more than 78 n hexahedra. This very significantly lowers the previous upper bound of 5396 n.
References:
1. Tristan Carrier Baudouin, Jean-Francois Remacle, Emilie Marchandise, Francois Henrotte, and Christophe Geuzaine. 2014. A frontal approach to hex-dominant mesh generation. Advanced Modeling and Simulation in Engineering Sciences 1, 1 (2014), 1. http://amses-journal.springeropen.com/articles/10.1186/2213-7467-1-8Google ScholarCross Ref
2. Marshall W. Bern, David Eppstein, and Jeff Erickson. 2002. Flipping Cubical Meshes. Eng. Comput. (Lond.) 18, 3 (2002), 173–187.Google ScholarCross Ref
3. Gunnar Brinkmann, Sam Greenberg, Catherine S. Greenhill, Brendan D. McKay, Robin Thomas, and Paul Wollan. 2005. Generation of simple quadrangulations of the sphere. Discrete Mathematics 305, 1–3 (2005), 33–54. Google ScholarDigital Library
4. Gunnar Brinkmann and Brendan D. McKay. 2007. Fast generation of planar graphs. MATCH Commun. Math. Comput. Chem 58, 2 (2007), 323–357.Google Scholar
5. Benjamin A. Burton. 2011. The pachner graph and the simplification of 3-sphere triangulations. In Proceedings of the 27th Symposium on Computational Geometry. 153–162. Google ScholarDigital Library
6. Carlos D. Carbonera and Jason F. Shepherd. 2010. A constructive approach to constrained hexahedral mesh generation. Eng. Comput. (Lond.) 26, 4 (2010), 341–350.Google ScholarDigital Library
7. Charles J. Colbourn and Kellogg S. Booth. 1981. Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM J. Comput. 10, 1 (1981), 203–225.Google ScholarDigital Library
8. David Eppstein. 1999a. Linear complexity hexahedral mesh generation. Computational Geometry 12, 1–2 (1999), 3–16. Google ScholarDigital Library
9. David Eppstein. 1999b. Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl. 3, 3 (1999). http://www.cs.brown.edu/publications/jgaa/accepted/99/Eppstein99.3.3.pdfGoogle ScholarCross Ref
10. Jeff Erickson. 2014. Efficiently hex-meshing things with topology. Discrete & Computational Geometry 52, 3 (2014), 427–449. Google ScholarDigital Library
11. Torsten Fahle, Stefan Schamberger, and Meinolf Sellmann. 2001. Symmetry Breaking. In Principles and Practice of Constraint Programming. 93–107. Google ScholarDigital Library
12. Xianzhong Fang, Weiwei Xu, Hujun Bao, and Jin Huang. 2016. All-hex meshing using closed-form induced polycube. ACM Trans. Graph. 35, 4 (2016), 124:1–124:9. Google ScholarDigital Library
13. Louis Funar. 1999. Cubulations mod bubble moves. Contemp. Math. 233 (1999), 29–44.Google ScholarCross Ref
14. Robert Furch. 1924. Zur grundlegung der kombinatorischen topologie. Abh. Math. Sem. Univ. Hamburg 3, 1 (1924), 69–88.Google ScholarCross Ref
15. Xifeng Gao, Wenzel Jakob, Marco Tarini, and Daniele Panozzo. 2017. Robust hex-dominant mesh generation using field-guided polyhedral agglomeration. ACM Trans. Graph. 36, 4 (2017), 114:1–114:13. Google ScholarDigital Library
16. Ian P. Gent, Karen E. Petrie, and Jean-François Puget. 2006. Symmetry in Constraint Programming. In Handbook of Constraint Programming. 329–376.Google Scholar
17. Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. 2018. Shellability is NP-Complete. In Proceedings of the 34th Symposium on Computational Geometry. 41:1–41:15.Google Scholar
18. James Gregson, Alla Sheffer, and Eugene Zhang. 2011. All-hex mesh generation via volumetric polycube deformation. Comput. Graph. Forum 30, 5 (2011), 1407–1416.Google ScholarCross Ref
19. Shuchu Han, Jiazhi Xia, and Ying He. 2011. Constructing hexahedral shell meshes via volumetric polycube maps. Computer-Aided Design 43, 10 (2011), 1222–1233. Google ScholarDigital Library
20. Yasushi Ito, Alan M. Shih, and Bharat K. Soni. 2009. Octree-based reasonable-quality hexahedral mesh generation using a new set of refinement templates. Internat. J. Numer. Methods Engrg. 77, 13 (2009), 1809–1833.Google ScholarCross Ref
21. Charles Jordan, Michael Joswig, and Lars Kastner. 2018. Parallel Enumeration of Triangulations. Electr. J. Comb. 25, 3 (2018), P3.6. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p6Google Scholar
22. N. Kowalski, F. Ledoux, and P. Frey. 2014. Block-structured Hexahedral Meshes for CAD Models Using 3D Frame Fields. Procedia Engineering 82 (2014), 59–71.Google ScholarCross Ref
23. Heng Liu, Paul Zhang, Edward Chien, Justin Solomon, and David Bommes. 2018. Singularity-constrained octahedral fields for hexahedral meshing. ACM Trans. Graph. 37, 4 (2018), 93:1–93:17. Google ScholarDigital Library
24. Marco Livesu, Alla Sheffer, Nicholas Vining, and Marco Tarini. 2015. Practical hex-mesh optimization via edge-cone rectification. ACM Trans. Graph. 34, 4 (2015), 141:1–141:11. Google ScholarDigital Library
25. Max Lyon, David Bommes, and Leif Kobbelt. 2016. HexEx: robust hexahedral mesh extraction. ACM Trans. Graph. 35, 4 (2016), 123:1–123:11. Google ScholarDigital Library
26. Loïc Maréchal. 2009. Advances in octree-based all-hexahedral mesh generation: Handling sharp features. In Proceedings of the 18th International Meshing Roundtable. 65–84.Google ScholarCross Ref
27. Scott A. Mitchell. 1996. A characterization of the quadrilateral meshes of a surface which admit a compatible hexahedral mesh of the enclosed volume. In Annual Symposium on Theoretical Aspects of Computer Science. Springer, 465–476. Google ScholarDigital Library
28. Scott A. Mitchell. 1999. The all-hex geode-template for conforming a diced tetrahedral mesh to any diced hexahedral mesh. Eng. Comput. (Lond.) 15, 3 (1999), 228–235.Google ScholarCross Ref
29. Scott A. Mitchell. 2002. A Technical History of Hexahedral Mesh Generation. https://www.sandia.gov/~samitch/_assets/documents/pptx/hex_mesh_history_samitch.ppt. Retrieved January 2, 2019.Google Scholar
30. Scott A. Mitchell and Timothy J. Tautges. 1994. Pillowing doublets: refining a mesh to ensure that faces share at most one edge. In Proceedings of the 4th International Meshing Roundtable. 231–240.Google Scholar
31. Matthias Müller-Hannemann. 1999. Hexahedral mesh generation by successive dual cycle elimination. Eng. Comput. (Lond.) 15, 3 (1999), 269–279.Google ScholarCross Ref
32. Peter Murdoch, Steven Benzley, Ted Blacker, and Scott A. Mitchell. 1997. The spatial twist continuum: a connectivity based method for representing all-hexahedral finite element meshes. Finite Elem. Anal. Des. 28, 2 (1997), 137–149. Google ScholarDigital Library
33. Matthias Nieser, Ulrich Reitebuch, and Konrad Polthier. 2011. CubeCover- parameterization of 3D volumes. Comput. Graph. Forum 30, 5 (2011), 1397–1406.Google ScholarCross Ref
34. Jeanne Pellerin, Amaury Johnen, Kilian Verhetsel, and Jean-François Remacle. 2018. Identifying combinations of tetrahedra into hexahedra: A vertex based strategy. Computer-Aided Design 105 (2018).Google Scholar
35. Jin Qian and Yongjie Zhang. 2010. Sharp feature preservation in octree-based hexahedral mesh generation for CAD assembly models. In Proceedings of the 19th International Meshing Roundtable. 243–262.Google ScholarCross Ref
36. Jean-Francois Remacle, Rajesh Gandham, and Tim Warburton. 2016. GPU accelerated spectral finite elements on all-hex meshes. J. Comput. Physics 324 (Nov. 2016), 246–257. Google ScholarDigital Library
37. Robert Schneiders. 1995. Open problem. http://www.robertschneiders.de/meshgeneration/open.html. Retrieved January 2, 2019.Google Scholar
38. Robert Schneiders. 1996. A grid-based algorithm for the generation of hexahedral element meshes. Eng. Comput. (Lond.) 12, 3–4 (Sep 1996), 168–177.Google Scholar
39. Jason F. Shepherd and Chris R. Johnson. 2008. Hexahedral mesh generation constraints. Eng. Comput. (Lond.) 24, 3 (Sept. 2008), 195–213. Google ScholarDigital Library
40. Hang Si. 2015. TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Trans. Math. Softw. 41, 2 (2015), 11:1–11:36. Google ScholarDigital Library
41. Dmitry Sokolov, Nicolas Ray, Lionel Untereiner, and Bruno Lévy. 2017. Hexahedral-dominant meshing. ACM Trans. Graph. 36, 4 (2017).Google ScholarCross Ref
42. Timothy J. Tautges, Ted Blacker, and Scott A. Mitchell. 1996. The whisker weaving algorithm: a connectivity-based method for constructing all-hexahedral finite element meshes. Internat. J. Numer. Methods Engrg. 39, 19 (1996), 3327–3349. <3327::AID-NME2>3.3.CO;2-8Google ScholarCross Ref
43. William P. Thurston. 1993. Hexahedral decomposition of polyhedra. Posting to sci.math. http://www.ics.uci.edu/~eppstein/gina/Thurston-hexahedra.htmlGoogle Scholar
44. Thomas Toulorge, Christophe Geuzaine, Jean-François Remacle, and Jonathan Lambrechts. 2013. Robust untangling of curvilinear meshes. J. Comput. Physics 254 (2013), 8–26. Google ScholarDigital Library
45. Kilian Verhetsel, Jeanne Pellerin, and Jean-François Remacle. 2018. A 44-element mesh of Schneiders’ pyramid: Bounding the difficulty of hex-meshing problems. In Proceedings of the 27th International Meshing Roundtable. Springer.Google Scholar
46. Jean-Christophe Weill and Franck Ledoux. 2016. Towards an automatic and reliable hexahedral meshing. http://tetrahedron.montefiore.ulg.ac.be/weill.pdf. Retrieved January 2, 2019.Google Scholar
47. Shang Xiang and Jianfei Liu. 2018. A 36-element solution to Schneiders’ pyramid hex-meshing problem and a parity-changing template for hex-mesh revision. arXiv preprint arXiv:1807.09415 (2018).Google Scholar
48. Soji Yamakawa and Kenji Shimada. 2002. HEXHOOP: modular templates for converting a hex-dominant mesh to an all-hex mesh. Eng. Comput. (Lond.) 18, 3 (2002), 211–228.Google ScholarCross Ref
49. Soji Yamakawa and Kenji Shimada. 2003. Fully-automated hex-dominant mesh generation with directionality control via packing rectangular solid cells. Internat. J. Numer. Methods Engrg. 57, 15 (2003), 2099–2129.Google ScholarCross Ref
50. Soji Yamakawa and Kenji Shimada. 2010. 88-element solution to Schneiders’ pyramid hex-meshing problem. International Journal for Numerical Methods in Biomedical Engineering 26, 12 (2010), 1700–1712.Google ScholarCross Ref
51. Wuyi Yu, Kang Zhang, Shenghua Wan, and Xin Li. 2014. Optimizing polycube domain construction for hexahedral remeshing. Computer-Aided Design 46 (2014), 58–68. Google ScholarDigital Library
52. Yongjie Zhang, Xinghua Liang, and Guoliang Xu. 2012. A robust 2-refinement algorithm in octree and rhombic dodecahedral tree based all-hexahedral mesh generation. In Proceedings of the 21st International Meshing Roundtable. 155–172.Google Scholar
53. Günter M. Ziegler. 1995. Lectures on polytopes. Graduate Texts in Mathematics, Vol. 152. Springer-Verlag, New York.Google Scholar
