“Interactive spacetime control of deformable objects” by Hildebrandt, Schulz, Tycowicz and Polthier

  • ©Klaus Hildebrandt, Christian Schulz, Christoph von Tycowicz, and Konrad Polthier




    Interactive spacetime control of deformable objects



    Creating motions of objects or characters that are physically plausible and follow an animator’s intent is a key task in computer animation. The spacetime constraints paradigm is a valuable approach to this problem, but it suffers from high computational costs. Based on spacetime constraints, we propose a framework for controlling the motion of deformable objects that offers interactive response times. This is achieved by a model reduction of the underlying variational problem, which combines dimension reduction, multipoint linearization, and decoupling of ODEs. After a preprocess, the cost for creating or editing a motion is reduced to solving a number of one-dimensional spacetime problems, whose solutions are the wiggly splines introduced by Kass and Anderson [2008]. We achieve interactive response times through a new fast and robust numerical scheme for solving the one-dimensional problems that is based on a closed-form representation of the wiggly splines.


    1. Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. In Proc. of ACM SIGGRAPH, 43–54. Google ScholarDigital Library
    2. Barbič, J., and James, D. L. 2005. Real-time subspaceintegration for St. Venant-Kirchhoff deformable models. ACM Trans. Graph. 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. Graph. 28, 53:1–53:9. Google ScholarDigital Library
    4. Barzel, R. 1997. Faking dynamics of ropes and springs. IEEE Comput. Graph. Appl. 17, 31–39. Google ScholarDigital Library
    5. Bergou, M., Mathur, S., Wardetzky, M., and Grinspun, E. 2007. TRACKS: Toward Directable Thin Shells. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
    6. Chai, J., and Hodgins, J. K. 2007. Constraint-based motion optimization using a statistical dynamic model. ACM Trans. Graph. 26. Google ScholarDigital Library
    7. Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29, 38:1-38:6. Google ScholarDigital Library
    8. Cohen, M. F. 1992. Interactive spacetime control for animation. Proc of ACM SIGGRAPH 26, 293–302. Google ScholarDigital Library
    9. Fang, A. C., and Pollard, N. S. 2003. Efficient synthesis of physically valid human motion. ACM Trans. Graph. 22, 417–426. Google ScholarDigital Library
    10. Gauss, C. F. 1829. Über ein neues allgemeines Grundgesetz der Mechanik. J. Reine Angew. Math. 4, 232–235.Google ScholarCross Ref
    11. Gleicher, M. 1997. Motion editing with spacetime constraints. In Proc. of Symp. on Interactive 3D Graphics, 139–148. Google ScholarDigital Library
    12. Griewank, A., Juedes, D., and Utke, J. 1996. Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++. ACM Trans. Math. Softw. 22, 2, 131–167. Google ScholarDigital Library
    13. Grinspun, E., Hirani, A. N., Desbrun, M., and Schröder, P. 2003. Discrete shells. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 62–67. Google ScholarDigital Library
    14. Guenter, B. 2007. Efficient symbolic differentiation for graphics applications. ACM Trans. Graph. 26. Google ScholarDigital Library
    15. Hildebrandt, K., Schulz, C., von Tycowicz, C., and Polthier, K. 2011. Interactive surface modeling using modal analysis. ACM Trans. Graph. 30, 119:1–119:11. Google ScholarDigital Library
    16. Hildebrandt, K., Schulz, C., von Tycowicz, C., and Polthier, K. 2012. Modal shape analysis beyond Laplacian. Computer Aided Geometric Design 29, 5, 204–218. Google ScholarDigital Library
    17. Huang, J., Shi, X., Liu, X., Zhou, K., Wei, L.-Y., Teng, S.-H., Bao, H., Guo, B., and Shum, H.-Y. 2006. Subspace gradient domain mesh deformation. ACM Trans. Graph. 25, 3, 1126–1134. Google ScholarDigital Library
    18. Idelsohn, S. R., and Cardona, A. 1985. A reduction method for nonlinear structural dynamic analysis. Comput. Meth. Appl. Mech. Eng. 49, 3, 253–279.Google ScholarCross Ref
    19. Kass, M., and Anderson, J. 2008. Animating oscillatory motion with overlap: wiggly splines. ACM Trans. Graph. 27, 28:1–28:8. Google ScholarDigital Library
    20. Kilian, M., Mitra, N. J., and Pottmann, H. 2007. Geometric modeling in shape space. ACM Trans. Graph. 26. Google ScholarDigital Library
    21. Kim, T., and James, D. L. 2009. Skipping steps in deformable simulation with online model reduction. ACM Trans. Graph. 28, 123:1–123:9. 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. McNamara, A., Treuille, A., Popović, Z., and Stam, J. 2004. Fluid control using the adjoint method. ACM Trans. Graph. 23, 449–456. Google ScholarDigital Library
    24. Nickell, R. 1976. Nonlinear dynamics by mode superposition. Comput. Meth. Appl. Mech. Eng. 7, 1, 107–129.Google ScholarCross Ref
    25. Pentland, A., and Williams, J. 1989. Good vibrations: modal dynamics for graphics and animation. Proc. of ACM SIGGRAPH 23, 207–214. Google ScholarDigital Library
    26. Popović, J., Seitz, S. M., and Erdmann, M. 2003. Motion sketching for control of rigid-body simulations. ACM Trans. Graph. 22, 1034–1054. Google ScholarDigital Library
    27. Ritchie, K., Callery, J., and Biri, K. 2005. The Art of Rigging. CG Toolkit.Google Scholar
    28. Safonova, A., Hodgins, J. K., and Pollard, N. S. 2004. Synthesizing physically realistic human motion in low-dimensional, behavior-specific spaces. ACM Trans. Graph. 23, 514–521. Google ScholarDigital Library
    29. Shabana, A. 1997. Theory of Vibration II: Vibration of Discrete and Continuous Systems, 2nd ed. Springer Verlag.Google Scholar
    30. Sulejmanpašić, A., and Popović, J. 2005. Adaptation of performed ballistic motion. ACM Trans. Graph. 24, 165–179. Google ScholarDigital Library
    31. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Proc. of ACM SIGGRAPH, 205–214. Google ScholarDigital Library
    32. Treuille, A., McNamara, A., Popović, Z., and Stam, J. 2003. Keyframe control of smoke simulations. ACM Trans. Graph. 22, 716–723. Google ScholarDigital Library
    33. Treuille, A., Lewis, A., and Popović, Z. 2006. Model reduction for real-time fluids. ACM Trans. Graph. 25, 826–834. Google ScholarDigital Library
    34. Wicke, M., Stanton, M., and Treuille, A. 2009. Modular bases for fluid dynamics. ACM Trans. Graph. 28, 39:1–39:8. Google ScholarDigital Library
    35. Wirth, B., Bar, L., Rumpf, M., and Sapiro, G. 2009. Geodesics in shape space via variational time discretization. In Proc. of the 7th Intern. Conf. on Energy Minimization Methods in Computer Vision and Pattern Recognition, 288–302. Google ScholarDigital Library
    36. Witkin, A., and Kass, M. 1988. Spacetime constraints. Proc. of ACM SIGGRAPH 22, 159–168. Google ScholarDigital Library
    37. Wojtan, C., Mucha, P. J., and Turk, G. 2006. Keyframe control of complex particle systems using the adjoint method. In Proc. of ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 15–23. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: