Quaternion Interpolation Project

This work was done as a semester project in the Intelligent Systems Laboratory under the supervision of Dr. Gershon Elber

Some background

Interpolation of an object’s location (translation), scale factor and orientation (rotation) from a parametric curve is a key element in computer animation.

Usually, the animation curve is specified by key frames associated with animation time. The curve is constructed with interpolation splines (Bezier, B-spline, Hermite and others) that traverse the given keyframes.

The animation is then projected by advancing the time factor and interpolating along the curve with a monotonously increasing parameter extracted from the animation time factor.

Interpolation of a uniform scale factor is the most simple one. A scale factor is a scalar and a spline curve is constructed from n (n being the number of keyframes the animator supplied for the animation) such scalars.

Translation is just a bit more complicated. Here every key frame is represented by a vector in R3 (translation by X, by Y and by Z) but since the 3 axes in R3 are translation-independent, they can be interpolated as three scalar curves and then be combined into the interpolated translation vector.

As for rotation - this is an entirely different story. The rotation along the axis in R3 is highly dependent. For example: a rotation of an object by 180° along the X axis, then by 180° along the Y axis and no rotation along the Z axis is equivalent to a rotation by 180° along the Z axis alone.

This is why the the order of axes in the rotation sequence is very important. But even if you maintain the right order of primitive rotation actions, an effect called Gimbal Lock creeps in and prevents the system from being truly axis independent.

The Gimbal lock effect is described in detail in the Image Synthesis course.

The first practical solution to this problem was offered by Ken Shoemake in an article titled "Animation Rotation with Quaternion Curves" published in SIGGRAPH 85’ (pages 245-254).

In this article he offered to use a 4D creature called a quaternion to interpolate along a curve on a unit size 4D ball (a group called S3). After this breakthrough, many variants of his solution were published and the most interesting of them was published by Myoung-Jun Kim, Myoung-Soo Kim and Sung Yong Shin in their article titled "A General Construction Scheme for Unit Quaternion Curves with Simple High Order Derivatives" published in SIGGRAPH 95’ (pages 369-376).

In this article they refined Shoemake’s method, fixed some of his mathematical errors and offered a complete set of mapping techniques from the ball in SO3 to R3 and vice-versa.

Our implementation

In this lab we chose to implement a complete solution for the animator.

The animator defines a set of key frames for the animated body. Each key frame holds the body’s uniform scale factor, translation, rotation and an associated animation time.

The animator can then choose from various animation parameters (animation start time, end time, frames per second etc.) and interpolation type (we offer Bezier and B-spline).

We added some code to the IRIT library that can extract transformation properties from a general transformation matrix.
This creates a vector of 7 scalars that corresponds to a general transformation matrix by storing rotation angles around the 3 axes, a scaling factor and transformation factors along the 3 axes.

Our system then creates a scalar spline curve for the scale factor, an R3 vector spline curve for the translation and a quaternion curve for the rotation.

The quaternions are created from the rotation matrices as part of the library code.

The curves are interpolated along the animation’s "in-between" frames and the result is a list of animation frames, each with its own set of scaling, translation and rotation values.

Our implementation is tightly integrated with IRIT.

Our tools read IRIT object date files, create IRIT animation curves and save them as animation objects in IRIT object data files.

A block diagram of the process would look like this:

The components

Our project is divided into 3 different components.
  1. The IRIT extensions

    this is a library that extends IRIT to support quaternions. It is made of three major parts:

  2. The Keyframes Builder

    this is a GUI tool for Win32 platforms (Windows 95, Windows NT 3.51 and 4.0) that the animator can use to interactively create animation key frames.

    With this tool, the animator can load any IRIT object, transform it in space and specify a list of key frames.

    When he’s done, he can specify animation parameters (start time, end time, frames per second, interpolation type etc.) and launch the interpolator tool.

    Refer to the Keyframes builder user's guide for instructions.

  3. The Interpol

    This is a sample implementation of the IRIT interpolation extensions.

    This tools accepts an ASCII key frames file (can be generated by the Keyframes Builder) and various animation parameters.

    It then creates interpolation spline curves, interpolates along the curves in the animation frames and saves the results as animation curve objects into an IRIT format data file.

    Refer to the Interpol user's guide for instructions.

Animation samples

We have included some samples of basic animations that were produced with our tools.
Those samples mainly demonstrate rotations of objects in space.
Go to samples page

Downloading the files

All the files are packed in the ZIP format.

Bibliography


The authors

Kesem Korakin
Moshe Zur
Eran Yariv