Efficient Animation Techniques Balancing Both User Control And Physical Realism (Thesis)

Abstract:

Specifying the motion of an animated linked figure such that
it achieves given tasks (e.g., throwing a ball into a basket) and performing
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 {em spacetime constraints} paradigm has been shown
to be a valuable approach to this problem, but it suffers from the
computational complexity growth as creatures and tasks approach those
one would like to animate. There are two sources which contribute to
the complexity problem: one is the symbolic processing of the
animator's constraints and the objective functions derived from the
physical models and the second lies in the numerical optimization phase.
This thesis reports on work to enhance the spacetime constraints
techniques both symbolically and numerically to significantly
speed up computations.

Our first contribution is to develop a new symbolic interface with a recursive
evaluation scheme so that the time required for gradient computation
which is needed by the numerical optimization is reduced from
exponential growth to the optimal quadratic growth. Furthermore, with the
new symbolic method, a language developed for the symbolic expressions
can be easily input, thus it provides a more convenient interface.

Secondly, we develop a keyframe optimization system which
allows the user to specify a few keyframes while letting the
computer determine the speed and timing, parameters which may be less
intuitive for the animator, by using optimization methods.
The novelty of this approach is that the user-specified keyframes are used
both to provide control over the motion and to reduce the complexity of the
optimization problem. This method has the advantage of providing much
of the user control of the traditional animation system while providing the
physical realism of the optimization based system. Due to the reduced
complexity of the optimization problem, the computation time
is nearly interactive for complex figures.

Finally we develop a hierarchical scheme to solve the nonlinear
variational problem arising in the spacetime constraints
formulation by using wavelets. In this scheme, 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 unknowns. In addition, the optimization problem is better
conditioned so that the convergence is faster.