“Vivace: a practical gauss-seidel method for stable soft body dynamics”
Conference:
Type(s):
Title:
- Vivace: a practical gauss-seidel method for stable soft body dynamics
Session/Category Title: Fantastic Elastics
Presenter(s)/Author(s):
Abstract:
The solution of large sparse systems of linear constraints is at the base of most interactive solvers for physically-based animation of soft body dynamics. We focus on applications with hard and tight per-frame resource budgets, such as video games, where the solution of soft body dynamics needs to be computed in a few milliseconds. Linear iterative methods are preferred in these cases since they provide approximate solutions within a given error tolerance and in a short amount of time. We present a parallel randomized Gauss-Seidel method which can be effectively employed to enable the animation of 3D soft objects discretized as large and irregular triangular or tetrahedral meshes. At the beginning of each frame, we partition the set of equations governing the system using a randomized graph coloring algorithm. The unknowns in the equations belonging to the same partition are independent of each other. Then, all the equations belonging to the same partition are solved at the same time in parallel. Our algorithm runs completely on the GPU and can support changes in the constraints topology. We tested our method as a solver for soft body dynamics within the Projective Dynamics and Position Based Dynamics frameworks. We show how the algorithmic simplicity of this iterative strategy enables great numerical stability and fast convergence speed, which are essential features for physically based animations with fixed and small hard time budgets. Compared to the state of the art, we found our method to be faster and scale better while providing stabler solutions for very small time budgets.
References:
1. Abel, S., and Erleben, K. 2015. Numerical methods for linear complementarity problems in physics-based animation: synthesis lectures on computer graphics and animation. Morgan & Claypool Publishers, United States.
2. Allard, J., Faure, F., Courtecuisse, H., Falipou, F., Duriez, C., and Kry, P. G. 2010. Volume contact constraints at arbitrary resolution. ACM Trans. Graph. 29, 4 (July), 82:1–82:10.
3. Bahi, J. M., Couturier, R., and Khodja, L. Z. 2011. Parallel gmres implementation for solving sparse linear systems on gpu clusters. In Proceedings of the 19th High Performance Computing Symposia, Society for Computer Simulation International, San Diego, CA, USA, HPC ’11, 12–19.
4. Bender, J., Müller, M., Otaduy, M. A., Teschner, M., and Macklin, M. 2014. A survey on position-based simulation methods in computer graphics. Computer Graphics Forum 33, 6, 228–251.
5. Bergou, M., Wardetzky, M., Harmon, D., Zorin, D., and Grinspun, E. 2006. A quadratic bending model for inextensible surfaces. In Proceedings of the Fourth Eurographics Symposium on Geometry Processing, Eurographics Association, Airela-Ville, Switzerland, Switzerland, SGP ’06, 227–230.
6. Bouaziz, S., Deuss, M., Schwartzburg, Y., Weise, T., and Pauly, M. 2012. Shape-up: Shaping discrete geometry with projections. Comput. Graph. Forum 31, 5 (Aug.), 1657–1667.
7. Bouaziz, S., Martin, S., Liu, T., Kavan, L., and Pauly, M. 2014. Projective dynamics: Fusing constraint projections for fast simulation. ACM Trans. Graph. 33, 4 (July), 154:1–154:11.
8. Brélaz, D. 1979. New methods to color the vertices of a graph. Commun. ACM 22, 4 (Apr.), 251–256.
9. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. 21, 3 (July), 594–603.
10. Coleman, T. F., and Moré, J. J. 1983. Estimation of sparse jacobian matrices and graph coloring problems. SIAM Journal on Numerical Analysis 20, 1, 187–209. Cross Ref
11. Fratarcangeli, M., and Pellacini, F. 2015. Scalable Partitioning for Parallel Position Based Dynamics. Computer Graphics Forum (Eurographics) 34, 2 (May), 405–413.
12. Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.
13. Golub, G. H., and Van Loan, C. F. 1996. Matrix Computations (3rd Ed.). Johns Hopkins University Press, Baltimore, MD, USA.
14. Govindaraju, N. K., Knott, D., Jain, N., Kabul, I., Tamstorf, R., Gayle, R., Lin, M. C., and Manocha, D. 2005. Interactive collision detection between deformable models using chromatic decomposition. ACM Trans. Graph. 24, 3 (July), 991–999.
15. Grable, D. A., and Panconesi, A. 2000. Fast distributed algorithms for brooksvizing colorings. Journal of Algorithms 37, 1, 85 — 120.
16. Jones, M. T., and Plassmann, P. E. 1993. A parallel graph coloring heuristic. SIAM J. Sci. Comput. 14, 3 (May), 654–669.
17. Liu, T., Bargteil, A. W., O’Brien, J. F., and Kavan, L. 2013. Fast simulation of mass-spring systems. ACM Trans. Graph. 32, 6 (Nov.), 214:1–214:7.
18. Luby, M. 1985. A simple parallel algorithm for the maximal independent set problem. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, ACM, New York, NY, USA, STOC ’85, 1–10.
19. Macklin, M., and Müller, M. 2013. Position based fluids. ACM Trans. Graph. 32, 4 (July), 104:1–104:12.
20. Macklin, M., Müller, M., Chentanez, N., and Kim, T.-Y. 2014. Unified particle physics for real-time applications. ACM Trans. Graph. 33, 4 (July), 153:1–153:12.
21. Matula, D. W., and Beck, L. L. 1983. Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30, 3 (July), 417–427.
22. Müller, M., Heidelberger, B., Hennix, M., and Ratcliff, J. 2007. Position based dynamics. J. Vis. Comun. Image Represent. 18, 2 (Apr.), 109–118.
23. Naumov, M., Castonguay, P., and Cohen, J. 2015. Parallel Graph Coloring with Applications to the Incomplete-LU Factorization on the GPU. Tech report, NVIDIA.
24. Saad, Y. 2003. Iterative Methods for Sparse Linear Systems, 2nd ed. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA.
25. Stam, J. 2009. Nucleus: Towards a unified dynamics solver for computer graphics. In Computer-Aided Design and Computer Graphics, 2009. CAD/Graphics ’09. 11th IEEE International Conference on, 1–11. Cross Ref
26. Tamstorf, R., Jones, T., and McCormick, S. F. 2015. Smoothed aggregation multigrid for cloth simulation. ACM Trans. Graph. 34, 6 (Oct.), 245:1–245:13.
27. Thomaszewski, B., Pabst, S., and Straer, W. 2009. Continuum-based strain limiting. Computer Graphics Forum 28, 2, 569–576. Cross Ref
28. Tonge, R., Benevolenski, F., and Voroshilov, A. 2012. Mass splitting for jitter-free parallel rigid body simulation. ACM Trans. Graph. 31, 4 (July), 105:1–105:8.
29. Vizing, V. G. 1964. On an estimate of the chromatic class of a p-graph. (russian). Diskret. Analiz. 3, 25–30.
30. Wang, H. 2015. A Chebyshev semi-iterative approach for accelerating projective and position-based dynamics. ACM Trans. Graph. 34, 6 (Oct.), 246:1–246:9.
31. Weber, D., Bender, J., Schnoes, M., Stork, A., and Fellner, D. 2013. Efficient gpu data structures and methods to solve sparse linear systems in dynamics applications. Computer Graphics Forum 32, 1, 16–26. Cross Ref
32. Welsh, D. J. A., and Powell, M. B. 1967. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal 10, 1, 85–86. Cross Ref
