{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T19:37:36Z","timestamp":1780688256900,"version":"3.54.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T00:00:00Z","timestamp":1638316800000},"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":[[2021,12]]},"abstract":"<jats:p>Due to their nice numerical properties, conforming hexahedral meshes are considered a prominent computational domain for simulation tasks. However, the automatic decomposition of a general 3D volume into a small number of hexahedral elements is very challenging. Methods that create an adaptive Cartesian grid and convert it into a conforming mesh offer superior robustness and are the only ones concretely used in the industry. Topological schemes that permit this conversion can be applied only if precise compatibility conditions among grid elements are observed. Some of these conditions are local, hence easy to formulate; others are not and are much harder to satisfy. State-of-the-art approaches fulfill these conditions by prescribing additional refinement based on special building rules for octrees. These methods operate in a restricted space of solutions and are prone to severely over-refine the input grids, creating a bottleneck in the simulation pipeline. In this article, we introduce a novel approach to transform a general adaptive grid into a new grid meeting hexmeshing criteria, without resorting to tree rules. Our key insight is that we can formulate all compatibility conditions as linear constraints in an integer programming problem by choosing the proper set of unknowns. Since we operate in a broader solution space, we are able to meet topological hexmeshing criteria at a much coarser scale than methods using octrees, also supporting generalized grids of any shape or topology. We demonstrate the superiority of our approach for both traditional grid-based hexmeshing and adaptive polycube-based hexmeshing. In all our experiments, our method never prescribed more refinement than the prior art and, in the average case, it introduced close to half the number of extra cells.<\/jats:p>","DOI":"10.1145\/3478513.3480508","type":"journal-article","created":{"date-parts":[[2021,12,10]],"date-time":"2021-12-10T18:29:20Z","timestamp":1639160960000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Generalized adaptive refinement for grid-based hexahedral meshing"],"prefix":"10.1145","volume":"40","author":[{"given":"Luca","family":"Pitzalis","sequence":"first","affiliation":[{"name":"University of Cagliari and CRS4, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Livesu","sequence":"additional","affiliation":[{"name":"IMATI-CNR, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gianmarco","family":"Cherchi","sequence":"additional","affiliation":[{"name":"University of Cagliari, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Enrico","family":"Gobbetti","sequence":"additional","affiliation":[{"name":"CRS4, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Riccardo","family":"Scateni","sequence":"additional","affiliation":[{"name":"University of Cagliari, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,12,10]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461931"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.proeng.2015.10.123"},{"key":"e_1_2_2_3_1","unstructured":"Arthur Bawin Fran\u00e7ois Henrotte and Jean-Fran\u00e7ois Remacle. 2020. Automatic feature-preserving size field for 3D mesh generation. arXiv:2009.03984 [math.NA]  Arthur Bawin Fran\u00e7ois Henrotte and Jean-Fran\u00e7ois Remacle. 2020. Automatic feature-preserving size field for 3D mesh generation. arXiv:2009.03984 [math.NA]"},{"key":"e_1_2_2_4_1","volume-title":"Proceedings, 4th international meshing roundtable","volume":"17","author":"Benzley Steven E","year":"1995","unstructured":"Steven E Benzley , Ernest Perry , Karl Merkley , Brett Clark , and Greg Sjaardama . 1995 . A comparison of all hexagonal and all tetrahedral finite element meshes for elastic and elasto-plastic analysis . In Proceedings, 4th international meshing roundtable , Vol. 17 . Citeseer, 179--191. Steven E Benzley, Ernest Perry, Karl Merkley, Brett Clark, and Greg Sjaardama. 1995. A comparison of all hexagonal and all tetrahedral finite element meshes for elastic and elasto-plastic analysis. In Proceedings, 4th international meshing roundtable, Vol. 17. Citeseer, 179--191."},{"key":"e_1_2_2_5_1","volume-title":"Meeting the challenge for automated conformal hexahedral meshing. In Proc. 9th international meshing roundtable. Springer, 11--20","author":"Blacker Ted","year":"2000","unstructured":"Ted Blacker . 2000 . Meeting the challenge for automated conformal hexahedral meshing. In Proc. 9th international meshing roundtable. Springer, 11--20 . Ted Blacker. 2000. Meeting the challenge for automated conformal hexahedral meshing. In Proc. 9th international meshing roundtable. Springer, 11--20."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2018.12.003"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13593"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12959"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/156482.156499"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323029"},{"key":"e_1_2_2_11_1","unstructured":"Distene SAS. 2020. MeshGems. http:\/\/www.meshgems.com\/volume-meshing-meshgems-hexa.html  Distene SAS. 2020. MeshGems. http:\/\/www.meshgems.com\/volume-meshing-meshgems-hexa.html"},{"key":"e_1_2_2_12_1","volume-title":"Proc. International ANSYS conference.","author":"Erke Wang Thomas Nelson","year":"2004","unstructured":"Thomas Nelson Erke Wang and Rainer Rauch . 2004 . Back to elements-tetrahedra vs. hexahedra . In Proc. International ANSYS conference. Thomas Nelson Erke Wang and Rainer Rauch. 2004. Back to elements-tetrahedra vs. hexahedra. In Proc. International ANSYS conference."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925957"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3151666.3151677"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13795"},{"key":"e_1_2_2_16_1","volume-title":"Foldover-free maps in 50 lines of code. arXiv preprint arXiv:2102.03069","author":"Garanzha Vladimir","year":"2021","unstructured":"Vladimir Garanzha , Igor Kaporin , Liudmila Kudryavtseva , Fran\u00e7ois Protais , Nicolas Ray , and Dmitry Sokolov . 2021. Foldover-free maps in 50 lines of code. arXiv preprint arXiv:2102.03069 ( 2021 ). Vladimir Garanzha, Igor Kaporin, Liudmila Kudryavtseva, Fran\u00e7ois Protais, Nicolas Ray, and Dmitry Sokolov. 2021. Foldover-free maps in 50 lines of code. arXiv preprint arXiv:2102.03069 (2021)."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.02015.x"},{"key":"e_1_2_2_18_1","unstructured":"LLC Gurobi Optimization. 2020. Gurobi Optimizer Reference Manual. http:\/\/www.gurobi.com  LLC Gurobi Optimization. 2020. Gurobi Optimizer Reference Manual. http:\/\/www.gurobi.com"},{"key":"e_1_2_2_19_1","volume-title":"Proc. 22nd International Meshing Roundtable - Research Notes. Sandia National Laboratories, 5B3:1--5B3:5.","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 Proc. 22nd International Meshing Roundtable - Research Notes. Sandia National Laboratories, 5B3:1--5B3:5. Kangkang Hu, Jin Qian, and Yongjie Zhang. 2013. Adaptive all-hexahedral mesh generation based on a hybrid octree and bubble packing. In Proc. 22nd International Meshing Roundtable - Research Notes. Sandia National Laboratories, 5B3:1--5B3:5."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2016.03.021"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602141"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.2470"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.250"},{"key":"e_1_2_2_24_1","volume-title":"Proc. 22nd International Meshing Roundtable","author":"Kremer Michael","unstructured":"Michael Kremer , David Bommes , Isaak Lim , and Leif Kobbelt . 2014. Advanced automatic hexahedral mesh generation from surface quad meshes . In Proc. 22nd International Meshing Roundtable . Springer , 147--164. Michael Kremer, David Bommes, Isaak Lim, and Leif Kobbelt. 2014. Advanced automatic hexahedral mesh generation from surface quad meshes. In Proc. 22nd International Meshing Roundtable. Springer, 147--164."},{"key":"e_1_2_2_25_1","volume-title":"Proc. 16th International Meshing Roundtable","author":"Ledoux Franck","unstructured":"Franck Ledoux and Jean-Christophe Weill . 2008. An extension of the reliable whisker weaving algorithm . In Proc. 16th International Meshing Roundtable . Springer , 215--232. Franck Ledoux and Jean-Christophe Weill. 2008. An extension of the reliable whisker weaving algorithm. In Proc. 16th International Meshing Roundtable. Springer, 215--232."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366196"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2015.05.004"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201344"},{"key":"e_1_2_2_29_1","first-page":"64","article-title":"Cinolib: A Generic Programming Header Only C++ Library for Processing Polygonal and Polyhedral Meshes","author":"Livesu Marco","year":"2019","unstructured":"Marco Livesu . 2019 . Cinolib: A Generic Programming Header Only C++ Library for Processing Polygonal and Polyhedral Meshes . Transactions on Computational Science XXXIV 34 (2019), 64 -- 76 . https:\/\/github.com\/mlivesu\/cinolib\/. Marco Livesu. 2019. Cinolib: A Generic Programming Header Only C++ Library for Processing Polygonal and Polyhedral Meshes. Transactions on Computational Science XXXIV 34 (2019), 64--76. https:\/\/github.com\/mlivesu\/cinolib\/.","journal-title":"Transactions on Computational Science"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3151666.3151691"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392472"},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Marco Livesu Luca Pitzalis and Gianmarco Cherchi. 2021. Optimal Dual Schemes for Adaptive Grid Based Hexmeshing. arXiv:2103.07745 [cs.GR]  Marco Livesu Luca Pitzalis and Gianmarco Cherchi. 2021. Optimal Dual Schemes for Adaptive Grid Based Hexmeshing. arXiv:2103.07745 [cs.GR]","DOI":"10.1145\/3494456"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766905"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508388"},{"key":"e_1_2_2_35_1","volume-title":"Proc. 18th international meshing roundtable","author":"Mar\u00e9chal Lo\u00efc","unstructured":"Lo\u00efc Mar\u00e9chal . 2009. Advances in octree-based all-hexahedral mesh generation: handling sharp features . In Proc. 18th international meshing roundtable . Springer , 65--84. Lo\u00efc Mar\u00e9chal. 2009. Advances in octree-based all-hexahedral mesh generation: handling sharp features. In Proc. 18th international meshing roundtable. Springer, 65--84."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/142675.142720"},{"key":"e_1_2_2_37_1","volume-title":"Proc. 9th international meshing roundtable. 267--291","author":"Owen Steven J","year":"1998","unstructured":"Steven J Owen . 1998 . A survey of unstructured mesh generation technology . In Proc. 9th international meshing roundtable. 267--291 . Steven J Owen. 1998. A survey of unstructured mesh generation technology. In Proc. 9th international meshing roundtable. 267--291."},{"key":"e_1_2_2_38_1","volume-title":"Hex-dominant meshing: mind the gap! Computer-Aided Design 102","author":"Ray Nicolas","year":"2018","unstructured":"Nicolas Ray , Dmitry Sokolov , Maxence Reberol , Franck Ledoux , and Bruno L\u00e9vy . 2018. Hex-dominant meshing: mind the gap! Computer-Aided Design 102 ( 2018 ), 94--103. Nicolas Ray, Dmitry Sokolov, Maxence Reberol, Franck Ledoux, and Bruno L\u00e9vy. 2018. Hex-dominant meshing: mind the gap! Computer-Aided Design 102 (2018), 94--103."},{"key":"e_1_2_2_39_1","unstructured":"Teseo Schneider Yixin Hu Xifeng Gao Jeremie Dumas Denis Zorin and Daniele Panozzo. 2019. A Large Scale Comparison of Tetrahedral and Hexahedral Elements for Finite Element Analysis. arXiv:1903.09332 [cs.NA]  Teseo Schneider Yixin Hu Xifeng Gao Jeremie Dumas Denis Zorin and Daniele Panozzo. 2019. A Large Scale Comparison of Tetrahedral and Hexahedral Elements for Finite Element Analysis. arXiv:1903.09332 [cs.NA]"},{"key":"e_1_2_2_40_1","volume-title":"A grid-based algorithm for the generation of hexahedral element meshes. Engineering with computers 12, 3-4","author":"Schneiders Robert","year":"1996","unstructured":"Robert Schneiders . 1996. A grid-based algorithm for the generation of hexahedral element meshes. Engineering with computers 12, 3-4 ( 1996 ), 168--177. Robert Schneiders. 1996. A grid-based algorithm for the generation of hexahedral element meshes. Engineering with computers 12, 3-4 (1996), 168--177."},{"key":"e_1_2_2_41_1","volume-title":"Proc. 6th International Meshing Roundtable. 195--196","author":"Schneiders Robert","year":"1997","unstructured":"Robert Schneiders . 1997 . An algorithm for the generation of hexahedral element meshes based on an octree technique . In Proc. 6th International Meshing Roundtable. 195--196 . Robert Schneiders. 1997. An algorithm for the generation of hexahedral element meshes based on an octree technique. In Proc. 6th International Meshing Roundtable. 195--196."},{"key":"e_1_2_2_42_1","volume-title":"Proc. VKI Lecture Series on Computational Fluid Dynamic. 2000--2004","author":"Schneiders Robert","year":"2000","unstructured":"Robert Schneiders . 2000 a. Algorithms for quadrilateral and hexahedral mesh generation . In Proc. VKI Lecture Series on Computational Fluid Dynamic. 2000--2004 . Robert Schneiders. 2000a. Algorithms for quadrilateral and hexahedral mesh generation. In Proc. VKI Lecture Series on Computational Fluid Dynamic. 2000--2004."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1142\/S021819590000022X"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(95)00013-V"},{"key":"e_1_2_2_45_1","volume-title":"Proc. 5th International Meshing Roundtable. Sandia National Labs, 205--216","author":"Schneiders Robert","year":"1996","unstructured":"Robert Schneiders , Roland Schindler , and Frank Weiler . 1996 . Octree-based generation of hexahedral element meshes . In Proc. 5th International Meshing Roundtable. Sandia National Labs, 205--216 . Robert Schneiders, Roland Schindler, and Frank Weiler. 1996. Octree-based generation of hexahedral element meshes. In Proc. 5th International Meshing Roundtable. Sandia National Labs, 205--216."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-007-0197-5"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/3225268.3225437"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.2679"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186562.1015810"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.139"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.buildenv.2021.107717"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2017.10.001"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13100"},{"key":"e_1_2_2_54_1","volume-title":"Adaptive and quality quadrilateral\/hexahedral meshing from volumetric data. Computer methods in applied mechanics and engineering 195, 9-12","author":"Zhang Yongjie","year":"2006","unstructured":"Yongjie Zhang and Chandrajit Bajaj . 2006. Adaptive and quality quadrilateral\/hexahedral meshing from volumetric data. Computer methods in applied mechanics and engineering 195, 9-12 ( 2006 ), 942--960. Yongjie Zhang and Chandrajit Bajaj. 2006. Adaptive and quality quadrilateral\/hexahedral meshing from volumetric data. Computer methods in applied mechanics and engineering 195, 9-12 (2006), 942--960."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3478513.3480508","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3478513.3480508","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:11:49Z","timestamp":1750191109000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3478513.3480508"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12]]},"references-count":54,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["10.1145\/3478513.3480508"],"URL":"https:\/\/doi.org\/10.1145\/3478513.3480508","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12]]},"assertion":[{"value":"2021-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}