Optimal Dual Schemes for Adaptive Grid Based Hexmeshing

Hexahedral meshes are a ubiquitous domain for the numerical resolution ofpartial differential equations. Computing a pure hexahedral mesh from anadaptively refined grid is a prominent approach to automatic hexmeshing,and requires the ability to restore the all hex property around the hangingnodes that arise at the interface between cells having different size. Themost advanced tools to accomplish this task are based on mesh dualization.These approaches use topological schemes to regularize the valence of innervertices and edges, such that dualizing the grid yields a pure hexahedralmesh. In this article, we study in detail the dual approach, and proposefour main contributions to it: (i) We enumerate all the possible transitionsthat dual methods must be able to handle, showing that prior schemes donot natively cover all of them; (ii) We show that schemes are internallyasymmetric, therefore not only their construction is ambiguous, but differentimplementative choices lead to hexahedral meshes with different singularstructure; (iii) We explore the combinatorial space of dual schemes,selecting the minimum set that covers all the possible configurations andalso yields the simplest singular structure in the output hexmesh; (iv) Weenlarge the class of adaptive grids that can be transformed into pure hexahedralmeshes, relaxing the tight topological requirements imposed byThe work of Marco Livesu was partly supported by EU ERC Advanced GrantCHANGE No. 694515. Gianmarco Cherchi gratefully acknowledges the support tohis research by PON R&I 2014-2020 AIM1895943-1.Authors' addresses: M. Livesu, CNR IMATI, via De Marini 6, 16149 Genoa, Italy; email:marco.livesu@gmail.com; L. Pitzalis, University of Cagliari and CRS4, via Ospedale72, 09124 Cagliari, Italy; email: luca.pitzalis94@gmail.com; G. Cherchi, University ofCagliari, via Ospedale 72, 09124 Cagliari, Italy; email: g.cherchi@unica.it.Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others thanACMmust be honored. Abstracting with credit is permitted. To copy otherwise, or republish,to post on servers or to redistribute to lists, requires prior specific permissionand/or a fee. Request permissions from permissions@acm.org.© 2021 Association for Computing Machinery.0730-0301/2021/12-ART15 $15.00https://doi.org/10.1145/3494456previous approaches. Our extensive experiments show that our transitionschemes consistently outperform prior art in terms of ability to convergeto a valid solution, amount and distribution of singular mesh edges, and elementcount. Last but not least, we publicly release our code and reveal aconspicuous amount of technical details that were overlooked in previousliterature, lowering an entry barrier that was hard to overcome for practitionersin the field.