“Animating deformable objects using sparse spacetime constraints” by Schulz, Tycowicz, Seidel and Hildebrandt

  • ©Christian Schulz, Christoph von Tycowicz, Hans-Peter Seidel, and Klaus Hildebrandt




    Animating deformable objects using sparse spacetime constraints


Session Title: Subspace & Spacetime



    We propose a scheme for animating deformable objects based on spacetime optimization. The main feature is that it robustly and within a few seconds generates interesting motion from a sparse set of spacetime constraints. Providing only partial (as opposed to full) keyframes for positions and velocities is sufficient. The computed motion satisfies the constraints and the remaining degrees of freedom are determined by physical principles using elasticity and the spacetime constraints paradigm. Our modeling of the spacetime optimization problem combines dimensional reduction, modal coordinates, wiggly splines, and rotation strain warping. Our solver is based on a theorem that characterizes the solutions of the optimization problem and allows us to restrict the optimization to low-dimensional search spaces. This treatment of the optimization problem avoids a time discretization and the resulting method can robustly deal with sparse input and wiggly motion.


    1. An, S. S., Kim, T., and James, D. L. 2008. Optimizing cubature for efficient integration of subspace deformations. ACM Trans. Graph. 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. 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. Barbič, J., Sin, F., and Grinspun, E. 2012. Interactive editing of deformable simulations. ACM Trans. Graph. 31, 4. Google ScholarDigital Library
    5. Bergou, M., Mathur, S., Wardetzky, M., and Grinspun, E. 2007. TRACKS: Toward Directable Thin Shells. ACM Trans. Graph. 26, 3, 50:1–50:10. Google ScholarDigital Library
    6. Choi, M. G., and Ko, H.-S. 2005. Modal warping: Real-time simulation of large rotational deformation and manipulation. IEEE Trans. Vis. Comput. Graphics 11, 1, 91–101. Google ScholarDigital Library
    7. Cohen, M. F. 1992. Interactive spacetime control for animation. Proc of ACM SIGGRAPH 26, 293–302. Google ScholarDigital Library
    8. Coros, S., Martin, S., Thomaszewski, B., Schumacher, C., Sumner, R., and Gross, M. 2012. Deformable objects alive! ACM Trans. Graph. 31, 4, 69:1–69:9. Google ScholarDigital Library
    9. Fang, A. C., and Pollard, N. S. 2003. Efficient synthesis of physically valid human motion. ACM Trans. Graph. 22, 3, 417–426. Google ScholarDigital Library
    10. Gleicher, M. 1997. Motion editing with spacetime constraints. In Proc. of Symp. on Interactive 3D Graphics, 139–148. Google ScholarDigital Library
    11. Heeren, B., Rumpf, M., Wardetzky, M., and Wirth, B. 2012. Time-discrete geodesics in the space of shells. Comp. Graph. Forum 31, 5, 1755–1764. Google ScholarDigital Library
    12. Hildebrandt, K., Schulz, C., von Tycowicz, C., and Polthier, K. 2012. Interactive spacetime control of deformable objects. ACM Trans. Graph. 31, 4, 71:1–71:8. Google ScholarDigital Library
    13. Huang, J., Tong, Y., Zhou, K., Bao, H., and Desbrun, M. 2011. Interactive shape interpolation through controllable dynamic deformation. IEEE Transactions on Visualization and Computer Graphics 17, 7, 983–992. Google ScholarDigital Library
    14. Kass, M., and Anderson, J. 2008. Animating oscillatory motion with overlap: wiggly splines. ACM Trans. Graph. 27, 3, 28:1–28:8. Google ScholarDigital Library
    15. Kilian, M., Mitra, N. J., and Pottmann, H. 2007. Geometric modeling in shape space. ACM Trans. Graph. 26, 3, 64:1–64:10. Google ScholarDigital Library
    16. Kim, T., and James, D. L. 2009. Skipping steps in deformable simulation with online model reduction. ACM Trans. Graph. 28, 5, 123:1–123:9. Google ScholarDigital Library
    17. Kim, J., and Pollard, N. S. 2011. Fast simulation of skeleton-driven deformable body characters. ACM Trans. Graph. 30, 5, 121:1–121:19. Google ScholarDigital Library
    18. Kondo, R., Kanai, T., and Anjyo, K.-i. 2005. Directable animation of elastic objects. In Symp. Comp. Anim., 127–134. Google ScholarDigital Library
    19. 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
    20. Li, S., Huang, J., Desbrun, M., and Jin, X. 2013. Interactive elastic motion editing through spacetime position constraints. Computer Animation and Virtual Worlds 24, 3–4, 409–417.Google ScholarCross Ref
    21. Martin, S., Thomaszewski, B., Grinspun, E., and Gross, M. 2011. Example-based elastic materials. ACM Trans. Graph. 30, 4, 72:1–72:8. Google ScholarDigital Library
    22. McNamara, A., Treuille, A., Popović, Z., and Stam, J. 2004. Fluid control using the adjoint method. ACM Trans. Graph. 23, 3, 449–456. Google ScholarDigital Library
    23. Müller, M., Dorsey, J., McMillan, L., Jagnow, R., and Cutler, B. 2002. Stable real-time deformations. In Proc. Symp. Comp. Anim., 49–54. 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, 4, 1034–1054. Google ScholarDigital Library
    27. 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, 3, 514–521. Google ScholarDigital Library
    28. Schulz, C., von Tycowicz, C., Seidel, H.-P., and Hildebrandt, K., 2014. Proofs of two theorems concerning sparse spacetime constraints. http://arxiv.org/abs/1405.1902.Google Scholar
    29. Si, H., and Gärtner, K. 2005. Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations. In Proceedings of the 14th International Meshing Roundtable. Springer, 147–163.Google Scholar
    30. Sifakis, E., and Barbič, J. 2012. FEM simulation of 3D deformable solids: A practitioner’s guide to theory, discretization and model reduction. In SIGGRAPH Courses, 20:1–20:50. Google ScholarDigital Library
    31. Sulejmanpašić, A., and Popović, J. 2005. Adaptation of performed ballistic motion. ACM Trans. Graph. 24, 1, 165–179. Google ScholarDigital Library
    32. Sumner, R. W., Zwicker, M., Gotsman, C., and Popović, J. 2005. Mesh-based inverse kinematics. ACM Trans. Graph. 24, 3, 488–495. Google ScholarDigital Library
    33. Tan, J., Turk, G., and Liu, C. K. 2012. Soft body locomotion. ACM Trans. Graph. 31, 4, 26:1–26:11. Google ScholarDigital Library
    34. Treuille, A., McNamara, A., Popović, Z., and Stam, J. 2003. Keyframe control of smoke simulations. ACM Trans. Graph. 22, 3, 716–723. Google ScholarDigital Library
    35. Valette, S., and Chassery, J.-M. 2004. Approximated centroidal Voronoi diagrams for uniform polygonal mesh coarsening. Computer Graphics Forum 23, 3, 381–389.Google ScholarCross Ref
    36. 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:1–213:10. Google ScholarDigital Library
    37. Wisniewski, K. 2010. Finite Rotation Shells. Springer.Google Scholar
    38. Witkin, A., and Kass, M. 1988. Spacetime constraints. Proc. of ACM SIGGRAPH 22, 159–168. Google ScholarDigital Library
    39. Wojtan, C., Mucha, P. J., and Turk, G. 2006. Keyframe control of complex particle systems using the adjoint method. In Proc. Symp. Comp. Anim., 15–23. Google ScholarDigital Library
    40. Xu, D., Zhang, H., Wang, Q., and Bao, H. 2005. Poisson shape interpolation. In Symp. Solid and Phys. Model., 267–274. Google ScholarDigital Library

ACM Digital Library Publication: