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

  • ©Jernej Barbic and Yili Zhao




    Real-time large-deformation substructuring



    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

ACM Digital Library Publication: