“Foldover-free maps in 50 lines of code” by Garanzha, Kaporin, Kudryavtseva, Protais, Ray, et al. …

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.

1. Noam Aigerman and Yaron Lipman. 2013. Injective and Bounded Distortion Mappings in 3D. ACM Trans. Graph. 32, 4, Article 106 (July 2013), 14 pages. Google ScholarDigital Library
2. John M Ball. 1976. Convexity conditions and existence theorems in nonlinear elasticity. Archive for rational mechanics and Analysis 63, 4 (1976), 337–403.Google Scholar
3. J. M. Ball. 1981. Global invertibility of Sobolev functions and the interpenetration of matter. Proceedings of the Royal Society of Edinburgh: Section A Mathematics 88, 3-4 (1981), 315–328. Google ScholarCross Ref
4. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013. Integer-Grid Maps for Reliable Quad Meshing. ACM Trans. Graph. 32, 4, Article 98 (July 2013), 12 pages. Google ScholarDigital Library
5. J.U Brackbill and J.S Saltzman. 1982. Adaptive zoning for singular problems in two dimensions. J. Comput. Phys. 46, 3 (1982), 342 — 368. Google ScholarCross Ref
6. Marcel Campen, Cláudio T. Silva, and Denis Zorin. 2016. Bijective Maps from Simplicial Foliations. ACM Trans. Graph. 35, 4, Article 74 (July 2016), 15 pages. Google ScholarDigital Library
7. AA Charakhch’yan and SA Ivanenko. 1997. A variational form of the Winslow grid generator. J. Comput. Phys. 136, 2 (1997), 385–398.Google ScholarDigital Library
8. WP Crowley. 1962. An equipotential zoner on a quadrilateral mesh. Memo, Lawrence Livermore National Lab 5 (1962).Google Scholar
9. Josh Danczyk and Krishnan Suresh. 2013. Finite element analysis over tangled simplicial meshes: Theory and implementation. Finite Elements in Analysis and Design 70-71 (2013), 57 — 67. Google ScholarCross Ref
10. R De Borst, PAJ Van Den Bogert, and J Zeilmaker. 1988. Modelling and analysis of rubberlike materials. HERON, 33 (1), 1988 (1988).Google Scholar
11. Xingyi Du, Noam Aigerman, Qingnan Zhou, Shahar Z. Kovalsky, Yajie Yan, Danny M. Kaufman, and Tao Ju. 2020. Lifting Simplices to Find Injectivity. ACM Trans. Graph. 39, 4, Article 120 (July 2020), 17 pages. Google ScholarDigital Library
12. Matthias Eck, Tony DeRose, Tom Duchamp, Hugues Hoppe, Michael Lounsbery, and Werner Stuetzle. 1995. Multiresolution Analysis of Arbitrary Meshes. In Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’95). Association for Computing Machinery, New York, NY, USA, 173–182. Google ScholarDigital Library
13. José Marıa Escobar, Eduardo Rodrıguez, Rafael Montenegro, Gustavo Montero, and José Marıa González-Yuste. 2003. Simultaneous untangling and smoothing of tetrahedral meshes. Computer Methods in Applied Mechanics and Engineering 192, 25 (2003), 2775–2787.Google ScholarCross Ref
14. Michael S. Floater. 1997. Parametrization and Smooth Approximation of Surface Triangulations. Comput. Aided Geom. Des. 14, 3 (April 1997), 231–250. Google ScholarDigital Library
15. P. J. Flory. 1961. Thermodynamic relations for high elastic materials. Trans. Faraday Soc. 57 (1961), 829–838. Issue 0. Google ScholarCross Ref
16. Lori A Freitag and Paul Plassmann. 2000. Local optimization-based simplicial mesh untangling and improvement. Internat. J. Numer. Methods Engrg. 49, 1-2 (2000), 109–125.Google ScholarCross Ref
17. Xiao-Ming Fu and Yang Liu. 2016. Computing Inversion-Free Mappings by Simplex Assembly. ACM Trans. Graph. 35, 6, Article 216 (Nov. 2016), 12 pages. Google ScholarDigital Library
18. VA Garanzha. 2000. The barrier method for constructing quasi-isometric grids. Computational Mathematics and Mathematical Physics 40 (2000), 1617–1637.Google Scholar
19. VA Garanzha and IE Kaporin. 1999. Regularization of the barrier variational method. Computational mathematics and mathematical physics 39, 9 (1999), 1426–1440.Google Scholar
20. V.A. Garanzha, L.N. Kudryavtseva, and S.V. Utyuzhnikov. 2014. Variational method for untangling and optimization of spatial meshes. J. Comput. Appl. Math. 269 (2014), 24 — 41. Google ScholarCross Ref
21. 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).Google Scholar
22. K. Hormann and G. Greiner. 2000. MIPS: An Efficient Global Parametrization Method. In Curve and Surface Design. Vanderbilt University press.Google Scholar
23. Kai Hormann, Konrad Polthier, and Alia Sheffer. 2008. Mesh Parameterization: Theory and Practice. In ACM SIGGRAPH ASIA 2008 Courses (Singapore) (SIGGRAPH Asia ’08). Association for Computing Machinery, New York, NY, USA, Article 12, 87 pages. Google ScholarDigital Library
24. S.A. Ivanenko. 1988. Generation of non-degenerate meshes. U. S. S. R. Comput. Math. and Math. Phys. 28, 5 (1988), 141–146. Google ScholarDigital Library
25. 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.Google Scholar
26. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial Complex Augmentation Framework for Bijective Maps. ACM Trans. Graph. 36, 6, Article 186 (Nov. 2017), 9 pages. Google ScholarDigital Library
27. Zhongshi Jiang, Teseo Schneider, Denis Zorin, and Daniele Panozzo. 2020. Bijective Projection in a Shell. ACM Trans. Graph. 39, 6, Article 247 (Nov. 2020), 18 pages. Google ScholarDigital Library
28. Patrick Knupp. 2000a. Winslow Smoothing On Two-Dimensional Unstructured Meshes. (05 2000).Google Scholar
29. 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.Google Scholar
30. Patrick M Knupp. 2001. Hexahedral and tetrahedral mesh untangling. Engineering with Computers 17, 3 (2001), 261–268.Google ScholarCross Ref
31. 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).Google Scholar
32. Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020. Incremental Potential Contact: Intersection-and Inversion-Free, Large-Deformation Dynamics. ACM Trans. Graph. 39, 4, Article 49 (July 2020), 20 pages. Google ScholarDigital Library
33. Yaron Lipman. 2012. Bounded Distortion Mapping Spaces for Triangular Meshes. ACM Trans. Graph. 31, 4, Article 108 (July 2012), 13 pages. Google ScholarDigital Library
34. Dong C. Liu and Jorge Nocedal. 1989. On the Limited Memory BFGS Method for Large Scale Optimization. Mathematical Programming 45, 1–3 (Aug. 1989), 503–528.Google ScholarDigital Library
35. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome 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.psGoogle Scholar
36. 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.Google Scholar
37. Matthias Nieser, Ulrich Reitebuch, and Konrad Polthier. 2011. CubeCover – Parameterization of 3D Volumes. Computer Graphics Forum (2011). Google ScholarCross Ref
38. Robert W. Penn. 1970. Volume Changes Accompanying the Extension of Rubber. Transactions of the Society of Rheology 14, 4 (1970), 509–517. Google ScholarCross Ref
39. Marina Faivushevna Prokhorova. 2008. Problems of homeomorphism arising in the theory of grid generation. Proceedings of the Steklov Institute of Mathematics 261, 1 (2008), 165–182.Google ScholarCross Ref
40. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 2, Article 16 (April 2017), 16 pages. Google ScholarDigital Library
41. Yu. G. Reshetnyak. 1966. Bounds on moduli of continuity for certain mappings. Siberian Mathematical Journal 7 (1966), 879–886.Google ScholarCross Ref
42. Martin Rumpf. 1996. A variational approach to optimal meshes. Numer. Math. 72, 4 (1996), 523–540.Google ScholarCross Ref
43. Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally Injective Mappings. Computer Graphics Forum (proceedings of Symposium on Geometry Processing) 32, 5 (2013).Google Scholar
44. Hanxiao Shen, Zhongshi Jiang, Denis Zorin, and Daniele Panozzo. 2019. Progressive Embedding. ACM Trans. Graph. 38, 4, Article 32 (July 2019), 13 pages. Google ScholarDigital Library
45. Anna Shtengel, Roi Poranne, Olga Sorkine-Hornung, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Geometric Optimization via Composite Majorization. ACM Trans. Graph. 36, 4, Article 38 (July 2017), 11 pages. Google ScholarDigital Library
46. Breannan Smith, Fernando De Goes, and Theodore Kim. 2019. Analytic Eigensystems for Isotropic Distortion Energies. ACM Trans. Graph. 38, 1, Article 3 (Feb. 2019), 15 pages. Google ScholarDigital Library
47. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. 34, 4, Article 70 (July 2015), 9 pages. Google ScholarDigital Library
48. Dmitry Sokolov. 2021. Supplemental material for “Foldover-free maps in 50 lines of code”. https://github.com/ssloy/invertible-maps. Accessed: 2020-04-26.Google Scholar
49. Jian-Ping Su, Xiao-Ming Fu, and Ligang Liu. 2019. Practical Foldover-Free Volumetric Mapping Construction. Computer Graphics Forum 38, 7 (2019), 287–297. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.13837 Google ScholarCross Ref
50. Jian-Ping Su, Chunyang Ye, Ligang Liu, and Xiao-Ming Fu. 2020. Efficient Bijective Parameterizations. ACM Trans. Graph. 39, 4, Article 111 (July 2020), 8 pages. Google ScholarDigital Library
51. Thomas Toulorge, Christophe Geuzaine, Jean-François Remacle, and Jonathan Lambrechts. 2013. Robust untangling of curvilinear meshes. J. Comput. Phys. 254 (2013), 8–26.Google ScholarDigital Library
52. W. T. Tutte. 1963. How to Draw a Graph. Proceedings of the London Mathematical Society s3-13, 1 (01 1963), 743–767. arXiv:https://academic.oup.com/plms/article-pdf/s3-13/1/743/4385170/s3-13-1-743.pdf Google ScholarCross Ref
53. Ofir Weber, Ashish Myles, and Denis Zorin. 2012. Computing Extremal Quasiconformal Maps. Computer Graphics Forum 31, 5 (2012), 1679–1689. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1467-8659.2012.03173.x Google ScholarDigital Library
54. Ofir Weber and Denis Zorin. 2014. Locally Injective Parametrization with Arbitrary Fixed Boundaries. ACM Trans. Graph. 33, 4, Article 75 (July 2014), 12 pages. Google ScholarDigital Library
55. Alan M Winslow. 1966. Numerical solution of the quasilinear Poisson equation in a nonuniform triangle mesh. Journal of computational physics 1, 2 (1966), 149–172.Google ScholarCross Ref
56. Chunyang Ye, Jian-Ping Su, Ligang Liu, and Xiao-Ming Fu. 2020. Memory-Efficient Bijective Parameterizations of Very-Large-Scale Models. Computer Graphics Forum 39, 7 (2020), 1–12. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.14122 Google ScholarCross Ref
57. Yufeng Zhu, Robert Bridson, and Danny M. Kaufman. 2018. Blended Cured QuasiNewton for Distortion Optimization. ACM Trans. Graph. 37, 4, Article 40 (July 2018), 14 pages. Google ScholarDigital Library