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, Bspline, 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 R^{3} (translation by X, by Y and by Z)
but since the 3 axes in R^{3} are
translationindependent, 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 R^{3} 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 245254).
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 MyoungJun Kim, MyoungSoo
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 369376).
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 R^{3} and viceversa.
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 Bspline).
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 R^{3}
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 "inbetween" 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.
 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 viceversa.
 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 R^{3} or
quaternions)
and the interpolation type
(Bezier or Bspline).
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 breakdown of a
general transformation matrix into a set of
7 primitive operations:

Rotation by X

Rotation by Y

Rotation by Z

Scaling

Translation by X

Translation by Y

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.
 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.

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. 245254.

MyoungJun Kim, MyoungSoo Kim, and Sung Yong Shin,
A General Construction Scheme for Unit Quaternions
Curves with Simple High Order Derivatives
, SIGGRAPH '95, pp. 369376.

Bert Juttler,
Visualization of Moving Objects Using Dual
Quaternion Curves
, Computer & Graphics, Vol. 18, No. 3, pp. 315326, '94.

MyoungJun Kim, MyoungSoo Kim,
A C^{2}continuous Bspline Quaternion Curve
Interpolating a Given Sequence of Solid Orientations
, In proc. of Computer Animation '95, pp. 7281.

MyoungJun Kim, MyoungSoo 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. 4357, '96.

MyoungSoo Kim and KeeWon Nam,
Hermite Interpolation of Solid Orientations
with Circular Blending Quaternion Curves
,The journal of visualization and computer animation,
Vol. 7, pp. 95110, '96.

Ken Shoemake,
Graphics Gems
,edited by Paul S. Heckbert, Academic Press, pp. 175191, '94.

Alan Watt and Mark Watt,
Advanced Animation and Rendering Techniques 
Theory and Practice
,AddisonWesley press, pp. 345368, '92.

MyoungSoo Kim and KeeWon Nam,
Interpolating Solid Orientations with
Circular Blending Quaternion Curves
,ComputerAided Design,
Vol. 27, No. 5, pp. 385398, '95.

Elaine Cohen and Richard F. Riesenfeld,
Computer Aided Geometric Design  236716 (in preparation)
,chapter 6.4.2, '89.
The authors
Kesem Korakin
Moshe Zur
Eran Yariv