“Smoothed aggregation multigrid for cloth simulation”
Conference:
Type(s):
Title:
- Smoothed aggregation multigrid for cloth simulation
Session/Category Title: Deformable Models
Presenter(s)/Author(s):
Abstract:
Existing multigrid methods for cloth simulation are based on geometric multigrid. While good results have been reported, geometric methods are problematic for unstructured grids, widely varying material properties, and varying anisotropies, and they often have difficulty handling constraints arising from collisions. This paper applies the algebraic multigrid method known as smoothed aggregation to cloth simulation. This method is agnostic to the underlying tessellation, which can even vary over time, and it only requires the user to provide a fine-level mesh. To handle contact constraints efficiently, a prefiltered preconditioned conjugate gradient method is introduced. For highly efficient preconditioners, like the ones proposed here, prefiltering is essential, but, even for simple preconditioners, prefiltering provides significant benefits in the presence of many constraints. Numerical tests of the new approach on a range of examples confirm 6–8x speedups on a fully dressed character with 371k vertices, and even larger speedups on synthetic examples.
References:
1. Adams, M., Brezina, M., Hu, J., and Tuminaro, R. 2003. Parallel Multigrid Smoothing: Polynomial Versus Gauss–Seidel. J. Comput. Phys. 188, 2 (July), 593–610.
2. Ascher, U. M., and Boxerman, E. 2003. On the modified conjugate gradient method in cloth simulation. The Visual Computer 19, 7–8, 526–531.
3. Baker, A. H., Falgout, R. D., Kolev, T. V., and Yang, U. M. 2011. Multigrid Smoothers for Ultraparallel Computing. SIAM Journal on Scientific Computing 33, 5, 2864–2887.
4. 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.
5. Bell, N., Dalton, S., and Olson, L. 2012. Exposing Fine-Grained Parallelism in Algebraic Multigrid Methods. SIAM Journal on Scientific Computing 34, 4, C123–C152.
6. Boxerman, E., and Ascher, U. 2004. Decomposing Cloth. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Eurographics Association, Aire-la-Ville, Switzerland, SCA ’04, 153–161.
7. Brandt, A., McCormick, S. F., and Ruge, J. W. 1985. Algebraic multigrid (AMG) for sparse matrix equations. In Sparsity and its Applications, D. J. Evans, Ed. Cambridge University Press, 257–284.
8. Brandt, A., Brannick, J., Kahl, K., and Livshits, I. 2011. Boot-strap AMG. SIAM J. Sci. Comput. 33, 2 (Mar.), 612–632.
9. Brandt, A. 1977. Multi-level adaptive solutions to boundary-value problems. Mathematics of Computation 31, 138, 333–390.
10. Brezina, M., Falgout, R., MacLachlan, S., Manteuffel, T., McCormick, S., and Ruge, J. 2004. Adaptive Smoothed Aggregation (αSA). SIAM Journal on Scientific Computing 25, 6, 1896–1920.
11. 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.
12. Briggs, W., Henson, V., and McCormick, S. 2000. A Multigrid Tutorial, Second Edition. Society for Industrial and Applied Mathematics.
13. Dalton, S., Olsen, L., and Bell, N. 2015. Optimizing Sparse Matrix-Matrix Multiplication for the GPU. ACM Transactions onMathematical Software 41, 4.
14. Fish, J., Pan, L., Belsky, V., and Gomaa, S. 1996. Unstructured multigrid methods for shells. International Journal for NumericalMethods in Engineering 39, 7, 1181–1197.
15. Gee, M. W., and Tuminaro, R. S. 2006. Nonlinear AlgebraicMultigrid for Constrained Solid Mechanics Problems Using Trilinos. Tech. Rep. SAND2006-2256, Sandia National Laboratories, April.
16. Gee, M., Ramm, E., and Wall, W. A. 2005. Parallel multilevel solution of nonlinear shell structures. Computer Methods in Applied Mechanics and Engineering 194, 21–24, 2513–2533. Computational Methods for Shells.
17. Golub, G. H., and Loan, C. F. V. 1983. Matrix Computations, 3rd ed. The Johns Hopkins University Press.
18. Golub, G. H., and Varga, R. S. 1961. Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order richardson iterative methods. NumerischeMathematik 3, 1, 157–168.
19. Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust Treatment of Simultaneous Collisions. ACM Trans. Graph. 27, 3 (Aug.), 23:1–23:4.
20. Hecht, F., Lee, Y. J., Shewchuk, J. R., and O’Brien, J. F. 2012. Updated Sparse Cholesky Factors for Corotational Elastodynamics. ACM Transactions on Graphics 31, 5 (Oct.), 123:1–13. Presented at SIGGRAPH 2012.
21. Horn, R. A., and Johnson, C. R. 1985. Matrix Analysis. Cambridge University Press. Cambridge Books Online.
22. Jeon, I., Choi, K.-J., Kim, T.-Y., Choi, B.-O., and Ko, H.-S. 2013. Constrainable Multigrid for Cloth. Computer Graphics Forum 32, 7, 31–39.
23. Krishnan, D., Fattal, R., and Szeliski, R. 2013. Efficient Preconditioning of Laplacian Matrices for Computer Graphics. ACM Trans. Graph. 32, 4 (July), 142:1–142:15.
24. Lee, Y., Yoon, S.-E., Oh, S., Kim, D., and Choi, S. 2010. Multi-Resolution Cloth Simulation. Computer Graphics Forum 29, 7, 2225–2232.
25. McCormick, S. 1984. Multigrid Methods for Variational Problems: Further Results. SIAM Journal on Numerical Analysis 21, 2, 255–263.
26. Míka, S., and Vaněk, P. 1992. Acceleration of convergence of a two-level algebraic algorithm by aggregation in smoothing process. Applications of Mathematics 37, 5, 343–356.
27. Narain, R., Samii, A., and O’Brien, J. F. 2012. Adaptive Anisotropic Remeshing for Cloth Simulation. ACM Trans. Graph. 31, 6 (Nov.), 152:1–152:10.
28. Oh, S., Noh, J., and Wohn, K. 2008. A physically faithful multigrid method for fast cloth simulation. Computer Animation and VirtualWorlds 19, 3–4, 479–492.
29. Otaduy, M. A., Tamstorf, R., Steinemann, D., and Gross, M. 2009. Implicit Contact Handling for Deformable Objects. Computer Graphics Forum 28, 2, 559–568.
30. Trottenberg, U., Oosterlee, C. W., and Schuller, A. 2000. Multigrid. Academic press.
31. van der Vorst, H. A. 1982. A Generalized Lanczos Scheme. Mathematics of Computation 39, 160 (Oct), pp. 559–561.
32. Vassilevski, P. S. 2008. Multilevel Block Factorization Preconditioners, Matrix-based Analysis and Algorithms for Solving Finite Element Equations. Springer.
