“WRAPD: weighted rotation-aware ADMM for parameterization and deformation” by Brown and Narain

Local-global solvers such as ADMM for elastic simulation and geometry optimization struggle to resolve large rotations such as bending and twisting modes, and large distortions in the presence of barrier energies. We propose two improvements to address these challenges. First, we introduce a novel local-global splitting based on the polar decomposition that separates the geometric nonlinearity of rotations from the material nonlinearity of the deformation energy. The resulting ADMM-based algorithm is a combination of an L-BFGS solve in the global step and proximal updates of element stretches in the local step. We also introduce a novel method for dynamic reweighting that is used to adjust element weights at runtime for improved convergence. With both improved rotation handling and element weighting, our algorithm is considerably faster than state-of-the-art approaches for quasi-static simulations. It is also much faster at making early progress in parameterization problems, making it valuable as an initializer to jump-start second-order algorithms.

1. Christie Alappat, Achim Basermann, Alan R. Bishop, Holger Fehske, Georg Hager, Olaf Schenk, Jonas Thies, and Gerhard Wellein. 2020. A Recursive Algebraic Coloring Technique for Hardware-Efficient Symmetric Sparse Matrix-Vector Multiplication. ACM Trans. Parallel Comput. 7, 3, Article 19 (June 2020), 37 pages. Google ScholarDigital Library
2. Martin Benning, Florian Knoll, Carola-Bibiane Schönlieb, and Tuomo Valkonen. 2016. Preconditioned ADMM with Nonlinear Operator Constraint. In System Modeling and Optimization, Lorena Bociu, Jean-Antoine Désidéri, and Abderrahmane Habbal (Eds.). Springer International Publishing, Cham, 117–126.Google Scholar
3. Miklos Bergou, Max Wardetzky, David Harmon, Denis Zorin, and Eitan Grinspun. 2006. A Quadratic Bending Model for Inextensible Surfaces. In Proceedings of the Fourth Eurographics Symposium on Geometry Processing (SGP ’06). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 227–230. http://dl.acm.org/citation.cfm?id=1281957.1281987Google ScholarDigital Library
4. Matthias Bollhöfer, Aryan Eftekhari, Simon Scheidegger, and Olaf Schenk. 2019. Large-scale Sparse Inverse Covariance Matrix Estimation. SIAM Journal on Scientific Computing 41, 1 (2019), A380–A401. arXiv:https://doi.org/10.1137/17M1147615 Google ScholarDigital Library
5. Matthias Bollhöfer, Olaf Schenk, Radim Janalik, Steve Hamm, and Kiran Gullapalli. 2020. State-of-the-Art Sparse Direct Solvers. (2020), 3–33. Google ScholarCross Ref
6. Sofien Bouaziz, Mario Deuss, Yuliy Schwartzburg, Thibaut Weise, and Mark Pauly. 2012. Shape-Up: Shaping Discrete Geometry with Projections. Comput. Graph. Forum 31, 5 (Aug. 2012), 1657–1667. Google ScholarDigital Library
7. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective Dynamics: Fusing Constraint Projections for Fast Simulation. ACM Trans. Graph. 33, 4, Article 154 (July 2014), 11 pages. Google ScholarDigital Library
8. S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. 2011. Google ScholarDigital Library
9. Christopher Brandt, Elmar Eisemann, and Klaus Hildebrandt. 2018. Hyper-Reduced Projective Dynamics. ACM Trans. Graph. 37, 4, Article Article 80 (July 2018), 13 pages. 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 Trans. Math. Softw. 35, 3, Article 22 (Oct. 2008), 14 pages. Google ScholarDigital Library
11. S. Claici, M. Bessmeltsev, S. Schaefer, and J. Solomon. 2017. Isometry-Aware Preconditioning for Mesh Parameterization. Comput. Graph. Forum 36, 5 (Aug. 2017), 37–47. Google ScholarDigital Library
12. Anqi Fu, Junzi Zhang, and Stephen Boyd. 2020. Anderson Accelerated Douglas-Rachford Splitting. SIAM Journal on Scientific Computing 42, 6 (2020), A3560–A3583.Google ScholarDigital Library
13. Theodore F. Gast, Craig Schroeder, Alexey Stomakhin, Chenfanfu Jiang, and Joseph M. Teran. 2015. Optimization Integrator for Large Time Steps. IEEE Transactions on Visualization and Computer Graphics 21, 10 (Oct. 2015), 1103–1115. Google ScholarDigital Library
14. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial Complex Augmentation Framework for Bijective Maps. ACM Trans. Graph. 36, 6, Article 186 (Nov. 2017), 9 pages. Google ScholarDigital Library
15. Martin Komaritzan and Mario Botsch. 2018. Projective Skinning. In Proc. ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games.Google Scholar
16. Martin Komaritzan and Mario Botsch. 2019. Fast Projective Skinning. In Motion, Interaction and Games (MIG ’19). Association for Computing Machinery, New York, NY, USA, Article 22, 10 pages. Google ScholarDigital Library
17. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Trans. Graph. 35, 4, Article 134 (July 2016), 11 pages. Google ScholarDigital Library
18. Ligang Liu, Chunyang Ye, Ruiqi Ni, and Xiao-Ming Fu. 2018. Progressive Parameterizations. ACM Transactions on Graphics(SIGGRAPH) 37, 4 (2018).Google Scholar
19. Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, and Steven J. Gortler. 2008. A Local/Global Approach to Mesh Parameterization. In Proceedings of the Symposium on Geometry Processing (SGP ’08). Eurographics Association, Goslar, DEU, 1495–1504.Google ScholarDigital Library
20. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2017. Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials. ACM Trans. Graph. 36, 4, Article 116a (May 2017), 16 pages. Google ScholarDigital Library
21. Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, and Markus Gross. 2011. Example-based Elastic Materials. ACM Trans. Graph. 30, 4, Article 72 (July 2011), 8 pages.Google ScholarDigital Library
22. Rahul Narain, Matthew Overby, and George E. Brown. 2016. ADMM ⊇ Projective Dynamics: Fast Simulation of General Constitutive Models. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA ’16). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 21–28. http://dl.acm.org/citation.cfm?id=2982818.2982822Google Scholar
23. Wenqing Ouyang, Yue Peng, Yuxin Yao, Juyong Zhang, and Bailin Deng. 2020. Anderson Acceleration for Nonconvex ADMM Based on Douglas-Rachford Splitting. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 221–239.Google Scholar
24. Matthew Overby, George E. Brown, Jie Li, and Rahul Narain. 2017. ADMM ⊇ Projective Dynamics: Fast Simulation of Hyperelastic Models with Dynamic Constraints. IEEE Transactions on Visualization and Computer Graphics 23, 10 (Oct 2017), 2222–2234. Google ScholarDigital Library
25. Yue Peng, Bailin Deng, Juyong Zhang, Fanyu Geng, Wenjie Qin, and Ligang Liu. 2018. Anderson Acceleration for Geometry Optimization and Physics Simulation. ACM Trans. Graph. 37, 4, Article 42 (July 2018), 14 pages. Google ScholarDigital Library
26. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 2, Article 37a (April 2017). Google ScholarDigital Library
27. Anna Shtengel, Roi Poranne, Olga Sorkine-Hornung, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Geometric Optimization via Composite Majorization. ACM Trans. Graph. 36, 4, Article 38 (July 2017), 11 pages. Google ScholarDigital Library
28. Olga Sorkine and Marc Alexa. 2007. As-Rigid-as-Possible Surface Modeling. In Proceedings of the Fifth Eurographics Symposium on Geometry Processing (SGP ’07). Eurographics Association, Goslar, DEU, 109–116.Google ScholarDigital Library
29. Jian-Ping Su, Xiao-Ming Fu, and Ligang Liu. 2019. Practical Foldover-Free Volumetric Mapping Construction. Computer Graphics Forum 38, 7 (2019), 287–297. Google ScholarCross Ref
30. Jian-Ping Su, Chunyang Ye, Ligang Liu, and Xiao-Ming Fu. 2020. Efficient Bijective Parameterizations. ACM Trans. Graph. 39, 4, Article 111 (July 2020), 8 pages. Google ScholarDigital Library
31. Marcel Weiler, Dan Koschier, and Jan Bender. 2016. Projective Fluids. In Proceedings of the 9th International Conference on Motion in Games (MIG ’16). ACM, New York, NY, USA, 79–84. Google ScholarDigital Library
32. Juyong Zhang, Yue Peng, Wenqing Ouyang, and Bailin Deng. 2019. Accelerating ADMM for Efficient Simulation and Optimization. ACM Trans. Graph. 38, 6, Article Article 163 (Nov. 2019), 21 pages. Google ScholarDigital Library
33. Yufeng Zhu, Robert Bridson, and Danny M. Kaufman. 2018. Blended Cured Quasi-newton for Distortion Optimization. ACM Trans. Graph. 37, 4, Article 40 (July 2018), 14 pages. Google ScholarDigital Library