“Accelerated quadratic proxy for geometric optimization”
Conference:
Type:
Title:
- Accelerated quadratic proxy for geometric optimization
Session/Category Title: MESHES & FIELDS
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We present the Accelerated Quadratic Proxy (AQP) – a simple first-order algorithm for the optimization of geometric energies defined over triangular and tetrahedral meshes.The main stumbling block of current optimization techniques used to minimize geometric energies over meshes is slow convergence due to ill-conditioning of the energies at their minima. We observe that this ill-conditioning is in large part due to a Laplacian-like term existing in these energies. Consequently, we suggest to locally use a quadratic polynomial proxy, whose Hessian is taken to be the Laplacian, in order to achieve a preconditioning effect. This already improves stability and convergence, but more importantly allows incorporating acceleration in an almost universal way, that is independent of mesh size and of the specific energy considered.Experiments with AQP show it is rather insensitive to mesh resolution and requires a nearly constant number of iterations to converge; this is in strong contrast to other popular optimization techniques used today such as Accelerated Gradient Descent and Quasi-Newton methods, e.g., L-BFGS. We have tested AQP for mesh deformation in 2D and 3D as well as for surface parameterization, and found it to provide a considerable speedup over common baseline techniques.
References:
1. Aigerman, N., Poranne, R., and Lipman, Y. 2015. Seamless surface mappings. ACM Transactions on Graphics (TOG) 34, 4, 72. Google ScholarDigital Library
2. Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. In Proceedings of the 25th annual conference on Computer graphics and interactive techniques, ACM, 43–54. Google ScholarDigital Library
3. Beck, A., and Teboulle, M. 2009. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences 2, 1, 183–202. Google ScholarDigital Library
4. Ben-Chen, M., Weber, O., and Gotsman, C. 2009. Variational harmonic maps for space deformation. In ACM Transactions on Graphics (TOG), vol. 28, ACM, 34. Google ScholarDigital Library
5. Botsch, M., and Sorkine, O. 2008. On linear variational surface deformation methods. Visualization and Computer Graphics, IEEE Transactions on 14, 1, 213–230. Google ScholarDigital Library
6. Botsch, M., Pauly, M., Gross, M. H., and Kobbelt, L. 2006. Primo: coupled prisms for intuitive surface modeling. In Symposium on Geometry Processing, no. EPFL-CONF-149310, 11–20. Google ScholarDigital Library
7. Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A simple geometric model for elastic deformations. In ACM Transactions on Graphics (TOG), vol. 29, ACM, 38. Google ScholarDigital Library
8. Combettes, P. L., and Pesquet, J.-C. 2011. Proximal splitting methods in signal processing. In Fixed-point algorithms for inverse problems in science and engineering. Springer, 185–212.Google Scholar
9. Degener, P., Meseth, J., and Klein, R. 2003. An adaptable surface parameterization method. IMR 3, 201–213.Google Scholar
10. Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic parameterizations of surface meshes. In Computer Graphics Forum, vol. 21, Wiley Online Library, 209–218.Google Scholar
11. Farago, I., and Karatson, J. 2008. Sobolev gradient type preconditioning for the saint-venant model of elasto-plastic torsion. Int. J. Numer. Anal. Model 5, 2, 206–221.Google Scholar
12. Floater, M. S., and Hormann, K. 2005. Surface parameterization: a tutorial and survey. Advances in multiresolution for geometric modelling 1, 1.Google Scholar
13. Fu, X.-M., Liu, Y., and Guo, B. 2015. Computing locally injective mappings by advanced mips. ACM Transactions on Graphics (TOG) 34, 4, 71. Google ScholarDigital Library
14. Grinspun, E., Hirani, A., Desbrun, M., and Schröder, P. 2003. Discrete Shells. In ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 62–67. Google ScholarDigital Library
15. Hildebrandt, K., Schulz, C., Tycowicz, C. V., and Polthier, K. 2011. Interactive surface modeling using modal analysis. ACM Transactions on Graphics (TOG) 30, 5, 119. Google ScholarDigital Library
16. Hormann, K., and Greiner, G. 2000. Mips: An efficient global parametrization method. Tech. rep., DTIC Document.Google Scholar
17. Huang, J., Shi, X., Liu, X., Zhou, K., Wei, L.-Y., Teng, S.-H., Bao, H., Guo, B., and Shum, H.-Y. 2006. Subspace gradient domain mesh deformation. ACM Transactions on Graphics (TOG) 25, 3, 1126–1134. Google ScholarDigital Library
18. Huang, Q.-X., Wicke, M., Adams, B., and Guibas, L. 2009. Shape decomposition using modal analysis. In Computer Graphics Forum, vol. 28, Wiley Online Library, 407–416.Google Scholar
19. Iserles, A. 2009. A first course in the numerical analysis of differential equations. No. 44. Cambridge University Press. Google ScholarDigital Library
20. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. In ACM Transactions on Graphics (TOG), vol. 24, ACM, 561–566. Google ScholarDigital Library
21. Kovalsky, S. Z., Aigerman, N., Basri, R., and Lipman, Y. 2014. Controlling singular values with semidefinite programming. ACM Transactions on Graphics 33, 4, 68. Google ScholarDigital Library
22. Kovalsky, S. Z., Aigerman, N., Basri, R., and Lipman, Y. 2015. Large-scale bounded distortion mappings. ACM Transactions on Graphics (TOG) 34, 6, 191. Google ScholarDigital Library
23. Lee, J., Sun, Y., and Saunders, M. 2012. Proximal newton-type methods for convex optimization. In Advances in Neural Information Processing Systems, 836–844.Google Scholar
24. Levy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Transactions on Graphics (TOG) 21, 3, 362–371. Google ScholarDigital Library
25. Li, H., and Lin, Z. 2015. Accelerated proximal gradient methods for nonconvex programming. In Advances in Neural Information Processing Systems, 379–387. Google ScholarDigital Library
26. Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. J. 2008. A local/global approach to mesh parameterization. In Computer Graphics Forum, vol. 27, Wiley Online Library, 1495–1504. Google ScholarDigital Library
27. Liu, T., Bargteil, A. W., O’Brien, J. F., and Kavan, L. 2013. Fast simulation of mass-spring systems. ACM Transactions on Graphics (TOG) 32, 6, 214. Google ScholarDigital Library
28. Nesterov, Y 1983. A method of solving a convex programming problem with convergence rate o (1/k2). In Soviet Mathematics Doklady, vol. 27, 372–376.Google Scholar
29. Nocedal, J., and Wright, S. 2006. Numerical optimization. Springer Science & Business Media.Google Scholar
30. Ochs, P., Chen, Y., Brox, T., and Pock, T. 2014. ipiano: Inertial proximal algorithm for nonconvex optimization. SIAM Journal on Imaging Sciences 7, 2, 1388–1419.Google ScholarCross Ref
31. Papadopoulo, T., and Lourakis, M. I. 2000. Estimating the jacobian of the singular value decomposition: Theory and applications. In Computer Vision-ECCV 2000. Springer, 554–570. Google ScholarDigital Library
32. Parikh, N., and Boyd, S. P. 2014. Proximal algorithms. Foundations and Trends in optimization 1,3, 127–239. Google ScholarDigital Library
33. Petersen, K. B., Pedersen, M. S., et al. 2008. The matrix cookbook. Technical University of Denmark 7, 15.Google Scholar
34. Polyak, B. T. 1964. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics 4, 5, 1–17.Google ScholarCross Ref
35. Saad, Y., and Van Der Vorst, H. A. 2000. Iterative solution of linear systems in the 20th century. Journal of Computational and Applied Mathematics 123, 1, 1–33. Google ScholarDigital Library
36. Sacht, L., Vouga, E., and Jacobson, A. 2015. Nested cages. ACM Transactions on Graphics (TOG) 34, 6, 170. Google ScholarDigital Library
37. Schuller, C., Kavan, L., Panozzo, D., and Sorkine-Hornung, O. 2013. Locally injective mappings. Computer Graphics Forum (proceedings of Symposium on Geometry Processing) 32, 5. Google ScholarDigital Library
38. Sheffer, A., Praun, E., and Rose, K. 2006. Mesh parameterization methods and their applications. Foundations and Trends(R) in Computer Graphics and Vision 2, 2, 105–171. Google ScholarDigital Library
39. Si, H. 2015. Tetgen, a delaunay-based quality tetrahedral mesh generator. ACM Transactions on Mathematical Software (TOMS) 41, 2, 11. Google ScholarDigital Library
40. Smith, J., and Schaefer, S. 2015. Bijective parameterization with free boundaries. ACM Trans. Graph. 34, 4 (July), 70:1–70:9. Google ScholarDigital Library
41. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Symposium on Geometry processing, vol. 4. Google ScholarDigital Library
42. Terzopoulos, D., and Fleischer, K. 1988. Modeling inelastic deformation: viscolelasticity, plasticity, fracture. In ACM Siggraph Computer Graphics, vol. 22, ACM, 269–278. Google ScholarDigital Library
43. Tuckerman, L. S. 2015. Laplacian preconditioning for the inverse arnoldi method. Communications in Computational Physics 18, 05, 1336–1351.Google ScholarCross Ref
44. Tutte, W. T. 1963. How to draw a graph. Proc. London Math. Soc 13, 3, 743–768.Google ScholarCross Ref
45. Wang, Y., Jacobson, A., Barbic, J., and Kavan, L. 2015. Linear subspace design for real-time shape deformation. ACM Trans. Graph. 34, 4. Google ScholarDigital Library
46. Wardetzky, M., Bergou, M., Harmon, D., Zorin, D., and Grinspun, E. 2007. Discrete quadratic curvature energies. Computer Aided Geometric Design 24, 8, 499–518. Google ScholarDigital Library
