User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Finding hexahedrizations for small quadrangulations of the sphere

Primary tabs

download
  • Open access
  • PDF
  • 4.04 M
Verhetsel, Kilian [UCL] Pellerin, Jeanne [UCL] Remacle, Jean-François [UCL]

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.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès libre
Publication date 2019
Language Anglais
Journal information "ACM Transactions on Graphics" - Vol. 38, no.4, p. 53(1-13) (2019)
Peer reviewed yes
Publisher Association for Computing Machinery (ACM)
issn 0730-0301
Publication status Publié
Affiliation UCL - SST/IMMC/MEMA - Applied mechanics and mathematics
Keywords hex-meshing ; shelling ; symmetry
Links
  1. Erickson Jeff, Efficiently Hex-Meshing Things with Topology, 10.1007/s00454-014-9624-3
  2. Erickson Jeff, Efficiently Hex-Meshing Things with Topology, 10.1007/s00454-014-9624-3
  3. Ziegler Günter M., Lectures on Polytopes, ISBN:9780387943657, 10.1007/978-1-4613-8431-1
  4. Zhang Yongjie, Liang Xinghua, Xu Guoliang, A Robust 2-Refinement Algorithm in Octree and Rhombic Dodecahedral Tree Based All-Hexahedral Mesh Generation, Proceedings of the 21st International Meshing Roundtable (2013) ISBN:9783642335723 p.155-172, 10.1007/978-3-642-33573-0_10
  5. Wuyi Yu, Kang Zhang, Shenghua Wan, and Xin Li. 2014. Optimizing polycube domain construction for hexahedral remeshing. Computer-Aided Design 46 (2014), 58--68.
  6. 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.
  7. Yamakawa Soji, Shimada Kenji, Fully-automated hex-dominant mesh generation with directionality control via packing rectangular solid cells, 10.1002/nme.754
  8. 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.
  9. 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).
  10. 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.
  11. Verhetsel Kilian, Pellerin Jeanne, Remacle Jean-François, A 44-Element Mesh of Schneiders’ Pyramid, Lecture Notes in Computational Science and Engineering (2019) ISBN:9783030139919 p.73-87, 10.1007/978-3-030-13992-6_5
  12. Thomas Toulorge, Christophe Geuzaine, Jean-François Remacle, and Jonathan Lambrechts. 2013. Robust untangling of curvilinear meshes. J. Comput. Physics 254 (2013), 8--26.
  13. William P. Thurston. 1993. Hexahedral decomposition of polyhedra. Posting to sci.math. http://www.ics.uci.edu/~eppstein/gina/Thurston-hexahedra.html
  14. 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-8
  15. Dmitry Sokolov, Nicolas Ray, Lionel Untereiner, and Bruno Lévy. 2017. Hexahedral-dominant meshing. ACM Trans. Graph. 36, 4 (2017).
  16. Hang Si. 2015. TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Trans. Math. Softw. 41, 2 (2015), 11:1--11:36.
  17. Jason F. Shepherd and Chris R. Johnson. 2008. Hexahedral mesh generation constraints. Eng. Comput. (Lond.) 24, 3 (Sept. 2008), 195--213.
  18. Robert Schneiders. 1996. A grid-based algorithm for the generation of hexahedral element meshes. Eng. Comput. (Lond.) 12, 3--4 (Sep 1996), 168--177.
  19. Robert Schneiders. 1995. Open problem. http://www.robertschneiders.de/meshgeneration/open.html. Retrieved January 2, 2019.
  20. 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.
  21. Qian Jin, Zhang Yongjie, Sharp Feature Preservation in Octree-Based Hexahedral Mesh Generation for CAD Assembly Models, Proceedings of the 19th International Meshing Roundtable (2010) ISBN:9783642154133 p.243-262, 10.1007/978-3-642-15414-0_15
  22. Pellerin Jeanne, Johnen Amaury, Verhetsel Kilian, Remacle Jean-François, Identifying combinations of tetrahedra into hexahedra: A vertex based strategy, 10.1016/j.cad.2018.05.004
  23. Matthias Nieser, Ulrich Reitebuch, and Konrad Polthier. 2011. CubeCover- parameterization of 3D volumes. Comput. Graph. Forum 30, 5 (2011), 1397--1406.
  24. 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.
  25. Matthias Müller-Hannemann. 1999. Hexahedral mesh generation by successive dual cycle elimination. Eng. Comput. (Lond.) 15, 3 (1999), 269--279.
  26. 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.
  27. 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.
  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.
  29. 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.
  30. Maréchal Loïc, Advances in Octree-Based All-Hexahedral Mesh Generation: Handling Sharp Features, Proceedings of the 18th International Meshing Roundtable (2009) ISBN:9783642043185 p.65-84, 10.1007/978-3-642-04319-2_5
  31. Max Lyon, David Bommes, and Leif Kobbelt. 2016. HexEx: robust hexahedral mesh extraction. ACM Trans. Graph. 35, 4 (2016), 123:1--123:11.
  32. 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.
  33. 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.
  34. 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.
  35. 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/v25i3p6
  36. 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. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/nme.2470
  37. Shuchu Han, Jiazhi Xia, and Ying He. 2011. Constructing hexahedral shell meshes via volumetric polycube maps. Computer-Aided Design 43, 10 (2011), 1222--1233.
  38. Gregson James, Sheffer Alla, Zhang Eugene, All-Hex Mesh Generation via Volumetric PolyCube Deformation, 10.1111/j.1467-8659.2011.02015.x
  39. 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.
  40. Gent Ian P., Petrie Karen E., Puget Jean-François, Symmetry in Constraint Programming, Handbook of Constraint Programming (2006) ISBN:9780444527264 p.329-376, 10.1016/s1574-6526(06)80014-3
  41. 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.
  42. Robert Furch. 1924. Zur grundlegung der kombinatorischen topologie. Abh. Math. Sem. Univ. Hamburg 3, 1 (1924), 69--88.
  43. Louis Funar. 1999. Cubulations mod bubble moves. Contemp. Math. 233 (1999), 29--44.
  44. 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.
  45. Fahle Torsten, Schamberger Stefan, Sellmann Meinolf, Symmetry Breaking, Principles and Practice of Constraint Programming — CP 2001 (2001) ISBN:9783540428633 p.93-107, 10.1007/3-540-45578-7_7
  46. Eppstein David, Subgraph Isomorphism in Planar Graphs and Related Problems, 10.7155/jgaa.00014
  47. David Eppstein. 1999a. Linear complexity hexahedral mesh generation. Computational Geometry 12, 1--2 (1999), 3--16.
  48. 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.
  49. Carlos D. Carbonera and Jason F. Shepherd. 2010. A constructive approach to constrained hexahedral mesh generation. Eng. Comput. (Lond.) 26, 4 (2010), 341--350.
  50. Burton Benjamin A., The pachner graph and the simplification of 3-sphere triangulations, 10.1145/1998196.1998220
  51. Gunnar Brinkmann and Brendan D. McKay. 2007. Fast generation of planar graphs. MATCH Commun. Math. Comput. Chem 58, 2 (2007), 323--357.
  52. 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.
  53. Marshall W. Bern, David Eppstein, and Jeff Erickson. 2002. Flipping Cubical Meshes. Eng. Comput. (Lond.) 18, 3 (2002), 173--187.
  54. 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-8
Bibliographic reference Verhetsel, Kilian ; Pellerin, Jeanne ; Remacle, Jean-François. Finding hexahedrizations for small quadrangulations of the sphere. In: ACM Transactions on Graphics, Vol. 38, no.4, p. 53(1-13) (2019)
Permanent URL http://hdl.handle.net/2078.1/218159