“Hexahedral-Dominant Meshing”
Conference:
Type:
Title:
- Hexahedral-Dominant Meshing
Session/Category Title: Meshing
Presenter(s)/Author(s):
Moderator(s):
Abstract:
This article introduces a method that generates a hexahedral-dominant mesh from an input tetrahedral mesh. It follows a three-step pipeline similar to the one proposed by Carrier Baudoin et al.: (1) generate a frame field, (2) generate a pointset P that is mostly organized on a regular grid locally aligned with the frame field, and (3) generate the hexahedral-dominant mesh by recombining the tetrahedra obtained from the constrained Delaunay triangulation of P.For step (1), we use a state-of-the-art algorithm to generate a smooth frame field. For step (2), we introduce an extension of Periodic Global Parameterization to the volumetric case. As compared with other global parameterization methods (such as CubeCover), our method relaxes some global constraints to avoid creating degenerate elements, at the expense of introducing some singularities that are meshed using non-hexahedral elements. For step (3), we build on the formalism introduced by Meshkat and Talmor, fill in a gap in their proof, and provide a complete enumeration of all the possible recombinations, as well as an algorithm that efficiently detects all the matches in a tetrahedral mesh.The method is evaluated and compared with the state of the art on a database of examples with various mesh complexities, varying from academic examples to real industrial cases. Compared with the method of Carrier-Baudoin et al., the method results in better scores for classical quality criteria of hexahedral-dominant meshes (hexahedral proportion, scaled Jacobian, etc.). The method also shows better robustness than CubeCover and its derivatives when applied to complicated industrial models.
References:
1. Ashby, Manteuffel, and Saylor. 1990. A taxonomy for conjugate gradient methods. J. Numer. Anal. 27 (1990), 1542–1568. Google ScholarDigital Library
2. Morgane Bergot, Gary Cohen, and Marc Duruflé. 2009. Higher-order finite elements for hybrid meshes using new nodal pyramidal elements. J. Sci. Comput. 42, 3 (2009), 345–381. DOI:http://dx.doi.org/10.1007/s10915-009-9334-9 Google ScholarDigital Library
3. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3, Article 77 (July 2009), 10 pages. DOI:http://dx.doi.org/10.1145/1531326.1531383 Google ScholarDigital Library
4. I. M. Bomze, M. Budinich, P. M. Pardalos, and M. Pelillo. 1999. The maximum clique problem. In Handbook of Combinatorial Optimization 4. Kluwer Academic.Google Scholar
5. Arnaud Botella, Bruno Lévy, and Guillaume Caumon. 2015. Indirect unstructured hex-dominant mesh generation using tetrahedra recombination. Comput. Geosci. (2015), 1–15. DOI:http://dx.doi.org/10.1007/ s10596-015-9484-9Google Scholar
6. Tristan Carrier-Baudouin, Jean-Franois Remacle, Emilie Marchandise, Franois Henrotte, and Christophe Geuzaine. 2014. A frontal approach to hex-dominant mesh generation. Adv. Model. Simul. Eng. Sci. 1, 1 (2014). DOI:http://dx.doi.org/10.1186/2213-7467-1-8Google Scholar
7. CGAL. CGAL Open Source Project. www.cgal.org.Google Scholar
8. S. A. Cook. 1971. The complexity of theorem-proving procedures. In Proc. 3rd ACM Symposium on Theory of Computing. ACM, New York, NY, 151–158. DOI:http://dx.doi.org/doi:10.1145/800157.805047 Google ScholarDigital Library
9. Hans-Christian Ebke, David Bommes, Marcel Campen, and Leif Kobbelt. 2013. QEx: Robust quad mesh extraction. ACM Trans. Graph. 32, 6, Article 168 (Nov. 2013), 10 pages. DOI:http://dx.doi.org/10.1145/ 2508363.2508372 Google ScholarDigital Library
10. Herbert Edelsbrunner and Ernst Peter Mücke. 1990. Simulation of simplicity. ACM Trans. Graph. 9, 1 (1990). Google ScholarDigital Library
11. Paul-Louis George, Frédéric Hecht, and E. Saltel. 1990. Fully automatic mesh generator for 3d domains of any shape. IMPACT Comput. Sci. Eng. 2, 3 (1990), 187–218. DOI:http://dx.doi.org/10.1016/ 0899-8248(90)90012-Y Google ScholarDigital Library
12. J. Gregson, A. Sheffer, and E. Zhang. 2011. All-hex mesh generation via volumetric polycube deformation. Computer Graphics Forum (Special Issue of Symposium on Geometry Processing 2011) 30, 5 (2011), to appear.Google Scholar
13. 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, Article 25 (June 2014), 11 pages. DOI:http://dx.doi.org/10.1145/2602141 Google ScholarDigital Library
14. 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. DOI:http://dx.doi.org/10.1145/2070781.2024177 Google ScholarDigital Library
15. Tengfei Jiang, Jin Huang, Yuanzhen Wang, Yiying Tong, and Hujun Bao. 2014. Frame field singularity correction for automatic hexahedralization. IEEE Trans. Vis. Comput. Graph. 20, 8 (2014), 1189–1199. DOI:http://dx.doi.org/10.1109/TVCG.2013.250 Google ScholarDigital Library
16. Felix Kälberer, Matthias Nieser, and Konrad Polthier. 2007. QuadCover — Surface parameterization using branched coverings. Comput. Graph. Forum 26, 3 (2007), 375–384.Google ScholarCross Ref
17. Bruno Lévy and Yang Liu. 2010. Lp centroidal voronoi tesselation and its applications. ACM Trans. Graph. 29, 4 (2010). DOI:http://dx.doi.org/10.1145/1833349.1778856 Google ScholarDigital Library
18. 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), 11 pages. DOI:http://dx.doi.org/10.1145/ 2366145.2366196 Google ScholarDigital Library
19. C. L. Liu. 1968. Introduction to Combinatorial Mathematics. McGraw-Hill, New York, NY.Google Scholar
20. Marco Livesu, Nicholas Vining, Alla Sheffer, James Gregson, and Riccardo Scateni. 2013. PolyCut: Monotone graph-cuts for polycube base-complex construction. Trans. Graph. (Proc. SIGGRAPH ASIA 2013) 32, 6 (2013). Google ScholarDigital Library
21. Bruno Lévy. 2000. OpenNL, Open Numerical Library. (2000). http://alice.loria.fr/index.php/software/4-library/23-opennl.html.Google Scholar
22. Bruno Lévy. 2015. Geogram, a programming library of geometric algorithms. (2015). http://alice.loria.fr/software/geogram/doc/html/index.html.Google Scholar
23. Bruno Lévy and Yang Liu. 2010. Lp centroidal voronoi tesselation and its applications. ACM Transactions on Graphics (SIGGRAPH Conference Proceedings) (2010). patent pending – FR 10/02920 (filed 07/09/10). Google ScholarDigital Library
24. Sia Meshkat and Dafna Talmor. 2000. Generating a mixed mesh of hexahedra, pentahedra and tetrahedra from an underlying tetrahedral mesh. Internat. J. Numer. Methods Engrg. 49, 1–2 (2000), 17–30. DOI:http://dx.doi.org/10.1002/1097-0207(20000910/20)49:1/2<17∷AID-NME920>3.0.CO;2-UGoogle ScholarCross Ref
25. Meyer and Pion. 2008. FPG: A code generator. In Real Numbers and Computers. 47–60. http://hal.inria.fr/inria-00344297Google Scholar
26. Ray J. Meyers, Timothy J. Tautges, Philip M. Tuchinsky, and Dr. Philip M. Tuchinsky. 1998. The “hex-tet” hex-dominant meshing algorithm as implemented in CUBIT. In in CUBIT; Proceedings, 7th International Meshing Roundtable 98. 151–158.Google Scholar
27. M. Nieser, U. Reitebuch, and K. Polthier. 2011. CubeCover–parameterization of 3d volumes. Comput. Graph. Forum 30, 5 (2011), 1397–1406. DOI:http://dx.doi.org/10.1111/j.1467-8659.2011.02014.xGoogle ScholarCross Ref
28. Nicolas Ray, Wan Chiu Li, Bruno Lévy, Alla Sheffer, and Pierre Alliez. 2006. Periodic global parameterization. ACM Trans. Graph. 25, 4 (Oct. 2006), 1460–1485. DOI:http://dx.doi.org/10.1145/1183287.1183297 Google ScholarDigital Library
29. Nicolas Ray and Dmitry Sokolov. 2015. On smooth 3d frame field design. CoRR http://arxiv.org/abs/1507.03351 (2015).Google Scholar
30. Jason F. Shepherd and Chris R. Johnson. 2008. Hexahedral mesh generation constraints. Eng. Comput. 24, 3 (June 2008), 195–213. DOI:http://dx.doi.org/ 10.1007/s00366-008-0091-4Google ScholarCross Ref
31. Shewchuk. 1997. Adaptive precision floating-point arithmetic. Discr. Comput. Geom. 18, 3 (1997).Google Scholar
32. Hang Si. 2015. TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Trans. Math. Softw. 41, 2, Article 11 (Feb. 2015), 36 pages. DOI:http://dx.doi.org/10.1145/2629697 Google ScholarDigital Library
33. Soji Yamakawa and Kenji Shimada. 2003. Fully-automated hex-dominant mesh generation with directionality control via packing rectangular solid cells. Internat. J. Numer. Methods Eng. 57, 15 (2003), 2099–2129. DOI:http://dx.doi.org/10.1002/nme.754Google ScholarCross Ref
34. Dongming Yan, Bruno Lévy, Yang Liu, Feng Sun, and Wenping Wang. 2009. Isotropic remeshing with fast and exact computation of restricted voronoi diagram. In ACM/EG Symposium on Geometry Processing/Computer Graphics Forum. Google ScholarDigital Library
