“Locally Meshable Frame Fields” by Bommes and Liu
Conference:
Type:
Title:
- Locally Meshable Frame Fields
Session/Category Title: Surface Reconstruction
Presenter(s)/Author(s):
Moderator(s):
Abstract:
The main robustness issue of state-of-the-art frame field based hexahedral mesh generation algorithms originates from non-meshable topological configurations, which do not admit the construction of an integer-grid map but frequently occur in smooth frame fields. In this article, we investigate the topology of frame fields and derive conditions on their meshability, which are the basis for a novel algorithm to automatically turn a given non-meshable frame field into a similar but locally meshable one. Despite local meshability is only a necessary but not sufficient condition for the stronger requirement of meshability, our algorithm increases the 2% success rate of generating valid integer-grid maps with state-of-the-art methods to 58%, when compared on the challenging HexMe dataset [Beaufort et al. 2022]. The source code of our implementation and the data of our experiments are available at https://lib.algohex.eu.
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 (2015), 70–82.
2. Daniel Asimov. 1993. Notes on the topology of vector fields and flows. Technical Report. Technical report, NASA Ames Research Center, 1993. RNR-93-003.
3. Pierre-Alexandre Beaufort, Maxence Reberol, Heng Liu, Franck Ledoux, and David Bommes. 2022. Hex Me If You Can. Computer Graphics Forum 41, 5 (2022), 125–134.
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 (2013), 1–12.
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. In Computer graphics forum, Vol. 32. Wiley Online Library, 51–76.
6. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3 (2009), 1–10.
7. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2012. Practical mixed-integer optimization for geometry processing. In Curves and Surfaces: 7th International Conference, Avignon, France, June 24–30, 2010, Revised Selected Papers 7. Springer, 193–206.
8. Michael L Brewer, Lori Freitag Diachin, Patrick M Knupp, Thomas Leurent, and Darryl J Melander. 2003. The Mesquite Mesh Quality Improvement Toolkit. In IMR.
9. Hendrik Brückler, David Bommes, and Marcel Campen. 2022a. Volume parametrization quantization for hexahedral meshing. ACM Trans. Graph. 41, 4 (2022), 1–19.
10. Hendrik Brückler, Ojaswi Gupta, Manish Mandad, and Marcel Campen. 2022b. The 3D Motorcycle Complex for Structured Volume Decomposition. In Computer Graphics Forum, Vol. 41. Wiley Online Library, 221–235.
11. Etienne Corman and Keenan Crane. 2019. Symmetric moving frames. ACM Trans. Graph. 38, 4 (2019), 1–16.
12. J Austin Cottrell, Alessandro Reali, Yuri Bazilevs, and Thomas JR Hughes. 2006. Isogeometric analysis of structural vibrations. Computer Methods in Applied Mechanics and Engineering 195, 41–43 (2006), 5257–5296.
13. Xingyi Du, Noam Aigerman, Qingnan Zhou, Shahar Z Kovalsky, Yajie Yan, Danny M Kaufman, and Tao Ju. 2020. Lifting simplices to find injectivity. ACM Trans. Graph. 39, 4 (2020).
14. Xianzhong Fang, Weiwei Xu, Hujun Bao, and Jin Huang. 2016. All-hex meshing using closed-form induced polycube. ACM Trans. Graph. 35, 4 (2016), 1–9.
15. Theodore Frankel. 2011. The Geometry of Physics: An Introduction (3 ed.). Cambridge University Press.
16. Xifeng Gao, Zhigang Deng, and Guoning Chen. 2015. Hexahedral mesh re-parameterization from aligned base-complex. ACM Trans. Graph. 34, 4 (2015), 1–10.
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 (jul 2017).
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 (2017), 1–13.
19. Xifeng Gao, Hanxiao Shen, and Daniele Panozzo. 2019. Feature Preserving Octree-Based Hexahedral Meshing. In Computer graphics forum, Vol. 38. Wiley Online Library, 135–149.
20. Vladimir Garanzha, Igor Kaporin, Liudmila Kudryavtseva, François Protais, David Desobry, and Dmitry Sokolov. 2022. Practical lowest distortion mapping. arXiv preprint arXiv:2201.12112 (2022).
21. Vladimir Garanzha, Igor Kaporin, Liudmila Kudryavtseva, François Protais, Nicolas Ray, and Dmitry Sokolov. 2021. Foldover-free maps in 50 lines of code. ACM Trans. Graph. 40, 4 (2021), 1–16.
22. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.
23. Tobias Günther and Irene Baeza Rojo. 2021. Introduction to vector field topology. In Topological Methods in Data Analysis and Visualization VI. Springer, 289–326.
24. Hao-Xiang Guo, Xiaohan Liu, Dong-Ming Yan, and Yang Liu. 2020. Cut-enhanced PolyCube-maps for feature-aware all-hex meshing. ACM Trans. Graph. 39, 4 (2020).
25. Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2018. Tetrahedral meshing in the wild. ACM Trans. Graph. 37, 4 (2018).
26. 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), 1–11.
27. Jin Huang, Yiying Tong, Hongyu Wei, and Hujun Bao. 2011. Boundary aligned smooth 3D cross-frame field. ACM Trans. Graph. 30, 6 (2011), 1–8.
28. Tengfei Jiang, Jin Huang, Yuanzhen Wang, Yiying Tong, and Hujun Bao. 2014. Frame Field Singularity Correction for Automatic Hexahedralization. IEEE Transactions on Visualization and Computer Graphics 20, 8 (2014), 1189–1199.
29. David A. Kopriva. 2009. Implementing spectral methods for partial differential equations: Algorithms for scientists and engineers. Springer Science & Business Media.
30. Felix Kälberer, Matthias Nieser, and Konrad Polthier. 2007. QuadCover – Surface Parameterization using Branched Coverings. Computer Graphics Forum 26, 3 (2007), 375–384.
31. Lingxiao Li, Paul Zhang, Dmitriy Smirnov, S Mazdak Abulnaga, and Justin Solomon. 2021. Interactive all-hex meshing via cuboid decomposition. ACM Trans. Graph. 40, 6 (2021), 1–17.
32. Yufei Li, Yang Liu, Weiwei Xu, Wenping Wang, and Baining Guo. 2012. All-hex meshing using singularity-restricted field. ACM Trans. Graph. 31, 6 (2012), 1–11.
33. Heng Liu, Paul Zhang, Edward Chien, Justin Solomon, and David Bommes. 2018. Singularity-constrained octahedral fields for hexahedral meshing. ACM Trans. Graph. 37, 4 (2018).
34. Marco Livesu, Nico Pietroni, Enrico Puppo, Alla Sheffer, and Paolo Cignoni. 2020. Loopy-cuts: Practical feature-preserving block decomposition for strongly hex-dominant meshing. ACM Trans. Graph. 39, 4 (2020).
35. Marco Livesu, Luca Pitzalis, and Gianmarco Cherchi. 2021. Optimal dual schemes for adaptive grid based hexmeshing. ACM Trans. Graph. 41, 2 (2021), 1–14.
36. Marco Livesu, Alla Sheffer, Nicholas Vining, and Marco Tarini. 2015. Practical hex-mesh optimization via edge-cone rectification. ACM Trans. Graph. 34, 4 (2015), 1–11.
37. Max Lyon, David Bommes, and Leif Kobbelt. 2016. HexEx: Robust hexahedral mesh extraction. ACM Trans. Graph. 35, 4 (2016), 1–11.
38. Manish Mandad, Ruizhi Chen, David Bommes, and Marcel Campen. 2022. Intrinsic mixed-integer polycubes for hexahedral meshing. Computer aided geometric design 94 (2022).
39. 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.
40. Zoë Marschner, David Palmer, Paul Zhang, and Justin Solomon. 2020. Hexahedral Mesh Repair via Sum-of-Squares Relaxation. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 133–147.
41. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust Field-Aligned Global Parametrization. ACM Trans. Graph. 33, 4, Article 135 (jul 2014).
42. Matthias Nieser, Ulrich Reitebuch, and Konrad Polthier. 2011. Cubecover-parameterization of 3d volumes. In Computer graphics forum, Vol. 30. Wiley Online Library, 1397–1406.
43. David Palmer, David Bommes, and Justin Solomon. 2020. Algebraic representations for volumetric frame fields. ACM Trans. Graph. 39, 2 (2020), 1–17.
44. Nico Pietroni, Marcel Campen, Alla Sheffer, Gianmarco Cherchi, David Bommes, Xifeng Gao, Riccardo Scateni, Franck Ledoux, Jean Remacle, and Marco Livesu. 2022. Hexmesh generation and processing: a survey. ACM Trans. Graph. 42, 2 (2022), 1–44.
45. Luca Pitzalis, Marco Livesu, Gianmarco Cherchi, Enrico Gobbetti, and Riccardo Scateni. 2021. Generalized adaptive refinement for grid-based hexahedral meshing. ACM Trans. Graph. 40, 6 (2021), 1–13.
46. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 2 (2017).
47. Nicolas Ray, Dmitry Sokolov, and Bruno Lévy. 2016. Practical 3D frame field generation. ACM Trans. Graph. 35, 6 (2016), 1–9.
48. Maxence Reberol, Alexandre Chemin, and Jean-François Remacle. 2019. Multiple approaches to frame field correction for CAD models. arXiv preprint arXiv:1912.01248 (2019).
49. Patrick Schmidt, Janis Born, David Bommes, Marcel Campen, and Leif Kobbelt. 2022. TinyAD: Automatic Differentiation in Geometry Processing Made Simple. In Computer graphics forum, Vol. 41. Wiley Online Library, 113–124.
50. Teseo Schneider, Yixin Hu, Xifeng Gao, Jeremie Dumas, Denis Zorin, and Daniele Panozzo. 2022. A large scale comparison of tetrahedral and hexahedral elements for finite element analysis. ACM Trans. Graph (2022).
51. Hanxiao Shen, Leyi Zhu, Ryan Capouellez, Daniele Panozzo, Marcel Campen, and Denis Zorin. 2022. Which Cross Fields Can Be Quadrangulated? Global Parameterization from Prescribed Holonomy Signatures. ACM Trans. Graph. 41, 4 (2022).
52. Dmitry Sokolov and Nicolas Ray. 2015. Fixing normal constraints for generation of polycubes. Technical Report.
53. Justin Solomon, Amir Vaxman, and David Bommes. 2017. Boundary element octahedral fields in volumes. ACM Trans. Graph. 36, 4 (2017).
54. Marco Tarini, Kai Hormann, Paolo Cignoni, and Claudio Montani. 2004. Polycube-maps. ACM Trans. Graph. 23, 3 (2004), 853–860.
55. Ryan Viertel and Braxton Osting. 2019. An Approach to Quad Meshing Based on Harmonic Cross-Valued Maps and the Ginzburg-Landau Theory. SIAM Journal on Scientific Computing 41, 1 (2019), A452–A479.
56. Ryan Viertel, Matthew L Staten, and Franck Ledoux. 2016. Analysis of Non-Meshable Automatically Generated Frame Fields. Technical Report. Sandia National Lab.(SNL-NM), Albuquerque, NM (United States).
57. Andreas Wächter and Lorenz T Biegler. 2006. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical programming 106, 1 (2006), 25–57.
58. David White, Lai Mingwu, Steven Benzley, and Gregory Sjaardema. 1996. Automated Hexahedral Mesh Generation by Virtual Decomposition. Proceedings of the 4th International Meshing Roundtable (1996).
59. Stephen Wright, Jorge Nocedal, et al. 1999. Numerical optimization. Springer Science 35, 67–68 (1999).
60. Kaoji Xu, Xifeng Gao, and Guoning Chen. 2018. Hexahedral mesh quality improvement via edge-angle optimization. Computers & Graphics 70 (2018), 17–27.
61. Wuyi Yu, Kang Zhang, and Xin Li. 2015. Recent algorithms on automatic hexahedral mesh generation. In 2015 10th International Conference on Computer Science & Education (ICCSE). IEEE, 697–702.
62. Paul Zhang, Xinyi Cynthia Fan, and Klara Mundilova. 2023. Local Decomposition of Hexahedral Singular Nodes into Singular Curves. Computer-Aided Design 158 (2023).
