“A chebyshev semi-iterative approach for accelerating projective and position-based dynamics” by Wang
Conference:
Type(s):
Title:
- A chebyshev semi-iterative approach for accelerating projective and position-based dynamics
Session/Category Title: Deformable Models
Presenter(s)/Author(s):
Abstract:
In this paper, we study the use of the Chebyshev semi-iterative approach in projective and position-based dynamics. Although projective dynamics is fundamentally nonlinear, its convergence behavior is similar to that of an iterative method solving a linear system. Because of that, we can estimate the “spectral radius” and use it in the Chebyshev approach to accelerate the convergence by at least one order of magnitude, when the global step is handled by the direct solver, the Jacobi solver, or even the Gauss-Seidel solver. Our experiment shows that the combination of the Chebyshev approach and the direct solver runs fastest on CPU, while the combination of the Chebyshev approach and the Jacobi solver outperforms any other combination on GPU, as it is highly compatible with parallel computing. Our experiment further shows position-based dynamics can be accelerated by the Chebyshev approach as well, although the effect is less obvious for tetrahedral meshes. The whole approach is simple, fast, effective, GPU-friendly, and has a small memory cost.
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 Proc. 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. Bouby, C., Fortuné, D., Pietraszkiewicz, W., and Vallée, C. 2005. Direct determination of the rotation in the polar decomposition of the deformation gradient by maximizing a Rayleigh quotient. Journal of Applied Mathematics and Mechanics 85, 3 (Mar.), 155–162.
5. Bridson, R., Marino, S., and Fedkiw, R. 2003. Simulation of clothing with folds and wrinkles. In Proceedings of SCA, 28–36.
6. Franca, L. 1989. An algorithm to compute the square root of 3×3 positive definite matrix. Computers. Math. Applic. 18, 5, 459–466.
7. Goldenthal, R., Harmon, D., Fattal, R., Bercovier, M., and Grinspun, E. 2007. Efficient simulation of inextensible cloth. ACM Trans. Graph. (SIGGRAPH) 26, 3 (July).
8. Golub, G. H., and Van Loan, C. F. 1996. Matrix Computations (3rd Ed.). Johns Hopkins University Press, Baltimore, MD, USA.
9. Golub, G. H., and Varga, R. S. 1961. Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods. Numerische Mathematik 3, 1, 157–168.
10. Gutknecht, M. H., and Röllin, S. 2002. The Chebyshev iteration revisited. Parallel Comput. 28, 2 (Feb.), 263–283.
11. 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.
12. 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.
13. 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.
14. Macklin, M., and Müller, M. 2013. Position based fluids. ACM Trans. Graph. (SIGGRAPH) 32, 4 (July), 104:1–104:12.
15. 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.
16. Martin, S., Thomaszewski, B., Grinspun, E., and Gross, M. 2011. Example-based elastic materials. ACM Trans. Graph. (SIGGRAPH) 30, 4 (July), 72:1–72:8.
17. 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.
18. Müller, M., Heidelberger, B., Hennix, M., and Ratcliff, J. 2007. Position based dynamics. J. Vis. Comun. Image Represent. 18, 2 (Apr.), 109–118.
19. Müller, M., Chentanez, N., Kim, T., and Macklin, M. 2014. Strain based dynamics. In Proceedings of SCA, 21–23.
20. Müller, M. 2008. Hierarchical position based dynamics. In Proceedings of VRIPHYS, 1–10.
21. Provot, X. 1996. Deformation constraints in a mass-spring model to describe rigid cloth behavior. In Proceedings of Graphics Interface, 147–154.
22. 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).
23. Stern, A., and Grinspun, E. 2009. Implicit-explicit variational integration of highly oscillatory problems. Multiscale Model. Simul. 7, 4, 1779–1794.
24. 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.
25. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. SIGGRAPH Comput. Graph. 21, 4 (Aug.), 205–214.
26. Thomaszewski, B., Pabst, S., and Strasser, W. 2009. Continuum-based strain limiting. Computer Graphics Forum (Eurographics) 28, 2, 569–576.
27. Wang, H., O’Brien, J., and Ramamoorthi, R. 2010. Multi-resolution isotropic strain limiting. ACM Trans. Graph. (SIGGRAPH Asia) 29, 6 (Dec.), 156:1–156:10.
