{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T05:25:42Z","timestamp":1662009942545},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2021,8,31]]},"abstract":"Mapping a triangulated surface to 2D space (or a tetrahedral mesh to 3D space) is an important problem in geometry processing. In computational physics, untangling plays an important role in mesh generation: it takes a mesh as an input, and moves the vertices to get rid of foldovers. In fact, mesh untangling can be considered as a special case of mapping where the geometry of the object is to be defined in the map space and the geometric domain is not explicit, supposing that each element is regular. In this paper, we propose a mapping method inspired by the untangling problem and compare its performance to the state of the art. The main advantage of our method is that the untangling aims at producing locally injective maps, which is the major challenge of mapping. In practice, our method produces locally injective maps in very difficult settings, both in 2D and 3D. We demonstrate it on a large reference database as well as on more difficult stress tests. For a better reproducibility, we publish the code in Python for a basic evaluation, and in C++ for more advanced applications.<\/jats:p>","DOI":"10.1145\/3450626.3459847","type":"journal-article","created":{"date-parts":[[2021,7,20]],"date-time":"2021-07-20T00:04:26Z","timestamp":1626739466000},"page":"1-16","source":"Crossref","is-referenced-by-count":5,"title":["Foldover-free maps in 50 lines of code"],"prefix":"10.1145","volume":"40","author":[{"given":"Vladimir","family":"Garanzha","sequence":"first","affiliation":[{"name":"Moscow Institute of Physics and Technology, Moscow, Russia"}]},{"given":"Igor","family":"Kaporin","sequence":"additional","affiliation":[{"name":"Moscow Institute of Physics and Technology, Moscow, Russia"}]},{"given":"Liudmila","family":"Kudryavtseva","sequence":"additional","affiliation":[{"name":"Moscow Institute of Physics and Technology, Moscow, Russia"}]},{"given":"Fran\u00e7ois","family":"Protais","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lorraine, Nancy, France"}]},{"given":"Nicolas","family":"Ray","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lorraine, Nancy, France"}]},{"given":"Dmitry","family":"Sokolov","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lorraine, Nancy, France"}]}],"member":"320","reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461931"},{"key":"e_1_2_2_2_1","volume-title":"Convexity conditions and existence theorems in nonlinear elasticity. Archive for rational mechanics and Analysis 63, 4","author":"Ball John M","year":"1976","unstructured":"John M Ball . 1976. Convexity conditions and existence theorems in nonlinear elasticity. Archive for rational mechanics and Analysis 63, 4 ( 1976 ), 337--403. John M Ball. 1976. Convexity conditions and existence theorems in nonlinear elasticity. Archive for rational mechanics and Analysis 63, 4 (1976), 337--403."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S030821050002014X"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2462014"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(82)90020-1"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925890"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1997.5750"},{"key":"e_1_2_2_8_1","volume-title":"Lawrence Livermore National Lab 5","author":"Crowley WP","year":"1962","unstructured":"WP Crowley . 1962. An equipotential zoner on a quadrilateral mesh. Memo , Lawrence Livermore National Lab 5 ( 1962 ). WP Crowley. 1962. An equipotential zoner on a quadrilateral mesh. Memo, Lawrence Livermore National Lab 5 (1962)."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.finel.2013.04.004"},{"key":"e_1_2_2_10_1","volume-title":"PAJ Van Den Bogert, and J Zeilmaker","author":"Borst R De","year":"1988","unstructured":"R De Borst , PAJ Van Den Bogert, and J Zeilmaker . 1988 . Modelling and analysis of rubberlike materials. HERON , 33 (1), 1988 (1988). R De Borst, PAJ Van Den Bogert, and J Zeilmaker. 1988. Modelling and analysis of rubberlike materials. HERON, 33 (1), 1988 (1988)."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392484"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/218380.218440"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0045-7825(03)00299-8"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8396(96)00031-3"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1039\/TF9615700829"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0207(20000910\/20)49:1\/2<109::AID-NME925>3.0.CO;2-U"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980231"},{"key":"e_1_2_2_18_1","first-page":"1617","article-title":"The barrier method for constructing quasi-isometric grids","volume":"40","author":"Garanzha VA","year":"2000","unstructured":"VA Garanzha . 2000 . The barrier method for constructing quasi-isometric grids . Computational Mathematics and Mathematical Physics 40 (2000), 1617 -- 1637 . VA Garanzha. 2000. The barrier method for constructing quasi-isometric grids. Computational Mathematics and Mathematical Physics 40 (2000), 1617--1637.","journal-title":"Computational Mathematics and Mathematical Physics"},{"key":"e_1_2_2_19_1","volume-title":"Regularization of the barrier variational method. Computational mathematics and mathematical physics 39, 9","author":"Garanzha VA","year":"1999","unstructured":"VA Garanzha and IE Kaporin . 1999. Regularization of the barrier variational method. Computational mathematics and mathematical physics 39, 9 ( 1999 ), 1426--1440. VA Garanzha and IE Kaporin. 1999. Regularization of the barrier variational method. Computational mathematics and mathematical physics 39, 9 (1999), 1426--1440."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2014.03.006"},{"key":"e_1_2_2_21_1","volume-title":"Computer Graphics Forum (Special Issue of Symposium on Geometry Processing 2011)","author":"Gregson J.","year":"2011","unstructured":"J. Gregson , A. Sheffer , and E. Zhang . 2011. All-Hex Mesh Generation via Volumetric PolyCube Deformation . Computer Graphics Forum (Special Issue of Symposium on Geometry Processing 2011) 30, 5 ( 2011 ). J. Gregson, A. Sheffer, and E. Zhang. 2011. All-Hex Mesh Generation via Volumetric PolyCube Deformation. Computer Graphics Forum (Special Issue of Symposium on Geometry Processing 2011) 30, 5 (2011)."},{"key":"e_1_2_2_22_1","volume-title":"MIPS: An Efficient Global Parametrization Method. In Curve and Surface Design","author":"Hormann K.","year":"2000","unstructured":"K. Hormann and G. Greiner . 2000 . MIPS: An Efficient Global Parametrization Method. In Curve and Surface Design . Vanderbilt University press . K. Hormann and G. Greiner. 2000. MIPS: An Efficient Global Parametrization Method. In Curve and Surface Design. Vanderbilt University press."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508044.1508091"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(88)90023-7"},{"key":"e_1_2_2_25_1","volume-title":"A mechanical model for a new grid generation method in computational fluid dynamics. Computer methods in applied mechanics and engineering 66, 3","author":"Jacquotte P","year":"1988","unstructured":"Olivier- P Jacquotte . 1988. A mechanical model for a new grid generation method in computational fluid dynamics. Computer methods in applied mechanics and engineering 66, 3 ( 1988 ), 323--338. Olivier-P Jacquotte. 1988. A mechanical model for a new grid generation method in computational fluid dynamics. Computer methods in applied mechanics and engineering 66, 3 (1988), 323--338."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3130800.3130895"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417769"},{"key":"e_1_2_2_28_1","volume-title":"Winslow Smoothing On Two-Dimensional Unstructured Meshes. (05","author":"Knupp Patrick","year":"2000","unstructured":"Patrick Knupp . 2000a. Winslow Smoothing On Two-Dimensional Unstructured Meshes. (05 2000 ). Patrick Knupp. 2000a. Winslow Smoothing On Two-Dimensional Unstructured Meshes. (05 2000)."},{"key":"e_1_2_2_29_1","volume-title":"Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities. Part II---a framework for","author":"Knupp Patrick M","year":"2000","unstructured":"Patrick M Knupp . 2000b. Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities. Part II---a framework for volume mesh optimization and the condition number of the Jacobian matrix. International Journal for numerical methods in engineering 48 , 8 ( 2000 ), 1165--1185. Patrick M Knupp. 2000b. Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities. Part II---a framework for volume mesh optimization and the condition number of the Jacobian matrix. International Journal for numerical methods in engineering 48, 8 (2000), 1165--1185."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003660170006"},{"key":"e_1_2_2_31_1","volume-title":"Large-scale bounded distortion mappings. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH Asia) 34, 6","author":"Kovalsky Shahar Z.","year":"2015","unstructured":"Shahar Z. Kovalsky , Noam Aigerman , Ronen Basri , and Yaron Lipman . 2015. Large-scale bounded distortion mappings. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH Asia) 34, 6 ( 2015 ). Shahar Z. Kovalsky, Noam Aigerman, Ronen Basri, and Yaron Lipman. 2015. Large-scale bounded distortion mappings. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH Asia) 34, 6 (2015)."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392425"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185604"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3112655.3112866"},{"key":"e_1_2_2_35_1","volume-title":"Least Squares Conformal Maps for Automatic Texture Atlas Generation. In ACM SIGGRAPH conference proceedings, ACM (Ed.). http:\/\/www.loria.fr\/publications\/2002\/A02-R-065\/A02-R-065","author":"L\u00e9vy Bruno","year":"2002","unstructured":"Bruno L\u00e9vy , Sylvain Petitjean , Nicolas Ray , and J\u00e9rome Maillo t. 2002 . Least Squares Conformal Maps for Automatic Texture Atlas Generation. In ACM SIGGRAPH conference proceedings, ACM (Ed.). http:\/\/www.loria.fr\/publications\/2002\/A02-R-065\/A02-R-065 .ps Bruno L\u00e9vy, Sylvain Petitjean, Nicolas Ray, and J\u00e9rome Maillo t. 2002. Least Squares Conformal Maps for Automatic Texture Atlas Generation. In ACM SIGGRAPH conference proceedings, ACM (Ed.). http:\/\/www.loria.fr\/publications\/2002\/A02-R-065\/A02-R-065.ps"},{"key":"e_1_2_2_36_1","volume-title":"Computer Graphics Forum","author":"Naitsat Alexander","unstructured":"Alexander Naitsat , Yufeng Zhu , and Yehoshua Y Zeevi . 2020. Adaptive Block Coordinate Descent for Distortion Optimization . In Computer Graphics Forum , Vol. 39 . Wiley Online Library , 360--376. Alexander Naitsat, Yufeng Zhu, and Yehoshua Y Zeevi. 2020. Adaptive Block Coordinate Descent for Distortion Optimization. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 360--376."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.02014.x"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1122\/1.549176"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1134\/S0081543808050155"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983621"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01044493"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050180"},{"key":"e_1_2_2_43_1","volume-title":"Locally Injective Mappings. Computer Graphics Forum (proceedings of Symposium on Geometry Processing) 32, 5","author":"Sch\u00fcller Christian","year":"2013","unstructured":"Christian Sch\u00fcller , Ladislav Kavan , Daniele Panozzo , and Olga Sorkine-Hornung . 2013. Locally Injective Mappings. Computer Graphics Forum (proceedings of Symposium on Geometry Processing) 32, 5 ( 2013 ). Christian Sch\u00fcller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally Injective Mappings. Computer Graphics Forum (proceedings of Symposium on Geometry Processing) 32, 5 (2013)."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323012"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073618"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3241041"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766947"},{"key":"e_1_2_2_48_1","unstructured":"Dmitry Sokolov. 2021. Supplemental material for \"Foldover-free maps in 50 lines of code\". https:\/\/github.com\/ssloy\/invertible-maps. Accessed: 2020-04-26. Dmitry Sokolov. 2021. Supplemental material for \"Foldover-free maps in 50 lines of code\". https:\/\/github.com\/ssloy\/invertible-maps. Accessed: 2020-04-26."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13837"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392435"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2013.07.022"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-13.1.743"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03173.x"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601227"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(66)90001-5"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14122"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201359"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450626.3459847","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T11:59:32Z","timestamp":1658750372000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450626.3459847"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,31]]},"references-count":57,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8,31]]}},"alternative-id":["10.1145\/3450626.3459847"],"URL":"http:\/\/dx.doi.org\/10.1145\/3450626.3459847","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":["Computer Graphics and Computer-Aided Design"],"published":{"date-parts":[[2021,8,31]]}}}