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

  • ©Hendrik Brückler, David Bommes, and Marcel Campen




    Volume parametrization quantization for hexahedral meshing



    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

ACM Digital Library Publication: