Abstract We present an efficient inverse-kinematics methodology based on the interpolation of example motions and positions. The technique is demonstrated on a number of inverse-kinematics positioning tasks for a human figure. In addition to simple positioning tasks, the method provides complete motion sequences that satisfy an inversekinematic goal. The interpolation at the heart of the algorithm allows an artist's influence to play a major role in ensuring that the system always generates plausible results. Due to the lightweight nature of the algorithm, we can position a character at extremely high frame rates, making the technique useful for time-critical run-time applications such as games. A talented animator can create believable characters that spark a desired response in an audience. Believable characters, a story, and a setting can transport a viewer for a time to another world. Animators, together with modelers, editors, sound engineers, and others can through tens of thousands of hours of human labor create theatrical masterpieces as seen in film. While these endeavors may produce the highest quality animation, current techniques are costly and are not appropriate for many problems. Interactive (unscripted) animation must adapt and change as needed to create a unique run-time experience each time such a system is executed. The most commercially successful interactive animation experiences are found in computer games, such as in Microsoft's Asheron's Call or MechWarrior. Avatar-mediated virtual conferencing, 3D chat, and other virtual reality applications also require interactive animation. In this paper we focus on providing tools to solve the inverse-kinematics (IK) problem. Inverse-kinematics generally refers to positioning an end effector such as a hand or foot to some goal location. IK is needed for crucial tasks. When a character needs to lift, touch, or otherwise manipulate a virtual object, inverse-kinematics is required. The reason IK problems are interesting and difficult is that there are, in general, an infinite number of ways one can position the joint angles of a complex figure such as a human to place the hand in some location. Finding a configuration that solves the IK problem and also looks "natural" remains an open research problem. Additionally, most applications do not require simply a static position of the character to place the hand in some location, but in fact a complete sequence to move the character to and from such a static position. We examine both the static and dynamic needs for inverse-kinematics. Finally, we wish to place much of the decision of what looks "natural" to the artist. Artist-centered interactive animation techniques have been an important topic of recent research. Bringing the artist back into focus is due to a realization that an artist's talent is hard to surpass and that artist supplied source material can be molded and changed as needed while respecting much of the original aesthetic. Research programs that seek to supplant, rather than support, the artist deny themselves a powerful ally. Furthermore, methods that leverage the artist's talent fit more eas- The "Verbs & Adverbs" system 14 , presented an efficient technique to control animation through interpolation using a combination of linear functions augmented with non-linear radial basis functions. The primary focus of that work was emotion control, such as varying a walk cycle from sad to happy (see Figure 1) . One of the other verbs shown was a reach, indicating that inverse-kinematic control was possible, as shown in Figure 2 . This paper expands upon that work, presenting a number of IK tasks solved through interpolation. The results are quantified and improved through a number of mathematical enhancements over the initial "Verbs & Adverbs" work, including use of a cardinal basis and automated methods for improving the accuracy of the inverse-kinematic tasks. We present two major enhancements to the "Verbs & Adverbs" system. First, we replace the interpolation per degreeof-freedom (DOF) with an interpolation per example by using cardinal basis functions. The resulting animation is equivalent but the use of the cardinal basis greatly reduces the number of interpolations that need to be performed, greatly increasing the efficiency of the system at design time and modestly increasing its runtime efficiency. Secondly, we show how the non-linearities in example-based IK solutions can be automatically corrected by insertion of pseudo-examples derived directly from the initial interpolation space designed by the artist. The resulting interpolation-based animation is highly efficient, running at many thousands of frames per second. The remainder of the paper will progress as follows. After a brief synopsis of related work, the construction of verbs will be covered in Section 3. This section will also detail the new cardinal basis construction and how it differs from the initial work in 14 . Section 4 will discuss the specifics of the inverse kinematics problem and how automatically generated pseudo-examples provide accurate and efficient results. Some results and conclusions will follow. The video figures referenced in this paper can be found with the accompanying conference materials and can also be found online in compressed form at http://research.microsoft.com/graphics/hfap/RBFIKVid.zip. Inverse-kinematics is one of the oldest problems in computer animation, tracing its origins back to the problem of positioning industrial robots. Positioning a character with rotational degrees of freedom is non-linear, but for small changes of an articulated figure's DOFs (i.e., the starting configuration is near the desired one), it is sufficiently smooth to enable an iterative linear IK solver. Girard and Maciejewski overview this technique in 5 . For complex motions, however, simple IK will often prove insufficient. Zhao and Badler 21 introduced a robust IK solution based on non-linear optimization. Rose, et al. 15 expanded this formulation to perform IK over entire motion sequences, mostly to enforce IK constraints during motion transitions. Non-linear IK is a powerful enough technique for complex motion capture analysis in the presence of noisy Rose, Sloan, and Cohen / IK by Example data, as shown by Bodenheimer, et al. 3 . Unfortunately, it suffers from being computationally expensive and by having a run-time that is highly dependent on the difficulty of the task and the quality of the initial guess. For real-time applications, this unpredictability reduces the technique's attractiveness. Motion retargetting 6 makes great use of IK over sequences of motions to adapt motions from one character to another with great success. Gleicher makes use of a much faster sequential quadratic programming approach. While it behaves less reliably than the method of 21 , it is much faster and can be used when the initial guesses are sufficiently good. Both these techniques make little use of the large body of human biomechanics knowledge. Synergy-based IK 7 uses a measure of how much a particular joint contributes to a given IK task (the synergy), in order to reduce the dimensionality of the problem and to help ensure that the results are humanlike. Rather than relying on complex models for how creatures move, our methodology primarily takes advantage of existing motion data and interpolates these to create new motions that solve the given IK constraint. A considerable amount of work has been undertaken with respect to editing existing animations and blending between two segments 15, 6, 9 . "Verbs & Adverbs" 14 presented an interpolated animation technique requiring a minimum of O(D) examples and which also allowed for local refinement of the interpolation space. These results were applied to shape interpolation in 17 with the key mathematical improvement being the use of cardinal basis functions. We further extend this work by bringing it into the animation domain, and in particular show how to apply this technique to inverse-kinematic problems. The efficiency of this interpolation is such that it can be reasonably used to control a large cast of characters acting simultaneously in conjunction with a high-level control mechanism such as in Musse, et al. 11 .
Rose et al. REF explored the idea of using certain poses as a seed for IK to blend between motions using radial basis functions (RBF) changing their style.
Artist-Directed Inverse-Kinematics Using Radial Basis Function Interpolation
ICAT Workshops
Computer Science