“Volume parametrization quantization for hexahedral meshing” by Brückler, Bommes and Campen

Developments in the field of parametrization-based quad mesh generation on surfaces have been impactful over the past decade. In this context, an important advance has been the replacement of error-prone rounding in the generation of integer-grid maps, by robust quantization methods. In parallel, parametrization-based hex mesh generation for volumes has been advanced. In this volumetric context, however, the state-of-the-art still relies on fragile rounding, not rarely producing defective meshes, especially when targeting a coarse mesh resolution. We present a method to robustly quantize volume parametrizations, i.e., to determine guaranteed valid choices of integers for 3D integer-grid maps. Inspired by the 2D case, we base our construction on a non-conforming cell decomposition of the volume, a 3D analogue of a T-mesh. In particular, we leverage the motorcycle complex, a recent generalization of the motorcycle graph, for this purpose. Integer values are expressed in a differential manner on the edges of this complex, enabling the efficient formulation of the conditions required to strictly prevent forcing the map into degeneration. Applying our method in the context of hexahedral meshing, we demonstrate that hexahedral meshes can be generated with significantly improved flexibility.

1. Noam Aigerman and Yaron Lipman. 2013. Injective and bounded distortion mappings in 3D. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–14.Google ScholarDigital Library
2. Cecil G Armstrong, Harold J Fogg, Christopher M Tierney, and Trevor T Robinson. 2015. Common themes in multi-block structured quad/hex mesh generation. Procedia Engineering 124 (2015), 70–82.Google ScholarCross Ref
3. Steven E. Benzley, Ernest Perry, Karl Merkley, Brett Clark, and Greg Sjaardema. 1995. A comparison of all hexagonal and all tetrahedral finite element meshes for elastic and elasto-plastic analysis. In Proc. 4th International Meshing Roundtable. 179–191.Google Scholar
4. Ted Blacker. 2000. Meeting the challenge for automated conformal hexahedral meshing. In Proceedings of International Meshing Roundtable. 11–20.Google Scholar
5. T Blacker. 2001. Automated conformal hexahedral meshing constraints, challenges and opportunities. Engineering with Computers 17, 3 (2001), 201–210.Google ScholarCross Ref
6. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013. Integer-Grid Maps for Reliable Quad Meshing. ACM Trans. Graph. 32, 4 (2013).Google ScholarDigital Library
7. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3 (2009), 77:1–77:10.Google ScholarDigital Library
8. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2010. Practical mixed-integer optimization for geometry processing. In International Conference on Curves and Surfaces. Springer, 193–206.Google Scholar
9. X. Bourdin, X. Trosseille, P. Petit, and P. Beillas. 2007. Comparison of tetrahedral and hexahedral meshes for organ finite element modeling: an application to kidney impact. In Proc. 20th Int. Technical Conference on the Enhanced Safety of Vehicles.Google Scholar
10. Matteo Bracci, Marco Tarini, Nico Pietroni, Marco Livesu, and Paolo Cignoni. 2019. HexaLab. net: An online viewer for hexahedral meshes. Computer-Aided Design 110 (2019), 24–36.Google ScholarDigital Library
11. Hendrik Brückler, Ojaswi Gupta, Manish Mandad, and Marcel Campen. 2022. The 3D Motorcycle Complex for Structured Volume Decomposition. Computer Graphics Forum 41, 2 (2022). Google ScholarCross Ref
12. Marcel Campen, David Bommes, and Leif Kobbelt. 2015. Quantized global parametrization. ACM Trans. Graph. 34, 6 (2015).Google ScholarDigital Library
13. Marcel Campen, Hanxiao Shen, Jiaran Zhou, and Denis Zorin. 2019. Seamless Parametrization with Arbitrary Cones for Arbitrary Genus. ACM Trans. Graph. 39, 1 (2019).Google Scholar
14. Marcel Campen, Cláudio T Silva, and Denis Zorin. 2016. Bijective maps from simplicial foliations. ACM Trans. Graph. 35, 4 (2016), 1–15.Google ScholarDigital Library
15. Marcel Campen and Denis Zorin. 2017. Similarity maps and field-guided T-splines: a perfect couple. ACM Trans. Graph. 36, 4 (2017), 1–16.Google ScholarDigital Library
16. Gianmarco Cherchi, Pierre Alliez, Riccardo Scateni, Max Lyon, and David Bommes. 2019. Selective padding for polycube-based hexahedral meshing. In Computer graphics forum, Vol. 38. 580–591.Google Scholar
17. Gianmarco Cherchi, Marco Livesu, and Riccardo Scateni. 2016. Polycube simplification for coarse layouts of surfaces and volumes. In Computer Graphics Forum, Vol. 35. 11–20.Google ScholarCross Ref
18. A.O. Cifuentes and A. Kalbag. 1992. A performance study of tetrahedral and hexahedral elements in 3-D finite element structural analysis. Finite Elements in Analysis and Design 12, 3 (1992), 313 — 318.Google ScholarDigital Library
19. Etienne Corman and Keenan Crane. 2019. Symmetric Moving Frames. ACM Trans. Graph. 38, 4 (2019).Google ScholarDigital Library
20. Mattéo Couplet, Maxence Reberol, and Jean-François Remacle. 2021. Generation of High-Order Coarse Quad Meshes on CAD Models via Integer Linear Programming. In AIAA Aviation 2021 Forum. 2991.Google Scholar
21. David Eppstein and Jeff Erickson. 1999. Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions. Discrete & Computational Geometry 22, 4 (1999), 569–592.Google ScholarCross Ref
22. David Eppstein, Michael T Goodrich, Ethan Kim, and Rasmus Tamstorf. 2008. Motorcycle graphs: canonical quad mesh partitioning. Comp. Graph. Forum 27, 5 (2008).Google Scholar
23. Jeff Erickson and Kim Whittlesey. 2005. Greedy optimal homotopy and homology generators. In SODA, Vol. 5. 1038–1046.Google Scholar
24. Xianzhong Fang, Weiwei Xu, Hujun Bao, and Jin Huang. 2016. All-Hex Meshing Using Closed-Form Induced Polycube. ACM Trans. Graph. 35, 4 (2016).Google ScholarDigital Library
25. Xiao-Ming Fu, Chong-Yang Bai, and Yang Liu. 2016. Efficient Volumetric PolyCube-Map Construction. Computer Graphics Forum 35, 7 (2016).Google Scholar
26. Xiao-Ming Fu, Jian-Ping Su, Zheng-Yu Zhao, Qing Fang, Chunyang Ye, and Ligang Liu. 2021. Inversion-free geometric mapping construction: A survey. Computational Visual Media 7, 3 (2021), 289–318.Google ScholarCross Ref
27. Xifeng Gao, Zhigang Deng, and Guoning Chen. 2015a. Hexahedral mesh re-parameterization from aligned base-complex. ACM Trans. Graph. 34, 4 (2015).Google ScholarDigital Library
28. Xifeng Gao, Tobias Martin, Sai Deng, Elaine Cohen, Zhigang Deng, and Guoning Chen. 2015b. Structured volume decomposition via generalized sweeping. IEEE transactions on visualization and computer graphics 22, 7 (2015), 1899–1911.Google Scholar
29. Xifeng Gao, Daniele Panozzo, Wenping Wang, Zhigang Deng, and Guoning Chen. 2017. Robust Structure Simplification for Hex Re-Meshing. ACM Trans. Graph. 36, 6 (2017).Google ScholarDigital Library
30. Vladimir Garanzha, Igor Kaporin, Liudmila Kudryavtseva, François Protais, Nicolas Ray, and Dmitry Sokolov. 2021. Foldover-free maps in 50 lines of code. arXiv preprint arXiv:2102.03069 (2021).Google Scholar
31. James Gregson, Alla Sheffer, and Eugene Zhang. 2011. All-Hex Mesh Generation via Volumetric PolyCube Deformation. Computer Graphics Forum 30, 5 (2011).Google Scholar
32. Gurobi Optimization, LLC. 2022. Gurobi Optimizer. https://www.gurobi.comGoogle Scholar
33. Jin Huang, Tengfei Jiang, Zeyun Shi, Yiying Tong, Hujun Bao, and Mathieu Desbrun. 2014. ℓ1-based construction of polycube maps from complex shapes. ACM Transactions on Graphics (TOG) 33, 3 (2014), 1–11.Google ScholarDigital Library
34. Jin Huang, Tengfei Jiang, Yuanzhen Wang, Yiying Tong, and Hujun Bao. 2012. Automatic frame field guided hexahedral mesh generation. Technical Report. Tech. report, State Key Lab of CAD & CG, College of Computer Science at Zhejiang University.Google Scholar
35. Jin Huang, Yiying Tong, Hongyu Wei, and Hujun Bao. 2011. Boundary aligned smooth 3D cross-frame field. ACM Trans. Graph. 30, 6 (2011).Google ScholarDigital Library
36. Tengfei Jiang, Jin Huang, Yuanzhen Wang, Yiying Tong, and Hujun Bao. 2014. Frame field singularity correctionfor automatic hexahedralization. IEEE Transactions on Visualization and Computer Graphics 20, 8 (2014), 1189–1199.Google ScholarDigital Library
37. Felix Kälberer, Matthias Nieser, and Konrad Polthier. 2007. QuadCover – Surface Parameterization using Branched Coverings. Computer Graphics Forum 26, 3 (2007).Google Scholar
38. Junho Kim, Miao Jin, Qian-Yi Zhou, Feng Luo, and Xianfeng Gu. 2008. Computing fundamental group of general 3-manifold. In International Symposium on Visual Computing. Springer, 965–974.Google ScholarDigital Library
39. Patrick Michael Knupp, CD Ernst, David C Thompson, CJ Stimpson, and Philippe PierreGoogle Scholar
40. Pebay. 2006. The verdict geometric quality library. Technical Report. Sandia Nat. Lab.Google Scholar
41. Zohar Levi. 2021. Direct Seamless Parametrization. ACM Trans. Graph. 40, 1 (2021).Google ScholarDigital Library
42. Zohar Levi. 2022. Seamless Parametrization of Spheres with Controlled Singularities. Comp. Graph. Forum (2022).Google Scholar
43. Yufei Li, Yang Liu, Weiwei Xu, Wenping Wang, and Baining Guo. 2012. All-hex meshing using singularity-restricted field. ACM Transactions on Graphics 31, 6 (2012), 177.Google ScholarDigital Library
44. Yaron Lipman. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Transactions on Graphics (TOG) 31, 4 (2012), 1–13.Google ScholarDigital Library
45. 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).Google ScholarDigital Library
46. Marco Livesu, Marco Attene, Giuseppe Patané, and Michela Spagnuolo. 2017. Explicit cylindrical maps for general tubular shapes. Computer-Aided Design 90 (2017), 27–36.Google ScholarDigital Library
47. Marco Livesu, Nico Pietroni, Enrico Puppo, Alla Sheffer, and Paolo Cignoni. 2020. LoopyCuts: Practical Feature-Preserving Block Decomposition for Strongly HexDominant Meshing. ACM Trans. Graph. 39, 4 (2020).Google ScholarDigital Library
48. Marco Livesu, Alla Sheffer, Nicholas Vining, and Marco Tarini. 2015. Practical Hex-Mesh Optimization via Edge-Cone Rectification. ACM Trans. Graph. 34, 4 (2015).Google ScholarDigital Library
49. Marco Livesu, Nicholas Vining, Alla Sheffer, James Gregson, and Riccardo Scateni. 2013. Polycut: Monotone graph-cuts for polycube base-complex construction. ACM Transactions on Graphics (TOG) 32, 6 (2013), 1–12.Google ScholarDigital Library
50. Max Lyon, David Bommes, and Leif Kobbelt. 2016. HexEx: Robust Hexahedral Mesh Extraction. ACM Transactions on Graphics 35, 4 (2016).Google ScholarDigital Library
51. Max Lyon, Marcel Campen, David Bommes, and Leif Kobbelt. 2019. Parametrization Quantization with Free Boundaries for Trimmed Quad Meshing. ACM Trans. Graph. 38, 4 (2019).Google ScholarDigital Library
52. Max Lyon, Marcel Campen, and Leif Kobbelt. 2021a. Quad Layouts via Constrained T-Mesh Quantization. Computer Graphics Forum 40, 2 (2021).Google Scholar
53. Max Lyon, Marcel Campen, and Leif Kobbelt. 2021b. Simpler Quad Layouts using Relaxed Singularities. In Computer Graphics Forum, Vol. 40. 169–179.Google ScholarCross Ref
54. Martin Marinov, Marco Amagliani, Tristan Barback, Jean Flower, Stephen Barley, Suguru Furuta, Peter Charrot, Iain Henley, Nanda Santhanam, G. Thomas Finnigan, Siavash Meshkat, Justin Hallet, Maciej Sapun, and Pawel Wolski. 2019. Generative Design Conversion to Editable and Watertight Boundary Representation. Computer-Aided Design 115 (2019), 194 — 205.Google ScholarDigital Library
55. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust field-aligned global parametrization. ACM Trans. Graph. 33, 4 (2014).Google ScholarDigital Library
56. M. Nieser, U. Reitebuch, and K. Polthier. 2011. CubeCover – Parameterization of 3D Volumes. Computer Graphics Forum 30, 5 (2011), 1397–1406.Google ScholarCross Ref
57. David Palmer, David Bommes, and Justin Solomon. 2020. Algebraic Representations for Volumetric Frame Fields. ACM Trans. Graph. 39, 2 (2020).Google ScholarDigital Library
58. Nico Pietroni, Marcel Campen, Alla Sheffer, Gianmarco Cherchi, David Bommes, Xifeng Gao, Riccardo Scateni, Franck Ledoux, Jean-Francois Remacle, and Marco Livesu. 2022. Hex-Mesh Generation and Processing: a Survey. https://arxiv.org/abs/2202.12670Google Scholar
59. Luca Pitzalis, Marco Livesu, Gianmarco Cherchi, Enrico Gobbetti, and Riccardo Scateni. 2021. Generalized adaptive refinement for grid-based hexahedral meshing. ACM Transactions on Graphics (TOG) 40, 6 (2021), 1–13.Google ScholarDigital Library
60. François Protais, Maxence Reberol, Nicolas Ray, Etienne Corman, Franck Ledoux, and Dmitry Sokolov. 2020. Robust Quantization for Polycube Maps. (Dec. 2020). preprint.Google Scholar
61. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 4 (2017).Google ScholarDigital Library
62. A. Ramos and J.A. Simões. 2006. Tetrahedral versus hexahedral finite elements in numerical modelling of the proximal femur. Medical Engineering & Physics 28, 9 (2006), 916 — 924.Google ScholarCross Ref
63. Nicolas Ray, Dmitry Sokolov, and Bruno Lévy. 2016. Practical 3D frame field generation. ACM Trans. Graph. 35, 6 (2016), 1–9.Google ScholarDigital Library
64. Maxence Reberol, Alexandre Chemin, and Jean-Francois Remacle. 2019. Multiple Approaches to Frame Field Correction for CAD Models. In Proc. 28th International Meshing Roundtable.Google Scholar
65. Josep Sarrate Ramos, Eloi Ruiz-Gironés, and Francisco Javier Roca Navarro. 2014. Unstructured and semi-structured hexahedral mesh generation methods. Computational Technology Reviews 10 (2014), 35–64.Google ScholarCross Ref
66. Teseo Schneider, Yixin Hu, Xifeng Gao, Jeremie Dumas, Denis Zorin, and Daniele Panozzo. 2019. A Large Scale Comparison of Tetrahedral and Hexahedral Elements for Finite Element Analysis. arXiv:1903.09332 (2019).Google Scholar
67. Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally injective mappings. Computer Graphics Forum 32, 5 (2013).Google Scholar
68. Feifei Shang, Yangke Gan, and Yufei Guo. 2017. Hexahedral mesh generation via constrained quadrilateralization. PloS one 12, 5 (2017).Google Scholar
69. Jason F Shepherd. 1999. Interval matching and control for hexahedral mesh generation of swept volumes. Master’s thesis. Brigham Young University-Provo.Google Scholar
70. J. F. Shepherd and C. R. Johnson. 2008. Hexahedral mesh generation constraints. Engineering with Computers 24, 3 (2008), 195–213.Google ScholarDigital Library
71. Justin Solomon, Amir Vaxman, and David Bommes. 2017. Boundary element octahedral fields in volumes. ACM Trans. Graph. 36, 4 (2017), 1.Google ScholarDigital Library
72. Srinivas C. Tadepalli, Ahmet Erdemir, and Peter R. Cavanagh. 2011. Comparison of hexahedral and tetrahedral elements in finite element analysis of the foot and footwear. Journal of Biomechanics 44, 12 (2011), 2337 — 2343.Google ScholarCross Ref
73. Kenshi Takayama. 2019. Dual Sheet Meshing: An Interactive Approach to Robust Hexahedralization. Computer Graphics Forum 38, 2 (2019), 37–48.Google ScholarCross Ref
74. Timothy J Tautges. 2001. The generation of hexahedral meshes for assembly geometry: survey and progress. Internat. J. Numer. Methods Engrg. 50, 12 (2001), 2617–2642.Google ScholarCross Ref
75. Y. Tong, P. Alliez, D. Cohen-Steiner, and M. Desbrun. 2006. Designing Quadrangulations with Discrete Harmonic Forms. In Proceedings of the Fourth Eurographics Symposium on Geometry Processing (SGP ’06). Eurographics Association, 201–210.Google Scholar
76. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional Field Synthesis, Design, and Processing. Computer Graphics Forum 35, 2 (2016).Google Scholar
77. Ryan Viertel, Matthew L Staten, and Franck Ledoux. 2016. Analysis of Non-Meshable Automatically Generated Frame Fields. Technical Report. Sandia National Lab.(SNL-NM), Albuquerque, NM (United States).Google Scholar
78. Erke Wang, Thomas Nelson, and Rainer Rauch. 2004. Back to elements-tetrahedra vs. hexahedra. In Proceedings of the 2004 international ANSYS conference.Google Scholar
79. Wei Wang, Yong Cao, and Tsubasa Okaze. 2021. Comparison of hexahedral, tetrahedral and polyhedral cells for reproducing the wind field around an isolated building by LES. Building and Environment 195 (2021), 107717.Google ScholarCross Ref
80. Ofir Weber and Denis Zorin. 2014. Locally injective parametrization with arbitrary fixed boundaries. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1–12.Google ScholarDigital Library
81. Haiyan Wu, Shuming Gao, Rui Wang, and Jinming Chen. 2018. Fuzzy clustering based pseudo-swept volume decomposition for hexahedral meshing. Computer-Aided Design 96 (2018), 42–58.Google ScholarCross Ref
82. Haiyan Wu, Shuming Gao, Rui Wang, and Mao Ding. 2017. A global approach to multi-axis swept mesh generation. Procedia Engineering 203 (2017), 414 — 426.Google ScholarCross Ref
83. Paul Zhang, Josh Vekhter, Edward Chien, David Bommes, Etienne Vouga, and Justin Solomon. 2020. Octahedral Frames for Feature-Aligned Cross Fields. ACM Trans. Graph. 39, 3 (2020).Google ScholarDigital Library
84. Jiaran Zhou, Changhe Tu, Denis Zorin, and Marcel Campen. 2020. Combinatorial construction of seamless parameter domains. Computer Graphics Forum 39, 2 (2020), 179–190.Google ScholarCross Ref