“LoopyCuts: practical feature-preserving block decomposition for strongly hex-dominant meshing” by Livesu, Pietroni, Puppo, Sheffer and Cignoni
Conference:
Type:
Title:
- LoopyCuts: practical feature-preserving block decomposition for strongly hex-dominant meshing
Session/Category Title: Making Delaunay and Voronoi Proud
Presenter(s)/Author(s):
Abstract:
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.
References:
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
