“Deformable object animation using reduced optimal control” by Barbic, da Silva and Popović

Keyframe animation is a common technique to generate animations of deformable characters and other soft bodies. With spline interpolation, however, it can be difficult to achieve secondary motion effects such as plausible dynamics when there are thousands of degrees of freedom to animate. Physical methods can provide more realism with less user effort, but it is challenging to apply them to quickly create specific animations that closely follow prescribed animator goals. We present a fast space-time optimization method to author physically based deformable object simulations that conform to animator-specified keyframes. We demonstrate our method with FEM deformable objects and mass-spring systems.Our method minimizes an objective function that penalizes the sum of keyframe deviations plus the deviation of the trajectory from physics. With existing methods, such minimizations operate in high dimensions, are slow, memory consuming, and prone to local minima. We demonstrate that significant computational speedups and robustness improvements can be achieved if the optimization problem is properly solved in a low-dimensional space. Selecting a low-dimensional space so that the intent of the animator is accommodated, and that at the same time space-time optimization is convergent and fast, is difficult. We present a method that generates a quality low-dimensional space using the given keyframes. It is then possible to find quality solutions to difficult space-time optimization problems robustly and in a manner of minutes.

1. Adams, B., Ovsjanikov, M., Wand, M., Seidel, H.-P., and Guibas, L. J. 2008. Meshless modeling of deformable shapes and their motion. In Symp. on Computer Animation (SCA), 77–86. 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 (SIGGRAPH 2005) 24, 3, 982–990. Google ScholarDigital Library
3. Barbič, J., and Popović, J. 2008. Real-time control of physically based simulations using gentle forces. ACM Trans. on Graphics (SIGGRAPH Asia 2008) 27, 5, 163:1–163:10. Google ScholarDigital Library
4. Bergou, M., Mathur, S., Wardetzky, M., and Grinspun, E. 2007. TRACKS: Toward directable thin shells. ACM Trans. on Graphics (SIGGRAPH 2007) 26, 3, 50:1–50:10. Google ScholarDigital Library
5. Brotman, L. S., and Netravali, A. N. 1988. Motion interpolation by optimal control. In Computer Graphics (Proc. of SIGGRAPH 88), vol. 22, 309–315. Google ScholarDigital Library
6. Capell, S., Green, S., Curless, B., Duchamp, T., and Popović, Z. 2002. Interactive skeleton-driven dynamic deformations. ACM Trans. on Graphics (SIGGRAPH 2002) 21, 3, 586–593. Google ScholarDigital Library
7. Chenney, S., and Forsyth, D. A. 2000. Sampling plausible solutions to multi-body constraint problems. In Proc. of ACM SIGGRAPH 2000, 219–228. Google ScholarDigital Library
8. Cohen, M. F. 1992. Interactive spacetime control for animation. In Computer Graphics (Proc. of SIGGRAPH 92), vol. 26, 293–302. Google ScholarDigital Library
9. Der, K. G., Sumner, R. W., and Popović, J. 2006. Inverse kinematics for reduced deformable models. ACM Trans. on Graphics (SIGGRAPH 2006) 25, 3, 1174–1179. Google ScholarDigital Library
10. Fang, A. C., and Pollard, N. S. 2003. Efficient synthesis of physically valid human motion. ACM Trans. on Graphics (SIGGRAPH 2003) 22, 3, 417–426. Google ScholarDigital Library
11. Gain, J., and Bechmann, D. 2008. A survey of spatial deformation from a user-centered perspective. ACM Trans. on Graphics 27, 4, 1–21. Google ScholarDigital Library
12. Gildin, E. 2006. Model and controller reduction of large-scale structures based on projection methods. PhD thesis, The Institute for Computational Engineering and Sciences, University of Texas at Austin.Google Scholar
13. Gleicher, M. 1997. Motion editing with spacetime constraints. In Proc. ACM Symp. on Interactive 3D Graphics, 139–148. Google ScholarDigital Library
14. Grzeszczuk, R., Terzopoulos, D., and Hinton, G. 1998. NeuroAnimator: Fast neural network emulation and control of physics-based models. In Proc. of ACM SIGGRAPH 98, 9–20. Google ScholarDigital Library
15. 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. on Graphics (SIGGRAPH 2006) 25, 3, 1126–1134. Google ScholarDigital Library
16. Jeon, H., and Choi, M.-H. 2007. Interactive motion control of deformable objects using localized optimal control. In Proc. of the IEEE Int. Conf. on Robotics and Automation, 2582–2587.Google Scholar
17. Kass, M., and Anderson, J. 2008. Animating oscillatory motion with overlap: Wiggly splines. ACM Trans. on Graphics (SIGGRAPH 2008) 27, 3, 28:1–28:8. Google ScholarDigital Library
18. Kondo, R., Kanai, T., and ichi Anjyo, K. 2005. Directable animation of elastic objects. In Symp. on Computer Animation (SCA), 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. for Numerical Methods in Engineering 51, 479–504.Google ScholarCross Ref
20. Liu, C. K., Hertzmann, A., and Popović, Z. 2005. Learning physics-based motion style with nonlinear inverse optimization. ACM Trans. on Graphics (SIGGRAPH 2005) 24, 3, 1071–1081. Google ScholarDigital Library
21. Liu, Z. 1996. Efficient animation techniques balancing both user control and physical realism. PhD thesis, Department of Comp. Science, Princeton University. Google ScholarDigital Library
22. McNamara, A., Treuille, A., Popović, Z., and Stam, J. 2004. Fluid control using the adjoint method. ACM Trans. on Graphics (SIGGRAPH 2004) 23, 3, 449–456. Google ScholarDigital Library
23. Mezger, J., Thomaszewski, B., Pabst, S., and Strasser, W. 2008. Interactive physically-based shape editing. In Proc. of the ACM symposium on Solid and physical modeling, 79–89. Google ScholarDigital Library
24. Popović, Z., and Witkin, A. P. 1999. Physically based motion transformation. In Proc. of SIGGRAPH 99, 11–20. Google ScholarDigital Library
25. Popović, J., Seitz, S. M., and Erdmann, M. 2003. Motion sketching for control of rigid-body simulations. ACM Trans. on Graphics 22, 4, 1034–1054. Google ScholarDigital Library
26. Press, W., Teukolsky, S., Vetterling, W., and Flannery, B. 2007. Numerical recipes: The art of scientific computing, third ed. Cambridge University Press, Cambridge, UK. Google ScholarDigital Library
27. Rose, C., Guenter, B., Bodenheimer, B., and Cohen, M. 1996. Efficient generation of motion transitions using spacetime constraints. In Proc. of ACM SIGGRAPH 96, 147–154. Google ScholarDigital Library
28. Safonova, A., Hodgins, J., and Pollard, N. 2004. Synthesizing physically realistic human motion in low-dimensional, behavior-specific spaces. ACM Trans. on Graphics (SIGGRAPH 2004) 23, 3, 514–521. Google ScholarDigital Library
29. Sulejmanpasić, A., and Popović, J. 2005. Adaptation of performed ballistic motion. ACM Trans. on Graphics 24, 1, 165–179. Google ScholarDigital Library
30. Treuille, A., McNamara, A., Popović, Z., and Stam, J. 2003. Keyframe control of smoke simulations. ACM Trans. on Graphics (SIGGRAPH 2003) 22, 3, 716–723. Google ScholarDigital Library
31. Treuille, A., Lewis, A., and Popović, Z. 2006. Model reduction for real-time fluids. ACM Trans. on Graphics (SIGGRAPH 2006) 25, 3, 826–834. Google ScholarDigital Library
32. Tu, X., and Terzopoulos, D. 1994. Artificial fishes: Physics, locomotion, perception, behavior. In Proc. of ACM SIGGRAPH 94, 43–50. Google ScholarDigital Library
33. Twigg, C. D., and James, D. L. 2007. Many-worlds browsing for control of multibody dynamics. ACM Trans. on Graphics (SIGGRAPH 2007) 26, 3, 14:1–14:8. Google ScholarDigital Library
34. Witkin, A., and Kass, M. 1988. Spacetime constraints. In Computer Graphics (Proc. of SIGGRAPH 88), vol. 22, 159–168. Google ScholarDigital Library
35. Wojtan, C., Mucha, P. J., and Turk, G. 2006. Keyframe control of complex particle systems using the adjoint method. In Symp. on Computer Animation (SCA), 15–23. Google ScholarDigital Library