“Cut-enhanced PolyCube-maps for feature-aware all-hex meshing” by Guo, Liu, Yan and Liu

  • ©Hao-Xiang Guo, Xiaohan Liu, Dong-Ming Yan, and Yang Liu




    Cut-enhanced PolyCube-maps for feature-aware all-hex meshing

Session/Category Title: Making Delaunay and Voronoi Proud



    Volumetric PolyCube-Map-based methods offer automatic ways to construct all-hexahedral meshes for closed 3D polyhedral domains, but their meshing quality is limited by the lack of interior singularities and feature alignment. In the presented work, we propose cut-enhanced PolyCube-Maps, to introduce essential interior singularities and preserve most input features. Our main idea is simple and intuitive: by inserting proper parameterization seams into the initial PolyCube-Map via novel PolyCube cutting operations, the mapping distortion can be reduced significantly.The cut-enhanced PolyCube-Map computation includes feature-aware PolyCube-Map construction and cut-enhanced PolyCube deformation. The former aims to preserve input feature edges during the initial PolyCube-Map construction. The latter introduces seams into the volumetric PolyCube shape by cutting it through selective PolyCube edges and deforms the modified PolyCube under the seamless constraints to compute a low-distortion PolyCube-Map. The hexahedral mesh induced by the final PolyCube-Map can be further enhanced by our mesh improvement algorithm.We validate the efficacy of our method on a collection of more than one hundred CAD models and demonstrate its advantages over other automatic all-hex meshing methods and padding strategies. The limitations of cut-enhanced PolyCube-Maps are also discussed thoroughly.


    1. MOSEK ApS. 2015. The MOSEK optimization toolbox.Google Scholar
    2. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Cláudio T. Silva, Marco Tarini, and Denis Zorin. 2013. Quad-mesh generation and processing: A survey. Comput. Graph. Forum 32, 6 (2013), 51–76.Google ScholarDigital Library
    3. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. (SIGGRAPH) 28 (2009), 77:1–77:10.Google ScholarDigital Library
    4. 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 ScholarCross Ref
    5. Michael Brewer, Lori Freitag Diachin, Patrick Knupp, Thomas Leurent, and Darryl Melander. 2003. The mesquite mesh quality improvement toolkit. In Int. Meshing Roundtable. 239–250.Google Scholar
    6. G. Cherchi, P. Alliez, R. Scateni, M. Lyon, and D. Bommes. 2019. Selective padding for PolyCube-based hexahedral meshing. Comput. Graph. Forum 38, 1 (2019), 580–591.Google ScholarCross Ref
    7. Etienne Corman and Keenan Crane. 2019. Symmetric moving frames. ACM Trans. Graph. (SIGGRAPH) 38, 4 (2019), 87:1–87:16.Google ScholarDigital Library
    8. David Eppstein and Elena Mumford. 2010. Steinitz Theorems for orthogonal polyhedra. In Symp. on Comp. Geom. 429–438.Google ScholarDigital Library
    9. J.M. Escobar, E. Rodríguez, R. Montenegro, G. Montero, and J.M. González-Yuste. 2003. Simultaneous untangling and smoothing of tetrahedral meshes. Comput. Methods Appl. Mech. Engrg. 192 (2003), 2775–2787.Google ScholarCross Ref
    10. Xianzhong Fang, Weiwei Xu, Hujun Bao, and Jin Huang. 2016. All-hex meshing using closed-form induced Polycube. ACM Trans. Graph. (SIGGRAPH) 35, 4 (2016), 124:1–124:9.Google ScholarDigital Library
    11. Xiao-Ming Fu, Chong-Yang Bai, and Yang Liu. 2016. Efficient volumetric PolyCube-map construction. Comput. Graph. Forum 35, 7 (2016), 97–106.Google ScholarDigital Library
    12. Xifeng Gao, Zhigang Deng, and Guoning Chen. 2015. Hexahedral mesh re-parameterization from aligned base-complex. ACM Trans. Graph. (SIGGRAPH) 34, 4 (2015), 142:1–142:10.Google ScholarDigital Library
    13. Xifeng Gao, Hanxiao Shen, and Daniele Panozzo. 2019. Feature preserving octree-based hexahedral meshing. Comput. Graph. Forum (SGP) 38, 5 (2019), 135–149.Google ScholarCross Ref
    14. James Gregson, Alla Sheffer, and Eugene Zhang. 2011. All-Hex mesh generation via volumetric PolyCube deformation. Comput. Graph. Forum (SGP) 30 (2011), 1407–1416.Google ScholarCross Ref
    15. Xianfeng Gu, Steven J. Gortler, and Hugues Hoppe. 2002. Geometry images. In SIGGRAPH. 355–361.Google Scholar
    16. Shuchu Han, Jiazhi Xia, and Ying He. 2010. Hexahedral shell mesh construction via volumetric PolyCube map. In ACM Symp. on Solid and Physical Modeling. 127–136.Google ScholarDigital Library
    17. Ying He, Hongyu Wang, Chi-Wing Fu, and Hong Qin. 2009. A divide-and-conquer approach for automatic PolyCube map construction. Computers & Graphics 33, 3 (2009), 369–380.Google ScholarDigital Library
    18. Jin Huang, Tengfei Jiang, Zeyun Shi, Yiying Tong, Hujun Bao, and Mathieu Desbrun. 2014. l1-based construction of PolyCube maps from complex shapes. ACM Trans. Graph. 33, 3 (2014), 25:1–25:11.Google ScholarDigital Library
    19. Tengfei Jiang, Jin Huang, Yuanzhen Wang, Yiying Tong, and Hujun Bao. 2014. Frame field singularity correction for automatic hexahedralization. IEEE. T. Vis. Comput. Gr. 20, 8 (2014), 1189–1199.Google ScholarDigital Library
    20. Felix Kälberer, Nieser Matthias, and Konrad Polthier. 2007. QuadCover — surface parameterization using branched coverings. Comput. Graph. Forum (SGP) 26 (2007), 375–384.Google ScholarCross Ref
    21. Patrick M. Knupp. 2001a. Algebraic mesh quality metrics. SIAM J. Sci. Comput. 23, 1 (2001), 193–218.Google ScholarDigital Library
    22. Patrick M Knupp. 2001b. Hexahedral and tetrahedral mesh untangling. Eng. Comput. 17, 3 (2001), 261–268.Google ScholarCross Ref
    23. Bo Li, Xin Li, Kexiang Wang, and Hong Qin. 2013. Surface mesh to volumetric spline conversion with generalized Poly-cubes. IEEE. T. Vis. Comput. Gr. 19 (2013), 1539–1551.Google ScholarDigital Library
    24. Minchen Li, Danny M. Kaufman, Vladimir G. Kim, Justin Solomon, and Alla Sheffer. 2018. OptCuts: Joint optimization of surface cuts and parameterization. ACM Trans. Graph. (SIGGRAPH ASIA) 37, 6 (2018), 247:1–247:13.Google Scholar
    25. Yufei Li, Yang Liu, Weiwei Xu, Wenping Wang, and Baining Guo. 2012. All-hex meshing using singularity-restricted field. ACM Trans. Graph. (SIGGRAPH ASIA) 31, 6 (2012), 177:1–177:11.Google Scholar
    26. D. C. Liu and J. Nocedal. 1989. On the limited memory method for large scale optimization. Mathematical Programming B 45 (1989), 503–528.Google ScholarDigital Library
    27. 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
    28. Marco Livesu, Alessandro Muntoni, Enrico Puppo, and Riccardo Scateni. 2016. Skeleton-driven adaptive hexahedral meshing of tubular shapes. Comput. Graph. Forum 35, 7 (2016), 237–246.Google ScholarDigital Library
    29. 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. (SIGGRAPH) 39, 4 (2020).Google ScholarDigital Library
    30. Marco Livesu, Alla Sheffer, Nicholas Vining, and Marco Tarini. 2015. Practical hexmesh optimization via edge-cone rectification. ACM Trans. Graph. (SIGGRAPH) 34, 4 (2015), 141:1–141:11.Google ScholarDigital Library
    31. Marco Livesu, Nicholas Vining, Alla Sheffer, James Gregson, and Riccardo Scateni. 2013. Polycut: monotone graph-cuts for PolyCube base-complex construction. ACM Trans. Graph. (SIGGRAPH ASIA) 32, 6 (2013), 171:1–171:12.Google Scholar
    32. Claudio Lobos. 2015. Towards a unified measurement of quality for mixed-elements. Technical Report. Universidad Tecnica Fedrericc Santa Maria.Google Scholar
    33. Max Lyon, David Bommes, and Leif Kobbelt. 2016. HexEx: robust hexahedral mesh extraction. ACM Trans. Graph. (SIGGRAPH) 35, 4 (2016), 123:1–123:11.Google ScholarDigital Library
    34. Loïc Maréchal. 2009. Advances in octree-based all-hexahedral mesh generation: handling sharp features. In Int. Meshing Roundtable. 65–84.Google Scholar
    35. M. Nieser, U. Reitebuch, and K. Polthier. 2011. CubeCover parameterization of 3D volumes. Comput. Graph. Forum (SGP) 30, 5 (2011), 1397–1406.Google ScholarCross Ref
    36. Roi Poranne, Marco Tarini, Sandro Huber, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Autocuts: simultaneous distortion and cut optimization for UV mapping. ACM Trans. Graph. (SIGGRAPH) 36, 6 (2017), 215:1–215:11.Google ScholarDigital Library
    37. E. Ruiz-Gironés, X. Roca, J. Sarrate, R. Montenegro, and J.M. Escobar. 2015. Simultaneous untangling and smoothing of quadrilateral and hexahedral meshes using an object-oriented framework. Advances in Engineering Software 80 (2015), 12–24.Google ScholarDigital Library
    38. R. Schneiders. 1996. A grid-based algorithm for the generation of hexahedral element meshes. Eng. Comput. 12, 3 (1996), 168–177.Google ScholarCross Ref
    39. Nicholas Sharp and Keenan Crane. 2018. Variational surface cutting. ACM Trans. Graph. (SIGGRAPH) 37, 4 (2018).Google ScholarDigital Library
    40. Alla Sheffer, Michal Etzion, Ari Rappoport, and Michel Bercovier. 1999. Hexahedral mesh generation using the embedded Voronoi graph. Eng. Comput. 15, 3 (1999), 248–262.Google ScholarCross Ref
    41. Jason F Shepherd and Chris R Johnson. 2008. Hexahedral mesh generation constraints. Eng. Comput. 24, 3 (2008), 195–213.Google ScholarCross Ref
    42. 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
    43. Justin Solomon, Amir Vaxman, and David Bommes. 2017. Boundary element octahedral fields in volumes. ACM Trans. Graph. 36, 3 (2017), 28:1–28:16.Google ScholarDigital Library
    44. Olga Sorkine, Daniel Cohen-Or, Rony Goldenthal, and Dani Lischinski. 2002. Bounded-distortion piecewise mesh parameterization. In Proceedings of the Conference on Visualization ’02. 355–362.Google ScholarDigital Library
    45. Matt Staten. 2007. Cubit Users’ Meeting.Google Scholar
    46. Matthew L. Staten, Steven J. Owen, and Ted D. Blacker. 2005. Unconstrained paving and plastering: a new idea for all hexahedral mesh generation. In Int. Meshing Roundtable. 399–416.Google Scholar
    47. Kenshi Takayama. 2019. Dual sheet meshing: An interactive approach to robust hexahedralization. Comput. Graph. Forum (EG) 38, 2 (2019), 37–48.Google ScholarCross Ref
    48. Marco Tarini, Kai Hormann, Paolo Cignoni, and Claudio Montani. 2004. PolyCube-Maps. ACM Trans. Graph. (SIGGRAPH) 23, 3 (2004), 853–860.Google ScholarDigital Library
    49. Rui Wang, Shuming Gao, Zhihao Zheng, and Jinming Chen. 2018. Hex mesh topological improvement based on frame field and sheet adjustment. Computer Aided Design 103 (2018), 103–117.Google ScholarCross Ref
    50. Rui Wang, Chun Shen, Jinming Chen, Haiyan Wu, and Shuming Gao. 2017. Sheet operation based block decomposition of solid models for hex meshing. Computer Aided Design 85 (2017), 123–137.Google ScholarDigital Library
    51. Yang Yang, Xiao-Ming Fu, and Ligang Liu. 2019. Computing surface PolyCube-Maps by constrained voxelization. Comput. Graph. Forum (PG) 38, 7 (2019), 37–48.Google Scholar
    52. 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
    53. Shangyou Zhang. 2005. Subtetrahedral test for the positive Jacobian of hexahedral elements. Technical Report. University of Delaware.Google Scholar

ACM Digital Library Publication: