Deformable Objects Collision Handling with Fast Convergence


Computer Graphics Forum (Special Issue of Pacific Graphics'2015), Wiley, 2015, 34(7): 269-278.

Siwang Li, Zherong Pan, Jin HuangHujun Bao, Xiaogang Jin


 Eight dinosaurs fall together. Collision decoupling scheme is adopted to handle the complex constraints efficiently,while stability and robustness are still preserved.


We present a stable and efficient simulator for deformable objects with collisions and contacts. For stability, an optimization derived from the implicit time integrator is solved in each timestep under the inequality constraints coming from collisions. To achieve fast convergence, we extend the MPRGP based solver from handling boxconstraints only to handling general linear constraints and prove its convergence. This generalization introduces a cost of solving dense linear systems in each step, but these systems can be reduced into diagonal ones for efficiency without affecting the general stability via pruning redundant collisions. Our solver is an order of magnitude faster, especially for elastic objects under large deformation compared with iterative constraint anticipation method (ICA), a typical method for stability. The efficiency, robustness and stability are further verified by our results.