More Web Proxy on the site http://driver.im/

research-article

Open access

Locally Meshable Frame Fields

Authors:

David BommesAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 42, Issue 4

Article No.: 112, Pages 1 - 20

https://doi.org/10.1145/3592457

Published: 26 July 2023 Publication History

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.

Supplementary Material

ZIP File (papers_871-supplemental.zip)

supplemental material

Download
422.32 MB

MP4 File (papers_871_VOD.mp4)

presentation

Download
331.15 MB

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.

Digital 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. 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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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).

Digital 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 (2016), 1--9.

Digital Library

[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.

Digital 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 (jul 2017).

Digital 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 (2017), 1--13.

Digital Library

[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.

Digital Library

[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).

Digital Library

[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).

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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).

Digital Library

[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).

Digital Library

[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.

Digital Library

[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.

Digital Library

[37]

Max Lyon, David Bommes, and Leif Kobbelt. 2016. HexEx: Robust hexahedral mesh extraction. ACM Trans. Graph. 35, 4 (2016), 1--11.

Digital Library

[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).

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[46]

Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 2 (2017).

Digital Library

[47]

Nicolas Ray, Dmitry Sokolov, and Bruno Lévy. 2016. Practical 3D frame field generation. ACM Trans. Graph. 35, 6 (2016), 1--9.

Digital Library

[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).

Digital Library

[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).

Digital Library

[54]

Marco Tarini, Kai Hormann, Paolo Cignoni, and Claudio Montani. 2004. Polycube-maps. ACM Trans. Graph. 23, 3 (2004), 853--860.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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).

Cited By

Gao JXiao ZShen SXu CCai JXu G(2025)Improved hexahedral mesh generation from quadrilateral surface meshesComputers & Structures10.1016/j.compstruc.2024.107620307(107620)Online publication date: Jan-2025
https://doi.org/10.1016/j.compstruc.2024.107620
Zheng XDuan JLei NLuo Z(2025)Feature-aware Singularity Structure Optimization for Hex MeshComputer-Aided Design10.1016/j.cad.2024.103825180(103825)Online publication date: Mar-2025
https://doi.org/10.1016/j.cad.2024.103825
Nigolian VCampen MBommes D(2024)A Progressive Embedding Approach to Bijective Tetrahedral Maps driven by Cluster Mesh TopologyACM Transactions on Graphics10.1145/368799243:6(1-14)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687992
Show More Cited By

Index Terms

Locally Meshable Frame Fields
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling

Recommendations

Singularity-constrained octahedral fields for hexahedral meshing

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 ...
Smoothness driven frame field generation for hexahedral meshing

For many years, providing an algorithm to generate hexahedral meshes that fulfill minimal geometric criteria (boundary-alignment, minimum of singularity vertices) and that is not limited to a category of geometries has been an open issue. In the past ...
Volume subdivision based hexahedral finite element meshing of domains with interior 2-manifold boundaries
AFRIGRAPH '06: Proceedings of the 4th international conference on Computer graphics, virtual reality, visualisation and interaction in Africa

We present a subdivision based algorithm for multi-resolution Hexahedral meshing. The input is a bounding rectilinear domain with a set of embedded 2-manifold boundaries of arbitrary genus and topology. The algorithm first constructs a simplified ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 42, Issue 4

August 2023

1912 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3609020

Issue’s Table of Contents

Copyright © 2023 Owner/Author(s).

This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 July 2023

Published in TOG Volume 42, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
746
Total Downloads

Downloads (Last 12 months)457
Downloads (Last 6 weeks)49

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gao JXiao ZShen SXu CCai JXu G(2025)Improved hexahedral mesh generation from quadrilateral surface meshesComputers & Structures10.1016/j.compstruc.2024.107620307(107620)Online publication date: Jan-2025
https://doi.org/10.1016/j.compstruc.2024.107620
Zheng XDuan JLei NLuo Z(2025)Feature-aware Singularity Structure Optimization for Hex MeshComputer-Aided Design10.1016/j.cad.2024.103825180(103825)Online publication date: Mar-2025
https://doi.org/10.1016/j.cad.2024.103825
Nigolian VCampen MBommes D(2024)A Progressive Embedding Approach to Bijective Tetrahedral Maps driven by Cluster Mesh TopologyACM Transactions on Graphics10.1145/368799243:6(1-14)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687992
Hirose YGillespie MBonilla Fominaya AMcCann J(2024)Solid KnittingACM Transactions on Graphics10.1145/365812343:4(1-15)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658123
Mitra RJimenez Berumen EHofmann MChien E(2024)Singular Foliations for Knit Graph DesignACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657487(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657487
Sella EFiebelman GAtia NAverbuch-Elor H(2024)Spice·E: Structural Priors in 3D Diffusion using Cross-Entity AttentionACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657461(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657461
Hu JHui KLiu ZZhang HFu C(2024)CNS-Edit: 3D Shape Editing via Coupled Neural Shape OptimizationACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657412(1-12)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657412
Yu XQin CShen DYang SMa HZhu HZhang XBaeza-Yates RBonchi F(2024)RIGL: A Unified Reciprocal Approach for Tracing the Independent and Group Learning ProcessesProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671711(4047-4058)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671711
Brückler HBommes DCampen M(2024)Integer‐Sheet‐Pump Quantization for Hexahedral MeshingComputer Graphics Forum10.1111/cgf.1513143:5Online publication date: 31-Jul-2024
https://doi.org/10.1111/cgf.15131
Hertzmann A(2024)New Insights in Smooth Occluding Contours for Nonphotorealistic RenderingIEEE Computer Graphics and Applications10.1109/MCG.2023.333878444:1(76-85)Online publication date: 26-Jan-2024
https://dl.acm.org/doi/10.1109/MCG.2023.3338784
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents