A Scalable Galerkin Multigrid Method for Real-time Simulation of Deformable Objects

We propose a simple yet efficient multigrid scheme to simulate high-resolution deformable objects in their full spaces at interactive frame rates. The point of departure of our method is the Galerkin projection which is simple to construct. However, a naive Galerkin multigrid does not scale well for large and irregular grids because it trades-off matrix sparsity for smaller sized linear systems which eventually stops improving the performance. Given that observation, we design our special projection criterion which is based on skinning space coordinates with piecewise constant weights, to make our Galerkin multigrid method scale for high-resolution meshes without suffering from dense linear solves. The usage of skinning space coordinates enables us to reduce the resolution of grids more aggressively, and our piecewise constant weights further ensure us to always deal with reasonably-sparse linear solves. Our projection matrices also help us to manage multi-level linear systems efficiently. Therefore, our method can be applied to different optimization schemes such as Newton's method and Projective Dynamics, pushing the resolution of a real-time simulation to orders of magnitudes higher. Our final GPU implementation outperforms the other state-of-the-art GPU deformable body simulators, enabling us to simulate large deformable objects with hundred thousands of degrees of freedom in real-time.

Zangyueyang Xian, Xin Tong, Tiantian Liu. A Scalable Galerkin Multigrid Method for Real-time Simulation of Deformable Objects. ACM Transactions on Graphics 38(6) [Proceedings of SIGGRAPH Asia],2019.    

We thank Alec Jacobson, Yang Liu and Eftychios Sifakis for many insightful discussions, Yuxiao Guo for helping with CUDA programming, Huamin Wang for providing his GPU simulation framework, and the anonymous reviewers for their valuable feedbacks.