“Real-time large-deformation substructuring” by Barbic and Zhao

This paper shows a method to extend 3D nonlinear elasticity model reduction to open-loop multi-level reduced deformable structures. Given a volumetric mesh, we decompose the mesh into several subdomains, build a reduced deformable model for each domain, and connect the domains using inertia coupling. This makes model reduction deformable simulations much more versatile: localized deformations can be supported without prohibitive computational costs, parts can be re-used and precomputation times shortened. Our method does not use constraints, and can handle large domain rigid body motion in addition to large deformations, due to our derivation of the gradient and Hessian of the rotation matrix in polar decomposition. We show real-time examples with multi-level domain hierarchies and hundreds of reduced degrees of freedom.

1. An, S. S., Kim, T., and James, D. L. 2008. Optimizing cubature for efficient integration of subspace deformations. ACM Trans. on Graphics 27, 5, 165:1–165:10. Google ScholarDigital Library
2. Barbič, J., and James, D. L. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. ACM Trans. on Graphics 24, 3, 982–990. Google ScholarDigital Library
3. Barbič, J., da Silva, M., and Popović, J. 2009. Deformable object animation using reduced optimal control. ACM Trans. on Graphics 28, 3. Google ScholarDigital Library
4. Bertails, F. 2009. Linear time super-helices. Comput. Graphics Forum 28, 2, 417–426.Google ScholarCross Ref
5. Capell, S., Green, S., Curless, B., Duchamp, T., and Popović, Z. 2002. Interactive skeleton-driven dynamic deformations. ACM Trans. on Graphics 21, 3, 586–593. Google ScholarDigital Library
6. Changizi, K., and Shabana, A. A. 1988. A recursive formulation for the dynamic analysis of open loop deformable multibody systems. Journal of Applied Mechanics 55, 3, 687–693.Google ScholarCross Ref
7. Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A Simple Geometric Model for Elastic Deformations. ACM Transactions on Graphics 29, 3, 38:1–38:6. Google ScholarDigital Library
8. Craig, R., and Bampton, M. 1968. Coupling of substructures for dynamic analysis. AIAA Journal 6, 7, 1313–1319.Google ScholarCross Ref
9. Debunne, G., Desbrun, M., Cani, M.-P., and Barr, A. H. 2001. Dynamic Real-Time Deformations Using Space & Time Adaptive Sampling. In Proc. of ACM SIGGRAPH 2001, 31–36. Google Scholar
10. Dodds, R. H., and Lopez, L. A. 1980. Substructuring in Linear and Nonlinear Analysis. International Journal for Numerical Methods in Engineering 15, 583–597.Google ScholarCross Ref
11. Farhat, C. 1988. A simple and efficient automatic FEM domain decomposer. Computers and Structures 28, 5, 579–602.Google ScholarCross Ref
12. Featherstone, R. 1987. Robot Dynamics Algorithms. Kluwer Academic Publishers, Boston. Google Scholar
13. Georgii, J., and Westermann, R. 2005. A multigrid framework for real-time simulation of deformable volumes. In Proc. of the 2nd Workshop On Virtual Reality Interaction and Physical Simulation, 50–57.Google Scholar
14. Grinspun, E., Krysl, P., and Schröder, P. 2002. CHARMS: A Simple Framework for Adaptive Simulation. In Proc. of ACM SIGGRAPH 2002. Google Scholar
15. Huang, J., Liu, X., Bao, H., Guo, B., and Shum, H.-Y. 2006. An efficient large deformation method using domain decomposition. Computers & Graphics 30, 6, 927–935. Google ScholarDigital Library
16. Huang, Q., Wicke, M., Adams, B., and Guibas, L. 2009. Shape decomposition using modal analysis. Computer Graphics Forum 28, 2, 407–416.Google ScholarCross Ref
17. James, D. L., and Pai, D. K. 2002. DyRT: Dynamic Response Textures for Real Time Deformation Simulation With Graphics Hardware. ACM Trans. on Graphics 21, 3, 582–585. Google ScholarDigital Library
18. James, D. L., and Pai, D. K. 2002. Real Time Simulation of Multizone Elastokinematic Models. In IEEE Int. Conf. on Robotics and Automation, 927–932.Google Scholar
19. Kaufman, D. M., Sueda, S., James, D. L., and Pai, D. K. 2008. Staggered Projections for Frictional Contact in Multibody Systems. ACM Transactions on Graphics 27, 5, 164:1–164:11. Google ScholarDigital Library
20. Kaufmann, P., Martin, S., Botsch, M., and Gross, M. 2009. Flexible Simulation of Deformable Models Using Discontinuous Galerkin FEM. J. of Graphical Models 71, 4, 153–167. Google ScholarDigital Library
21. Kharevych, L., Mullen, P., Owhadi, H., and Desbrun, M. 2009. Numerical coarsening of inhomogeneous elastic materials. ACM Trans. on Graphics 28, 3, 51:1–51:8. Google ScholarDigital Library
22. Kim, T., and James, D. L. 2009. Skipping steps in deformable simulation with online model reduction. ACM Trans. Graph. 28, 5, 1–9. Google ScholarDigital Library
23. Krysl, P., Lall, S., and Marsden, J. E. 2001. Dimensional model reduction in non-linear finite element dynamics of solids and structures. Int. J. for Numerical Methods in Engineering 51, 479–504.Google ScholarCross Ref
24. Mathai, A. M. 1997. Jacobians of Matrix Transformations and Functions of Matrix Argument. World Scientific Publishing Co.Google Scholar
25. Metaxas, D., and Terzopoulos, D. 1992. Dynamic deformation of solid primitives with constraints. In Computer Graphics (Proc. of SIGGRAPH 92), 309–312. Google Scholar
26. Müller, M., and Gross, M. 2004. Interactive Virtual Materials. In Proc. of Graphics Interface 2004, 239–246. Google ScholarDigital Library
27. Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless Deformations Based on Shape Matching. In Proc. of ACM SIGGRAPH 2005, 471–478. Google Scholar
28. Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2006. Physically based deformable models in computer graphics. Computer Graphics Forum 25, 4, 809–836.Google ScholarCross Ref
29. Nesme, M., Kry, P. G., Jeřábková, L., and Faure, F. 2009. Preserving topology and elasticity for embedded deformable models. ACM Trans. on Graphics 28, 3, 52:1–52:9. Google ScholarDigital Library
30. Patnaik, S., Gendy, A., and Hopkins, D. 1994. Design optimization of large structural systems with substructuring in a parallel computational environment. Computing Systems in Engineering 5, 4-6, 425–440.Google ScholarCross Ref
31. Ryu, Y. S., and Arora, J. S. 1985. Review of Nonlinear FE Methods with Substructures. Journal of Engineering Mechanics 111, 11, 1361–1379.Google ScholarCross Ref
32. Shabana, A. A. 2005. Dynamics of Multibody Systems. Cambridge Univ. Press, New York, NY.Google Scholar
33. Sharf, I., and D’Eleuterio, G. 1988. Computer simulation of elastic chains using a recursive formulation. In IEEE Conf. on Robotics and Automation, vol. 3, 1539–1545.Google Scholar
34. Storaasli, O. O., and Bergan, P. 1987. Nonlinear Substructuring Method for Concurrent Processing Computers. AIAA 25, 6, 871–876.Google ScholarCross Ref
35. Toselli, A., and Widlund, O. 2004. Domain Decomposition Methods. Springer.Google Scholar
36. Treuille, A., Lewis, A., and Popović, Z. 2006. Model reduction for real-time fluids. ACM Trans. on Graphics 25, 3, 826–834. Google ScholarDigital Library
37. Twigg, C., and Kačić-Alesić, Z. 2010. Point cloud glue: constraining simulations using the procrustes transform. In Symp. on Computer Animation (SCA), 45–54. Google ScholarDigital Library
38. Wicke, M., Stanton, M., and Treuille, A. 2009. Modular bases for fluid dynamics. ACM Trans. on Graphics 28, 3, 39:1–39:8. Google ScholarDigital Library