“LoopyCuts: practical feature-preserving block decomposition for strongly hex-dominant meshing” by Livesu, Pietroni, Puppo, Sheffer and Cignoni

  • ©Marco Livesu, Nico Pietroni, Enrico Puppo, Alla Sheffer, and Paolo Cignoni




    LoopyCuts: practical feature-preserving block decomposition for strongly hex-dominant meshing

Session/Category Title: Making Delaunay and Voronoi Proud



    We present a new fully automatic block-decomposition algorithm for feature-preserving, strongly hex-dominant meshing, that yields results with a drastically larger percentage of hex elements than prior art. Our method is guided by a surface field that conforms to both surface curvature and feature lines, and exploits an ordered set of cutting loops that evenly cover the input surface, defining an arrangement of loops suitable for hex-element generation. We decompose the solid into coarse blocks by iteratively cutting it with surfaces bounded by these loops. The vast majority of the obtained blocks can be turned into hexahedral cells via simple midpoint subdivision. Our method produces pure hexahedral meshes in approximately 80% of the cases, and hex-dominant meshes with less than 2% non-hexahedral cells in the remaining cases. We demonstrate the robustness of our method on 70+ models, including CAD objects with features of various complexity, organic and synthetic shapes, and provide extensive comparisons to prior art, demonstrating its superiority.


    1. T. Blacker. 1996. The Cooper Tool. In Proc. 5th Int. Meshing Roundtable. 13–29.Google Scholar
    2. T. Blacker. 2000. Meeting the challenge for automated conformal hexahedral meshing. In Proc. 9th Int. Meshing Roundtable. 11–20.Google Scholar
    3. I. Boier-Martin, H. Rushmeier, and J. Jin. 2004. Parameterization of triangle meshes over quadrilateral domains. In Proc. Eurographics Symp. on Geom. Proc. 193–203.Google Scholar
    4. D. Bommes, H. Zimmer, and L. Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3 (2009), 77.Google ScholarDigital Library
    5. M. Bracci, M. Tarini, N. Pietroni, M. Livesu, and P. Cignoni. 2019. HexaLab. net: an online viewer for hexahedral meshes. Computer-Aided Design 110 (2019), 24–36.Google ScholarDigital Library
    6. M. Campen, D. Bommes, and L. Kobbelt. 2012. Dual loops meshing: quality quad layouts on manifolds. ACM Trans. Graph. 31, 4 (2012), 110.Google ScholarDigital Library
    7. N. A. Carr, J. Hoberock, K. Crane, and J. C. Hart. 2006. Rectangular Multi-chart Geometry Images. In Proc. Eurographics Symp. on Geom. Proc. 181–190.Google Scholar
    8. G. Cherchi, M. Livesu, and R. Scateni. 2016. Polycube Simplification for Coarse Layouts of Surfaces and Volumes. Comput. Graph. Forum 35, 5 (2016), 11–20.Google Scholar
    9. E. Corman and K. Crane. 2019. Symmetric Moving Frames. ACM Trans. Graph. 38, 4 (2019), 1–16.Google ScholarDigital Library
    10. M. Corsini, P. Cignoni, and R. Scopigno. 2012. Efficient and Flexible Sampling with Blue Noise Properties of Triangular Meshes. IEEE Trans. Vis. Comput. Graph. 18, 6 (June 2012), 914–924.Google ScholarDigital Library
    11. J. Daniels II, C. T. Silva, and E. Cohen. 2009. Semi-regular Quadrilateral-only Remeshing from Simplified Base Domains. Comput. Graph. Forum 28 (July 2009), 1427–1435.Google Scholar
    12. F. de Goes, M. Desbrun, and Y. Tong. 2016. Vector field processing on triangle meshes. In ACM SIGGRAPH 2016 Courses. ACM, 27.Google Scholar
    13. D. DeCarlo, A. Finkelstein, S. Rusinkiewicz, and A. Santella. 2003. Suggestive Contours for Conveying Shape. ACM Trans. Graph. 22, 3 (2003), 848–855.Google ScholarDigital Library
    14. O. Diamanti, A. Vaxman, D. Panozzo, and O. Sorkine-Hornung. 2014. Designing N-PolyVector Fields with Complex Polynomials. Comput. Graph. Forum 33, 5 (2014), 1–11.Google ScholarDigital Library
    15. A. Doi and A. Koide. 1991. An efficient method of triangulating equi-valued surfaces by using tetrahedral cells. IEICE Trans. Inf. and Sys. E74, 1 (1991), 214–224.Google Scholar
    16. X. Fang, W. Xu, H. Bao, and J. Huang. 2016. All-hex Meshing Using Closed-form Induced Polycube. ACM Trans. Graph. 35, 4 (2016), 124:1–124:9.Google ScholarDigital Library
    17. X.-M. Fu, C.-Y. Bai, and Y. Liu. 2016. Efficient Volumetric PolyCube-Map Construction. In Comput. Graph. Forum, Vol. 35. 97–106.Google ScholarDigital Library
    18. S. Gao, Z. Zheng, R. Wang, Y. Liao, and M. Ding. 2018. Dual Surface Based Approach to Block Decomposition of Solid Models. In Proc. 27th Int. Meshing Roundtable.Google Scholar
    19. X. Gao, Z. Deng, and G. Chen. 2015. Hexahedral mesh re-parameterization from aligned base-complex. ACM Trans. Graph. 34, 4 (2015), 142.Google ScholarDigital Library
    20. X. Gao, W. Jakob, M. Tarini, and D. Panozzo. 2017a. Robust Hex-dominant Mesh Generation Using Field-guided Polyhedral Agglomeration. ACM Trans. Graph. 36, 4 (July 2017), 114:1–114:13.Google ScholarDigital Library
    21. X. Gao, D. Panozzo, W. Wang, Z. Deng, and G. Chen. 2017b. Robust structure simplification for hex re-meshing. ACM Trans. Graph. 36, 6 (2017), 185.Google ScholarDigital Library
    22. X. Gao, H. Shen, and D. Panozzo. 2019. Feature Preserving Octree-Based Hexahedral Meshing. In Comput. Graph. Forum, Vol. 38. 135–149.Google ScholarCross Ref
    23. J. Gregson, A. Sheffer, and E. Zhang. 2011. All-Hex Mesh Generation via Volumetric PolyCube Deformation. Comput. Graph. Forum 30, 5 (2011), 1407–1416.Google ScholarCross Ref
    24. G. Guennebaud, B. Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org. (2010).Google Scholar
    25. J. Huang, T. Jiang, Z. Shi, Y. Tong, H. Bao, and M. Desbrun. 2014. L1-Based Construction of Polycube Maps from Complex Shapes. ACM Trans. Graph. 33, 3 (2014), 25.Google ScholarDigital Library
    26. J. Huang, Y. Tong, H. Wei, and H. Bao. 2011. Boundary aligned smooth 3D cross-frame field. In ACM Trans. Graph., Vol. 30. ACM, 143.Google ScholarDigital Library
    27. Y. Ito, A. M. Shih, and B. K. Soni. 2009. Octree-based reasonable-quality hexahedral mesh generation using a new set of refinement templates. Int. Jou. Num. Meth. Eng. 77, 13 (2009), 1809–1833.Google ScholarCross Ref
    28. W. Jakob, M. Tarini, D. Panozzo, and O. Sorkine-Hornung. 2015. Instant field-aligned meshes. ACM Trans. Graph. 34, 6 (2015), 189–1.Google ScholarDigital Library
    29. T. Jiang, J. Huang, Y. Wang, Y. Tong, and H. Bao. 2014. Frame field singularity correction for automatic hexahedralization. IEEE Trans. Vis. Comput. Graph. 20, 8 (2014), 1189–1199.Google ScholarDigital Library
    30. F. Kälberer, M. Nieser, and K. Polthier. 2007. QuadCover: Surface Parameterization using Branched Coverings. Comput. Graph. Forum 26, 3 (2007), 375–384.Google ScholarCross Ref
    31. N. Kowalski, F. Ledoux, and P. Frey. 2016. Smoothness driven frame field generation for hexahedral meshing. Computer-Aided Design 72 (2016), 65–77.Google ScholarDigital Library
    32. Nicolas Kowalski, Franck Ledoux, Matthew L Staten, and Steve J Owen. 2012. Fun sheet matching: towards automatic block decomposition for hexahedral meshes. Engineering with Computers 28, 3 (2012), 241–253.Google ScholarDigital Library
    33. M. Lanthier, A. Maheshwari, and J.-R. Sack. 2001. Approximating shortest paths on weighted polyhedral surfaces. Algorithmica 30, 4 (2001), 527–562.Google ScholarCross Ref
    34. B. Lévy and Y. Liu. 2010. Lp Centroidal Voronoi Tesselation and its Applications. ACM Trans. Graph. 29, 4 (2010), 119.1–119.11.Google ScholarDigital Library
    35. T. S. Li, R. M. McKeag, and C. G. Armstrong. 1995. Hexahedral meshing using midpoint subdivision and integer programming. Comput. Methods App. Mech. Eng. 124, 1-2 (1995), 171–193.Google ScholarCross Ref
    36. Y. Li, Y. Liu, W. Xu, W. Wang, and B. Guo. 2012. All-hex Meshing Using Singularity-restricted Field. ACM Trans. Graph. 31, 6 (2012), 177.1–177.11.Google ScholarDigital Library
    37. H. Lin, S. Jin, H. Liao, and Q. Jian. 2015. Quality Guaranteed All-hex Mesh Generation by a Constrained Volume Iterative Fitting Algorithm. Computer-Aided Design 67, C (2015), 107–117.Google Scholar
    38. H. Liu, P. Zhang, E. Chien, J. Solomon, and D. Bommes. 2018. Singularity-constrained octahedral fields for hexahedral meshing. ACM Trans. Graph. 37, 4 (2018), 93.Google ScholarDigital Library
    39. S. Liu and R. Gadh. 1997. Automatic Hexahedral Mesh Generation by Recursive Convex and Swept Volume Decomposition. In Proc. 6th Int. Meshing Roundtable. 217–231.Google Scholar
    40. M. Livesu. 2017. cinolib: a generic programming header only C++ library for processing polygonal and polyhedral meshes. https://github.com/mlivesu/cinolib/. (2017).Google Scholar
    41. M. Livesu, M. Attene, G. Patané, and M. Spagnuolo. 2017. Explicit Cylindrical Maps for General Tubular Shapes. Computer-Aided Design 90 (2017), 27–36.Google ScholarDigital Library
    42. M. Livesu, A. Muntoni, E. Puppo, and R. Scateni. 2016. Skeleton-driven Adaptive Hexahedral Meshing of Tubular Shapes. Comput. Graph. Forum 35, 7 (2016), 237–246.Google ScholarDigital Library
    43. M. Livesu, A. Sheffer, N. Vining, and M. Tarini. 2015. Practical Hex-Mesh Optimization via Edge-Cone Rectification. ACM Trans. Graph. 34, 4 (2015).Google ScholarDigital Library
    44. M. Livesu, N. Vining, A. Sheffer, J. Gregson, and R. Scateni. 2013. PolyCut: Monotone Graph-Cuts for PolyCube Base-Complex Construction. ACM Trans. Graph. 32, 6 (2013).Google ScholarDigital Library
    45. J. H.-C. Lu, W. R. Quadros, and K. Shimada. 2017. Evaluation of user-guided semiautomatic decomposition tool for hexahedral mesh generation. Jou. Comput. Design Eng. 4, 4 (2017), 330–338.Google ScholarCross Ref
    46. I. Macêdo, J. P. Gois, and L. Velho. 2011. Hermite Radial Basis Functions Implicits. Comput. Graph. Forum 30, 1 (2011), 27–42.Google ScholarCross Ref
    47. L. Maréchal. 2009. Advances in Octree-Based All-Hexahedral Mesh Generation: Handling Sharp Features. In Proc. 18th Int. Meshing Roundtable. 65–84.Google ScholarCross Ref
    48. S. Meshkat and D. Talmor. 2000. Generating a mixed mesh of hexahedra, pentahedra and tetrahedra from an underlying tetrahedral mesh. Int. Jou. Num. Meth. Eng. 49, 1-2 (2000), 17–30.Google ScholarCross Ref
    49. K. Miyoshi and T. Blacker. 2000. Hexahedral Mesh Generation Using Multi-Axis Cooper Algorithm. In Proc. 9th Int. Meshing Roundtable. 89–97.Google Scholar
    50. M. Nieser, U. Reitebuch, and K. Polthier. 2011. CubeCover – Parameterization of 3D Volumes. Comput. Graph. Forum 30, 5 (2011), 1397–1406.Google Scholar
    51. Steven Owen. 2009. A Survey of Unstructured Mesh Generation Technology. http://www.andrew.cmu.edu/user/sowen/survey/hexsurv.html. (2009).Google Scholar
    52. J. Pellerin, A. Johnen, and J.-F. Remacle. 2017. Identifying combinations of tetrahedra into hexahedra: a vertex based strategy. Procedia Engineering 203 (2017), 2–13. 26rd International Meshing Roundtable (IMR26).Google ScholarCross Ref
    53. N. Pietroni, E. Puppo, G. Marcias, R. Scopigno, and P. Cignoni. 2016. Tracing Field-Coherent Quad Layouts. Comput. GraphForum 35, 7 (2016), 485–496.Google ScholarDigital Library
    54. W. R. Quadros. 2014. LayTracks3D: A New Approach to Meshing General Solids using Medial Axis Transform. Procedia Engineering 82 (2014), 72–87. 23rd International Meshing Roundtable (IMR23).Google ScholarCross Ref
    55. N. Ray, D. Sokolov, M. Reberol, F. Ledoux, and B. Levy. 2018. Hex-dominant meshing: mind the gap! Computer-Aided Design 102 (2018), 94–103.Google Scholar
    56. E. Ruiz-Gironés, X. Roca, and J. Sarrate. 2011. Using a computational domain and a three-stage node location procedure for multi-sweeping algorithms. Advances in Eng. Software 42, 9 (2011), 700–713.Google ScholarDigital Library
    57. R. Schneiders. 1996. A grid-based algorithm for the generation of hexahedral element meshes. Eng. with Computers 12, 3 (1996), 168–177.Google ScholarCross Ref
    58. A. Sheffer, M. Etzion, A. Rappoport, and M. Bercovier. 1999. Hexahedral Mesh Generation using the Embedded Voronoi Graph. Eng. with Computers 15, 3 (1999), 248–262.Google ScholarCross Ref
    59. J. F. Shepherd and C. R. Johnson. 2008. Hexahedral mesh generation constraints. Eng. with Computers 24, 3 (2008), 195–213.Google ScholarDigital Library
    60. H. Si. 2015. TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Trans. Math. Software 41, 2 (2015), 11.Google ScholarDigital Library
    61. D. Sokolov, N. Ray, L. Untereiner, and B. Lévy. 2016a. Hexahedral-Dominant Meshing. ACM Trans. Graph. 35, 5 (2016), 157:1–157:23.Google ScholarDigital Library
    62. Dmitry Sokolov, Nicolas Ray, Lionel Untereiner, and Bruno Lévy. 2016b. Hexahedral-dominant meshing. ACM Transactions on Graphics (TOG) 35, 5 (2016), 1–23.Google ScholarDigital Library
    63. J. Solomon, A. Vaxman, and D. Bommes. 2017. Boundary element octahedral fields in volumes. ACM Trans. Graph. 36, 3 (2017), 28.Google ScholarDigital Library
    64. K. Takayama. 2019. Dual Sheet Meshing: An Interactive Approach to Robust Hexahedralization. Comput. Graph. Forum 38, 2 (2019), 37–48.Google ScholarCross Ref
    65. M. Tarini, K. Hormann, P. Cignoni, and C. Montani. 2004. Polycube-maps. In ACM Trans. Graph., Vol. 23. ACM, 853–860.Google ScholarDigital Library
    66. A. Vaxman, M. Campen, O. Diamanti, D. Panozzo, D. Bommes, K. Hildebrandt, and M. Ben-Chen. 2016. Directional field synthesis, design, and processing. In Comput. Graph. Forum, Vol. 35. 545–572.Google ScholarCross Ref
    67. Visual Computing Lab. 2018. The VCG Library. Italian National Research Council – ISTI. http://vcg.isti.cnr.it/vcglib/Google Scholar
    68. R. Wang, C. Shen, J. Chen, H. Wu, and S. Gao. 2017. Sheet operation based block decomposition of solid models for hex meshing. Computer-Aided Design 85 (2017), 123–137. 24th International Meshing Roundtable (IMR24).Google ScholarDigital Library
    69. S. Yamakawa and K. Shimada. 2002. Hex-dominant mesh generation with directionality control via packing rectangular solid cells. In Proc. Geometric Modeling and Processing. IEEE, 107–118.Google Scholar
    70. Q. Zhou and A. Jacobson. 2016. Thingi10k: A dataset of 10,000 3d-printing models. arXiv preprint arXiv:1605.04797 (2016).Google Scholar

ACM Digital Library Publication:

Overview Page: