{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T22:57:47Z","timestamp":1776207467450,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,7,21]],"date-time":"2013-07-21T00:00:00Z","timestamp":1374364800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["257474"],"award-info":[{"award-number":["257474"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007867","name":"Aachen Institute for Advanced Study in Computational Engineering Science","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007867","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DFG EXC 89"],"award-info":[{"award-number":["DFG EXC 89"]}],"id":[{"id":"10.13039\/501100001659","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":[[2013,7,21]]},"abstract":"<jats:p>Quadrilateral remeshing approaches based on global parametrization enable many desirable mesh properties. Two of the most important ones are (1) high regularity due to explicit control over irregular vertices and (2) smooth distribution of distortion achieved by convex variational formulations. Apart from these strengths, state-of-the-art techniques suffer from limited reliability on real-world input data, i.e. the determined map might have degeneracies like (local) non-injectivities and consequently often cannot be used directly to generate a quadrilateral mesh. In this paper we propose a novel convex Mixed-Integer Quadratic Programming (MIQP) formulation which ensures by construction that the resulting map is within the class of so called Integer-Grid Maps that are guaranteed to imply a quad mesh. In order to overcome the NP-hardness of MIQP and to be able to remesh typical input geometries in acceptable time we propose two additional problem specific optimizations: a complexity reduction algorithm and singularity separating conditions. While the former decouples the dimension of the MIQP search space from the input complexity of the triangle mesh and thus is able to dramatically speed up the computation without inducing inaccuracies, the latter improves the continuous relaxation, which is crucial for the success of modern MIQP optimizers. Our experiments show that the reliability of the resulting algorithm does not only annihilate the main drawback of parametrization based quad-remeshing but moreover enables the global search for high-quality coarse quad layouts - a difficult task solely tackled by greedy methodologies before.<\/jats:p>","DOI":"10.1145\/2461912.2462014","type":"journal-article","created":{"date-parts":[[2013,7,16]],"date-time":"2013-07-16T18:06:45Z","timestamp":1373998005000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":187,"title":["Integer-grid maps for reliable quad meshing"],"prefix":"10.1145","volume":"32","author":[{"given":"David","family":"Bommes","sequence":"first","affiliation":[{"name":"Inria Sophia Antipolis - M\u00e9diterran\u00e9e"}]},{"given":"Marcel","family":"Campen","sequence":"additional","affiliation":[{"name":"RWTH Aachen University"}]},{"given":"Hans-Christian","family":"Ebke","sequence":"additional","affiliation":[{"name":"RWTH Aachen University"}]},{"given":"Pierre","family":"Alliez","sequence":"additional","affiliation":[{"name":"Inria Sophia Antipolis - M\u00e9diterran\u00e9e"}]},{"given":"Leif","family":"Kobbelt","sequence":"additional","affiliation":[{"name":"RWTH Aachen University"}]}],"member":"320","published-online":{"date-parts":[[2013,7,21]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1576246.1531383"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11620-9_5"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.01868.x"},{"key":"e_1_2_2_4_1","unstructured":"Bommes D. L\u00e9vy B. Pietroni N. Puppo E. Silva C. Tarini M. and Zorin D. 2012. State of the art in quad meshing. In Eurographics STARS.  Bommes D. L\u00e9vy B. Pietroni N. Puppo E. Silva C. Tarini M. and Zorin D. 2012. State of the art in quad meshing. In Eurographics STARS ."},{"key":"e_1_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Botsch M. Kobbelt L. Pauly M. Alliez P. and L\u00e9vy B. 2010. Polygon Mesh Processing. AK Peters.  Botsch M. Kobbelt L. Pauly M. Alliez P. and L\u00e9vy B. 2010. Polygon Mesh Processing . AK Peters.","DOI":"10.1201\/b10688"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03171.x"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185606"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/280811.280992"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1457515.1409101"},{"key":"e_1_2_2_10_1","volume-title":"SGP '09: Proceedings of the Symposium on Geometry Processing, Eurographics Association, Aire-la-Ville","author":"Daniels II, J.","unstructured":"Daniels , II, J. , Silva , C. T. , and Cohen , E . 2009. Localized quadrilateral coarsening . In SGP '09: Proceedings of the Symposium on Geometry Processing, Eurographics Association, Aire-la-Ville , Switzerland, Switzerland, 1437--1444. Daniels, II, J., Silva, C. T., and Cohen, E. 2009. Localized quadrilateral coarsening. In SGP '09: Proceedings of the Symposium on Geometry Processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 1437--1444."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1179352.1141993"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00502"},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Floater M. S. and Hormann K. 2005. Surface parameterization: a tutorial and survey. In Advances in Multiresolution for Geometric Modelling N. A. Dodgson M. S. Floater and M. A. Sabin Eds. Mathematics and Visualization. Springer Berlin Heidelberg 157--186.  Floater M. S. and Hormann K. 2005. Surface parameterization: a tutorial and survey. In Advances in Multiresolution for Geometric Modelling N. A. Dodgson M. S. Floater and M. A. Sabin Eds. Mathematics and Visualization. Springer Berlin Heidelberg 157--186.","DOI":"10.1007\/3-540-26808-1_9"},{"key":"e_1_2_2_14_1","unstructured":"Gu Z. Rothberg E. and Bixby R. 2011. Gurobi optimizer 4.5: http:\/\/www.gurobi.com.  Gu Z. Rothberg E. and Bixby R. 2011. Gurobi optimizer 4.5: http:\/\/www.gurobi.com."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281500.1281510"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409100"},{"key":"e_1_2_2_17_1","unstructured":"IBM 2012. Ilog cplex optimizer 12: http:\/\/www.ibm.com.  IBM 2012. Ilog cplex optimizer 12: http:\/\/www.ibm.com."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2007.01060.x"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1201775.882275"},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Kimmel R. and Sethian J. A. 1998. Computing geodesic paths on manifolds. In Proc. Natl. Acad. Sci. USA 8431--8435.  Kimmel R. and Sethian J. A. 1998. Computing geodesic paths on manifolds. In Proc. Natl. Acad. Sci. USA 8431--8435.","DOI":"10.1073\/pnas.95.15.8431"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839778.1839797"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2011.05.003"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366196"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185604"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.915688"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27413-8_31"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-874X(97)81956-7"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.02014.x"},{"key":"e_1_2_2_29_1","unstructured":"Novotni M. and Klein R. 2002. Computing geodesic distances on triangular meshes. In The 10-th International Conference in Central Europe on Computer Graphics Visualization and Computer Vision'2002 (WSCG'2002).  Novotni M. and Klein R. 2002. Computing geodesic distances on triangular meshes. In The 10-th International Conference in Central Europe on Computer Graphics Visualization and Computer Vision'2002 (WSCG'2002) ."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0207(19990330)44:9<1317::AID-NME532>3.0.CO;2-N"},{"key":"e_1_2_2_31_1","unstructured":"Pardalos P. and Resende M. 2002. Handbook of applied optimization. Oxford University Press Incorporated.  Pardalos P. and Resende M. 2002. Handbook of applied optimization . Oxford University Press Incorporated."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2009.96"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024183"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183287.1183297"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1356682.1356683"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1561\/0600000011"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1399504.1360676"},{"key":"e_1_2_2_38_1","volume-title":"Computer Graphics Forum (Special Issue of Eurographics 2010 Conference) 29","author":"Tarini M.","unstructured":"Tarini , M. , Pietroni , N. , Cignoni , P. , Panozzo , D. , and Puppo , E . 2010. Practical quad mesh simplification . Computer Graphics Forum (Special Issue of Eurographics 2010 Conference) 29 , 2, 407--418. Tarini, M., Pietroni, N., Cignoni, P., Panozzo, D., and Puppo, E. 2010. Practical quad mesh simplification. Computer Graphics Forum (Special Issue of Eurographics 2010 Conference) 29, 2, 407--418."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024176"},{"key":"e_1_2_2_40_1","volume-title":"Proc. of SGP, EG Association, Aire-la-Ville, Switzerland, SGP '06","author":"Tong Y.","unstructured":"Tong , Y. , Alliez , P. , Cohen-Steiner , D. , and Desbrun , M . 2006. Designing quadrangulations with discrete harmonic forms . In Proc. of SGP, EG Association, Aire-la-Ville, Switzerland, SGP '06 , 201--210. Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In Proc. of SGP, EG Association, Aire-la-Ville, Switzerland, SGP '06, 201--210."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0559-y"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03173.x"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.117"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778855"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2461912.2462014","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2461912.2462014","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:39Z","timestamp":1750236519000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2461912.2462014"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,21]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,7,21]]}},"alternative-id":["10.1145\/2461912.2462014"],"URL":"https:\/\/doi.org\/10.1145\/2461912.2462014","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7,21]]},"assertion":[{"value":"2013-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}