Position-based dynamics (PBD) is an efficient and robust method for animating soft bodies, rigid bodies and fluids. Recently, this method gained popularity in the computer animation community because it is relatively easy to implement while still being able to synthesize believable results at interactive rate. The animated bodies are modeled by using a large set of linearized geometrical constraints which are iteratively solved using a sequential Gauss-Seidel method on a single core CPU. However, when the animated scene involves a large number of objects, solving the constraints sequentially one after the other makes the computation of the motion too slow and not suitable for interactive applications. In this paper, we present a massively parallel implementation of position based dynamics which runs on the local GPU. In the initialization phase, the linearized geometrical constraints are divided in independent clusters using a fast, greedy coloring graph algorithm. Then, during the animation, the constraints belonging to each cluster are solved in parallel on the GPU. We employ an efficient simulation pipeline using a memory layout which favor both the memory access time for computation and batching for visualization. Our experiments show that the performance speed-up of our parallel implementation is several orders of magnitude faster than its serial counterpart.
[BB08] BENDER J., BAYER D.: Parallel simulation of inextensible cloth. In Virtual Reality Interactions and Physical Simulations (VRIPhys) (November 2008). 2
[BDP*02] BOISSONNAT J.-D., DEVILLERS O., PION S., TEILLAUD M., YVINEC M.: Triangulations in cgal. Comput. Geom. Theory Appl. 22, 1-3 (May 2002), 5–19. 3, 5
[BMOT13] BENDER J., MÜLLER M., OTADUY M. A., TESCHNER M.: Position-based methods for the simulation of solid objects in computer graphics. In EUROGRAPHICS 2013 State of the Art Reports (2013), Eurographics Association. 2, 3
[CA09] COURTECUISSE H., ALLARD J.: Parallel dense gaussseidel algorithm on many-core processors. In High Performance Computing and Communications, 2009. HPCC ’09. 11th IEEE International Conference on (June 2009), pp. 139–147. 2
[CM83] COLEMAN T. F., MORE J. J.: Estimation of sparse jacobian matrices and graph coloring problems. Journal of Numerical Analasis 20 (1983), 187–209. 4
[Cou10] COUMANS E.: Bullet 2.76 physics sdk manual, 2010. 2
[DB13] DEUL C., BENDER J.: Physically-based character skinning. In Virtual Reality Interactions and Physical Simulations (VRIPhys) (2013). 2
[DCB14] DEUL C., CHARRIER P., BENDER J.: Position-based rigid body dynamics. In Computer Animation & Social Agents (CASA) (2014). accepted. 2
[Dro07] DRONE S.: Real-time particle systems on the gpu in dynamic environments. In ACM SIGGRAPH 2007 Courses (New York, NY, USA, 2007), SIGGRAPH ’07, ACM, pp. 80–96. 4
[Fra12] FRATARCANGELI M.: Position-based facial animation synthesis. Computer Animation and Virtual Worlds 23, 3-4 (2012), 457–466. 2
[GJ79] GAREY M. R., JOHNSON D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979. 4, 6
[KH13] KIRK D. B., HWU W.-M. W.: Programming MassivelyParallel Processors: A Hands-on Approach, 2 ed. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2013. 2
[KPFG07] KUBIAK B., PIETRONI N., FRATARCANGELI M., GANOVELLI F.: "A Robust Method for Real-Time Thread Simulation". In ACM Symposium on Virtual Reality Software and Technology (VRST) (New Port Beach, CA, USA, November 2007), ACM, (Ed.). 2
[KW03] KRÜGER J., WESTERMANN R.: Linear algebra operators for gpu implementation of numerical algorithms. ACM Trans. Graph. 22, 3 (July 2003), 908–916. 2
[M¨08] MÜLLER M.: Hierarchical position based dynamics. In Virtual Reality Interactions and Physical Simulations (VRIPhys2008) (Grenoble, November 2008). 2
[MB83] MATULA D. W., BECK L. L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30, 3 (July 1983), 417–427. 4
[MHHR06] MÜLLER M., HEIDELBERGER B., HENNIX M., RATCLIFF J.: Position based dynamics. In Virtual Reality Interactions and Physical Simulations (VRIPhys) (Madrid, November 6-7 2006). 1, 3, 4
[MM13] MACKLIN M., MÜLLER M.: Position based fluids. ACM Trans. Graph. 32, 4 (July 2013), 104:1–104:12. 2
[nvB13] : NVIDIA CUDA Compute Unified Device Architecture - Best Practices Guide, version 5.5 ed., 2013. 4
[NVI13] NVIDIA: Physx sdk 9.13 documentation, 2013. 2
[RF14] RUMMAN N. A., FRATARCANGELI M.: Position-based skinning. In Eurographics/ACM Spring conference on Computer Graphics (SCCG) (2014). accepted. 2
[WBS13] WEBER D., BENDER J., SCHNOES M., STORK A., FELLNER D.: Efficient gpu data structures and methods to solve sparse linear systems in dynamics applications. Computer Graphics Forum 32, 1 (2013), 16–26. 2
