“Descent methods for elastic body simulation on the GPU” by Wang and Yang
Conference:
Type(s):
Title:
- Descent methods for elastic body simulation on the GPU
Session/Category Title: Fantastic Elastics
Presenter(s)/Author(s):
Abstract:
We show that many existing elastic body simulation approaches can be interpreted as descent methods, under a nonlinear optimization framework derived from implicit time integration. The key question is how to find an effective descent direction with a low computational cost. Based on this concept, we propose a new gradient descent method using Jacobi preconditioning and Chebyshev acceleration. The convergence rate of this method is comparable to that of L-BFGS or nonlinear conjugate gradient. But unlike other methods, it requires no dot product operation, making it suitable for GPU implementation. To further improve its convergence and performance, we develop a series of step length adjustment, initialization, and invertible model conversion techniques, all of which are compatible with GPU acceleration. Our experiment shows that the resulting simulator is simple, fast, scalable, memory-efficient, and robust against very large time steps and deformations. It can correctly simulate the deformation behaviors of many elastic materials, as long as their energy functions are second-order differentiable and their Hessian matrices can be quickly evaluated. For additional speedups, the method can also serve as a complement to other techniques, such as multi-grid.
References:
1. Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. In Proceedings of the 25th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, SIGGRAPH ’98, 43–54.
2. Bergou, M., Wardetzky, M., Harmon, D., Zorin, D., and Grinspun, E. 2006. A quadratic bending model for inextensible surfaces. In Proceedings of SGP, 227–230.
3. Bouaziz, S., Martin, S., Liu, T., Kavan, L., and Pauly, M. 2014. Projective dynamics: Fusing constraint projections for fast simulation. ACM Trans. Graph. (SIGGRAPH) 33, 4 (July), 154:1–154:11.
4. Bridson, R., Marino, S., and Fedkiw, R. 2003. Simulation of clothing with folds and wrinkles. In Proceedings of SCA, 28–36.
5. Cordero, A., Hueso, J. L., Martínez, E., and Torregrosa, J. R. 2010. New modifications of Potra-Pták’s method with optimal fourth and eighth orders of convergence. J. Comput. Appl. Math. 234, 10 (Sept.), 2969–2976.
6. Daviet, G., Bertails-Descoubes, F., and Boissieux, L. 2011. A hybrid iterative solver for robustly capturing Coulomb friction in hair dynamics. ACM Trans. Graph. (SIGGRAPH Asia) 30, 6 (Dec.), 139:1–139:12.
7. Dick, C., Georgii, J., and Westermann, R. 2011. A real-time multigrid finite hexahedra method for elasticity simulation using CUDA. Simulation Modelling Practice and Theory 19, 2, 801–816. Cross Ref
8. Fei, Y., Rong, G., Wang, B., and Wang, W. 2014. Parallel L-BFGS-B algorithm on GPU. Comput. Graph. 40 (May), 1–9.
9. Fung, Y.-C. 1993. Biomechanics: Mechanical properties of living tissues. Springer-Verlag. Cross Ref
10. Garg, A., Grinspun, E., Wardetzky, M., and Zorin, D. 2007. Cubic shells. In Proceedings of SCA, 91–98.
11. Golub, G. H., and Van Loan, C. F. 1996. Matrix computations (3rd Ed.). Johns Hopkins University Press, Baltimore, MD, USA.
12. Gutknecht, M. H., and Röllin, S. 2002. The Chebyshev iteration revisited. Parallel Computing, 28, 263–283.
13. Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of SCA, 131–140.
14. Kharevych, L., Yang, W., Tong, Y., Kanso, E., Marsden, J. E., Schröder, P., and Desbrun, M. 2006. Geometric, variational integrators for computer animation. In Proceedings of SCA, 43–51.
15. Kim, T.-Y., Chentanez, N., and Müller-Fischer, M. 2012. Long range attachments – A method to simulate inextensible clothing in computer games. In Proceedings of SCA, 305–310.
16. Liu, T., Bargteil, A. W., O’Brien, J. F., and Kavan, L. 2013. Fast simulation of mass-spring systems. ACM Trans. Graph. (SIGGRAPH Asia) 32, 6 (Nov.), 214:1–214:7.
17. Macklin, M., and Müller, M. 2013. Position based fluids. ACM Trans. Graph. (SIGGRAPH) 32, 4 (July), 104:1–104:12.
18. Macklin, M., Müller, M., Chentanez, N., and Kim, T.-Y. 2014. Unified particle physics for real-time applications. ACM Trans. Graph. (SIGGRAPH) 33, 4 (July), 153:1–153:12.
19. Macosko, C. W. 1994. Rheology: Principles, measurement and applications. VCH Publishers.
20. McAdams, A., Selle, A., Tamstorf, R., Teran, J., and Sifakis, E. 2011. Computing the singular value decomposition of 3×3 matrices with minimal branching and elementary floating point operations. Technical report, University of Wisconsin – Madison.
21. McAdams, A., Zhu, Y., Selle, A., Empey, M., Tamstorf, R., Teran, J., and Sifakis, E. 2011. Efficient elasticity for character skinning with contact and collisions. ACM Trans. Graph. (SIGGRAPH) 30, 4 (July), 37:1–37:12.
22. Müller, M., and Gross, M. 2004. Interactive virtual materials. In Proceedings of Graphics Interface, 239–246.
23. Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. (SIGGRAPH) 24, 3 (July), 471–478.
24. Müller, M., Heidelberger, B., Hennix, M., and Ratcliff, J. 2007. Position based dynamics. J. Vis. Comun. Image Represent. 18, 2 (Apr.), 109–118.
25. Müller, M., Chentanez, N., Kim, T., and Macklin, M. 2014. Strain based dynamics. In Proceedings of SCA, 21–23.
26. Müller, M. 2008. Hierarchical position based dynamics. In Proceedings of VRIPHYS, 1–10.
27. Nesterov, Y. 2004. Introductory lectures on convex optimization: A basic course. Applied optimization. Kluwer Academic Publ., Boston, Dordrecht, London.
28. O’donoghue, B., and Candès, E. 2015. Adaptive restart for accelerated gradient schemes. Found. Comput. Math. 15, 3 (June), 715–732.
29. Ogden, R. W. 1997. Non-linear elastic deformations. Dover Civil and Mechanical Engineering. Dover Publications, Inc.
30. Patterson, T., Mitchell, N., and Sifakis, E. 2012. Simulation of complex nonlinear elastic bodies using lattice deformers. ACM Trans. Graph. (SIGGRAPH Asia) 31, 6 (Nov.), 197:1–197:10.
31. Perez, J., Perez, A. G., and Otaduy, M. A. 2013. Simulation of hyperelastic materials using energy constraints. In Proceedings of the XXIII CEIG (Spanish Conference on Computer Graphics).
32. Provot, X. 1996. Deformation constraints in a mass-spring model to describe rigid cloth behavior. In Proceedings of Graphics Interface, 147–154.
33. Rivers, A. R., and James, D. L. 2007. FastLSM: Fast lattice shape matching for robust real-time deformation. ACM Trans. Graph. (SIGGRAPH) 26, 3 (July).
34. Stern, A., and Grinspun, E. 2009. Implicit-explicit variational integration of highly oscillatory problems. Multiscale Model. Simul. 7, 4, 1779–1794. Cross Ref
35. Su, J., Sheth, R., and Fedkiw, R. 2013. Energy conservation for the simulation of deformable bodies. IEEE Transactions on Visualization and Computer Graphics 19, 2 (Feb.), 189–200.
36. Teran, J., Sifakis, E., Irving, G., and Fedkiw, R. 2005. Robust quasistatic finite elements and flesh simulation. In Proceedings of SCA, 181–190.
37. Thomaszewski, B., Pabst, S., and Strasser, W. 2009. Continuum-based strain limiting. Computer Graphics Forum (Eurographics) 28, 2, 569–576. Cross Ref
38. Tournier, M., Nesme, M., Gilles, B., and Faure, F. 2015. Stable constrained dynamics. ACM Trans. Graph. (SIGGRAPH) 34, 4 (July), 132:1–132:10.
39. Wang, H., O’Brien, J., and Ramamoorthi, R. 2010. Multiresolution isotropic strain limiting. ACM Trans. Graph. (SIGGRAPH Asia) 29, 6 (Dec.), 156:1–156:10.
40. Wang, H. 2015. A Chebyshev semi-iterative approach for accelerating projective and position-based dynamics. ACM Trans. Graph. (SIGGRAPH Asia) 34, 6 (Oct.), 246:1–246:9.
41. Xu, H., Sin, F., Zhu, Y., and Barbič, J. 2015. Nonlinear material design using principal stretches. ACM Trans. Graph. (SIGGRAPH) 34, 4 (July), 75:1–75:11.
42. Zhu, Y., Sifakis, E., Teran, J., and Brandt, A. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. 29, 2 (Apr.), 16:1–16:18.
