{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T10:17:30Z","timestamp":1758709050362,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,3,21]],"date-time":"2023-03-21T00:00:00Z","timestamp":1679356800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["ERC-2015-AdG-694020"],"award-info":[{"award-number":["ERC-2015-AdG-694020"]}]},{"name":"Fonds de la Recherche Scientifique de Belgique"},{"name":"European Union\u2019s Horizon 2020","award":["853343"],"award-info":[{"award-number":["853343"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2023,3,31]]},"abstract":"<jats:p>We present a robust technique to build a topologically optimal all-hexahedral layer on the boundary of a model with arbitrarily complex ridges and corners. The generated boundary layer mesh strictly respects the geometry of the input surface mesh, and it is optimal in the sense that the hexahedral valences of the boundary edges are as close as possible to their ideal values (local dihedral angle divided by 90\u00b0). Starting from a valid watertight surface mesh (all-quad in practice), we build a global optimization integer programming problem to minimize the mismatch between the hexahedral valences of the boundary edges and their ideal values. The formulation of the integer programming problem relies on the duality between boundary hexahedral configurations and triangulations of the disk, which we reframe in terms of integer constraints. The global problem is solved efficiently by performing combinatorial branch-and-bound searches on a series of sub-problems defined in the vicinity of complicated ridges\/corners, where the local mesh topology is necessarily irregular because of the inherent constraints in hexahedral meshes. From the integer solution, we build the topology of the all-hexahedral layer, and the mesh geometry is computed by untangling\/smoothing. Our approach is fully automated, topologically robust, and fast.<\/jats:p>","DOI":"10.1145\/3577196","type":"journal-article","created":{"date-parts":[[2022,12,20]],"date-time":"2022-12-20T12:52:51Z","timestamp":1671540771000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Robust Topological Construction of All-hexahedral Boundary Layer Meshes"],"prefix":"10.1145","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7065-9191","authenticated-orcid":false,"given":"Maxence","family":"Reberol","sequence":"first","affiliation":[{"name":"Universit\u00e9 catholique de Louvain, Louvain-la-Neuve, Belgique"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7377-3491","authenticated-orcid":false,"given":"Kilian","family":"Verhetsel","sequence":"additional","affiliation":[{"name":"Universit\u00e9 catholique de Louvain, Louvain-la-Neuve, Belgique"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1578-1367","authenticated-orcid":false,"given":"Fran\u00e7ois","family":"Henrotte","sequence":"additional","affiliation":[{"name":"Universit\u00e9 catholique de Louvain, Louvain-la-Neuve, Belgique"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3190-1341","authenticated-orcid":false,"given":"David","family":"Bommes","sequence":"additional","affiliation":[{"name":"University of Bern, Bern, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4798-6458","authenticated-orcid":false,"given":"Jean-Fran\u00e7ois","family":"Remacle","sequence":"additional","affiliation":[{"name":"Universit\u00e9 catholique de Louvain, Louvain-la-Neuve, Belgique"}]}],"member":"320","published-online":{"date-parts":[[2023,3,21]]},"reference":[{"key":"e_1_3_5_2_2","volume-title":"Proceedings of the 12th International Meshing Roundtable","author":"Brewer Michael L.","year":"2003","unstructured":"Michael L. Brewer, Lori Freitag Diachin, Patrick M. Knupp, Thomas Leurent, and Darryl J. Melander. 2003. The mesquite mesh quality improvement toolkit. In Proceedings of the 12th International Meshing Roundtable."},{"issue":"2","key":"e_1_3_5_3_2","first-page":"323","article-title":"Fast generation of planar graphs","volume":"58","author":"Brinkmann Gunnar","year":"2007","unstructured":"Gunnar Brinkmann, Brendan D. McKay, et\u00a0al. 2007. Fast generation of planar graphs. MATCH Commun. Math. Comput. Chem. 58, 2 (2007), 323\u2013357.","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"e_1_3_5_4_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. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 580\u2013591."},{"issue":"4","key":"e_1_3_5_5_2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1080\/12506559.2000.10511454","article-title":"G\u00e9n\u00e9ration de maillage et adaptation de maillage par optimisation locale","volume":"9","author":"Coupez Thierry","year":"2000","unstructured":"Thierry Coupez. 2000. G\u00e9n\u00e9ration de maillage et adaptation de maillage par optimisation locale. Revue Europ\u00e9enne Des \u00e9l\u00e9ments Finis 9, 4 (2000), 403\u2013423.","journal-title":"Revue Europ\u00e9enne Des \u00e9l\u00e9ments Finis"},{"key":"e_1_3_5_6_2","first-page":"195","article-title":"How to subdivide pyramids, prisms, and hexahedra into tetrahedra.","volume":"99","author":"Dompierre Julien","year":"1999","unstructured":"Julien Dompierre, Paul Labb\u00e9, Marie-Gabrielle Vallet, and Ricardo Camarero. 1999. How to subdivide pyramids, prisms, and hexahedra into tetrahedra. IMR 99 (1999), 195.","journal-title":"IMR"},{"key":"e_1_3_5_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-014-9624-3"},{"key":"e_1_3_5_8_2","first-page":"135","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. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 135\u2013149."},{"key":"e_1_3_5_9_2","article-title":"Foldover-free maps in 50 lines of code","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).","journal-title":"arXiv preprint arXiv:2102.03069"},{"key":"e_1_3_5_10_2","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0207(20000910\/20)49:1\/2<193::aid-nme929>3.0.co;2-r"},{"key":"e_1_3_5_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/nme.2579"},{"key":"e_1_3_5_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024177"},{"key":"e_1_3_5_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-02335-9_19"},{"key":"e_1_3_5_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0207(20000720)48:8<1165::AID-NME940>3.0.CO;2-Y"},{"key":"e_1_3_5_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00366-010-0207-5"},{"key":"e_1_3_5_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-02335-9_9"},{"key":"e_1_3_5_17_2","unstructured":"Franck Ledoux. 2020. MAMBO Dataset. (2020). https:\/\/gitlab.com\/franck.ledoux\/mambo."},{"key":"e_1_3_5_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33573-0_19"},{"key":"e_1_3_5_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75103-8_13"},{"key":"e_1_3_5_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201344"},{"key":"e_1_3_5_21_2","article-title":"Optimal dual schemes for adaptive grid based hexmeshing","author":"Livesu Marco","year":"2021","unstructured":"Marco Livesu, Luca Pitzalis, and Gianmarco Cherchi. 2021. Optimal dual schemes for adaptive grid based hexmeshing. arXiv preprint arXiv:2103.07745 (2021).","journal-title":"arXiv preprint arXiv:2103.07745"},{"key":"e_1_3_5_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508388"},{"key":"e_1_3_5_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33573-0_29"},{"key":"e_1_3_5_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925976"},{"key":"e_1_3_5_25_2","doi-asserted-by":"publisher","DOI":"10.2514\/6.2017-0585"},{"key":"e_1_3_5_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04319-2_5"},{"key":"e_1_3_5_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.proeng.2016.11.007"},{"key":"e_1_3_5_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s003660050022"},{"key":"e_1_3_5_29_2","first-page":"1397","volume-title":"Computer Graphics Forum","author":"Nieser Matthias","year":"2011","unstructured":"Matthias Nieser, Ulrich Reitebuch, and Konrad Polthier. 2011. CubeCover\u2013parameterization of 3D volumes. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 1397\u20131406."},{"key":"e_1_3_5_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982408"},{"key":"e_1_3_5_31_2","article-title":"Multiple approaches to frame field correction for CAD models","author":"Reberol Maxence","year":"2019","unstructured":"Maxence Reberol, Alexandre Chemin, and Jean-Fran\u00e7ois Remacle. 2019. Multiple approaches to frame field correction for CAD models. International Meshing Roundtable (2019).","journal-title":"International Meshing Roundtable"},{"key":"e_1_3_5_32_2","article-title":"Quasi-structured quadrilateral meshing in Gmsh\u2013a robust pipeline for complex CAD models","author":"Reberol Maxence","year":"2021","unstructured":"Maxence Reberol, Christos Georgiadis, and Jean-Fran\u00e7ois Remacle. 2021. Quasi-structured quadrilateral meshing in Gmsh\u2013a robust pipeline for complex CAD models. arXiv preprint arXiv:2103.04652 (2021).","journal-title":"arXiv preprint arXiv:2103.04652"},{"key":"e_1_3_5_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/bf01198732"},{"key":"e_1_3_5_34_2","first-page":"11","article-title":"Gecode","author":"Schulte Christian","year":"2006","unstructured":"Christian Schulte, Mikael Lagerkvist, and Guido Tack. 2006. Gecode. Software Download and Online Material at the Website:http:\/\/www.gecode.org (2006), 11\u201313.","journal-title":"Software Download and Online Material at the Website:http:\/\/www.gecode.org"},{"key":"e_1_3_5_35_2","volume-title":"Topologic and Geometric Constraint-based Hexahedral Mesh Generation","author":"Shepherd Jason F.","year":"2007","unstructured":"Jason F. Shepherd. 2007. Topologic and Geometric Constraint-based Hexahedral Mesh Generation, Vol. 68."},{"key":"e_1_3_5_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629697"},{"key":"e_1_3_5_37_2","doi-asserted-by":"publisher","DOI":"10.1002\/(sici)1097-0207(19961015)39:19<3327::aid-nme2>3.0.co;2-h"},{"key":"e_1_3_5_38_2","doi-asserted-by":"publisher","DOI":"10.2514\/6.1997-1980"},{"key":"e_1_3_5_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323017"},{"key":"e_1_3_5_40_2","doi-asserted-by":"publisher","DOI":"10.1115\/1.4047239"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3577196","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3577196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:32Z","timestamp":1750178852000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3577196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,21]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3,31]]}},"alternative-id":["10.1145\/3577196"],"URL":"https:\/\/doi.org\/10.1145\/3577196","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2023,3,21]]},"assertion":[{"value":"2021-09-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}