“Subspace condensation: full space adaptivity for subspace deformations” by Teng, Meyer, DeRose and Kim

  • ©Yun Teng, Mark Meyer, Tony DeRose, and Theodore Kim




    Subspace condensation: full space adaptivity for subspace deformations


Session Title: Deform Me a Solid



    Subspace deformable body simulations can be very fast, but can behave unrealistically when behaviors outside the prescribed subspace such as novel external collisions, are encountered. We address this limitation by presenting a fast, flexible new method that allows full space computation to be activated in the neighborhood of novel events while the rest of the body still computes in a subspace. We achieve this using a method we call subspace condensation, a variant on the classic static condensation precomputation. However, instead of a precomputation, we use the speed of subspace methods to perform the condensation at every frame. This approach allows the full space regions to be specified arbitrarily at runtime, and forms a natural two-way coupling with the subspace regions. While condensation is usually only applicable to linear materials, the speed of our technique enables its application to non-linear materials as well. We show the effectiveness of our approach by applying it to a variety of articulated character scenarios.


    1. An, S. S., Kim, T., and James, D. L. 2008. Optimizing Cubature for Efficient Integration of Subspace Deformations. ACM Trans. Graph. 27, 5 (Dec.), 165. Google ScholarDigital Library
    2. Baran, I., and Popović, J. 2007. Automatic rigging and animation of 3d characters. In ACM Trans. Graph., vol. 26, 72. Google ScholarDigital Library
    3. Barbič, J., and James, D. L. 2005. Real-Time Subspace Integration for St. Venant-Kirchhoff Deformable Models. ACM Trans. on Graphics 24, 3 (Aug.), 982–990. Google ScholarDigital Library
    4. Barbič, J., and Zhao, Y. 2011. Real-time large-deformation substructuring. ACM Trans. on Graphics 30. Google ScholarDigital Library
    5. Bathe, K.-J. 2007. Finite Element Procedures. Prentice Hall.Google Scholar
    6. Bro-Nielsen, M., and Cotin, S. 1996. Real-time volumetric deformable models for surgery simulation using finite elements and condensation. In Computer graphics forum, vol. 15, Wiley Online Library, 57–66.Google Scholar
    7. Gao, M., Mitchell, N., and Sifakis, E. 2014. Steklovpoincaré skinning. In Eurographics/ACM SIGGRAPH Symposium on Computer Animation, 139–148.Google Scholar
    8. Gascón, J., Zurdo, J. S., and Otaduy, M. A. 2010. Constraint-based simulation of adhesive contact. In Proc. of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation. Google ScholarDigital Library
    9. Gibson, S. F., and Mirtich, B. 1997. A Survey of Deformable Models in Computer Graphics. Tech. Rep. TR-97-19, Mitsubishi Electric Research Laboratories, Cambridge, MA, November.Google Scholar
    10. Guennebaud, G., Jacob, B., et al., 2010. Eigen v3. http://eigen.tuxfamily.org.Google Scholar
    11. Guyan, R. J. 1965. Reduction of stiffness and mass matrices. AIAA journal 3, 2, 380–380.Google ScholarCross Ref
    12. Hahn, F., Thomaszewski, B., Coros, S., Sumner, R. W., Cole, F., Meyer, M., DeRose, T., and Gross, M. 2014. Subspace clothing simulation using adaptive bases. ACM Trans. Graph. 33, 4 (July), 105:1–105:9. Google ScholarDigital Library
    13. Harmon, D., and Zorin, D. 2013. Subspace integration with local deformations. ACM Trans. Graph. 32, 4, 107. Google ScholarDigital Library
    14. Hauser, K. K., Shen, C., and O’Brien, J. F. 2003. Interactive deformation using modal analysis with constraints. In Graphics Interface, vol. 3, 16–17.Google Scholar
    15. Irons, B. 1965. Structural eigenvalue problems-elimination of unwanted variables. AIAA journal 3, 5, 961–962.Google ScholarCross Ref
    16. James, D. L., and Pai, D. K. 2003. Multiresolution green’s function methods for interactive simulation of large-scale elastostatic objects. ACM Trans. Graph. 22, 1 (Jan.), 47–82. Google ScholarDigital Library
    17. Kavan, L., Collins, S., Žára, J., and O’Sullivan, C. 2007. Skinning with dual quaternions. In Proceedings of the Symposium on Interactive 3D Graphics and Games, ACM, 39–46. Google ScholarDigital Library
    18. Kim, T., and Delaney, J. 2013. Subspace fluid re-simulation. ACM Trans. Graph. 32 (July). Google ScholarDigital Library
    19. Kim, T., and James, D. L. 2009. Skipping steps in deformable simulation with online model reduction. ACM Trans. Graph. 28, 5 (Dec.), 123:1–123:9. Google ScholarDigital Library
    20. Kim, T., and James, D. L. 2011. Physics-based character skinning using multi-domain subspace deformations. In ACM SIGGRAPH/ Eurographics Sym. on Computer Animation, 63–72. Google ScholarDigital Library
    21. Kry, P. G., James, D. L., and Pai, D. K. 2002. EigenSkin: Real Time Large Deformation Character Skinning in Hardware. In ACM SIGGRAPH Sym. on Computer Animation, 153–160. Google ScholarDigital Library
    22. Krysl, P., Lall, S., and Marsden, J. E. 2001. Dimensional model reduction in non-linear finite element dynamics of solids and structures. Int. J. Numer. Meth. Eng. 51, 479–504.Google ScholarCross Ref
    23. Leung, A. Y.-T. 1978. An accurate method of dynamic condensation in structural analysis. Int. J. Numer. Meth. Eng. 12, 11, 1705–1715.Google ScholarCross Ref
    24. Li, S., Huang, J., de Goes, F., Jin, X., Bao, H., and Desbrun, M. 2014. Space-time editing of elastic motion through material optimization and reduction. ACM Transactions on Graphics 33, 4. Google ScholarDigital Library
    25. McAdams, A., Zhu, Y., Selle, A., Empey, M., Tamstorf, R., Teran, J., and Sifakis, E. 2011. Efficient elasticity for character skinning with contact and collisions. ACM Trans. Graph. 30, 4 (July), 37:1–37:12. Google ScholarDigital Library
    26. Nealen, A., Muller, M., Keiser, R., Boxerman, E., and Carlson, M. 2005. Physically based deformable models in computer graphics. In Eurographics: State of the Art Report.Google Scholar
    27. Paz, M. 1989. Modified dynamic condensation method. Journal of Structural Engineering 115, 1, 234–238.Google ScholarCross Ref
    28. Pentland, A., and Williams, J. 1989. Good vibrations: Modal dynamics for graphics and animation. In Computer Graphics (Proceedings of SIGGRAPH 89), 215–222. Google ScholarDigital Library
    29. Sifakis, E., and Barbič, J. 2012. Fem simulation of 3d deformable solids: a practitioner’s guide to theory, discretization and model reduction. In ACM SIGGRAPH Courses, 20:1–20:50. Google ScholarDigital Library
    30. Teng, Y., Otaduy, M. A., and Kim, T. 2014. Simulating articulated subspace self-contact. ACM Trans. Graph. 33, 4 (July), 106:1–106:9. Google ScholarDigital Library
    31. von Tycowicz, C., Schulz, C., Seidel, H.-P., and Hildebrandt, K. 2013. An efficient construction of reduced deformable objects. ACM Trans. Graph. 32, 6, 213. Google ScholarDigital Library
    32. Wicke, M., Stanton, M., and Treuille, A. 2009. Modular bases for fluid dynamics. In ACM Trans. Graph., vol. 28, ACM, 39. Google ScholarDigital Library
    33. Wilson, E. L. 1974. The static condensation algorithm. Int.J. Numer. Meth. Eng. 8, 1, 198–203.Google ScholarCross Ref
    34. Xu, H., Li, Y., Chen, Y., and Barbic, J. 2014. Interactive material design using model reduction. ACM Trans. on Graphics. Google ScholarDigital Library
    35. Xu, W., Umentani, N., Chao, Q., Mao, J., Jin, X., and Tong, X. 2014. Sensitivity-optimized rigging for example-based real-time clothing synthesis. ACM Trans. Graph. 33, 4 (July), 107:1–107:11. Google ScholarDigital Library
    36. Yang, Y., Xu, W., Guo, X., Zhou, K., and Guo, B. 2013. Boundary-aware multi-domain subspace deformation. IEEE Transactions on Visualization and Computer Graphics.Google ScholarCross Ref

ACM Digital Library Publication: