{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:22:26Z","timestamp":1758824546622,"version":"3.41.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T00:00:00Z","timestamp":1562889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC-2015-AdG-694020"],"award-info":[{"award-number":["ERC-2015-AdG-694020"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2019,8,31]]},"abstract":"<jats:p>This paper tackles the challenging problem of constrained hexahedral meshing. An algorithm is introduced to build combinatorial hexahedral meshes whose boundary facets exactly match a given quadrangulation of the topological sphere. This algorithm is the first practical solution to the problem. It is able to compute small hexahedral meshes of quadrangulations for which the previously known best solutions could only be built by hand or contained thousands of hexahedra. These challenging quadrangulations include the boundaries of transition templates that are critical for the success of general hexahedral meshing algorithms.<\/jats:p>\n          <jats:p>\n            The algorithm proposed in this paper is dedicated to building combinatorial hexahedral meshes of small quadrangulations and ignores the geometrical problem. The key idea of the method is to exploit the equivalence between quad flips in the boundary and the insertion of hexahedra glued to this boundary. The tree of all sequences of flipping operations is explored, searching for a path that transforms the input quadrangulation\n            <jats:italic>Q<\/jats:italic>\n            into a new quadrangulation for which a hexahedral mesh is known. When a small hexahedral mesh exists, a sequence transforming\n            <jats:italic>Q<\/jats:italic>\n            into the boundary of a cube is found; otherwise, a set of pre-computed hexahedral meshes is used.\n          <\/jats:p>\n          <jats:p>\n            A novel approach to deal with the large number of problem symmetries is proposed. Combined with an efficient backtracking search, it allows small shellable hexahedral meshes to be found for all even quadrangulations with up to 20 quadrangles. All 54, 943 such quadrangulations were meshed using no more than 72 hexahedra. This algorithm is also used to find a construction to fill arbitrary domains, thereby proving that any ball-shaped domain bounded by\n            <jats:italic>n<\/jats:italic>\n            quadrangles can be meshed with no more than 78\n            <jats:italic>n<\/jats:italic>\n            hexahedra. This very significantly lowers the previous upper bound of 5396\n            <jats:italic>n.<\/jats:italic>\n          <\/jats:p>","DOI":"10.1145\/3306346.3323017","type":"journal-article","created":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T19:04:08Z","timestamp":1562958248000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Finding hexahedrizations for small quadrangulations of the sphere"],"prefix":"10.1145","volume":"38","author":[{"given":"Kilian","family":"Verhetsel","sequence":"first","affiliation":[{"name":"Universit\u00e9 catholique de Louvain, Belgique"}]},{"given":"Jeanne","family":"Pellerin","sequence":"additional","affiliation":[{"name":"Universit\u00e9 catholique de Louvain, Belgique"}]},{"given":"Jean-Fran\u00e7ois","family":"Remacle","sequence":"additional","affiliation":[{"name":"Universit\u00e9 catholique de Louvain, Belgique"}]}],"member":"320","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1186\/2213-7467-1-8"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003660200016"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.10.005"},{"key":"e_1_2_2_4_1","first-page":"323","article-title":"Fast generation of planar graphs","volume":"58","author":"Brinkmann Gunnar","year":"2007","journal-title":"MATCH Commun. Math. Comput. Chem"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998220"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3225288.3225582"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210015"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00032-7"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00014"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-014-9624-3"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Torsten Fahle Stefan Schamberger and Meinolf Sellmann. 2001. Symmetry Breaking. In Principles and Practice of Constraint Programming. 93--107.   Torsten Fahle Stefan Schamberger and Meinolf Sellmann. 2001. Symmetry Breaking. In Principles and Practice of Constraint Programming. 93--107.","DOI":"10.1007\/3-540-45578-7_7"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925957"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/233\/03424"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02954617"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073676"},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Ian P. Gent Karen E. Petrie and Jean-Fran\u00e7ois Puget. 2006. Symmetry in Constraint Programming. In Handbook of Constraint Programming. 329--376.  Ian P. Gent Karen E. Petrie and Jean-Fran\u00e7ois Puget. 2006. Symmetry in Constraint Programming. In Handbook of Constraint Programming. 329--376.","DOI":"10.1016\/S1574-6526(06)80014-3"},{"volume-title":"Proceedings of the 34th Symposium on Computational Geometry. 41:1--41:15","year":"2018","author":"Goaoc Xavier","key":"e_1_2_2_17_1"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.02015.x"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2011.06.023"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.2470"},{"key":"e_1_2_2_21_1","first-page":"P3","article-title":"Parallel Enumeration of Triangulations","volume":"25","author":"Jordan Charles","year":"2018","journal-title":"Electr. J. Comb."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.proeng.2014.10.373"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201344"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766905"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925976"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04319-2_5"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/646511.695185"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003660050018"},{"volume-title":"A Technical History of Hexahedral Mesh Generation. https:\/\/www.sandia.gov\/~samitch\/_assets\/documents\/pptx\/hex_mesh_history_samitch.ppt. Retrieved","year":"2019","author":"Mitchell Scott A.","key":"e_1_2_2_29_1"},{"volume-title":"Proceedings of the 4th International Meshing Roundtable. 231--240","author":"Scott","key":"e_1_2_2_30_1"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003660050022"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-874X(97)81956-7"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.02014.x"},{"volume-title":"Identifying combinations of tetrahedra into hexahedra: A vertex based strategy. Computer-Aided Design 105","year":"2018","author":"Pellerin Jeanne","key":"e_1_2_2_34_1"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15414-0_15"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2016.08.005"},{"key":"e_1_2_2_37_1","unstructured":"Robert Schneiders. 1995. Open problem. http:\/\/www.robertschneiders.de\/meshgeneration\/open.html. Retrieved January 2 2019.  Robert Schneiders. 1995. Open problem. http:\/\/www.robertschneiders.de\/meshgeneration\/open.html. Retrieved January 2 2019."},{"key":"e_1_2_2_38_1","first-page":"3","article-title":"A grid-based algorithm for the generation of hexahedral element meshes","volume":"12","author":"Schneiders Robert","year":"1996","journal-title":"Eng. Comput. (Lond.)"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/3225268.3225437"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629697"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3126827"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0207(19961015)39:19<3327::AID-NME2>3.0.CO;2-H"},{"key":"e_1_2_2_43_1","unstructured":"William P. Thurston. 1993. Hexahedral decomposition of polyhedra. Posting to sci.math. http:\/\/www.ics.uci.edu\/~eppstein\/gina\/Thurston-hexahedra.html  William P. Thurston. 1993. Hexahedral decomposition of polyhedra. Posting to sci.math. http:\/\/www.ics.uci.edu\/~eppstein\/gina\/Thurston-hexahedra.html"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2013.07.022"},{"volume-title":"Proceedings of the 27th International Meshing Roundtable. Springer.","year":"2018","author":"Verhetsel Kilian","key":"e_1_2_2_45_1"},{"key":"e_1_2_2_46_1","unstructured":"Jean-Christophe Weill and Franck Ledoux. 2016. Towards an automatic and reliable hexahedral meshing. http:\/\/tetrahedron.montefiore.ulg.ac.be\/weill.pdf. Retrieved January 2 2019.  Jean-Christophe Weill and Franck Ledoux. 2016. Towards an automatic and reliable hexahedral meshing. http:\/\/tetrahedron.montefiore.ulg.ac.be\/weill.pdf. Retrieved January 2 2019."},{"volume-title":"A 36-element solution to Schneiders' pyramid hex-meshing problem and a parity-changing template for hex-mesh revision. arXiv preprint arXiv:1807.09415","year":"2018","author":"Xiang Shang","key":"e_1_2_2_47_1"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003660200019"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.754"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/cnm.1256"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2013.08.018"},{"volume-title":"Proceedings of the 21st International Meshing Roundtable. 155--172","year":"2012","author":"Zhang Yongjie","key":"e_1_2_2_52_1"},{"volume-title":"Lectures on polytopes. Graduate Texts in Mathematics","author":"Ziegler G\u00fcnter M.","key":"e_1_2_2_53_1"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3306346.3323017","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3306346.3323017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:52Z","timestamp":1750206352000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3306346.3323017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,12]]},"references-count":53,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3306346.3323017"],"URL":"https:\/\/doi.org\/10.1145\/3306346.3323017","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2019,7,12]]},"assertion":[{"value":"2019-07-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}