“Blended cured quasi-newton for distortion optimization” by Zhu, Bridson and Kaufman
Conference:
Type:
Entry Number: 40
Title:
- Blended cured quasi-newton for distortion optimization
Session/Category Title: A Race to the Bottom (of the Geometric Energy Plot)
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Optimizing distortion energies over a mesh, in two or three dimensions, is a common and critical problem in physical simulation and geometry processing. We present three new improvements to the state of the art: a barrier-aware line-search filter that cures blocked descent steps due to element barrier terms and so enables rapid progress; an energy proxy model that adaptively blends the Sobolev (inverse-Laplacian-processed) gradient and L-BFGS descent to gain the advantages of both, while avoiding L-BFGS’s current limitations in distortion optimization tasks; and a characteristic gradient norm providing a robust and largely mesh- and energy-independent convergence criterion that avoids wrongful termination when algorithms temporarily slow their progress. Together these improvements form the basis for Blended Cured Quasi-Newton (BCQN), a new distortion optimization algorithm. Over a wide range of problems over all scales we show that BCQN is generally the fastest and most robust method available, making some previously intractable problems practical while offering up to an order of magnitude improvement in others.
References:
1. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2015. Seamless surface mappings. ACM Transactions on Graphics (TOG) 34, 4 (2015), 72. Google ScholarDigital Library
2. Mirela Ben-chen, Craig Gotsman, and Guy Bunin. 2008. Conformal flattening by curvature prescription and metric scaling. Computer Graphics Forum 27 (2008).Google Scholar
3. Dimitri P. Bertsekas. 2016. Nonlinear Programming. Athena Scientific.Google Scholar
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 (July 2013), 98:1–98:12. Google ScholarDigital Library
5. J Bonet and AJ Burton. 1998. A simple orthotropic, transversely isotropic hyperelastic constitutive equation for large strain computations. Computer methods in applied mechanics and engineering 162, 1 (1998), 151–164.Google Scholar
6. Allan F Bower. 2009. Applied mechanics of solids. CRC press.Google Scholar
7. Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A simple geometric model for elastic deformations. ACM Transactions on Graphics (TOG) 29, 4 (2010), 38. Google ScholarDigital Library
8. Renjie Chen and Ofir Weber. 2017. GPU-accelerated Locally Injective Shape Deformation. ACM Trans. Graph. 36, 6 (Nov. 2017), 214:1–214:13. Google ScholarDigital Library
9. 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), 108:1–108:12. Google ScholarDigital Library
10. Yanqing Chen, Timothy A. Davis, William W. Hager, and Sivasankaran Rajamanickam. 2008. Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate. ACM Transactions on Mathematical Software (TOMS) 35, 3 (2008), 14. Google ScholarDigital Library
11. Sebastian Claici, Mikhail Bessmeltsev, Scott Schaefer, and Justin Solomon. 2017. Isometry-Aware Preconditioning for Mesh Parameterization. In Proceedings of the Symposium on Geometry Processing.Google ScholarDigital Library
12. Richard W. Cottle, Jong-Shi Pang, and Richard E. Stone. 2009. The Linear Complementarity Problem. Society for Industrial & Applied Mathematics (SIAM).Google Scholar
13. Mathieu Desbrun, Mark Meyer, and Pierre Alliez. 2002. Intrinsic parameterizations of surface meshes. In Computer Graphics Forum, Vol. 21. Wiley Online Library, 209–218.Google Scholar
14. A Fischer. 1992. A special Newton-type optimization method. 24 (1992), 269–284.Google Scholar
15. Xiao-Ming Fu, Yang Liu, and Baining Guo. 2015. Computing locally injective mappings by advanced MIPS. ACM Transactions on Graphics (TOG) 34, 4 (2015), 71. Google ScholarDigital Library
16. N.J. Higham. 1992. Estimating the matrix p-norm. Numer. Math. 62 (1992). Google ScholarDigital Library
17. Kai Hormann and Günther Greiner. 2000. MIPS: An efficient global parametrization method. Technical Report. DTIC Document.Google Scholar
18. Lianjun Jiang, Richard H Byrd, Elizabeth Eskow, and Robert B Schnabel. 2004. A preconditioned L-BFGS algorithm with application to molecular energy minimization. Technical Report. DTIC Document.Google Scholar
19. Shahar Z Kovalsky, Noam Aigerman, Ronen Basri, and Yaron Lipman. 2015. Large-scale bounded distortion mappings. ACM Trans. Graph 34, 6 (2015), 191. Google ScholarDigital Library
20. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH) 35, 4 (2016). Google ScholarDigital Library
21. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. In ACM Transactions on Graphics (TOG), Vol. 21. ACM, 362–371. Google ScholarDigital Library
22. Yaron Lipman. 2012. Bounded Distortion Mapping Spaces for Triangular Meshes. ACM Trans. Graph. 31, 4 (July 2012), 108:1–108:13. Google ScholarDigital Library
23. Richard Lipton, Donald Rose, and Robert Targan. 1979. Generalized Nested Dissection. SIAM J. Numer. Anal. 16, 2 (1979), 346–358.Google ScholarDigital Library
24. 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. Google ScholarDigital Library
25. 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), 23. Google ScholarDigital Library
26. Tobias Martin, Pushkar Joshi, Miklós Bergou, and Nathan Carr. 2013. Efficient Non-linear Optimization via Multi-scale Gradient Filtering. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 89–100. Google ScholarDigital Library
27. Melvin Mooney. 1940. A Theory of Large Elastic Deformation. Journal of Applied Physics 11, 9 (1940), 582–592.Google ScholarCross Ref
28. Patrick Mullen, Yiying Tong, Pierre Alliez, and Mathieu Desbrun. 2008. Spectral Conformal Parameterization. In Proceedings of the Symposium on Geometry Processing (SGP ’08). Eurographics Association, 1487–1494. Google ScholarDigital Library
29. Yurii Nesterov. 1983. A method of solving a convex programming problem with convergence rate O(1/sqr(k)). Soviet Mathematics Doklady 27 (1983), 372–376.Google Scholar
30. JW Neuberger. 1985. Steepest descent and differential equations. Journal of the Mathematical Society of Japan 37, 2 (1985), 187–195.Google ScholarCross Ref
31. J. Nocedal and S. Wright. 2006. Numerical Optimization. Springer New York.Google Scholar
32. Raymond Ogden. 1972. Large Deformation Isotropic Elasticity – On the Correlation of Theory and Experiment for Incompressible Rubberlike Solids. In Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences. 565–584.Google Scholar
33. Cosmin G. Petra, Olaf Schenk, and Mihai Anitescu. 2014a. Real-time stochastic optimization of complex energy systems on high-performance computers. IEEE Computing in Science & Engineering 16, 5 (2014).Google ScholarCross Ref
34. Cosmin G. Petra, Olaf Schenk, Miles Lubin, and Klaus Gärtner. 2014b. An augmented incomplete factorization approach for computing the Schur complement in stochastic optimization. SIAM Journal on Scientific Computing 36, 2 (2014).Google ScholarCross Ref
35. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 2 (April 2017), 16:1–16:16. Google ScholarDigital Library
36. Ronald S. Rivlin. 1948. Some Applications of Elasticity Theory to Rubber Engineering. In Proc. Rubber Technology Conference. 1–8.Google Scholar
37. 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), 11. Google ScholarDigital Library
38. Breannan Smith, Danny M. Kaufman, Etienne Vouga, Rasmus Tamstorf, and Eitan Grinspun. 2012. Reflections on Simultaneous Impact. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2012) 31, 4 (2012), 106:1–106:12. Google ScholarDigital Library
39. Jason Smith and Scott Schaefer. 2015. Bijective parameterization with free boundaries. ACM Transactions on Graphics (TOG) 34, 4 (2015), 70. Google ScholarDigital Library
40. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling. In Symposium on Geometry processing, Vol. 4. Google ScholarDigital Library
41. 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. Google ScholarDigital Library
42. Huamin Wang and Yin Yang. 2016. Descent methods for elastic body simulation on the GPU. ACM Transactions on Graphics (TOG) 35, 6 (2016), 212. Google ScholarDigital Library
43. Ofir Weber, Ashish Myles, and Denis Zorin. 2012. Computing extremal quasiconformal maps. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 1679–1689. Google ScholarDigital Library
44. Hongyi Xu, Funshing Sin, Yufeng Zhu, and Jernej Barbič. 2015. Nonlinear material design using principal stretches. ACM Transactions on Graphics (TOG) 34, 4 (2015), 75. Google ScholarDigital Library
