Hierarchical spacetime control

ABSTRACT

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.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Richard H. Bartels , John C. Beatty , Brian A. Barsky, An introduction to splines for use in computer graphics & geometric modeling, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 3: Chui, C., and Quak, E. Wavelets on a bounded interval. Nu-merical Methods of Approximation Theory 9 (1992), 53-75.
• 4: Charles K. Chui, An introduction to wavelets, Academic Press Professional, Inc., San Diego, CA, 1992
• 5: Michael F. Cohen, Interactive spacetime control for animation, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.293-302, July 1992
• 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: David R. Forsey , Richard H. Bartels, Hierarchical B-spline refinement, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.205-212, Aug. 1988
• 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: Steven J. Gortler , Peter Schröder , Michael F. Cohen , Pat Hanrahan, Wavelet radiosity, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.221-230, September 1993 [doi>10.1145/166117.166146]
• 11: Michael Kass, CONDOR: constraint-based dataflow, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.321-330, July 1992
• 12: J. Thomas Ngo , Joe Marks, Spacetime constraints revisited, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.343-350, September 1993 [doi>10.1145/166117.166160]
• 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: D Terzopoulos, Image analysis using multigrid relaxation methods, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.2, p.129-139, March 1986 [doi>10.1109/TPAMI.1986.4767767]
• 17: Michiel van de Panne, Sensor-actuator networks, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.335-342, September 1993 [doi>10.1145/166117.166159]
• 18: Andrew Witkin , Michael Kass, Spacetime constraints, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.159-168, Aug. 1988

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Measurement, Performance, Theory