“Accelerated quadratic proxy for geometric optimization”

  • ©Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman




    Accelerated quadratic proxy for geometric optimization

Session/Category Title:   MESHES & FIELDS




    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.


    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

ACM Digital Library Publication:

Overview Page: