“Interactive all-hex meshing via cuboid decomposition” by Li, Zhang, Smirnov, Abulnaga and Solomon
Conference:
Type(s):
Title:
- Interactive all-hex meshing via cuboid decomposition
Session/Category Title: Meshing
Presenter(s)/Author(s):
Abstract:
Standard PolyCube-based hexahedral (hex) meshing methods aim to deform the input domain into an axis-aligned PolyCube volume with integer corners; if this deformation is bijective, then applying the inverse map to the voxelized PolyCube yields a valid hex mesh. A key challenge in these methods is to maintain the bijectivity of the PolyCube deformation, thus reducing the robustness of these algorithms. In this work, we present an interactive pipeline for hex meshing that sidesteps this challenge by using a new representation of PolyCubes as unions of cuboids. We begin by deforming the input tetrahedral mesh into a near-PolyCube domain whose faces are loosely aligned to the major axis directions. We then build a PolyCube by optimizing the layout of a set of cuboids with user guidance to closely fit the deformed domain. Finally, we construct an inversion-free pullback map from the voxelized PolyCube to the input domain while optimizing for mesh quality metrics. We allow extensive user control over each stage, such as editing the voxelized PolyCube, positioning surface vertices, and exploring the trade-off among competing quality metrics, while also providing automatic alternatives. We validate our method on over one hundred shapes, including models that are challenging for past PolyCube-based and frame-field-based methods. Our pipeline reliably produces hex meshes with quality on par with or better than state-of-the-art. We additionally conduct a user study with 21 participants in which the majority prefer hex meshes they make using our tool to the ones from automatic state-of-the-art methods. This demonstrates the need for intuitive interactive hex meshing tools where the user can dictate the priorities of their mesh.
References:
1. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Transactions On Graphics (TOG) 28, 3 (2009), 1–10.
2. Matteo Bracci, Marco Tarini, Nico Pietroni, Marco Livesu, and Paolo Cignoni. 2019. HexaLab. net: An online viewer for hexahedral meshes. Computer-Aided Design 110 (2019), 24–36.
3. Marcel Campen and Leif Kobbelt. 2014. Dual strip weaving: Interactive design of quad layouts using elastica strips. ACM Transactions on Graphics (TOG) 33, 6 (2014), 1–10.
4. Gianmarco Cherchi, Pierre Alliez, Riccardo Scateni, Max Lyon, and David Bommes. 2019. Selective padding for polycube-based hexahedral meshing. In Computer graphics forum, Vol. 38. Wiley Online Library, 580–591.
5. Etienne Corman and Keenan Crane. 2019. Symmetric moving frames. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–16.
6. Hans-Christian Ebke, Patrick Schmidt, Marcel Campen, and Leif Kobbelt. 2016. Interactively controlled quad remeshing of high resolution 3D models. ACM Transactions on Graphics (TOG) 35, 6 (2016), 1–13.
7. David Eppstein and Elena Mumford. 2010. Steinitz theorems for orthogonal polyhedra. In Proceedings of the twenty-sixth annual symposium on Computational geometry. 429–438.
8. Xianzhong Fang, Weiwei Xu, Hujun Bao, and Jin Huang. 2016. All-hex meshing using closed-form induced polycube. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1–9.
9. Xiao-Ming Fu, Chong-Yang Bai, and Yang Liu. 2016. Efficient volumetric polycube-map construction. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 97–106.
10. Xiao-Ming Fu, Yang Liu, and Baining Guo. 2015. Computing locally injective mappings by advanced MIPS. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–12.
11. Xifeng Gao, Zhigang Deng, and Guoning Chen. 2015. Hexahedral mesh re-parameterization from aligned base-complex. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–10.
12. 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.
13. 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, Article 102 (July 2021), 16 pages.
14. James Gregson, Alla Sheffer, and Eugene Zhang. 2011. All-hex mesh generation via volumetric polycube deformation. In Computer graphics forum, Vol. 30. Wiley Online Library, 1407–1416.
15. Hao-Xiang Guo, Xiaohan Liu, Dong-Ming Yan, and Yang Liu. 2020. Cut-enhanced PolyCube-maps for feature-aware all-hex meshing. ACM Transactions on Graphics (TOG) 39, 4 (2020), 106–1.
16. Yixin Hu, Teseo Schneider, Bolun Wang, Denis Zorin, and Daniele Panozzo. 2020. Fast tetrahedral meshing in the wild. ACM Transactions on Graphics (TOG) 39, 4 (2020), 117–1.
17. Jin Huang, Tengfei Jiang, Zeyun Shi, Yiying Tong, Hujun Bao, and Mathieu Desbrun. 2014. l1-based construction of polycube maps from complex shapes. ACM Transactions on Graphics (TOG) 33, 3 (2014), 1–11.
18. Jin Huang, Yiying Tong, Hongyu Wei, and Hujun Bao. 2011. Boundary aligned smooth 3D cross-frame field. ACM transactions on graphics (TOG) 30, 6 (2011), 1–8.
19. Wenzel Jakob, Marco Tarini, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Instant field-aligned meshes. ACM Trans. Graph. 34, 6 (2015), 189–1.
20. Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014).
21. Juncong Lin, Xiaogang Jin, Zhengwen Fan, and Charlie CL Wang. 2008. Automatic polycube-maps. In International Conference on Geometric Modeling and Processing. Springer, 3–16.
22. 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), 93–1.
23. Lei Liu, Yongjie Zhang, Yang Liu, and Wenping Wang. 2015. Feature-preserving T-mesh construction using skeleton-based polycubes. Computer-Aided Design 58 (2015), 162–172.
24. Marco Livesu, Nico Pietroni, Enrico Puppo, Alla Sheffer, and Paolo Cignoni. 2020. LoopyCuts: Practical Feature-Preserving Block Decomposition for Strongly Hex-Dominant Meshing. ACM Trans. Graph. 39, 4, Article 121 (July 2020), 17 pages.
25. Marco Livesu, Alla Sheffer, Nicholas Vining, and Marco Tarini. 2015. Practical hex-mesh optimization via edge-cone rectification. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–11.
26. Marco Livesu, Nicholas Vining, Alla Sheffer, James Gregson, and Riccardo Scateni. 2013. PolyCut: monotone graph-cuts for PolyCube base-complex construction. ACM Transactions on Graphics (TOG) 32, 6 (2013), 1–12.
27. 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.
28. Matthias Nieser, Ulrich Reitebuch, and Konrad Polthier. 2011. Cubecover-parameterization of 3d volumes. In Computer graphics forum, Vol. 30. Wiley Online Library, 1397–1406.
29. David Palmer, David Bommes, and Justin Solomon. 2020. Algebraic Representations for Volumetric Frame Fields. ACM Trans. Graph. 39, 2, Article 16 (April 2020), 17 pages.
30. Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems 32, H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. Fox, and R. Garnett (Eds.). Curran Associates, Inc., 8024–8035. http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf
31. François Protais, Maxence Reberol, Nicolas Ray, Etienne Corman, Franck Ledoux, and Dmitry Sokolov. 2020. Robust Quantization for Polycube Maps. (2020).
32. Roshan Quadros. 2021. The CUBIT Geometry and Meshing Toolkit. https://cubit.sandia.gov/.
33. Nicolas Ray, Dmitry Sokolov, and Bruno Lévy. 2016. Practical 3D frame field generation. ACM Transactions on Graphics (TOG) 35, 6 (2016), 1–9.
34. Jason F Shepherd and Chris R Johnson. 2008. Hexahedral mesh generation constraints. Engineering with Computers 24, 3 (2008), 195–213.
35. Dmitriy Smirnov, Matthew Fisher, Vladimir G Kim, Richard Zhang, and Justin Solomon. 2020. Deep parametric shape predictions using distance fields. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 561–570.
36. Dmitry Sokolov and Nicolas Ray. 2015. Fixing normal constraints for generation of polycubes. Research Report. LORIA. https://hal.inria.fr/hal-01211408
37. Justin Solomon, Amir Vaxman, and David Bommes. 2017. Boundary element octahedral fields in volumes. ACM Transactions on Graphics (TOG) 36, 4 (2017), 1.
38. Kenshi Takayama. 2019. Dual sheet meshing: An interactive approach to robust hexa-hedralization. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 37–48.
39. Marco Tarini, Kai Hormann, Paolo Cignoni, and Claudio Montani. 2004. Polycube-maps. ACM transactions on graphics (TOG) 23, 3 (2004), 853–860.
40. Shubham Tulsiani, Hao Su, Leonidas J Guibas, Alexei A Efros, and Jitendra Malik. 2017. Learning shape abstractions by assembling volumetric primitives. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2635–2643.
41. 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).
42. Yang Yang, Xiao-Ming Fu, and Ligang Liu. 2019. Computing Surface PolyCube-Maps by Constrained Voxelization. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 299–309.
43. Wuyi Yu, Kang Zhang, Shenghua Wan, and Xin Li. 2014. Optimizing polycube domain construction for hexahedral remeshing. Computer-Aided Design 46 (2014), 58–68.
44. Shangyou Zhang. 2005. Subtetrahedral test for the positive Jacobian of hexahedral elements. preprint (2005).
45. Hui Zhao, Xuan Li, Wencheng Wang, Xiaoling Wang, Shaodong Wang, Na Lei, and Xiangfeng Gu. 2019. Polycube Shape Space. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 311–322.
