Deformable object animation using reduced optimal control

ABSTRACT

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.

REFERENCES

• 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.
• 2: Jernej Barbič , Doug L. James, Real-Time subspace integration for St. Venant-Kirchhoff deformable models, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 3: Jernej Barbič , Jovan Popović, Real-time control of physically based simulations using gentle forces, ACM Transactions on Graphics (TOG), v.27 n.5, December 2008
• 4: Miklós Bergou , Saurabh Mathur , Max Wardetzky , Eitan Grinspun, TRACKS: toward directable thin shells, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 5: Lynne Shapiro Brotman , Arun N. Netravali, Motion interpolation by optimal control, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.309-315, June 1988
• 6: Steve Capell , Seth Green , Brian Curless , Tom Duchamp , Zoran Popović, Interactive skeleton-driven dynamic deformations, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 7: Stephen Chenney , D. A. Forsyth, Sampling plausible solutions to multi-body constraint problems, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.219-228, July 2000 [doi>10.1145/344779.344882]
• 8: Michael F. Cohen, Interactive spacetime control for animation, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.293-302, July 1992
• 9: Kevin G. Der , Robert W. Sumner , Jovan Popović, Inverse kinematics for reduced deformable models, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 10: Anthony C. Fang , Nancy S. Pollard, Efficient synthesis of physically valid human motion, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 11: James Gain , Dominique Bechmann, A survey of spatial deformation from a user-centered perspective, ACM Transactions on Graphics (TOG), v.27 n.4, p.1-21, October 2008 [doi>10.1145/1409625.1409629]
• 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.
• 13: Michael Gleicher, Motion editing with spacetime constraints, Proceedings of the 1997 symposium on Interactive 3D graphics, p.139-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253321]
• 14: Radek Grzeszczuk , Demetri Terzopoulos , Geoffrey Hinton, NeuroAnimator: fast neural network emulation and control of physics-based models, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.9-20, July 1998 [doi>10.1145/280814.280816]
• 15: Jin Huang , Xiaohan Shi , Xinguo Liu , Kun Zhou , Li-Yi Wei , Shang-Hua Teng , Hujun Bao , Baining Guo , Heung-Yeung Shum, Subspace gradient domain mesh deformation, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 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.
• 17: Michael Kass , John Anderson, Animating oscillatory motion with overlap: wiggly splines, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 18: Ryo Kondo , Takashi Kanai , Ken-ichi Anjyo, Directable animation of elastic objects, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073385]
• 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.
• 20: C. Karen Liu , Aaron Hertzmann , Zoran Popović, Learning physics-based motion style with nonlinear inverse optimization, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 21: Zicheng Liu, Efficient animation techniques balancing both user control and physical realism, Princeton University, Princeton, NJ, 1996
• 22: Antoine McNamara , Adrien Treuille , Zoran Popović , Jos Stam, Fluid control using the adjoint method, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 23: Johannes Mezger , Bernhard Thomaszewski , Simon Pabst , Wolfgang Straßer, Interactive physically-based shape editing, Proceedings of the 2008 ACM symposium on Solid and physical modeling, June 02-04, 2008, Stony Brook, New York [doi>10.1145/1364901.1364915]
• 24: Zoran Popović , Andrew Witkin, Physically based motion transformation, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.11-20, July 1999 [doi>10.1145/311535.311536]
• 25: Jovan Popović , Steven M. Seitz , Michael Erdmann, Motion sketching for control of rigid-body simulations, ACM Transactions on Graphics (TOG), v.22 n.4, p.1034-1054, October 2003 [doi>10.1145/944020.944025]
• 26: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical Recipes 3rd Edition: The Art of Scientific Computing, Cambridge University Press, New York, NY, 2007
• 27: Charles Rose , Brian Guenter , Bobby Bodenheimer , Michael F. Cohen, Efficient generation of motion transitions using spacetime constraints, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.147-154, August 1996 [doi>10.1145/237170.237229]
• 28: Alla Safonova , Jessica K. Hodgins , Nancy S. Pollard, Synthesizing physically realistic human motion in low-dimensional, behavior-specific spaces, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 29: Adnan Sulejmanpašić , Jovan Popović, Adaptation of performed ballistic motion, ACM Transactions on Graphics (TOG), v.24 n.1, p.165-179, January 2005 [doi>10.1145/1037957.1037966]
• 30: Adrien Treuille , Antoine McNamara , Zoran Popović , Jos Stam, Keyframe control of smoke simulations, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 31: Adrien Treuille , Andrew Lewis , Zoran Popović, Model reduction for real-time fluids, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 32: Xiaoyuan Tu , Demetri Terzopoulos, Artificial fishes: physics, locomotion, perception, behavior, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.43-50, July 1994 [doi>10.1145/192161.192170]
• 33: Christopher D. Twigg , Doug L. James, Many-worlds browsing for control of multibody dynamics, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 34: Andrew Witkin , Michael Kass, Spacetime constraints, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.159-168, June 1988
• 35: Chris Wojtan , Peter J. Mucha , Greg Turk, Keyframe control of complex particle systems using the adjoint method, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Animation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Virtual reality

Keywords:
control, deformations, keyframes, model reduction, space-time