“Penetration-free projective dynamics on the GPU” by Lan, Ma, Yang, Zheng, Li, et al. …

We present a GPU algorithm for deformable simulation. Our method offers good computational efficiency and penetration-free guarantee at the same time, which are not common with existing techniques. The main idea is an algorithmic integration of projective dynamics (PD) and incremental potential contact (IPC). PD is a position-based simulation framework, favored for its robust convergence and convenient implementation. We show that PD can be employed to handle the variational optimization with the interior point method e.g., IPC. While conceptually straightforward, this requires a dedicated rework over the collision resolution and the iteration modality to avoid incorrect collision projection with improved numerical convergence. IPC exploits a barrier-based formulation, which yields an infinitely large penalty when the constraint is on the verge of being violated. This mechanism guarantees intersection-free trajectories of deformable bodies during the simulation, as long as they are apart at the rest configuration. On the downside, IPC brings a large amount of nonlinearity to the system, making PD slower to converge. To mitigate this issue, we propose a novel GPU algorithm named A-Jacobi for faster linear solve at the global step of PD. A-Jacobi is based on Jacobi iteration, but it better harvests the computation capacity on modern GPUs by lumping several Jacobi steps into a single iteration. In addition, we also re-design the CCD root finding procedure by using a new minimum-gradient Newton algorithm. Those saved time budgets allow more iterations to accommodate stiff IPC barriers so that the result is both realistic and collision-free. Putting together, our algorithm simulates complicated models of both solids and shells on the GPU at an interactive rate or even in real time.

