# 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:
• The quaternion primitive operations:
here we implemented the quaternion structure, the addition and multiplication of quaternions, the exponent and logarithm of quaternions, a function that calculates a quaternion to the power of a real number and the transformation between a quaternion and a rotation matrix and vice-versa.

• The interpolations:
here we implemented a complete set of interpolators (both scalar and quaternion based).

An interpolant accepts a list of increasing time factors, a list of key points (scalars, vectors in R3 or quaternions) and the interpolation type (Bezier or B-spline).

Then the interpolant can be used to interpolate an animation parameter along the curve at a given animation time.

The scalar interpolants are based upon IRIT cagd library.

• The matrix to transformation operators:
here we implemented the break-down of a general transformation matrix into a set of 7 primitive operations:
1. Rotation by X
2. Rotation by Y
3. Rotation by Z
4. Scaling
5. Translation by X
6. Translation by Y
7. Translation by Z
The primitive operations are performed in that order.

This set of operations is a compact representation of a general 4x4 transformation matrix.

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

• Ken Shoemake, Animating Rotations with Quaternion Curves , SIGGRAPH '85, pp. 245-254.
• Myoung-Jun Kim, Myoung-Soo Kim, and Sung Yong Shin, A General Construction Scheme for Unit Quaternions Curves with Simple High Order Derivatives , SIGGRAPH '95, pp. 369-376.
• Bert Juttler, Visualization of Moving Objects Using Dual Quaternion Curves , Computer & Graphics, Vol. 18, No. 3, pp. 315-326, '94.
• Myoung-Jun Kim, Myoung-Soo Kim, A C2-continuous B-spline Quaternion Curve Interpolating a Given Sequence of Solid Orientations , In proc. of Computer Animation '95, pp. 72-81.
• Myoung-Jun Kim, Myoung-Soo Kim, and Sung Yong Shin, A Compact Differential Formula for the First Derivative of a Unit Quaternion Curve ,The journal of visualization and computer animation, Vol. 7, pp. 43-57, '96.
• Myoung-Soo Kim and Kee-Won Nam, Hermite Interpolation of Solid Orientations with Circular Blending Quaternion Curves ,The journal of visualization and computer animation, Vol. 7, pp. 95-110, '96.
• Ken Shoemake, Graphics Gems ,edited by Paul S. Heckbert, Academic Press, pp. 175-191, '94.
• Alan Watt and Mark Watt, Advanced Animation and Rendering Techniques - Theory and Practice ,Addison-Wesley press, pp. 345-368, '92.
• Myoung-Soo Kim and Kee-Won Nam, Interpolating Solid Orientations with Circular Blending Quaternion Curves ,Computer-Aided Design, Vol. 27, No. 5, pp. 385-398, '95.
• Elaine Cohen and Richard F. Riesenfeld, Computer Aided Geometric Design - 236716 (in preparation) ,chapter 6.4.2, '89.

Kesem Korakin
Moshe Zur
Eran Yariv