“Mass splitting for jitter-free parallel rigid body simulation” by Tonge, Benevolenski and Voroshilov

We present a parallel iterative rigid body solver that avoids common artifacts at low iteration counts. In large or real-time simulations, iteration is often terminated before convergence to maximize scene size. If the distribution of the resulting residual energy varies too much from frame to frame, then bodies close to rest can visibly jitter. Projected Gauss-Seidel (PGS) distributes the residual according to the order in which contacts are processed, and preserving the order in parallel implementations is very challenging. In contrast, Jacobi-based methods provide order independence, but have slower convergence. We accelerate projected Jacobi by dividing each body mass term in the effective mass by the number of contacts acting on the body, but use the full mass to apply impulses. We further accelerate the method by solving contacts in blocks, providing wallclock performance competitive with PGS while avoiding visible artifacts. We prove convergence to the solution of the underlying linear complementarity problem and present results for our GPU implementation, which can simulate a pile of 5000 objects with no visible jittering at over 60 FPS.

1. Anitescu, M., and Potra, F. A. 1997. Formulating dynamic multi-rigid-body contact problems with friction as solvable linear complementarity problems. Nonlinear Dynamics 14, 231–247.Google ScholarCross Ref
2. Baraff, D. 1991. Coping with friction for non-penetrating rigid body simulation. In Proceedings of the 18th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, SIGGRAPH ’91, 31–41. Google ScholarDigital Library
3. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. Proceedings of ACM Siggraph, 594–603. Google ScholarDigital Library
4. Catto, E. 2005. Iterative dynamics with temporal coherence. Presented at the Game Developers Conference.Google Scholar
5. Cline, M. B., and Pai, D. K. 2003. Post-stabilization for rigid body simulation with contact and constraints. In ICRA, IEEE, 3744–3751.Google Scholar
6. Cottle, R., Pang, J.-S., and Stone, R. 1992. The Linear Complementarity Problem. Academic Press.Google Scholar
7. Coumans, E. 2011. Game physics artefacts. Presented at the Game Developers Conference.Google Scholar
8. Daviet, G., Bertails-Descoubes, F., and Boissieux, L. 2011. A hybrid iterative solver for robustly capturing coulomb friction in hair dynamics. In Proceedings of the 2011 SIGGRAPH Asia Conference, ACM, New York, NY, USA, SA ’11, 139:1–139:12. Google Scholar
9. Dostal, Z., and Schoberl, J. 2005. Minimizing quadratic functions subject to bound constraints with the rate of convergence and finite termination. Computational Optimization and Applications 30, 23–43. Google ScholarDigital Library
10. Erleben, K. 2004. Stable, Robust, and Versatile Multibody Dynamics Animation. PhD thesis, University of Copenhagen Copenhagen.Google Scholar
11. Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Non-convex rigid bodies with stacking. In ACM SIGGRAPH 2003 Papers, ACM, New York, NY, USA, SIGGRAPH ’03, 871–878. Google ScholarDigital Library
12. Gustafsson, D. 2010. Understanding game physics artefacts. In Game Physics Pearls. A K Peters, ch. 2.Google Scholar
13. Harada, T. 2007. Real-time rigid body simulation on GPUs. In GPU gems 3. Addison-Wesley Professional, ch. 29.Google Scholar
14. Harada, T. 2009. Parallelizing the physics pipeline: Physics simulations on the GPU. Presented at the Game Developers Conference.Google Scholar
15. Harada, T. 2011. A parallel constraint solver for a rigid body simulation. Presented at SIGGRAPH Asia. Google ScholarDigital Library
16. Hege, H.-C., and Stüben, H. 1991. Vectorization and parallelization of irregular problems via graph coloring. In ICS, 47–56. Google ScholarDigital Library
17. Hsu, S.-W., and Keyser, J. 2010. Piles of objects. In ACM SIGGRAPH Asia 2010 papers, ACM, New York, NY, USA, SIGGRAPH ASIA ’10, 155:1–155:6. Google ScholarDigital Library
18. Kaufman, D. M., Edmunds, T., and Pai, D. K. 2005. Fast frictional dynamics for rigid bodies. In ACM SIGGRAPH 2005 Papers, ACM, New York, NY, USA, SIGGRAPH ’05, 946–956. Google ScholarDigital Library
19. Kaufman, D. M., Sueda, S., James, D. L., and Pai, D. K. 2008. Staggered projections for frictional contact in multibody systems. In ACM SIGGRAPH Asia 2008 papers, ACM, New York, NY, USA, SIGGRAPH Asia ’08, 164:1–164:11. Google ScholarDigital Library
20. Lacoursière, C. 2007. A parallel block iterative method for interactive contacting rigid multibody simulations on multicore pcs. In Proceedings of the 8th international conference on Applied parallel computing: state of the art in scientific computing, Springer-Verlag, Berlin, Heidelberg, PARA’06, 956–965. Google ScholarDigital Library
21. Lengyel, E. 2011. A jitter-tolerant rigid body sleep condition. In Game Engine Gems 2. A K Peters, ch. 23.Google Scholar
22. Morales, J., Nocedal, J., and Smelyanskiy, M. 2008. An algorithm for the fast solution of symmetric linear complementarity problems. Numerische Mathematik 111, 251–266. Google ScholarDigital Library
23. Müller, M., and Chentanez, N. 2011. Solid simulation with oriented particles. In ACM SIGGRAPH 2011 papers, ACM, New York, NY, USA, SIGGRAPH ’11, 92:1–92:10. Google ScholarDigital Library
24. Murty, K. G. 1988. Iterative methods for LCPs. In Linear Complementarity, Linear and Non-linear Programming. Helderman Verlag, ch. 9.Google Scholar
25. NVIDIA. 2011. NVIDIA PhysX 3.2 user guide.Google Scholar
26. Parker, E. G., and O’Brien, J. F. 2009. Real-time deformation and fracture in a game environment. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, ACM, New York, NY, USA, SCA ’09, 165–175. Google ScholarDigital Library
27. Renouf, M., and Alart, P. 2005. Conjugate gradient type algorithms for frictional multi-contact problems: applications to granular materials. Computer Methods in Applied Mechanics and Engineering 194, 18–20, 2019–2041.Google ScholarCross Ref
28. Silcowitz, M., Niebe, S., and Erleben, K. 2010. A nonsmooth nonlinear conjugate gradient method for interactive contact force problems. The Visual Computer 26, 893–901. Google ScholarDigital Library
29. Stewart, D. E., and Trinkle, J. C. 1996. An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and coulomb friction. International Journal for Numerical Methods in Engineering 39, 15, 2673–2691.Google ScholarCross Ref
30. Tasora, A., Negrut, D., and Anitescu, M. 2008. A GPU-based implementation of a cone convex complementarity approach for simulating rigid body dynamics with frictional contact. ASME Conference Proceedings 2008, 48722, 107–118.Google Scholar
31. Tonge, R., Zhang, L., and Sequeira, D. 2004. Method and program solving LCPs for rigid body dynamics. United States Patent 7079145.Google Scholar
32. Tonge, R., Wyatt, B., and Nicholson, B. 2010. PhysX GPU rigid bodies in Batman: Arkham Asylum. In Game Programming Gems 8, A. Lake, Ed. Cengage Learning, ch. 7.2, 590–601.Google Scholar
33. Vizing, V. G. 1964. On an estimate of the chromatic class of a p-graph. Diskret. Analiz. 3, 25–30.Google Scholar