thumbnail

Optimal Dual Schemes for Adaptive Grid Based Hexmeshing

Marco Livesu, Luca Pitzalis, and Gianmarco Cherchi

December 2021

Abstract

Hexahedral meshes are a ubiquitous domain for the numerical resolution of partial differential equations. Computing a pure hexahedral mesh from an adaptively refined grid is a prominent approach to automatic hexmeshing, and requires the ability to restore the all hex property around the hanging nodes that arise at the interface between cells having different size. The most advanced tools to accomplish this task are based on mesh dualization. These approaches use topological schemes to regularize the valence of inner vertices and edges, such that dualizing the grid yields a pure hexahedral mesh. In this article, we study in detail the dual approach, and propose four main contributions to it: (i) We enumerate all the possible transitions that dual methods must be able to handle, showing that prior schemes do not natively cover all of them; (ii) We show that schemes are internally asymmetric, therefore not only their construction is ambiguous, but different implementative choices lead to hexahedral meshes with different singular structure; (iii) We explore the combinatorial space of dual schemes, selecting the minimum set that covers all the possible configurations and also yields the simplest singular structure in the output hexmesh; (iv) We enlarge the class of adaptive grids that can be transformed into pure hexahedral meshes, relaxing one of the tight topological requirements imposed by previous approaches. Our extensive experiments show that our transition schemes consistently outperform prior art in terms of ability to converge to a valid solution, amount and distribution of singular mesh edges, and element count. Last but not least, we publicly release our code and reveal a conspicuous amount of technical details that were overlooked in previous literature, lowering an entry barrier that was hard to overcome for practitioners in the field.

Reference and download information

Marco Livesu, Luca Pitzalis, and Gianmarco Cherchi. Optimal Dual Schemes for Adaptive Grid Based Hexmeshing. ACM Transactions on Graphics, 41(2): 15:1-15:14, December 2021. DOI: 10.1145/3494456.

Related multimedia productions

Bibtex citation record

@article{Livesu:2021:ODS,
    author = {Marco Livesu and Luca Pitzalis and Gianmarco Cherchi},
    title = {Optimal Dual Schemes for Adaptive Grid Based Hexmeshing},
    journal = {ACM Transactions on Graphics},
    volume = {41},
    number = {2},
    pages = {15:1--15:14},
    month = {December},
    year = {2021},
    issn = {0730-0301},
    abstract = {Hexahedral meshes are a ubiquitous domain for the numerical resolution of partial differential equations. Computing a pure hexahedral mesh from an adaptively refined grid is a prominent approach to automatic hexmeshing, and requires the ability to restore the all hex property around the hanging nodes that arise at the interface between cells having different size. The most advanced tools to accomplish this task are based on mesh dualization. These approaches use topological schemes to regularize the valence of inner vertices and edges, such that dualizing the grid yields a pure hexahedral mesh. In this article, we study in detail the dual approach, and propose four main contributions to it: (i) We enumerate all the possible transitions that dual methods must be able to handle, showing that prior schemes do not natively cover all of them; (ii) We show that schemes are internally asymmetric, therefore not only their construction is ambiguous, but different implementative choices lead to hexahedral meshes with different singular structure; (iii) We explore the combinatorial space of dual schemes, selecting the minimum set that covers all the possible configurations and also yields the simplest singular structure in the output hexmesh; (iv) We enlarge the class of adaptive grids that can be transformed into pure hexahedral meshes, relaxing one of the tight topological requirements imposed by previous approaches. Our extensive experiments show that our transition schemes consistently outperform prior art in terms of ability to converge to a valid solution, amount and distribution of singular mesh edges, and element count. Last but not least, we publicly release our code and reveal a conspicuous amount of technical details that were overlooked in previous literature, lowering an entry barrier that was hard to overcome for practitioners in the field.},
    doi = {10.1145/3494456},
    url = {http://vic.crs4.it/vic/cgi-bin/bib-page.cgi?id='Livesu:2021:ODS'},
}