{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T19:37:31Z","timestamp":1780688251590,"version":"3.54.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,12,6]],"date-time":"2021-12-06T00:00:00Z","timestamp":1638748800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3494456","type":"journal-article","created":{"date-parts":[[2021,12,6]],"date-time":"2021-12-06T22:30:40Z","timestamp":1638829840000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Optimal Dual Schemes for Adaptive Grid Based Hexmeshing"],"prefix":"10.1145","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4688-7060","authenticated-orcid":false,"given":"Marco","family":"Livesu","sequence":"first","affiliation":[{"name":"CNR IMATI, Genoa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luca","family":"Pitzalis","sequence":"additional","affiliation":[{"name":"University of Cagliari and CRS4, Cagliari, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2029-1119","authenticated-orcid":false,"given":"Gianmarco","family":"Cherchi","sequence":"additional","affiliation":[{"name":"University of Cagliari, Cagliari, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,12,6]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461931"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2018.12.003"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185606"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.1985.276275"},{"key":"e_1_3_1_6_2","first-page":"580","volume-title":"Computer Graphics Forum","author":"Cherchi Gianmarco","year":"2019","unstructured":"Gianmarco Cherchi, Pierre Alliez, Riccardo Scateni, Max Lyon, and David Bommes. 2019. Selective padding for polycube-based hexahedral meshing. Computer Graphics Forum 38, 1 (2019),580\u2013591."},{"key":"e_1_3_1_7_2","unstructured":"CoreForm. 2020. Cubit. Retrieved Nov 22nd 2021 from https:\/\/coreform.com\/products\/coreform-cubit\/."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323029"},{"key":"e_1_3_1_9_2","unstructured":"Dassault Syst\u00e9mes. 2020. Spatial Corp. Retrieved Nov 22nd 2021 from https:\/\/www.spatial.com\/products\/3d-precise-mesh."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925957"},{"key":"e_1_3_1_11_2","unstructured":"Ferrari. 2020. Tech Insight: CFD Design in the 488GTE. Retrieved Nov 22nd 2021 from https:\/\/www.ferrari.com\/en-EN\/competizioni-gt\/articles\/tech-insight-cfd-design-in-the-488-gte."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/3151666.3151677"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2473835"},{"key":"e_1_3_1_14_2","first-page":"135\u2013 149","volume-title":"Computer Graphics Forum","author":"Gao Xifeng","year":"2019","unstructured":"Xifeng Gao, Hanxiao Shen, and Daniele Panozzo. 2019. Feature preserving octree-based hexahedral meshing. Computer Graphics Forum 38, 5 (2019), 135\u2013 149."},{"key":"e_1_3_1_15_2","first-page":"1407","volume-title":"Computer Graphics Forum","author":"Gregson James","year":"2011","unstructured":"James Gregson, Alla Sheffer, and Eugene Zhang. 2011. All-hex mesh generation via volumetric polycube deformation. Computer Graphics Forum 30, 5 (2011), 1407\u20131416."},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(79)90079-0"},{"key":"e_1_3_1_17_2","article-title":"Adaptive all-hexahedral mesh generation based on a hybrid octree and bubble packing","author":"Hu Kangkang","year":"2013","unstructured":"Kangkang Hu, Jin Qian, and Yongjie Zhang. 2013. Adaptive all-hexahedral mesh generation based on a hybrid octree and bubble packing. In Proceedings of the 22nd International Meshing Roundtable.","journal-title":"Proceedings of the 22nd International Meshing Roundtable"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201353"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2602141"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1002\/nme.2470"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-02335-9_9"},{"key":"e_1_3_1_22_2","first-page":"70","volume-title":"Proceedings of the 2013 Signal Processing: Algorithms, Architectures, Arrangements, and Applications","author":"Krishnamoorthy Aravindh","year":"2013","unstructured":"Aravindh Krishnamoorthy and Deepak Menon. 2013. Matrix inversion using Cholesky decomposition. In Proceedings of the 2013 Signal Processing: Algorithms, Architectures, Arrangements, and Applications. IEEE, 70\u201372."},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/1833349.1778856"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366196"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2015.05.004"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201344"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-59958-7_4"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.5555\/3151666.3151691"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392472"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2766905"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508388"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/37402.37422"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04319-2_5"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.proeng.2016.11.007"},{"key":"e_1_3_1_35_2","first-page":"133","volume-title":"Computer Graphics Forum","author":"Marschner Zo\u00eb","year":"2020","unstructured":"Zo\u00eb Marschner, David Palmer, Paul Zhang, and Justin Solomon. 2020. Hexahedral mesh repair via sum-of-squares relaxation. Computer Graphics Forum 39, 5(2020), 133\u2013147."},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/646511.695185"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.2004.28"},{"key":"e_1_3_1_38_2","first-page":"1397\u2013 1406","volume-title":"Computer Graphics Forum","author":"Nieser Matthias","year":"2011","unstructured":"Matthias Nieser, Ulrich Reitebuch, and Konrad Polthier. 2011. Cubecover\u2013parameterization of 3d volumes. Computer Graphics Forum 30, 5 (2011), 1397\u2013 1406."},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14361"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313797"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(95)00013-V"},{"key":"e_1_3_1_42_2","first-page":"195","volume-title":"Proceedings of the 6th International Meshing Roundtable","author":"Schneiders Robert","year":"1997","unstructured":"Robert Schneiders. 1997. An algorithm for the generation of hexahedral element meshes based on an octree technique. In Proceedings of the 6th International Meshing Roundtable. 195\u2013196."},{"key":"e_1_3_1_43_2","article-title":"Algorithms for quadrilateral and hexahedral mesh generation","author":"Schneiders Robert","year":"2000","unstructured":"Robert Schneiders. 2000. Algorithms for quadrilateral and hexahedral mesh generation. In Proceedings of the VKI Lecture Series on Computational Fluid Dynamic.","journal-title":"Proceedings of the VKI Lecture Series on Computational Fluid Dynamic"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1142\/S021819590000022X"},{"key":"e_1_3_1_45_2","volume-title":"Proceedings of the 5th International Meshing Roundtable","author":"Schneiders Robert","year":"1996","unstructured":"Robert Schneiders, Roland Schindler, and Frank Weiler. 1996. Octree-based generation of hexahedral element meshes. In Proceedings of the 5th International Meshing Roundtable. Citeseer."},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-007-0197-5"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620320406"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3065254"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/0927-0256(94)90138-4"},{"key":"e_1_3_1_50_2","unstructured":"Timothy J. Tautges and Sarah E. Knoop. 2003. Topology modification of hexahedral meshes using atomic dual-based operations. In Proceedings of the 12th International Meshing Roundtable (IMR\u201903) . 415\u2013423. http:\/\/imr.sandia.gov\/papers\/abstracts\/Ta301.html."},{"key":"e_1_3_1_51_2","volume-title":"Proceedings of the 2004 International ANSYS Conference","author":"Wang Erke","year":"2004","unstructured":"Erke Wang, Thomas Nelson, and Rainer Rauch. 2004. Back to elements-tetrahedra vs. hexahedra. In Proceedings of the 2004 International ANSYS Conference. Ansys Pennsylvania."},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.buildenv.2021.107717"},{"key":"e_1_3_1_53_2","volume-title":"Automatic Geometry-Adaptive Generation of Quadrilateral and Hexahedral Element Meshes for the FEM","author":"Weiler F.","year":"1996","unstructured":"F. Weiler, R. Schindler, and R. Schneiders. 1996. Automatic Geometry-Adaptive Generation of Quadrilateral and Hexahedral Element Meshes for the FEM. Technical Report. Mississippi State Univ., Mississippi State, MS."},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.finel.2007.03.001"},{"key":"e_1_3_1_55_2","article-title":"Thingi10k: A dataset of 10,000 3d-printing models","author":"Zhou Qingnan","year":"2016","unstructured":"Qingnan Zhou and Alec Jacobson. 2016. Thingi10k: A dataset of 10,000 3d-printing models. arXiv:1605.04797. Retrieved from https:\/\/arxiv.org\/abs\/1605.04797.","journal-title":"arXiv:1605.04797"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494456","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3494456","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:43Z","timestamp":1750193323000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494456"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,6]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3494456"],"URL":"https:\/\/doi.org\/10.1145\/3494456","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,6]]},"assertion":[{"value":"2021-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}