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

摘要

We propose a simple yet efficient multigrid scheme to simulate high-resolutiondeformable objects in their full spaces at interactive frame rates. The pointof departure of our method is the Galerkin projection which is simple toconstruct. However, a naïve Galerkin multigrid does not scale well for largeand irregular grids because it trades-off matrix sparsity for smaller sizedlinear systems which eventually stops improving the performance. Giventhat observation, we design our special projection criterion which is basedon skinning space coordinates with piecewise constant weights, to make ourGalerkin multigrid method scale for high-resolution meshes without sufferingfrom dense linear solves. The usage of skinning space coordinates enablesus to reduce the resolution of grids more aggressively, and our piecewiseconstant weights further ensure us to always deal with reasonably-sparselinear solves. Our projection matrices also help us to manage multi-levellinear systems efficiently. Therefore, our method can be applied to differentoptimization schemes such as Newton’s method and Projective Dynamics,pushing the resolution of a real-time simulation to orders of magnitudeshigher. Our final GPU implementation outperforms the other state-of-the-artGPU deformable body simulators, enabling us to simulate large deformableobjects with hundred thousands of degrees of freedom in real-time.