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

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