1. Farid Alizadeh, Jean-Pierre A Haeberly, and Michael L Overton. 1997. Complementarity and nondegeneracy in semidefinite programming. Mathematical programming 77, 1 (1997), 111–128.Google Scholar
2. Owe Axelsson. 1977. Solution of linear systems of equations: iterative methods. In Sparse matrix techniques. Springer, 1–51.Google Scholar
3. Jernej Barbič and Yili Zhao. 2011. Real-time large-deformation substructuring. ACM transactions on graphics (TOG) 30, 4 (2011), 1–8.Google Scholar
4. Jernej Barbič and Doug L James. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. In ACM Trans. Graph. (TOG), Vol. 24. ACM, 982–990.Google ScholarDigital Library
5. 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.Google ScholarDigital Library
6. Robert Bridson, Ronald Fedkiw, and John Anderson. 2002. Robust treatment of collisions, contact and friction for cloth animation. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques. 594–603.Google ScholarDigital Library
7. Tyson Brochu, Essex Edwards, and Robert Bridson. 2012. Efficient geometrically exact continuous collision detection. ACM Transactions on Graphics (TOG) 31, 4 (2012), 1–7.Google ScholarDigital Library
8. Steve Capell, Seth Green, Brian Curless, Tom Duchamp, and Zoran Popović. 2002a. Interactive skeleton-driven dynamic deformations. In ACM Trans. Graph. (TOG), Vol. 21. ACM, 586–593.Google ScholarDigital Library
9. Steve Capell, Seth Green, Brian Curless, Tom Duchamp, and Zoran Popović. 2002b. A multiresolution framework for dynamic deformations. In Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation. 41–47.Google ScholarDigital Library
10. Min Gyu Choi and Hyeong-Seok Ko. 2005. Modal warping: Real-time simulation of large rotational deformation and manipulation. IEEE Trans. on Visualization and Computer Graphics 11, 1 (2005), 91–101.Google ScholarDigital Library
11. Jinhyun Choo, Yidong Zhao, Yupeng Jiang, Minchen Li, Chenfanfu Jiang, and Kenichi Soga. 2021. A barrier method for frictional contact on embedded interfaces. arXiv:2107.05814 [math.NA]Google Scholar
12. Sung-Jin Chung. 1989. NP-completeness of the linear complementarity problem. Journal of optimization theory and applications 60, 3 (1989), 393–399.Google ScholarDigital Library
13. Richard W Cottle, Jong-Shi Pang, and Richard E Stone. 2009. The linear complementarity problem. SIAM.Google Scholar
14. Gilles Daviet, Florence Bertails-Descoubes, and Laurence Boissieux. 2011. A hybrid iterative solver for robustly capturing coulomb friction in hair dynamics. In Proceedings of the 2011 SIGGRAPH Asia Conference. 1–12.Google ScholarDigital Library
15. Yu Fang, Minchen Li, Chenfanfu Jiang, and Danny M Kaufman. 2021. Guaranteed globally injective 3D deformation processing. ACM Trans. Graph.(TOG) 40, 4 (2021).Google ScholarDigital Library
16. Charbel Farhat, Michael Lesoinne, and Kendall Pierson. 2000. A scalable dual-primal domain decomposition method. Numerical linear algebra with applications 7, 7–8 (2000), 687–714.Google Scholar
17. François Faure, Benjamin Gilles, Guillaume Bousquet, and Dinesh K Pai. 2011. Sparse meshless models of complex deformable solids. In ACM Trans. Graph. (TOG), Vol. 30. ACM, 73.Google ScholarDigital Library
18. Zachary Ferguson, Minchen Li, Teseo Schneider, Francisca Gil-Ureta, Timothy Langlois, Chenfanfu Jiang, Denis Zorin, Danny M Kaufman, and Daniele Panozzo. 2021. Intersection-free rigid body dynamics. ACM Transactions on Graphics 40, 4 (2021), 183.Google ScholarDigital Library
19. 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.Google ScholarDigital Library
20. Marco Fratarcangeli, Huamin Wang, and Yin Yang. 2018. Parallel iterative solvers for real-time elastic deformations. In SIGGRAPH Asia 2018 Courses. 1–45.Google Scholar
21. Ming Gao, Andre Pradhana Tampubolon, Chenfanfu Jiang, and Eftychios Sifakis. 2017. An adaptive generalized interpolation material point method for simulating elastoplastic materials. ACM Trans. Graph. (TOG) 36, 6 (2017), 223.Google ScholarDigital Library
22. Benjamin Gilles, Guillaume Bousquet, Francois Faure, and Dinesh K Pai. 2011. Frame-based elastic models. ACM Trans. Graph. (TOG) 30, 2 (2011), 15.Google ScholarDigital Library
23. Gene H Golub and Richard S Varga. 1961. Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods. Numer. Math. 3, 1 (1961), 157–168.Google ScholarDigital Library
24. Eitan Grinspun, Petr Krysl, and Peter Schröder. 2002. CHARMS: A simple framework for adaptive simulation. ACM transactions on graphics (TOG) 21, 3 (2002), 281–290.Google ScholarDigital Library
25. William W Hager. 1989. Updating the inverse of a matrix. SIAM review 31, 2 (1989), 221–239.Google Scholar
26. David Harmon, Etienne Vouga, Breannan Smith, Rasmus Tamstorf, and Eitan Grinspun. 2009. Asynchronous contact mechanics. In ACM SIGGRAPH 2009 papers. 1–12.Google ScholarDigital Library
27. David Harmon, Etienne Vouga, Rasmus Tamstorf, and Eitan Grinspun. 2008. Robust treatment of simultaneous collisions. In ACM SIGGRAPH 2008 papers. 1–4.Google ScholarDigital Library
28. Kris K Hauser, Chen Shen, and James F O’Brien. 2003. Interactive Deformation Using Modal Analysis with Constraints.. In Graphics Interface, Vol. 3. 16–17.Google Scholar
29. Florian Hecht, Yeon Jin Lee, Jonathan R Shewchuk, and James F O’Brien. 2012. Updated sparse cholesky factors for corotational elastodynamics. ACM Trans. Graph. (TOG) 31, 5 (2012), 123.Google ScholarDigital Library
30. Rudi Helfenstein and Jonas Koko. 2012. Parallel preconditioned conjugate gradient algorithm on GPU. J. Comput. Appl. Math. 236, 15 (2012), 3584–3590.Google ScholarDigital Library
31. Nicholas J Higham. 2009. Cholesky factorization. Wiley Interdisciplinary Reviews: Computational Statistics 1, 2 (2009), 251–254.Google ScholarDigital Library
32. Takeo Igarashi, Tomer Moscovich, and John F Hughes. 2005. As-rigid-as-possible shape manipulation. ACM transactions on Graphics (TOG) 24, 3 (2005), 1134–1141.Google Scholar
33. Geoffrey Irving, Joseph Teran, and Ronald Fedkiw. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation. 131–140.Google ScholarDigital Library
34. Couro Kane, Jerrold E Marsden, Michael Ortiz, and Matthew West. 2000. Variational integrators and the Newmark algorithm for conservative and dissipative mechanical systems. International Journal for numerical methods in engineering 49, 10 (2000), 1295–1325.Google ScholarCross Ref
35. Carl T Kelley. 1995. Iterative methods for linear and nonlinear equations. SIAM.Google Scholar
36. Theodore Kim and Doug L James. 2009. Skipping steps in deformable simulation with online model reduction. In ACM Trans. Graph. (TOG), Vol. 28. ACM, 123.Google ScholarDigital Library
37. Theodore Kim and Doug L James. 2012. Physics-based character skinning using multidomain subspace deformations. IEEE transactions on visualization and computer graphics 18, 8 (2012), 1228–1240.Google ScholarDigital Library
38. Martin Komaritzan and Mario Botsch. 2018. Projective skinning. Proceedings of the ACM on Computer Graphics and Interactive Techniques 1, 1 (2018), 1–19.Google ScholarDigital Library
39. Martin Komaritzan and Mario Botsch. 2019. Fast projective skinning. In Motion, Interaction and Games. 1–10.Google Scholar
40. Lei Lan, Ran Luo, Marco Fratarcangeli, Weiwei Xu, Huamin Wang, Xiaohu Guo, Junfeng Yao, and Yin Yang. 2020. Medial Elastics: Efficient and Collision-Ready Deformation via Medial Axis Transform. ACM Transactions on Graphics (TOG) 39, 3 (2020), 1–17.Google ScholarDigital Library
41. Lei Lan, Yin Yang, Danny Kaufman, Junfeng Yao, Minchen Li, and Chenfanfu Jiang. 2021. Medial IPC: accelerated incremental potential contact with medial elastics. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–16.Google ScholarDigital Library
42. Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M Kaufman. 2020. Incremental potential contact: Intersection- and inversion-free, large-deformation dynamics. ACM transactions on graphics 39, 4 (2020).Google ScholarDigital Library
43. Minchen Li, Danny M. Kaufman, and Chenfanfu Jiang. 2021b. Codimensional Incremental Potential Contact. ACM Trans. Graph. (SIGGRAPH) 40, 4, Article 170 (2021).Google ScholarDigital Library
44. Xuan Li, Yu Fang, Minchen Li, and Chenfanfu Jiang. 2021a. BFEMP: Interpenetrationfree MPM-FEM coupling with barrier contact. Computer Methods in Applied Mechanics and Engineering (2021), 114350.Google Scholar
45. Tiantian Liu, Adam W. Bargteil, James F. O’Brien, and Ladislav Kavan. 2013. Fast Simulation of Mass-spring Systems. ACM Trans. Graph. (TOG) 32, 6 (2013), 214:1–214:7.Google ScholarDigital Library
46. 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), 1–16.Google ScholarDigital Library
47. Ran Luo, Tianjia Shao, Huamin Wang, Weiwei Xu, Xiang Chen, Kun Zhou, and Yin Yang. 2018. NNWarp: Neural network-based nonlinear deformation. IEEE transactions on visualization and computer graphics 26, 4 (2018), 1745–1759.Google Scholar
48. Miles Macklin and Matthias Muller. 2021. A Constraint-based Formulation of Stable Neo-Hookean Materials. In Motion, Interaction and Games. 1–7.Google Scholar
49. Miles Macklin, Matthias Müller, and Nuttapong Chentanez. 2016. XPBD: position-based simulation of compliant constrained dynamics. In Proceedings of the 9th International Conference on Motion in Games. 49–54.Google ScholarDigital Library
50. Miles Macklin, Kier Storey, Michelle Lu, Pierre Terdiman, Nuttapong Chentanez, Stefan Jeschke, and Matthias Müller. 2019. Small Steps in Physics Simulation. In Proceedings of the 18th Annual ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Los Angeles, California) (SCA ’19). Association for Computing Machinery, New York, NY, USA, Article 2, 7 pages. Google ScholarDigital Library
51. Sebastian Martin, Peter Kaufmann, Mario Botsch, Eitan Grinspun, and Markus Gross. 2010. Unified simulation of elastic rods, shells, and solids. In ACM Trans. Graph. (TOG), Vol. 29. ACM, 39.Google ScholarDigital Library
52. Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, and Markus Gross. 2011. Example-based elastic materials. In ACM SIGGRAPH 2011 papers. 1–8.Google ScholarDigital Library
53. Matthias Müller, Bruno Heidelberger, Marcus Hennix, and John Ratcliff. 2007. Position based dynamics. Journal of Visual Communication and Image Representation 18, 2 (2007), 109–118.Google ScholarDigital Library
54. Matthias Müller, Bruno Heidelberger, Matthias Teschner, and Markus Gross. 2005. Meshless deformations based on shape matching. In ACM Trans. Graph. (TOG), Vol. 24. ACM, 471–478.Google ScholarDigital Library
55. 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. 2016.Google Scholar
56. Jorge Nocedal and Stephen Wright. 2006. Numerical optimization. Springer Science & Business Media.Google Scholar
57. Raymond W Ogden. 1997. Non-linear elastic deformations. Courier Corporation.Google Scholar
58. Miguel A Otaduy, Rasmus Tamstorf, Denis Steinemann, and Markus Gross. 2009. Implicit contact handling for deformable objects. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 559–568.Google Scholar
59. 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.Google ScholarDigital Library
60. Albert Peiret, Sheldon Andrews, József Kövecses, Paul G Kry, and Marek Teichmann. 2019. Schur complement-based substructuring of stiff multibody systems with contact. ACM Transactions on Graphics (TOG) 38, 5 (2019), 1–17.Google ScholarDigital Library
61. Alex Pentland and John Williams. 1989. Good vibrations: Modal dynamics for graphics and animation. In SIGGRAPH Comput. Graph., Vol. 23. ACM.Google ScholarDigital Library
62. Xavier Provot. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Computer Animation and Simulation’97. Springer, 177–189.Google Scholar
63. Jason Sanders and Edward Kandrot. 2010. CUDA by example: an introduction to generalpurpose GPU programming. Addison-Wesley Professional.Google Scholar
64. Siyuan Shen, Yang Yin, Tianjia Shao, He Wang, Chenfanfu Jiang, Lei Lan, and Kun Zhou. 2021. High-order Differentiable Autoencoder for Nonlinear Model Reduction. arXiv preprint arXiv:2102.11026 (2021).Google Scholar
65. Breannan Smith, Fernando De Goes, and Theodore Kim. 2018. Stable neo-hookean flesh simulation. ACM Transactions on Graphics (TOG) 37, 2 (2018), 1–15.Google ScholarDigital Library
66. Rasmus Tamstorf, Toby Jones, and Stephen F McCormick. 2015. Smoothed aggregation multigrid for cloth simulation. ACM Trans. Graph. (TOG) 34, 6 (2015), 245.Google ScholarDigital Library
67. Min Tang, Tongtong Wang, Zhongyuan Liu, Ruofeng Tong, and Dinesh Manocha. 2018. I-Cloth: Incremental collision handling for GPU-based interactive cloth simulation. ACM Transactions on Graphics (TOG) 37, 6 (2018), 1–10.Google ScholarDigital Library
68. Yun Teng, Mark Meyer, Tony DeRose, and Theodore Kim. 2015. Subspace condensation: Full space adaptivity for subspace deformations. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–9.Google ScholarDigital Library
69. Demetri Terzopoulos and Kurt Fleischer. 1988. Deformable models. The visual computer 4, 6 (1988), 306–331.Google Scholar
70. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically deformable models, In Proceedings of the 14th annual conference on Computer graphics and interactive techniques. ACM Siggraph Computer Graphics 21, 4, 205–214.Google ScholarDigital Library
71. Demetri Terzopoulos, Andrew Witkin, and Michael Kass. 1988. Constraints on deformable models: Recovering 3D shape and nonrigid motion. Artificial intelligence 36, 1 (1988), 91–123.Google Scholar
72. Matthias Teschner, Stefan Kimmerle, Bruno Heidelberger, Gabriel Zachmann, Laks Raghupathi, Arnulph Fuhrmann, M-P Cani, François Faure, Nadia Magnenat-Thalmann, Wolfgang Strasser, et al. 2005. Collision detection for deformable objects. In Computer graphics forum, Vol. 24. Wiley Online Library, 61–81.Google Scholar
73. Endong Wang, Qing Zhang, Bo Shen, Guangyong Zhang, Xiaowei Lu, Qing Wu, and Yajuan Wang. 2014. Intel math kernel library. In High-Performance Computing on the Intel® Xeon Phi™. Springer, 167–188.Google Scholar
74. 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.Google ScholarDigital Library
75. Huamin Wang and Yin Yang. 2016. Descent methods for elastic body simulation on the GPU. ACM Trans. Graph. (TOG) 35, 6 (2016), 212.Google ScholarDigital Library
76. Qisi Wang, Yutian Tao, Eric Brandt, Court Cutting, and Eftychios Sifakis. 2021. Optimized processing of localized collisions in projective dynamics. In Computer Graphics Forum, Vol. 40. Wiley Online Library, 382–393.Google Scholar
77. Xinlei Wang, Minchen Li, Yu Fang, Xinxin Zhang, Ming Gao, Min Tang, Danny M Kaufman, and Chenfanfu Jiang. 2020. Hierarchical optimization time integration for cfl-rate mpm stepping. ACM Transactions on Graphics (TOG) 39, 3 (2020), 1–16.Google ScholarDigital Library
78. Max Wardetzky, Miklós Bergou, David Harmon, Denis Zorin, and Eitan Grinspun. 2007. Discrete quadratic curvature energies. Computer Aided Geometric Design 24, 8–9 (2007), 499–518.Google ScholarDigital Library
79. Jianhua Wu and Leif Kobbelt. 2005. Structure Recovery via Hybrid Variational Surface Approximation.. In Comput. Graph. Forum, Vol. 24. 277–284.Google ScholarCross Ref
80. Longhua Wu, Botao Wu, Yin Yang, and Huamin Wang. 2020. A Safe and Fast Repulsion Method for GPU-based Cloth Self Collisions. ACM Transactions on Graphics (TOG) 40, 1 (2020), 1–18.Google ScholarDigital Library
81. Xiaofeng Wu, Rajaditya Mukherjee, and Huamin Wang. 2015. A unified approach for subspace simulation of deformable bodies in multiple domains. ACM Transactions on Graphics (TOG) 34, 6 (2015), 1–9.Google ScholarDigital Library
82. 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), 1–13.Google ScholarDigital Library
83. Yin Yang, Dingzeyu Li, Weiwei Xu, Yuan Tian, and Changxi Zheng. 2015. Expediting precomputation for reduced deformable simulation. ACM Trans. Graph. (TOG) 34, 6 (2015).Google ScholarDigital Library
84. Yin Yang, Weiwei Xu, Xiaohu Guo, Kun Zhou, and Baining Guo. 2013. Boundary-aware multidomain subspace deformation. IEEE transactions on visualization and computer graphics 19, 10 (2013), 1633–1645.Google ScholarCross Ref
85. Juyong Zhang, Yue Peng, Wenqing Ouyang, and Bailin Deng. 2019. Accelerating ADMM for efficient simulation and optimization. ACM Transactions on Graphics (TOG) 38, 6 (2019), 1–21.Google ScholarDigital Library
86. Xinyu Zhang, Minkyoung Lee, and Young J Kim. 2006. Interactive continuous collision detection for non-convex polyhedra. The Visual Computer 22, 9 (2006), 749–760.Google ScholarDigital Library
87. Yongning Zhu, Eftychios Sifakis, Joseph Teran, and Achi Brandt. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. (TOG) 29, 2 (2010), 16.Google ScholarDigital Library
88. Olgierd Cecil Zienkiewicz, Robert Leroy Taylor, Perumal Nithiarasu, and JZ Zhu. 1977. The finite element method. Vol. 3. McGraw-hill London.Google Scholar