“Singularity-constrained octahedral fields for hexahedral meshing” by Liu, Zhang, Chien, Solomon and Bommes
Conference:
Type(s):
Entry Number: 93
Title:
- Singularity-constrained octahedral fields for hexahedral meshing
Session/Category Title: Fields and Remeshing
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Despite high practical demand, algorithmic hexahedral meshing with guarantees on robustness and quality remains unsolved. A promising direction follows the idea of integer-grid maps, which pull back the Cartesian hexahedral grid formed by integer isoplanes from a parametric domain to a surface-conforming hexahedral mesh of the input object. Since directly optimizing for a high-quality integer-grid map is mathematically challenging, the construction is usually split into two steps: (1) generation of a surface-aligned octahedral field and (2) generation of an integer-grid map that best aligns to the octahedral field. The main robustness issue stems from the fact that smooth octahedral fields frequently exhibit singularity graphs that are not appropriate for hexahedral meshing and induce heavily degenerate integer-grid maps. The first contribution of this work is an enumeration of all local configurations that exist in hex meshes with bounded edge valence, and a generalization of the Hopf-Poincaré formula to octahedral fields, leading to necessary local and global conditions for the hex-meshability of an octahedral field in terms of its singularity graph. The second contribution is a novel algorithm to generate octahedral fields with prescribed hex-meshable singularity graphs, which requires the solution of a large nonlinear mixed-integer algebraic system. This algorithm is an important step toward robust automatic hexahedral meshing since it enables the generation of a hex-meshable octahedral field.
References:
1. Cecil G. Armstrong, Harold J. Fogg, Christopher M. Tierney, and Trevor T. Robinson. 2015. Common Themes in Multi-block Structured Quad/Hex Mesh Generation. Procedia Engineering 124, Supplement C (2015), 70 — 82. 24th Int. Meshing Roundtable.Google ScholarCross Ref
2. Tristan Carrier Baudouin, Jean-François Remade, Emilie Marchandise, François Henrotte, and Christophe Geuzaine. 2014. A frontal approach to hex-dominant mesh generation. Advanced Modeling and Simulation in Engineering Sciences 1, 1 (10 Feb 2014), 8.Google Scholar
3. P.-E. Bernard, J.-F. Remade, N. Kowalski, and C. Geuzaine. 2016. Frame field smoothness-based approach for hex-dominant meshing. Computer-Aided Design 72, Supplement C (2016), 78 — 86. 23rd International Meshing Roundtable. Google ScholarDigital Library
4. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013a. Integer-grid Maps for Reliable Quad Meshing. ACM Trans. Graph. 32, 4, Article 98 (July 2013), 12 pages. Google ScholarDigital Library
5. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, Marco Tarini, and Denis Zorin. 2013b. Quad-Mesh Generation and Processing: A Survey. Computer Graphics Forum 32, 6 (2013), 51–76. Google ScholarDigital Library
6. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer Quadrangulation. ACM Trans. Graph. 28, 3, Article 77 (July 2009), 10 pages. Google ScholarDigital Library
7. R. Bowen and S. Fisk. 1967. Generations of Triangulations of the Sphere. Math. Comp. 21 (1967), 250–252.Google Scholar
8. Marcel Campen, David Bommes, and Leif Kobbelt. 2015. Quantized Global Parametrization. ACM Trans. Graph. 34, 6, Article 192 (Oct. 2015), 12 pages. Google ScholarDigital Library
9. Marcel Campen and Denis Zorin. 2017. Similarity Maps and Field-guided T-splines: A Perfect Couple. ACM Trans. Graph. 36, 4, Article 91 (July 2017), 16 pages. Google ScholarDigital Library
10. Keenan Crane, Mathieu Desbrun, and Peter Schröder. 2010. Trivial Connections on Discrete Surfaces. Computer Graphics Forum 29, 5 (2010), 1525–1533.Google ScholarCross Ref
11. Tamal K. Dey and Sumanta Guha. 1998. Computing Homology Groups of Simplicial Complexes in R3. J. ACM 45, 2 (March 1998), 266–287. Google ScholarDigital Library
12. 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), 168:1–168:10 pages. Google ScholarDigital Library
13. Jeff Erickson. 2014. Efficiently Hex-Meshing Things with Topology. Discrete & Computational Geometry 52, 3 (Oct. 2014), 427–449. Google ScholarDigital Library
14. Xianzhong Fang, Weiwei Xu, Hujun Bao, and Jin Huang. 2016. All-hex Meshing Using Closed-form Induced Polycube. ACM Trans. Graph. 35, 4, Article 124 (July 2016), 124:1–124:9 pages. Google ScholarDigital Library
15. Xiao-Ming Fu, Chong-Yang Bai, and Yang Liu. 2016. Efficient Volumetric PolyCube-Map Construction. Computer Graphics Forum 35, 7 (2016), 97–106. Google ScholarDigital Library
16. Xifeng Gao, Zhigang Deng, and Guoning Chen. 2015. Hexahedral Mesh Reparameterization from Aligned Base-complex. ACM Trans. Graph. 34, 4, Article 142 (July 2015), 10 pages. Google ScholarDigital Library
17. Xifeng Gao, Wenzel Jakob, Marco Tarini, and Daniele Panozzo. 2017a. Robust Hex-dominant Mesh Generation Using Field-guided Polyhedral Agglomeration. ACM Trans. Graph. 36, 4, Article 114 (July 2017), 13 pages. Google ScholarDigital Library
18. Xifeng Gao, Daniele Panozzo, Wenping Wang, Zhigang Deng, and Guoning Chen. 2017b. Robust Structure Simplification for Hex Re-meshing. ACM Trans. Graph. 36, 6, Article 185 (Nov. 2017), 13 pages. Google ScholarDigital Library
19. James Gregson, Alla Sheffer, and Eugene Zhang. 2011. All-Hex Mesh Generation via Volumetric PolyCube Deformation. Computer Graphics Forum 30, 5 (2011), 1407–1416.Google ScholarCross Ref
20. Allen Hatcher. 2001. Algebraic Topology. Cambridge University Press, Cambridge, UK.Google Scholar
21. 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. Google ScholarDigital Library
22. 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. Google ScholarDigital Library
23. Tengfei Jiang, Jin Huang, Yuanzhen Wang, Yiying Tong, and Hujun Bao. 2014. Frame Field Singularity Correction for Automatic Hexahedralization. IEEE Trans. on Visualization & Computer Graphics 20, 8 (Aug. 2014), 1189–1199. Google ScholarDigital Library
24. Felix Kaelberer, Matthias Nieser, and Konrad Polthier. 2007. QuadCover – Surface Parameterization using Branched Coverings. Computer Graphics Forum 26, 3 (2007), 375–384.Google ScholarCross Ref
25. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013. Globally Optimal Direction Fields. ACM Trans. Graph. 32, 4, Article 59 (July 2013), 10 pages. Google ScholarDigital Library
26. N. Kowalski, F. Ledoux, and P. Frey. 2014. Block-structured Hexahedral Meshes for CAD Models Using 3D Frame Fields. Procedia Engineering 82, Supplement C (2014), 59–71. 23rd International Meshing Roundtable (IMR23).Google ScholarCross Ref
27. N. Kowalski, F. Ledoux, and P. Frey 2016. Smoothness driven frame field generation for hexahedral meshing. Computer-Aided Design 72, Supplement C (2016), 65 — 77. 23rd International Meshing Roundtable. Google ScholarDigital Library
28. Michael Kremer, David Bommes, Isaak Lim, and Leif Kobbelt. 2014. Advanced Automatic Hexahedral Mesh Generation from Surface Quad Meshes. Springer International Publishing, Cham, 147–164.Google Scholar
29. 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. Google ScholarDigital Library
30. Heng Liu, Paul Zhang, Edward Chien, Justin Solomon, and David Bommes. 2018. Source Code: Singularity-Constrained Octahedral Fields for Hexahedral Meshing, https://graphics.rwth-aachen.de:9000/SCOF/SingularityConstrainedOctahedralFieldsGoogle Scholar
31. Marco Livesu, Alla Sheffer, Nicholas Vining, and Marco Tarini. 2015. Practical Hex-mesh Optimization via Edge-cone Rectification. ACM Trans. Graph. 34, 4, Article 141 (July 2015), 11 pages. Google ScholarDigital Library
32. Max Lyon, David Bommes, and Leif Kobbelt. 2016. HexEx: Robust Hexahedral Mesh Extraction. ACM Trans. Graph. 35, 4, Article 123 (July 2016), 11 pages. Google ScholarDigital Library
33. Loic Marechal. 2009. Advances in Octree-Based All-Hexahedral Mesh Generation: Handling Sharp Features. In Proceedings of the 18th International Meshing Roundtable. Springer, Berlin, Heidelberg, 65–84.Google ScholarCross Ref
34. Tobias Martin, Elaine Cohen, and Robert M. Kirby. 2012. SMI 2012: Mixed-element Volume Completion from NURBS Surfaces. Comput. Graph. 36, 5 (Aug. 2012), 7. Google ScholarDigital Library
35. Karl Merkley, Corey Ernst, Jason Shepherd, and Michael Borden. 2008. Methods and Applications of Generalized Sheet Insertion for Hexahedral Meshing. In Proceedings of the 16th International Meshing Roundtable. Springer Berlin Heidelberg, Berlin, Heidelberg, 233–250.Google ScholarCross Ref
36. N. Mishra and D.G. Sarvate. 2008. A Note on Non-Regular Planar Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing 66 (2008), 17–31.Google Scholar
37. Matthias Nieser, Ulrich Reitebuch, and Konrad Polthier. 2011. CubeCover-Parameterization of 3D Volumes. Computer Graphics Forum 30, 5 (2011), 1397–1406.Google ScholarCross Ref
38. Jonathan Palacios, Lawrence Roy, Prashant Kumar, Chen-Yuan Hsu, Weikai Chen, ChongyangMa, Li-Yi Wei, and Eugene Zhang. 2017. Tensor Field Design in Volumes. ACM Trans. Graph. 36, 6, Article 188 (Nov. 2017), 15 pages. Google ScholarDigital Library
39. Nicolas Ray, Dmitry Sokolov, and Bruno Lévy. 2016. Practical 3D Frame Field Generation. ACM Trans. Graph. 35, 6, Article 233 (Nov. 2016), 9 pages. Google ScholarDigital Library
40. Nicolas Ray, Dmitry Sokolov, Maxence Reberol, Franck Ledoux, and Bruno Lévy 2017. Hexahedral Meshing: Mind the Gap! Technical Report. INRIA.Google Scholar
41. Nicolas Ray, Bruno Vallet, Wan Chiu Li, and Bruno Lévy 2008. N-symmetry Direction Field Design. ACM Trans. Graph. 27, 2, Article 10 (May 2008), 13 pages. Google ScholarDigital Library
42. E. F. Schmeichel and S. L. Hakimi. 1977. On Planar Graphical Degree Sequences. SIAM J. Appl. Math. 32, 3 (1977), 598–609.Google ScholarDigital Library
43. Jason F. Shepherd and Chris R. Johnson. 2008. Hexahedral Mesh Generation Constraints. Eng with Comput. 24, 3 (June 2008), 195–213.Google ScholarCross Ref
44. Dmitry Sokolov and Nicolas Ray. 2015. Fixing normal constraints for generation of polycubes. Technical Report. INRIA.Google Scholar
45. Dmitry Sokolov, Nicolas Ray, Lionel Untereiner, and Bruno Lévy. 2016. Hexahedral-Dominant Meshing. ACM Trans. Graph. 35, 5, Article 157 (June 2016), 23 pages. Google ScholarDigital Library
46. Justin Solomon, Amir Vaxman, and David Bommes. 2017. Boundary Element Octahedral Fields in Volumes. ACM Trans. Graph. 36, 3, Article 28 (May 2017), 16 pages. Google ScholarDigital Library
47. Marco Tarini, Kai Hormann, Paolo Cignoni, and Claudio Montani. 2004. PolyCube-Maps. ACM Trans. Graph. 23, 3 (Aug. 2004), 853–860. Google ScholarDigital Library
48. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional Field Synthesis, Design, and Processing. Computer Graphics Forum 35, 2 (2016), 545–572.Google ScholarCross Ref
49. Ryan Viertel, Matthew L Staten, and Franck Ledoux. 2016. Analysis of Non-Meshable Automatically Generated Frame Fields. Technical Report. Sandia National Laboratories (SNL-NM), Albuquerque, NM (United States).Google Scholar
50. Rui Wang, Shuming Gao, Zhihao Zheng, and Jinming Chen. 2016. Frame Field Guided Topological Improvement for Hex Mesh Using Sheet Operations. Procedia Engineering 163 (2016), 276 — 288. 25th International Meshing Roundtable.Google ScholarCross Ref
51. W. Yu, K. Zhang, and X. Li. 2015. Recent algorithms on automatic hexahedral mesh generation. In 2015 10th International Conference on Computer Science Education (ICCSE). 697–702.Google Scholar
