“Variational quasi-harmonic maps for computing diffeomorphisms” by Wang, Guo and Solomon
Conference:
Type:
Title:
- Variational quasi-harmonic maps for computing diffeomorphisms
Session/Category Title: Marvelous Mappings
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Computation of injective (or inversion-free) maps is a key task in geometry processing, physical simulation, and shape optimization. Despite being a longstanding problem, it remains challenging due to its highly nonconvex and combinatoric nature. We propose computation of variational quasi-harmonic maps to obtain smooth inversion-free maps. Our work is built on a key observation about inversion-free maps: A planar map is a diffeomorphism if and only if it is quasi-harmonic and satisfies a special Cauchy boundary condition. We hence equate the inversion-free mapping problem to an optimal control problem derived from our theoretical result, in which we search in the space of parameters that define an elliptic PDE. We show that this problem can be solved by minimizing within a family of functionals. Similarly, our discretized functionals admit exactly injective maps as the minimizers, empirically producing inversion-free discrete maps of triangle meshes. We design efficient numerical procedures for our problem that prioritize robust convergence paths. Experiments show that on challenging examples our methods can achieve up to orders of magnitude improvement over state-of-the-art, in terms of speed or quality. Moreover, we demonstrate how to optimize a generic energy in our framework while restricting to quasi-harmonic maps.
References:
1. Robert Acar. 1993. Identification of the coefficient in elliptic equations. SIAM Journal on Control and Optimization 31, 5 (1993), 1221–1244.
2. Lars Valerian Ahlfors. 2006. Lectures on quasiconformal mappings. Vol. 38. American Mathematical Soc.
3. Noam Aigerman and Yaron Lipman. 2013. Injective and bounded distortion mappings in 3D. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–14.
4. Giovanni Alessandrini and Vincenzo Nesi. 2001. Univalent σ-harmonic mappings. Archive for Rational Mechanics and Analysis 158, 2 (2001), 155–171.
5. Giovanni Alessandrini and Vincenzo Nesi. 2021. Globally diffeomorphic σ-harmonic mappings. Annali di Matematica Pura ed Applicata (1923-) 200, 4 (2021), 1625–1635.
6. Kari Astala, Tadeusz Iwaniec, and Gaven Martin. 2008. Elliptic Partial Differential Equations and Quasiconformal Mappings in the Plane (PMS-48). In Elliptic Partial Differential Equations and Quasiconformal Mappings in the Plane (PMS-48). Princeton University Press.
7. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal flattening by curvature prescription and metric scaling. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 449–458.
8. Mirela Ben-Chen, Ofir Weber, and Craig Gotsman. 2009. Variational harmonic maps for space deformation. ACM Transactions on Graphics (TOG) 28, 3 (2009), 34.
9. George E Brown and Rahul Narain. 2021. WRAPD: weighted rotation-aware ADMM for parameterization and deformation. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–14.
10. Marcel Campen, Ryan Capouellez, Hanxiao Shen, Leyi Zhu, Daniele Panozzo, and Denis Zorin. 2021. Efficient and robust discrete conformal equivalence with boundary. ACM Transactions on Graphics (TOG) 40, 6 (2021), 1–16.
11. Renjie Chen and Ofir Weber. 2017. GPU-accelerated locally injective shape deformation. ACM Transactions on Graphics (TOG) 36, 6 (2017), 1–13.
12. Renjie Chen, Ofir Weber, Daniel Keren, and Mirela Ben-Chen. 2013. Planar shape interpolation with bounded distortion. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–12.
13. Edward Chien, Zohar Levi, and Ofir Weber. 2016. Bounded distortion parametrization in the space of metrics. ACM Transactions on Graphics (TOG) 35, 6 (2016), 1–16.
14. Gustave Choquet. 1945. Sur un type de transformation analytique généralisant la représentation conforme et définie au moyen de fonctions harmoniques. Bull. Sci. Math. 69, 2 (1945), 156–165.
15. Sebastian Claici, Mikhail Bessmeltsev, Scott Schaefer, and Justin Solomon. 2017. Isometry-Aware Preconditioning for Mesh Parameterization. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 37–47.
16. Tobias H Colding and William P Minicozzi. 2011. A course in minimal surfaces. Vol. 121. American Mathematical Soc.
17. Prabir Daripa. 1993. A fast algorithm to solve the Beltrami equation with applications to quasiconformal mappings. J. Comput. Phys. 106, 2 (1993), 355–365.
18. Timothy A Davis et al. 2015. SuiteSparse: A suite of sparse matrix software. URL http://faculty.cse.tamu.edu/davis/suitesparse.html (2015).
19. Fernando de Goes, Beibei Liu, Max Budninskiy, Yiying Tong, and Mathieu Desbrun. 2014. Discrete 2-tensor fields on triangulations. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 13–24.
20. Jesse Douglas. 1931. Solution of the problem of Plateau. Trans. Amer. Math. Soc. 33, 1 (1931), 263–321.
21. Jérôme Droniou and Christophe Le Potier. 2011. Construction and convergence study of schemes preserving the elliptic local maximum principle. SIAM J. Numer. Anal. 49, 2 (2011), 459–490.
22. Xingyi Du, Noam Aigerman, Qingnan Zhou, Shahar Z Kovalsky, Yajie Yan, Danny M Kaufman, and Tao Ju. 2020. Lifting simplices to find injectivity. ACM Transactions on Graphics (TOG) 39, 4 (2020), 120–1.
23. Xingyi Du, Noam Aigerman, Qingnan Zhou, Shahar Z Kovalsky, Yajie Yan, Danny M Kaufman, and Tao Ju. 2021. Optimizing Global Injectivity for Constrained Parameterization. ACM Transactions on Graphics (TOG) 40, 8 (2021), 1x.
24. Xingyi Du, Danny M Kaufman, Qingnan Zhou, Shahar Kovalsky, Yajie Yan, Noam Aigerman, and Tao Ju. 2022. Isometric Energies for Recovering Injectivity in Constrained Mapping. In SIGGRAPH Asia 2022 Conference Papers. 1–9.
25. Peter Duren. 2004. Harmonic mappings in the plane. Vol. 156. Cambridge University Press.
26. Lawrence C Evans. 1998. Partial differential equations. Graduate studies in mathematics 19, 4 (1998), 7.
27. Yu Fang, Minchen Li, Chenfanfu Jiang, and Danny M Kaufman. 2021. Guaranteed globally injective 3D deformation processing. ACM Transactions on Graphics (TOG) 40, 4 (2021), 10–1145.
28. Guy Fargion and Ofir Weber. 2022. Globally Injective Flattening via a Reduced Harmonic Subspace. ACM Transactions on Graphics (TOG) 41, 6 (2022), 1–17.
29. Michael Floater. 2003a. One-to-one piecewise linear mappings over triangulations. Math. Comp. 72, 242 (2003), 685–696.
30. Michael S Floater. 2003b. Mean value coordinates. Computer Aided Geometric Design 20, 1 (2003), 19–27.
31. Emil O Frind and George F Pinder. 1973. Galerkin solution of the inverse problem for aquifer transmissivity. Water Resources Research 9, 5 (1973), 1397–1410.
32. Xiao-Ming Fu, Yang Liu, and Baining Guo. 2015. Computing locally injective mappings by advanced MIPS. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–12.
33. Xiao-Ming Fu, Jian-Ping Su, Zheng-Yu Zhao, Qing Fang, Chunyang Ye, and Ligang Liu. 2021. Inversion-free geometric mapping construction: A survey. Computational Visual Media 7, 3 (2021), 289–318.
34. Ming Gao, Nathan Mitchell, and Eftychios Sifakis. 2014. Steklov-Poincaré skinning. In Proc. Symposium on Computer Animation. 139–148.
35. Vladimir Garanzha, Igor Kaporin, Liudmila Kudryavtseva, François Protais, Nicolas Ray, and Dmitry Sokolov. 2021. Foldover-free maps in 50 lines of code. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–16.
36. Frederick P Gardiner and Nikola Lakic. 2000. Quasiconformal Teichmuller theory. Number 76. American Mathematical Soc.
37. David Gilbarg and Neil S Trudinger. 2015. Elliptic partial differential equations of second order. Springer.
38. Mark Gillespie, Boris Springborn, and Keenan Crane. 2021. Discrete conformal equivalence of polyhedral surfaces. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–20.
39. Steven J Gortler, Craig Gotsman, and Dylan Thurston. 2006. Discrete one-forms on meshes and applications to 3D mesh parameterization. Computer Aided Geometric Design 23, 2 (2006), 83–112.
40. Xianfeng David Gu, Feng Luo, Jian Sun, and Tianqi Wu. 2018. A discrete uniformization theorem for polyhedral surfaces. Journal of Differential Geometry 109, 2 (2018), 223–256.
41. Michael Hinze and Tran Nhan Tam Quyen. 2016. Matrix coefficient identification in an elliptic equation with the convex energy functional method. Inverse Problems 32, 8 (2016), 085007.
42. Kai Hormann and Giinther Greiner. 2000. MIPS: An Efficient Global Parametrization Method. France on 1–7 July 1999. Proceedings, Volume 1. Curve and Surface Design. F61775-99-WF068 (2000), 153.
43. Victor Isakov. 2017. Inverse Problems for Partial Differential Equations. Vol. 127. Springer.
44. Kazufumi Ito and Karl Kunisch. 1990. The augmented Lagrangian method for parameter estimation in elliptic systems. SIAM Journal on Control and Optimization 28, 1 (1990), 113–136.
45. Tadeusz Iwaniec, Leonid V Kovalev, and Jani Onninen. 2012. Hopf differentials and smoothing Sobolev homeomorphisms. International Mathematics Research Notices 2012, 14 (2012), 3256–3277.
46. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial complex augmentation framework for bijective maps. ACM Transactions on Graphics 36, 6 (2017).
47. Andreas Kirsch. 2011. An introduction to the mathematical theory of inverse problems. Vol. 120. Springer Science & Business Media.
48. Hellmuth Kneser. 1926. Losung der aufgabe 41. Jahresber. Deutsche Meth. (1926), 123–124.
49. Shahar Z Kovalsky, Noam Aigerman, Ronen Basri, and Yaron Lipman. 2014. Controlling singular values with semidefinite programming. ACM Transactions on Graphics (TOG) 33, 4 (2014), 68–1.
50. Shahar Z Kovalsky, Noam Aigerman, Ingrid Daubechies, Michael Kazhdan, Jianfeng Lu, and Stefan Steinerberger. 2020. Non-convex planar harmonic maps. arXiv preprint arXiv:2001.01322 (2020).
51. Shahar Z Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated quadratic proxy for geometric optimization. ACM Transactions on Graphics (TOG) 35, 4 (2016), 134.
52. Zohar Levi and Ofir Weber. 2016. On the convexity and feasibility of the bounded distortion harmonic mapping problem. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1–15.
53. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Transactions on Graphics (TOG) 21, 3 (2002), 362–371.
54. Wentao Liao, Renjie Chen, Yuchen Hua, Ligang Liu, and Ofir Weber. 2021. Real-time locally injective volumetric deformation. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–16.
55. Selena Ling, Nicholas Sharp, and Alec Jacobson. 2022. VectorAdam for rotation equivariant geometry optimization. Advances in Neural Information Processing Systems (2022).
56. Yaron Lipman. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Transactions on Graphics (TOG) 31, 4 (2012), 1–13.
57. Yaron Lipman. 2014. Bijective mappings of meshes with boundary and the degree in mesh processing. SIAM Journal on Imaging Sciences 7, 2 (2014), 1263–1283.
58. Yaron Lipman, Vladimir G Kim, and Thomas A Funkhouser. 2012. Simple formulas for quasiconformal plane deformations. ACM Transactions on Graphics (TOG) 31, 5 (2012), 1–13.
59. Richard Liska and Mikhail Shashkov. 2008. Enforcing the discrete maximum principle for linear finite element solutions of second-order elliptic problems. Commun. Comput. Phys. 3, 4 (2008), 852–877.
60. Ligang Liu, Chunyang Ye, Ruiqi Ni, and Xiao-Ming Fu. 2018. Progressive parameterizations. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–12.
61. Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, and Steven J Gortler. 2008. A local/global approach to mesh parameterization. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 1495–1504.
62. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2017. Quasi-newton methods for real-time simulation of hyperelastic materials. ACM Transactions on Graphics (TOG) 36, 3 (2017), 1–16.
63. Tiantian Liu, Ming Gao, Lifeng Zhu, Eftychios Sifakis, and Ladislav Kavan. 2016. Fast and robust inversion-free shape manipulation. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 1–11.
64. Changna Lu, Weizhang Huang, and Jianxian Qiu. 2014. Maximum principle in linear finite element approximations of anisotropic diffusion-convection-reaction problems. Numer. Math. 127, 3 (2014), 515–537.
65. Lok Ming Lui, Ka Chun Lam, Shing-Tung Yau, and Xianfeng Gu. 2014. Teichmuller mapping (t-map) and its applications to landmark matching registration. SIAM Journal on Imaging Sciences 7, 1 (2014), 391–426.
66. Lok Ming Lui and Tsz Ching Ng. 2015. A splitting method for diffeomorphism optimization problem using Beltrami coefficients. Journal of Scientific Computing 63, 2 (2015), 573–611.
67. Yanwen Luo. 2022. Spaces of geodesic triangulations of surfaces. Discrete & Computational Geometry (2022), 1–19.
68. Patrick Mullen, Yiying Tong, Pierre Alliez, and Mathieu Desbrun. 2008. Spectral conformal parameterization. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 1487–1494.
69. Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim, and Miles Macklin. 2015. Air meshes for robust collision handling. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–9.
70. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable locally injective mappings. ACM Transactions on Graphics (TOG) 36, 4 (2017), 1.
71. T. Rado. 1926. Aufgave 41. Jber. Deutsch. Math. 35 (1926).
72. Gerard R Richter. 1981. An inverse problem for the steady state diffusion equation. SIAM J. Appl. Math. 41, 2 (1981), 210–221.
73. Rohan Sawhney and Keenan Crane. 2017. Boundary First Flattening. ACM Transactions on Graphics (TOG) 37, 1 (2017), 5.
74. John Schreiner, Arul Asirvatham, Emil Praun, and Hugues Hoppe. 2004. Inter-surface mapping. In ACM SIGGRAPH 2004 Papers. 870–877.
75. Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally injective mappings. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 125–135.
76. Rajsekhar Setaluri, Yu Wang, Nathan Mitchell, Ladislav Kavan, and Eftychios Sifakis. 2015. Fast grid-based nonlinear elasticity for 2D deformations. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 67–76.
77. Alla Sheffer and Eric de Sturler. 2001. Parameterization of faceted surfaces for meshing using angle-based flattening. Engineering with Computers 17, 3 (2001), 326–337.
78. Alla Sheffer, Bruno Lévy, Maxim Mogilnitsky, and Alexander Bogomyakov. 2005. ABF++: fast and robust angle based flattening. ACM Transactions on Graphics (TOG) 24, 2 (2005), 311–330.
79. Hanxiao Shen, Zhongshi Jiang, Denis Zorin, and Daniele Panozzo. 2019. Progressive embedding. ACM Transactions on Graphics (TOG) 38, 4 (2019), 32.
80. Anna Shtengel, Roi Poranne, Olga Sorkine-Hornung, Shahar Z Kovalsky, and Yaron Lipman. 2017. Geometric optimization via composite majorization. ACM Transactions on Graphics (TOG) 36, 4 (2017), 1–11.
81. Jason Smith and Scott Schaefer. 2015. Bijective parameterization with free boundaries. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–9.
82. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling. In Proc. SGP, Vol. 4.
83. Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal equivalence of triangle meshes. In ACM Transactions on Graphics (TOG). 1–11.
84. Oded Stein, Jiajin Li, and Justin Solomon. 2022. A splitting scheme for flip-free distortion energies. SIAM Journal on Imaging Sciences 15, 2 (2022), 925–959.
85. Michael E Taylor. 2010. Partial differential equations I. Basic theory. Applied Mathematical Sciences 115 (2010).
86. Fredi Tröltzsch. 2010. Optimal control of partial differential equations: theory, methods, and applications. Vol. 112. American Mathematical Soc.
87. William Thomas Tutte. 1963. How to draw a graph. Proceedings of the London Mathematical Society 3, 1 (1963), 743–767.
88. Yu Wang, Mirela Ben-Chen, Iosif Polterovich, and Justin Solomon. 2018. Steklov spectral geometry for extrinsic shape analysis. ACM Transactions on Graphics (TOG) 37, 7 (2018), 21.
89. Yu Wang and Justin Solomon. 2019. Intrinsic and extrinsic operators for shape analysis. In Handbook of Numerical Analysis. Vol. 20. Elsevier, 41–115.
90. Yu Wang and Justin Solomon. 2021. Fast quasi-harmonic weights for geometric data interpolation. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–15.
91. Max Wardetzky, Saurabh Mathur, Felix Kälberer, and Eitan Grinspun. 2007. Discrete Laplace operators: no free lunch. In Symposium on Geometry Processing. 33–37.
92. Ofir Weber, Ashish Myles, and Denis Zorin. 2012. Computing extremal quasiconformal maps. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 1679–1689.
93. Ofir Weber and Denis Zorin. 2014. Locally injective parametrization with arbitrary fixed boundaries. ACM Transactions on Graphics (TOG) 33, 4 (2014), 75.
94. Stephen Wright, Jorge Nocedal, et al. 1999. Numerical optimization. Springer Science 35, 67–68 (1999), 7.
95. Yin Xu, Renjie Chen, Craig Gotsman, and Ligang Liu. 2011. Embedding a triangular graph within a given boundary. Computer Aided Geometric Design 28, 6 (2011), 349–356.
96. Shin Yoshizawa, Alexander Belyaev, and Hans-Peter Seidel. 2004. A fast and simple stretch-minimizing mesh parameterization. In Proceedings Shape Modeling Applications, 2004. IEEE, 200–208.
97. Rhaleb Zayer, Christian Rossl, and H-P Seidel. 2005. Discrete tensorial quasi-harmonic maps. In International Conference on Shape Modeling and Applications 2005 (SMI’05). IEEE, 276–285.
98. Yufeng Zhu, Robert Bridson, and Danny M Kaufman. 2018. Blended cured quasi-newton for distortion optimization. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–14.
