“GPU-accelerated locally injective shape deformation” by Chen and Weber
Conference:
Type(s):
Title:
- GPU-accelerated locally injective shape deformation
Session/Category Title: Mappings and Deformation
Presenter(s)/Author(s):
Abstract:
We present a highly efficient planar meshless shape deformation algorithm. Our method is based on an unconstrained minimization of isometric energies, and is guaranteed to produce C∞ locally injective maps by operating within a reduced dimensional subspace of harmonic maps. We extend the harmonic subspace of [Chen and Weber 2015] to support multiply-connected domains, and further provide a generalization of the bounded distortion theorem that appeared in that paper. Our harmonic map, as well as the gradient and the Hessian of our isometric energies possess closed-form expressions. A key result is a simple-and-fast analytic modification of the Hessian of the energy such that it is positive definite, which is crucial for the successful operation of a Newton solver. The method is straightforward to implement and is specifically designed to harness the processing power of modern graphics hardware. Our modified Newton iterations are shown to be extremely effective, leading to fast convergence after a handful of iterations, while each iteration is fast due to a combination of a number of factors, such as the smoothness and the low dimensionality of the subspace, the closed-form expressions for the differentials, and the avoidance of expensive strategies to ensure positive definiteness. The entire pipeline is carried out on the GPU, leading to deformations that are significantly faster to compute than the state-of-the-art.
References:
1. L.V. Ahlfors. 1979. Complex analysis: an introduction to the theory of analytic functions of one complex variable. McGraw-Hill.
2. Noam Aigerman and Yaron Lipman. 2013. Injective and bounded distortion mappings in 3D. ACM Transactions on Graphics 32, 4 (2013), 106.
3. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2014. Lifted bijections for low distortion surface mappings. ACM Transactions on Graphics 33, 4 (2014), 69.
4. MOSEK ApS. 2017. The MOSEK optimization software. http://www.mosek.com/
5. Sheldon Axler. 1986. Harmonic functions from a complex analysis viewpoint. The American mathematical monthly 93, 4 (1986), 246–258.
6. Alon Bright, Edward Chien, and Ofir Weber. 2017. Harmonic Global Parametrization with Rational Holonomy. ACM Transactions on Graphics 36, 4, Article 89 (2017).
7. Renjie Chen and Ofir Weber. 2015. Bounded distortion harmonic mappings in the plane. ACM Transactions on Graphics 34, 4, Article 73 (2015).
8. Edward Chien, Renjie Chen, and Ofir Weber. 2016a. Bounded Distortion Harmonic Shape Interpolation. ACM Transactions on Graphics 35, 4, Article 105 (2016).
9. Edward Chien, Zohar Levi, and Ofir Weber. 2016b. Bounded distortion parametrization in the space of metrics. ACM Transactions on Graphics 35, 6, Article 215 (2016).
10. cuSOLVER. 2017. CUDA Linear Solvers Library. http://developer.nvidia.com/cusolver. (2017). Accessed: 13-May-2017.
11. Peter Duren. 2004. Harmonic mappings in the plane. Cambridge University Press.
12. Xiao-Ming Fu and Yang Liu. 2016. Computing inversion-free mappings by simplex assembly. ACM Transactions on Graphics 35, 6 (2016), 216.
13. Xiao-Ming Fu, Yang Liu, and Baining Guo. 2015. Computing locally injective mappings by advanced MIPS. ACM Transactions on Graphics 34, 4 (2015), 71.
14. Eden Fedida Hefetz, Edward Chien, and Ofir Weber. 2017. Fast Planar Harmonic Deformations with Alternating Tangential Projections. Computer Graphics Forum 36, 5 (2017), 175–188. Proceedings of Symposium on Geometry Processing 2017.
15. Kai Hormann and Michael S. Floater. 2006. Mean value coordinates for arbitrary planar polygons. ACM Transactions on Graphics 25, 4 (2006), 1424–1441.
16. Takeo Igarashi, Tomer Moscovich, and John F. Hughes. 2005. As-rigid-as-possible shape manipulation. ACM Transactions on Graphics 24, 3 (2005), 1134–1141.
17. Alec Jacobson, Ilya Baran, Jovan Popović, and Olga Sorkine. 2011. Bounded biharmonic weights for real-time deformation. ACM Transactions on Graphics 30, 4, Article 78 (2011).
18. Ladislav Kavan, Steven Collins, Jiří Žára, and Carol O’Sullivan. 2007. Skinning with dual quaternions. In Proceedings of the 2007 symposium on Interactive 3D graphics and games. ACM, 39–46.
19. Shahar Z. Kovalsky, Noam Aigerman, Ronen Basri, and Yaron Lipman. 2015. Large-scale bounded distortion mappings. ACM Transactions on Graphics 34, 6, Article 191 (2015).
20. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Transactions on Graphics 35, 4, Article 134 (2016).
21. Zohar Levi and Ofir Weber. 2016. On the convexity and feasibility of the bounded distortion harmonic mapping problem. ACM Transactions on Graphics 35, 4, Article 106 (2016).
22. Yaron Lipman. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Transactions on Graphics 31, 4 (2012), 108.
23. Yaron Lipman, Johannes Kopf, Daniel Cohen-Or, and David Levin. 2007. GPU-assisted positive mean value coordinates for mesh deformations. In Symposium on geometry processing, Vol. 257. 117–123.
24. Yaron Lipman, Olga Sorkine, David Levin, and Daniel Cohen-Or. 2005. Linear rotation-invariant coordinates for meshes. ACM Transactions on Graphics 24, 3 (2005), 479–487.
25. Ligang Liu, Lei Zhang, YinXu, Craig Gotsman, and Steven J. Gortler. 2008. A local/global approach to mesh parameterization. Computer Graphics Forum 27, 5 (2008), 1495–1504.
26. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2017. Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials. ACM Transactions on Graphics 36, 3 (2017), 23.
27. Tobias Martin, Pushkar Joshi, Miklós Bergou, and Nathan Carr. 2013. Efficient Nonlinear Optimization via Multi-scale Gradient Filtering. Computer Graphics Forum 32, 6 (2013), 89–100.
28. Jorge Nocedal and Stephen Wright. 2006. Numerical Optimization. Springer New York.
29. Roi Poranne and Yaron Lipman. 2014. Provably good planar mappings. ACM Transactions on Graphics 33, 4 (2014), 76.
30. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Transactions on Graphics 36, 2, Article 16 (2017).
31. John Schreiner, Arul Asirvatham, Emil Praun, and Hugues Hoppe. 2004. Inter-surface mapping. ACM Transactions on Graphics 23, 3 (2004), 870–877.
32. Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally injective mappings. Computer Graphics Forum 32, 5 (2013), 125–135.
33. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Transactions on Graphics 34, 4, Article 70 (2015).
34. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible Surface Modeling. In Proceedings of the Symposium on Geometry Processing. Eurographics, Switzerland, 109–116.
35. Joseph Teran, Eftychios Sifakis, Geoffrey Irving, and Ronald Fedkiw. 2005. Robust quasistatic finite elements and flesh simulation. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer Animation. ACM, 181–190.
36. Amir Vaxman, Christian Müller, and Ofir Weber. 2015. Conformal mesh deformations with Möbius transformations. ACM Transactions on Graphics 34, 4, Article 55 (2015).
37. Ofir Weber. 2010. Hybrid Methods for Interactive Shape Manipulation. Ph.D. Dissertation. Technion – Israel Institute of Technology.
38. Ofir Weber. 2017. Planar Shape Deformation. In Generalized Barycentric Coordinates in Computer Graphics and Computational Mechanics, Kai Hormann and N. Sukumar (Eds.). CRC Press, Boca Raton, FL, Chapter 7, 28.
39. Ofir Weber, Mirela Ben-Chen, and Craig Gotsman. 2009. Complex Barycentric Coordinates with Applications to Planar Shape Deformation. Computer Graphics Forum 28, 2 (2009), 587–597. Cross Ref
40. Ofir Weber, Mirela Ben-Chen, Craig Gotsman, and Kai Hormann. 2011. A complex view of barycentric mappings. Computer Graphics Forum 30, 5 (2011), 1533–1542. Cross Ref
41. Ofir Weber and Craig Gotsman. 2010. Controllable conformal maps for shape deformation and interpolation. ACM Transactions on Graphics 29, 4, Article 78 (2010).
42. Ofir Weber, Olga Sorkine, Yaron Lipman, and Craig Gotsman. 2007. Context-Aware Skeletal Shape Deformation. Computer Graphics Forum 26, 3 (2007), 265–274. Cross Ref
43. Rhaleb Zayer, Christian Rössl, Zachi Karni, and Hans-Peter Seidel. 2005. Harmonic guidance for surface deformation. Computer Graphics Forum 24, 3 (2005), 601–609. Cross Ref
