“Robust structure simplification for hex re-meshing”
Conference:
Type(s):
Title:
- Robust structure simplification for hex re-meshing
Session/Category Title: Volumes
Presenter(s)/Author(s):
Abstract:
We introduce a robust and automatic algorithm to simplify the structure and reduce the singularities of a hexahedral mesh. Our algorithm interleaves simplification operations to collapse sheets and chords of the base complex of the input mesh with a geometric optimization, which improves the elements quality. All our operations are guaranteed not to introduce elements with negative Jacobians, ensuring that our algorithm always produces valid hex-meshes, and not to increase the Hausdorff distance from the original shape more than a user-defined threshold, ensuring a faithful approximation of the input geometry. Our algorithm can improve meshes produced with any existing hexahedral meshing algorithm — we demonstrate its effectiveness by processing a dataset of 194 hex-meshes created with octree-based, polycube-based, and field-aligned methods.
References:
1. Y Bazilevs, L Beirão da Veiga, JA Cottrell, TJR Hughes, and G Sangalli. 2006. Isogeometric analysis: approximation, stability and error estimates for h-refined meshes. Mathematical Models and Methods in Applied Sciences 16, 07 (2006), 1031–1090. Cross Ref
2. 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 Proceedings of the 4th International Meshing Roundtable. 179–191.
3. David Bommes, Timm Lempfer, and Leif Kobbelt. 2011. Global Structure Optimization of Quadrilateral Meshes. CGF 30, 2 (2011), 375–384. Cross Ref
4. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Cláudio Silva, Marco Tarini, and Denis Zorin. 2013. Quad-Mesh Generation and Processing: A Survey. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 51–76.
5. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3, Article 77 (July 2009), 10 pages.
6. Michael J Borden, Steven E Benzley, and Jason F Shepherd. 2002. Hexahedral Sheet Extraction. In Proc. of the 11th International Meshing Roundtable. 147–152.
7. Xavier Bourdin, Xavier Trosseille, Philippe Petit, and Philippe Beillas. 2007. Comparison of tetrahedral and hexaedral meshes for organ finite element modeling: an application to kidney impact. In 20th International Technical Conference on the Enhanced Safety of Vehicle. Lyon, France.
8. Agostino Bozzo, Daniele Panozzo, Enrico Puppo, Nico Pietroni, and Luigi Rocca. 2010. Adaptive quad mesh simplification. In Eurographics Italian Chapter Conference 2010.
9. M. Brewer, L. Diachin, P. Knupp, T. Leurent, and D. Melander. 2003. The Mesquite Mesh Quality Improvement Toolkit. In Proc. of the 12th International Meshing Roundtable. 239–250.
10. Gianmarco Cherchi, Marco Livesu, and Riccardo Scateni. 2016. Polycube Simplification for Coarse Layouts of Surfaces and Volumes. Computer Graphics Forum 35, 5 (2016), 11–20. Cross Ref
11. 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–4 (1992), 313–318.
12. Paolo Cignoni, Cláudio Rocchini, and Roberto Scopigno. 1996. Metro: Measuring Error on Simplified Surfaces. Technical Report. Paris, France, France.
13. Joel Daniels, Cláudio T Silva, and Elaine Cohen. 2009a. Semi-regular Quadrilateral-only Remeshing from Simplified Base Domains. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 1427–1435.
14. Joel Daniels, Cláudio T. Silva, Jason Shepherd, and Elaine Cohen. 2008. Quadrilateral mesh simplification. ACM Trans. Graph. 27, 5, Article 148 (Dec. 2008), 9 pages.
15. Joel Daniels, II, Cláudio T. Silva, and Elaine Cohen. 2009b. Localized Quadrilateral Coarsening. In Proceedings of the Symposium on Geometry Processing (SGP ’09). 1437–1444.
16. Xianzhong Fang, Weiwei Xu, Hujun Bao, and Jin Huang. 2016. All-Hex Meshing using Closed-Form Induced Polycube. Transactions on Graphics (Proc. SIGGRAPH 2016) 35, 4 (2016).
17. Xiao-Ming Fu, Chong-YangBai, and Yang Liu. 2016. Efficient Volumetric PolyCube-Map Construction. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 97–106.
18. Xifeng Gao, Zhigang Deng, and Guoning Chen. 2015. Hexahedral Mesh Reparameterization from Aligned Base-Complex. ACM Trans. Graph. (SIGGRAPH ’15) 34, 4, Article 142 (2015), 10 pages.
19. Xifeng Gao, Wenzel Jakob, Marco Tarini, and Daniele Panozzo. 2017. Robust Hexdominant Mesh Generation Using Field-guided Polyhedral Agglomeration. ACM Trans. Graph. 36, 4, Article 114 (July 2017), 13 pages.
20. Xifeng Gao, Tobias Martin, Sai Deng, Elaine Cohen, Zhigang Deng, and Guoning Chen. 2016. Structured Volume Decomposition via Generalized Sweeping. IEEE TVCG 22, 7 (2016), 1899–1911.
21. James Gregson, Alla Sheffer, and Eugene Zhang. 2011. All-Hex Mesh Generation via Volumetric PolyCube Deformation. CGF 30, 5 (2011), 1407–1416. Cross Ref
22. 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.
23. Jin Huang, Yiying Tong, Hongyu Wei, and Hujun Bao. 2011. Boundary aligned smooth 3D cross-frame field. ACM Trans. Graph. 30, 6, Article 143 (Dec. 2011), 8 pages.
24. Thomas J.R. Hughes, John A. Cottrell, and Yuri Bazilevs. 2005. Isogeometric analysis: CAD, finite elements, NURBS, exact geometry, and mesh refinement. Computer Methods in Applied Mechanics and Engineering 194 (2005), 4135–4195. Cross Ref
25. Yasushi Ito, Alan M. Shih, and Bharat K. Soni. 2009. Octree-based reasonable-quality hexahedral mesh generation using a new set of refinement templates. Int. J. Numer. Meth. Engng 77 (2009), 1809–1833. Cross Ref
26. Tengfei Jiang, Jin Huang, Yuanzhen Wang, Yiying Tong, and Hujun Bao. 2014. Frame Field Singularity Correction for Automatic Hexahedralization. IEEE TVCG 20, 8 (Aug. 2014), 1189–1199.
27. Patrick M. Knupp. 2000. Hexahedral Mesh Untangling and Algebraic Mesh Quality Metrics. In Proceedings, 9th International Meshing Roundtable. 173–183.
28. Patrick M Knupp. 2003. A method for hexahedral mesh shape optimization. International journal for numerical methods in engineering 58, 2 (2003), 319–332.
29. Leif Kobbelt, Jens Vorsatz, and Hans-Peter Seidel. 1999. Multiresolution Hierarchies on Unstructured Triangle Meshes. Comput. Geom. Theory Appl. 14, 1–3 (Nov. 1999), 5–24.
30. 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.
31. Franck Ledoux and Jason Shepherd. 2010. Topological modifications of hexahedral meshes via sheet operations: a theoretical study. Engineering with Computers 26, 4 (2010), 433–447.
32. Benoît Leonard, Alpesh Patel, and Charles Hirsch. 2000. Multigrid acceleration in a 3D Navier-Stokes solver using unstructured hexahedral meshes with adaptation. In Multigrid Methods VI. Springer, 150–156.
33. Bo Li, Xin Li, Kexiang Wang, and Hong Qin. 2013. Surface Mesh to Volumetric Spline Conversion with Generalized Poly-cubes. IEEE TVCG 19, 9 (2013), 1539–1551.
34. Bo Li and Hong Qin. 2012. Component-aware tensor-product trivariate splines of arbitrary topology. Computers & Graphics 36, 5 (2012), 329–340.
35. Yufei Li, Yang Liu, Weiwei Xu, Wenping Wang, and Baining Guo. 2012. All-hex meshing using singularity-restricted field. ACM Trans. Graph. 31, 6, Article 177 (Nov. 2012), 177:1–177:11 pages.
36. Marco Livesu, Alessandro Muntoni, Enrico Puppo, and Riccardo Scateni. 2016. Skeleton-driven Adaptive Hexahedral Meshing of Tubular Shapes. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 237–246.
37. Marco Livesu, Alla Sheffer, Nicholas Vining, and Marco Tarini. 2015. Practical Hex-Mesh Optimization via Edge-Cone Rectification. Transactions on Graphics (Proc. SIGGRAPH 2015) 34, 4 (2015).
38. Marco Livesu, Nicholas Vining, Alla Sheffer, James Gregson, and Riccardo Scateni. 2013. PolyCut: monotone graph-cuts for PolyCube base-complex construction. ACM Trans. Graph. 32, 6 (2013), 171.
39. Max Lyon, David Bommes, and Leif Kobbelt. 2016. HexEx: Robust Hexahedral Mesh Extraction. ACM Trans. Graph. 35, 4, Article 123 (July 2016), 11 pages.
40. Loïc Maréchal. 2009. Advances in octree-based all-hexahedral mesh generation: handling sharp features. In proceedings of the 18th International Meshing Roundtable. Springer, 65–84. Cross Ref
41. MeshGems. 2015. Volume Meshing: MeshGems-Hexa. http://meshgems.com/volume-meshing-meshgems-hexa.html. (2015).
42. Ashish Myles, Nico Pietroni, Denis Kovacs, and Denis Zorin. 2010. Feature-aligned T-meshes. ACM Trans. Graph. 29, Article 117 (July 2010), 11 pages. Issue 4.
43. Matthias Nieser, Ulrich Reitebuch, and Konrad Polthier. 2011. CubeCover- Parameterization of 3D Volumes. CGF 30, 5 (2011), 1397–1406. Cross Ref
44. Steven J Owen. 1998. A Survey of Unstructured Mesh Generation Technology. In IMR. 239–267.
45. Daniele Panozzo, Ilya Baran, Olga Diamanti, and Olga Sorkine-Hornung. 2013. Weighted Averages on Surfaces. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH) 32, 4 (2013), 60:1–60:12.
46. PARDISO. 2017. PARDISO. http://www.pardiso-project.org/. (2017).
47. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 2, Article 16 (April 2017), 16 pages.
48. 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. Cross Ref
49. Eloi Ruiz-Gironés, Xevi Roca, and Jose Sarrate. 2014. Optimizing mesh distortion by hierarchical iteration relocation of the nodes on the CAD entities. Procedia Engineering 82 (2014), 101–113. Cross Ref
50. Eloi Ruiz-Gironés, Xevi Roca, Josep Sarrate, Rafael Montenegro, and José María Escobar. 2015. Simultaneous untangling and smoothing of quadrilateral and hexahedral meshes using an object-oriented framework. Advances in Engineering Software 80 (2015), 12–24.
51. National Lab Sandia. 2016. CUBIT. https://cubit.sandia.gov/. (2016).
52. Jason F. Shepherd and Chris R. Johnson. 2008. Hexahedral Mesh Generation Constraints. Eng. with Comput. 24, 3 (June 2008), 195–213. Cross Ref
53. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. 34, 4, Article 70 (July 2015), 9 pages.
54. C. J. Stimpson, C. D. Ernst, P. Knupp, P. P. Pébayand, and D. Thompson. 2007. The Verdict Geometric Quality Library. (2007).
55. Yi Su, KH Lee, and A Senthil Kumar. 2004. Automatic hexahedral mesh generation for multi-domain composite models using a hybrid projective grid-based method. Computer-Aided Design 36, 3 (2004), 203–215. Cross Ref
56. Srinivas C. Tadepalli, Ahmet Erdemir, and Peter R. Cavanagh. 2010. A Comparison of the Performance of Hexahedral and Tetrahedral Elements in Finite Element Models of the Foot. In ASME 2010 Summer Bioengineering Conference, Parts A and B.
57. Marco Tarini, Nico Pietroni, Paolo Cignoni, Daniele Panozzo, and Enrico Puppo. 2010. Practical quad mesh simplification. CGF 29, 2 (2010), 407–418. Cross Ref
58. Marco Tarini, Enrico Puppo, Daniele Panozzo, Nico Pietroni, and Paolo Cignoni. 2011. Simple Quad Domains for Field Aligned Mesh Parametrization. ACM Trans. Graph. 30, 6, Article 142 (Dec. 2011), 12 pages.
59. Timothy J Tautges and Sarah E Knoop. 2003. Topology modification of hexahedral meshes using atomic dual-based operations. In Proc. of the 12th International Meshing Roundtable. 415–423.
60. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional Field Synthesis, Design, and Processing. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 545–572.
61. Yoshitaka Wada, Junichi Shinbori, and Masanori Kikuchi. 2006. Adaptive FEM analysis technique using multigrid method for unstructured hexahedral meshes. Key Engineering Materials 306 (2006), 565–570. Cross Ref
62. Thomas James Wilson, Josep Sarrate Ramos, Xavier Roca Ramón, Rafael Montenegro Armas, and José Maria Escobar Sánchez. 2012. Untangling and smoothing of quadrilateral and hexahedral meshes. (2012).
63. Hongmei Zhang, Guoqun Zhao, and Xinwu Ma. 2007. Adaptive generation of hexahedral element mesh using an improved grid-based method. Computer-Aided Design 39, 10 (2007), 914–928. Cross Ref
64. Yongjie Zhang and Chandrajit Bajaj. 2006. Adaptive and quality quadrilateral/hexahedral meshing from volumetric data. Computer methods in applied mechanics and engineering 195, 9 (2006), 942–960.
65. Y. J. Zhang, X. Liang, and Guoliang Xu. 2013. A robust 2-refinement algorithm in octree or rhombic dodecahedral tree based all-hexahedral mesh generation. Computer Methods in Applied Mechanics and Engineering 256 (2013), 88–100. Cross Ref
