“An Efficient Multigrid Method for the Simulation of High Resolution Elastic Solids” by Zhu, Sifakis, Teran and Brandt

We present a multigrid framework for the simulation of high-resolution elastic deformable models, designed to facilitate scalability on shared memory multiprocessors. We incorporate several state-of-the-art techniques from multigrid theory, while adapting them to the specific requirements of graphics and animation applications, such as the ability to handle elaborate geometry and complex boundary conditions. Our method supports simulation of linear elasticity and corotational linear elasticity. The efficiency of our solver is practically independent of material parameters, even for near-incompressible materials. We achieve simulation rates as high as 6 frames per second for test models with 256K vertices on an 8-core SMP, and 1.6 frames per second for a 2M vertex object on a 16-core SMP.

1. Barbic, J. and James, D. 2005. Real-Time subspace integration of St. Venant-Kirchoff deformable models. ACM Trans. Graph. 24, 3, 982–990. 
2. Bolz, J., Farmer, I., Grinspun, E., and Schroder, P. 2003. Sparse matrix solvers on the GPU: Conjugate gradients and multigrid. ACM Trans. Graph. 22, 3, 917–924. 
3. Bonet, J. and Wood, R. 1997. Nonlinear Continuum Mechanics for Finite Element Analysis. Cambridge University Press.
4. Brandt, A. 1977. Multi-Level adaptive solutions to boundary-value problems. Math. Comput. 31, 138, 333–390.
5. Brandt, A. 1986. Algebraic multigrid theory: The symmetric case. Appl. Math. Comput. 19, 1-4, 23–56. 
6. Brandt, A. 1994. Rigorous quantitative analysis of multigrid, I: Constant coefficients two-level cycle with L₂-norm. SIAM J. Numer. Anal. 31, 1695. 
7. Brandt, A. and Dinar, N. 1978. Multigrid solutions to elliptic flow problems. In Numerical Methods for Partial Differential Equations, 53–147.
8. Brezzi, F. and Fortin, M. 1991. Mixed and Hybrid Finite Element Methods. Springer-Verlag, New York. 
9. Capell, S., Green, S., Curless, B., Duchamp, T., and Popović, Z. 2002. A multiresolution framework for dynamic deformations. In Proceedings of the ACM SIGGRAPH Symposium on Computer Animation. ACM Press, 41–48. 
10. Debunne, G., Desbrun, M., Cani, M., and Barr, A. 2001. Dynamic real-time deformations using space and time adaptive sampling. In Proceedings of the SIGGRAPH. Vol. 20. 31–36. 
11. Dick, C., Georgii, J., Burgkart, R., and Westermann, R. 2008. Computational steering for patient-specific implant planning in orthopedics. In Proceedings of Visual Computing for Biomedicine Conference. 83–92. 
12. Gaspar, F., Gracia, J., Lisbona, F., and Oosterlee, C. 2008. Distributive smoothers in multigrid for problems with dominating graddiv operators. Numer. Linear Algeb. Appl. 15, 8, 661–683.
13. Georgii, J. and Westermann, R. 2006. A multigrid framework for real-time simulation of deformable bodies. Comput. Graph. 30, 3, 408–415. 
14. Georgii, J. and Westermann, R. 2008. Corotated finite elements made fast and stable. In Proceedings of the 5th Workshop On Virtual Reality Interaction and Physical Simulation.
15. Goodnight, N., Woolley, C., Lewin, G., Luebke, D., and Humphreys, G. 2003. A multigrid solver for boundary value problems using programmable graphics hardware. In Proceedings of the ACM SIGGRAPH/Eurographics Conference on Graphics Hardware. 102–111. 
16. Green, S., Turkiyyah, G., and Storti, D. 2002. Subdivision-based multilevel methods for large scale engineering simulation of thin shells. In Proceedings of the 7th ACM Symposium on Solid Modeling and Applications. ACM, New York, 265–272. 
17. Griebel, M., Oeltz, D., and Schweitzer, M. A. 2003. An algebraic multigrid method for linear elasticity. SIAM J. Sci. Comput. 25, 407. 
18. Grinspun, E., Krysl, P., and Schröder, P. 2002. CHARMS: A simple framework for adaptive simulation. ACM Trans. Graph. 21, 281–290. 
19. Harlow, F. and Welch, J. 1965. Numerical calculation of time-dependent viscous incompressible flow of fluid with free surface. Phys. Fluids 8, 2182–2189.
20. Hauth, M. and Strasser, W. 2004. Corotational Simulation of Deformable Solids. In Proceedings of the International Conferences in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG). 137–145.
21. Hughes, C., Grzeszczuk, R., Sifakis, E., Kim, D., Kumar, S., Selle, A., Chhugani, J., Holliman, M., and Chen, Y.-K. 2007. Physical simulation for animation and visual effects: Parallelization and characterization for chip multiprocessors. In Proceedings of the International Symposium on Computer Architecture. 
22. Hughes, T. 1987. The Finite Element Method: Linear Static and Dynamic Finite Element Analysis. Prentice Hall.
23. Irving, G., Schroeder, C., and Fedkiw, R. 2007. Volume conserving finite element simulations of deformable models. ACM Trans. Graph. 26, 3. 
24. James, D. and Fatahalian, K. 2003. Precomputing interactive dynamic deformable scenes. ACM Trans. Graph. 22, 879–887. 
25. Kaufmann, P., Martin, S., Botsch, M., and Gross, M. 2008. Flexible Simulation of Deformable Models Using Discontinuous Galerkin FEM. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 
26. Kaufmann, P., Martin, S., Botsch, M., and Gross, M. 2009. Flexible simulation of deformable models using discontinuous Galerkin FEM. Graph. Models 71, 4, 153–167. 
27. Kazhdan, M. and Hoppe, H. 2008. Streaming multigrid for gradient-domain operations on large images. ACM Trans. Graph. 27, 3. 
28. Lee, S.-H., Sifakis, E., and Terzopoulos, D. 2009. Comprehensive biomechanical modeling and simulation of the upper body. ACM Trans. Graph. 28, 4, 1–17. 
29. Lekien, F. and Marsden, J. 2005. Tricubic interpolation in three dimensions. Int. J. Numer. Methods Engin. 63, 3, 455–471.
30. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Trans. Graph. 23, 457–462. 
31. Molino, N., Bao, Z., and Fedkiw, R. 2004. A virtual node algorithm for changing mesh topology during simulation. ACM Trans. Graph. 23, 385–392. 
32. Müller, M., Dorsey, J., McMillan, L., Jagnow, R., and Cutler, B. 2002. Stable real-time deformations. In Proceedings of the ACM SIGGRAPH Symposium on Computer Animation. 49–54. 
33. Müller, M. and Gross, M. 2004. Interactive virtual materials. In Proceedings of the Conference on Graphics Interface. 239–246. 
34. Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. 24, 3, 471–478. 
35. Müller, M., Teschner, M., and Gross, M. 2004. Physically-based simulation of objects represented by surface meshes. In Proceedings of the Computer Graphics International Conference. 156–165. 
36. Ni, X., Garland, M., and Hart, J. 2004. Fair Morse functions for extracting the topological structure of a surface mesh. ACM Trans. Graph. 23, 3, 613–622. 
37. O’Brien, J. and Hodgins, J. 1999. Graphical modeling and animation of brittle fracture. In Proceedings of the SIGGRAPH. 137–146. 
38. Otaduy, M. A., Germann, D., Redon, S., and Gross, M. 2007. Adaptive deformations with fast tight bounds. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’07). 181–190. 
39. Rivers, A. and James, D. 2007. FastLSM: Fast lattice shape matching for robust real-time deformation. ACM Trans. Graph. 26, 3. 
40. Shi, L., Yu, Y., Bell, N., and Feng, W. 2006. A Fast multigrid algorithm for mesh deformation. ACM Trans. Graph., 1108–1117.
41. Sifakis, E., Shinar, T., Irving, G., and Fedkiw, R. 2007. Hybrid simulation of deformable solids. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 81–90. 
42. Teran, J., Sifakis, E., Irving, G., and Fedkiw, R. 2005. Robust quasistatic finite elements and flesh simulation. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 181–190. 
43. Terzopoulos, D. and Fleischer, K. 1988. Deformable models. Visual Comput. 4, 6, 306–331.
44. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. ACM Comput. Graph. 21, 4, 205–214. 
45. Thomaszewski, B., Pabst, S., and Blochinger, W. 2007. Exploiting parallelism in physically-based simulations on multi-core processor architectures. In Proceedings of the EG Symposium on Parallel Graphics and Visualization. 
46. Trottenberg, U., Oosterlee, C., and Schuller, A. 2001. Multigrid. Academic Press, San Diego, CA. 
47. Wu, X. and Tendick, F. 2004. Multigrid integration for interactive deformable body simulation. In Proceedings of the International Symposium on Medical Simulation. ACM, New York, 92–104.