“Hierarchical spacetime control” by Liu, Gortler and Cohen

Specifying the motion of an animated linked figure such that it achieves given tasks (e.g., throwing a ball into a basket) and performs the tasks in a realistic fashion (e.g., gracefully, and following physical laws such as gravity) has been an elusive goal for computer animators. The spacetime constraints paradigm has been shown to be a valuable approach to this problem, but it suffers from computational complexity growth as creatures and tasks approach those one would like to animate. The complexity is shown to be, in part, due to the choice of finite basis with which to represent the trajectories of the generalized degrees of freedom. This paper describes new features to the spacetime constraints paradigm to address this problem.The functions through time of the generalized degrees of freedom are reformulated in a hierarchical wavelet representation. This provides a means to automatically add detailed motion only where it is required, thus minimizing the number of discrete variables. In addition the wavelet basis is shown to lead to better conditioned systems of equations and thus faster convergence.

1. Aho, A. V., Sethi, R., and Ullman, J. D. Compilers: Prici-ples, Techniques and Tools. Addison Wesley, 1986.]]
2. Bartels, R., Beatty, J., and Barsky, B. An Introduction to Splines for Use in Computer Graphics and Modeling. Morgan Kaufmann, 1987.]]
3. Chui, C., and Quak, E. Wavelets on a bounded interval. Nu-merical Methods of Approximation Theory 9 (1992), 53-75.]]
4. Chui, C. K. An Introduction to Wavelets, vol. 1 of Wavelet Analysis and its Applications. Academic Press Inc., 1992.]]
5. Cohen, M. F. Interactive spacetime control for animation. Com-puter Graphics 26, 2 (July 1992), 293-302.]]
6. Dahmen, W., and Kunoth, A. Multilevel preconditioning. Numerische Mathematik 63 (1992), 315-344.]]
7. Fletcher, R. Practical Methods of Optimization, vol. 1. John Wiley and Sons, 1980.]]
8. Forsey, D., and Bartels, R. Hierarchical b-spline refinement. Computer Graphics 22, 4 (August 1988), 205-212.]]
9. Gortler, S., and Cohen, M. F. Variational modeling with wavelets. Tech. Rep. CS-TR-456-94, Department of Computer Sci-ence, Princeton University, 1994.]]
10. Gortler, S., Schr? oder, P., Cohen, M., and Hanrahan, P. Wavelet radiosity. In Computer Graphics, Annual Conference Series, 1993 (August 1993), Siggraph, pp. 221-230.]]
11. Kass, M. Condor: Constraint based dataflow. Computer Graphics 26, 2 (July 1992), 321-330.]]
12. Ngo, J. T., and Marks, J. Spacetime constraints revisited. In Computer Graphics, Annual Conference Series, 1993 (August 1993), Siggraph, pp. 343-350.]]
13. Papalambros, P. Y., and Wilde, D. J. Principles of Optimal Design. Cambridge University Press, Cambridge, England, 1988.]]
14. Quak, E., and Weyrich, N. Decomposition and reconstruction algorithms for spline wavelets on a bounded interval. Tech. Rep. 294, Center for Approximation Theory, Texas A&M, 1993.]]
15. Rall, L. B. Automatic Differentiation: Techniques and Applica-tions. Springer-Verlag, 1981.]]
16. Terzopoulos, D. Image analysis using multigrid relaxation meth-ods. IEEE PAMI 8, 2 (March 1986), 129-139.]]
17. van de Panne, M., and Fiume, E. Sensor-actuator networks. In Computer Graphics, Annual Conference Series, 1993 (August 1993), Siggraph, pp. 335-342.]]
18. Witkin, A., and Kass, M. Spacetime constraints. Computer Graphics 22, 4 (August 1988), 159-168.]]