“Interactive cutting and tearing in projective dynamics with progressive cholesky updates” by Li, Liu, Kavan and Chen
Conference:
Type(s):
Title:
- Interactive cutting and tearing in projective dynamics with progressive cholesky updates
Session/Category Title: Geometry Processing and Simulation
Presenter(s)/Author(s):
Abstract:
We propose a new algorithm for updating a Cholesky factorization which speeds up Projective Dynamics simulations with topological changes. Our approach addresses an important limitation of the original Projective Dynamics, i.e., that topological changes such as cutting, fracturing, or tearing require full refactorization which compromises computation speed, especially in real-time applications. Our method progressively modifies the Cholesky factor of the system matrix in the global step instead of computing it from scratch. Only a small amount of overhead is added since most of the topological changes in typical simulations are continuous and gradual. Our method is based on the update and downdate routine in CHOLMOD, but unlike recent related work, supports dynamic sizes of the system matrix and the addition of new vertices. Our approach allows us to introduce clean cuts and perform interactive remeshing. Our experiments show that our method works particularly well in simulation scenarios involving cutting, tearing, and local remeshing operations.
References:
1. Iago Berndt, Rafael Torchelsen, and Anderson Maciel. 2017. Efficient surgical cutting with position-based dynamics. IEEE computer graphics and applications 37, 3 (2017), 24–31.
2. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective dynamics: Fusing constraint projections for fast simulation. ACM transactions on graphics (TOG) 33, 4 (2014), 1–11.
3. Christopher Brandt, Elmar Eisemann, and Klaus Hildebrandt. 2018. Hyper-reduced projective dynamics. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–13.
4. 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), 1–14.
5. Kazem Cheshmi, Danny M Kaufman, Shoaib Kamil, and Maryam Mehri Dehnavi. 2020. NASOQ: numerically accurate sparsity-oriented QP solver. ACM Transactions on Graphics (TOG) 39, 4 (2020), 96–1.
6. Elizabeth Cuthill. 1972. Several strategies for reducing the bandwidth of matrices. In Sparse matrices and their applications. Springer, 157–166.
7. Timothy A Davis. 2006. Direct methods for sparse linear systems. SIAM.
8. Timothy A Davis and William W Hager. 1999. Modifying a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 20, 3 (1999), 606–627.
9. Timothy A Davis and William W Hager. 2001. Multiple-rank modifications of a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 22, 4 (2001), 997–1013. Timothy A Davis and William W Hager. 2005. Row modifications of a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 26, 3 (2005), 621–639.
10. Timothy A. Davis and William W. Hager. 2009. Dynamic Supernodes in Sparse Cholesky Update/Downdate and Triangular Solves. ACM Trans. Math. Softw. 35, 4, Article 27 (Feb. 2009), 23 pages.
11. Timothy A. Davis, Sivasankaran Rajamanickam, and Wissam M. Sid-Lakhdar. 2016. A survey of direct methods for sparse linear systems. Acta Numerica 25 (2016), 383–566.
12. Tao Du, Kui Wu, Pingchuan Ma, Sebastien Wah, Andrew Spielberg, Daniela Rus, and Wojciech Matusik. 2021. DiffPD: Differentiable Projective Dynamics with Contact. arXiv preprint arXiv:2101.05917 (2021).
13. Andreas Enzenhöfer, Nicolas Lefebvre, and Sheldon Andrews. 2019. Efficient block pivoting for multibody simulations with contact. In Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. 1–9.
14. Marco Fratarcangeli, Valentina Tibaldo, and Fabio Pellacini. 2016. Vivace: A practical Gauss-Seidel method for stable soft body dynamics. ACM Transactions on Graphics (TOG) 35, 6 (2016), 1–9.
15. Philip E Gill, Gene H Golub, Walter Murray, and Michael A Saunders. 1974. Methods for modifying matrix factorizations. Mathematics of computation 28, 126 (1974), 505–535.
16. Johannes Grimm. 2005. Tearing of membranes for interactive real-time surgical training. Studies in health technology and informatics 111 (2005), 153–159.
17. Halfbrick Studios. 2010. Fruit Ninja. https://apps.apple.com/us/app/fruit-ninja/id403858572
18. Florian Hecht, Yeon Jin Lee, Jonathan R Shewchuk, and James F O’Brien. 2012. Updated sparse Cholesky factors for corotational elastodynamics. ACM Transactions on Graphics (TOG) 31, 5 (2012), 1–13.
19. Philipp Herholz and Marc Alexa. 2018. Factor once: reusing Cholesky factorizations on sub-meshes. ACM Transactions on Graphics (TOG) 37, 6 (2018), 1–9.
20. Philipp Herholz and Olga Sorkine-Hornung. 2020. Sparse Cholesky updates for interactive mesh parameterization. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–14.
21. Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. 1993. Mesh optimization. In Proceedings of the 20th annual conference on Computer graphics and interactive techniques. 19–26.
22. M Intel. 2007. Intel math kernel library. (2007).
23. George Karypis and Vipin Kumar. 2009. MeTis: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 4.0. http://www.cs.umn.edu/~metis.
24. Martin Komaritzan and Mario Botsch. 2018. Projective skinning. Proceedings of the ACM on Computer Graphics and Interactive Techniques 1, 1 (2018), 1–19.
25. Martin Komaritzan and Mario Botsch. 2019. Fast Projective Skinning. In Motion, Interaction and Games. 1–10.
26. Jing Li, Tiantian Liu, and Ladislav Kavan. 2019. Fast simulation of deformable characters with articulated skeletons in projective dynamics. In Proceedings of the 18th annual ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 1–10.
27. Jing Li, Tiantian Liu, and Ladislav Kavan. 2020. Soft Articulated Characters in Projective Dynamics. IEEE Transactions on Visualization and Computer Graphics (2020).
28. Joseph W. H. Liu, Esmond G. Ng, and Barry W. Peyton. 1993. On Finding Supernodes for Sparse Matrix Computations. SIAM J. Matrix Anal. Appl. 14, 1 (1993), 242–252. arXiv:https://doi.org/10.1137/0614019
29. 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.
30. Mickaël Ly, Jean Jouve, Laurence Boissieux, and Florence Bertails-Descoubes. 2020. Projective Dynamics with Dry Frictional Contact. ACM Transactions on Graphics 1 (2020), 8.
31. Aleka McAdams, Yongning Zhu, Andrew Selle, Mark Empey, Rasmus Tamstorf, Joseph Teran, and Eftychios Sifakis. 2011. Efficient elasticity for character skinning with contact and collisions. In ACM SIGGRAPH 2011 papers. 1–12.
32. Rahul Narain, Matthew Overby, and George E Brown. 2016. ADMM ⊇ projective dynamics: fast simulation of general constitutive models. In Symposium on Computer Animation, Vol. 1.
33. 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 (2017), 2222–2234.
34. Rasmus Tamstorf, Toby Jones, and Stephen F McCormick. 2015. Smoothed aggregation multigrid for cloth simulation. ACM Transactions on Graphics (TOG) 34, 6 (2015), 1–13.
35. Robert Endre Tarjan. 1976. Graph theory and Gaussian elimination. In Sparse Matrix Computations. Elsevier, 3–22.
36. Huamin Wang. 2015. A chebyshev semi-iterative approach for accelerating projective and position-based dynamics. ACM Transactions on Graphics (TOG) 34, 6 (2015), 1–9.
37. Yuting Wang, Chenfanfu Jiang, Craig A Schroeder, and Joseph Teran. 2014. An Adaptive Virtual Node Algorithm with Robust Mesh Cutting. In Symposium on Computer Animation. 77–85.
38. Jun Wu, Rüdiger Westermann, and Christian Dick. 2015. A survey of physically based simulation of cuts in deformable bodies. In Computer Graphics Forum, Vol. 34. Wiley Online Library, 161–187.
39. Zangyueyang Xian, Xin Tong, and Tiantian Liu. 2019. A Scalable Galerkin Multigrid Method for Real-time Simulation of Deformable Objects. ACM Transactions on Graphics (TOG) 38, 6 (2019).
40. Yu-Hong Yeung, Jessica Crouch, and Alex Pothen. 2016. Interactively cutting and constraining vertices in meshes using augmented matrices. ACM Transactions on Graphics (TOG) 35, 2 (2016), 1–17.
41. Yu-Hong Yeung, Alex Pothen, and Jessica Crouch. 2018. AMPS: A Real-time Mesh Cutting Algorithm for Surgical Simulations. arXiv preprint arXiv:1811.00328 (2018).
