Transformations and the Graphics Pipeline(Basic Computer Graphics) Part 6

Quaternions and In-betweening

This short section describes another aspect of how transformations get used in animation. In particular, we discuss a nice application of quaternions. Unit quaternions are a more efficient way to represent a rotation of R3 than the standard matrix representation of SO(3).Other references for the topic of this section are [WatW92], [Hogg92], and [Shoe93].

We recall some basic facts about the correspondence between rotations about the origin in R3 and unit quaternions. First of all, the quaternion algebra H is just R4 endowed with the quaternion product. The metric on H is the same as that on R4. The standard basis vectorstmpc646795_thumb[2][2][2][2][2]are now denoted by 1, i, j, k, respectively. The subspace generated by i, j, and k is identified with R3 by mapping the quaternion tmpc646796_thumb[2][2][2][2][2]and vice versa. The rotation R of R3 through angle Θ about the directed line through the origin with unit direction vector n is mapped to the quaternion q defined by

tmpc646801_thumb[2][2][2][2][2]

Conversely, lettmpc646802_thumb[2][2][2][2][2]be    a    unit    quaterniontmpc646803_thumb[2][2][2][2][2]and express q in the form

tmpc646806_thumb[2][2][2][2][2]

where n is a unit vector of R3. If Mq is the matrix defined by

tmpc646807_thumb[2][2][2][2][2]

 

thentmpc646809_thumb[2][2][2][2][2]and    the map of R3 that sendstmpc646810_thumb[2][2][2][2][2]is    a    rotationtmpc646811_thumb[2][2][2][2][2]about    the line through the origin with direction vector n through the angle 2Θ.

 

Interpolating between two quaternions.

Figure 4.26. Interpolating between two quaternions.

This mapping

tmpc646815_thumb[2][2][2][2][2]

has the property thattmpc646816_thumb[2][2][2][2][2]

Now, suppose an object is moved by a one-parameter family of matrices M(s) e SO(3). Assume that we have only specified this family at a fixed set of values si. How can we interpolate between these values? In animation such an interpolation is called in-betweening. A simple interpolation of the form

tmpc646818_thumb[2][2][2][2][2]

would not work because the interpolants would not again be elements of SO(3). One could try to use Euler angles, but there are problems with this also. See [Shoe85]. A better way is to translate our maps into quaternions and to look for a one-parameter family of unit quaternions q(s) that interpolates between two quaternions a and b. However, a simple linear interpolation followed by a normalization to get unit quaternions does not work well either for the same reason that one does not get a uniform subdivision of an arc of a circle by centrally projecting a uniform subdivision of the chord connecting its endpoints. What would happen in the animation is that the object would move faster in the middle of the interpolation. A better solution is to subdivide the arc of the great circle in S3 connecting a and b. See Figure 4.26.

Lemma. Let a and b be two unit quaternions that make an angle oftmpc646819_thumb[2][2][2][2][2] with each other, that is,tmpc646820_thumb[2][2][2][2][2]Then the unit quaternion c(t) that

lies in the plane spanned by a and b and which makes an angletmpc646821_thumb[2][2][2][2][2]withtmpc646822_thumb[2][2][2][2][2]is defined by the equation

tmpc646827_thumb[2][2][2][2][2]

Proof. By hypothesis,

tmpc646828_thumb[2][2][2][2][2]

for some real numbers r and s. Taking the dot product of both sides of this equation with a and b leads to equations

tmpc646829_thumb[2][2][2][2][2]

and

tmpc646830_thumb[2][2][2][2][2]

Solving equations (4.29) and (4.30) for r and s and using some standard trigonometric identities leads to the stated result.

Example. Let ^tmpc646831_thumb[2][2][2][2][2]be    the    positively    directed    x- and y-axis, respectively.

Let R0 and R1 be the rotations about the directed linestmpc646832_thumb[2][2][2][2][2]respectively, through

angletmpc646833_thumb[2][2][2][2][2]be the matrices that represent them.Iftmpc646834_thumb[2][2][2][2][2]is the 1-parameter family of in-betweening matrices in SO(3) betweentmpc646835_thumb[2][2][2][2][2]then what istmpc646836_thumb[2][2][2][2][2]

Solution. The unit direction vectors fortmpc646837_thumb[2][2][2][2][2] respectively. Therefore, by equation (4.25)

tmpc646845_thumb[2][2][2][2][2]

and

tmpc646846_thumb[2][2][2][2][2]

are the unit quaternions corresponding to rotationtmpc646847_thumb[2][2][2][2][2]The angle Θ  between q0 and q1 is defined by

tmpc646849_thumb[2][2][2][2][2]

It follows that

tmpc646850_thumb[2][2][2][2][2]

Using equation (4.28), let

tmpc646851_thumb[2][2][2][2][2]

Finally, equation (4.27) implies that

tmpc646852_thumb[2][2][2][2][2]

We can also see from the expression fortmpc646853_thumb[2][2][2][2][2]and equation (4.26) thattmpc646854_thumb[2][2][2][2][2]defines a rotation about the directed line through the origin with direction vector (1,1,0) and angletmpc646855_thumb[2][2][2][2][2]where

tmpc646859_thumb[2][2][2][2][2]

It is clear that the quaternions c(t) defined by Lemma 4.14.1 do indeed lie on a great circles in the unit sphere of the quaternions. We have solved the uniform spacing problem, but unfortunately this is not the end of the story as far as animation is concerned. Two points on a circle divide the circle into two arcs. If the points are not antipodal points, then one typically is interested in the smaller arc. In our situation we cannot simply always take the smaller arc without further consideration because we are representing rotations by quaternions, and if q is a unit quaternion, both q and -q correspond to the same rotation in SO(3). The solution suggested in [WatW92] is, given representations a and b for two rotations, to choose between a, b and a, -b. One compares the distance between a and b, la – bl, to the distance between a and -b, la + bl. If the former is smaller use a, b otherwise use a, -b.

After getting our uniformly spaced quaternions c(ti) along the arc, if we were to do a linear interpolation between them, then the motion may look jerky. It is better to smooth things out by using Bezier curves or, more generally, splines, but this is somewhat more complicated in quaternion space than it was in Rn. See [BCGH92], [WatW92], [Hogg92], or [Shoe93] for what needs to be done.

Conclusions

Transformations were at the center of all the discussions in this topic. We would like to emphasize one last time that when it comes to representing and defining affine transformations one should do that via frames if at all possible. Frames are orthonormal basis and these are easy to define. Without them, geometric modeling for n-dimensional objects would become very complicated when n is larger than 2. Once one has a frame it can be interpreted as a transformation, a coordinate system, or as defining a change of coordinates.

The main role of homogeneous coordinates and projective space is as the natural setting for projective transformations. The mathematics becomes much easier. A practical application is that one can replace all transformations, including translations, with matrices in uniform way. We described some of the main perspective and parallel projections.

The discussion in this topic emphasized a mathematical view of transformations. Let us add a few comments about efficiency because there are times when efficiency is more important than clarity. Transformations get used a lot in geometric modeling and generating them in a systematic way, which usually involves representing them as a composite of primitive ones, involves more arithmetic operations than necessary. The papers [Gold90] and [Mill99] describe a more efficient approach. For example, suppose we express an arbitrary affine transformation T of R3 in the form

tmpc646860_thumb[2][2][2][2][2]

where M is a 3 x 3 matrix and v is a fixed translation vector. If T is a rotation through an angletmpc646861_thumb[2][2][2][2][2]about a line L through a point q with direction vector w, then it is shown that

tmpc646863_thumb[2][2][2][2][2]

where I is the 3 x 3 identity matrix,

tmpc646864_thumb[2][2][2][2][2]

and

tmpc646865_thumb[2][2][2][2][2]

With this representation, an optimized computation takes 15 multiplications and 10 additions to compute M and 9 multiplications and 9 additions to compute v. The number of operations to compute the matrix M and vector v with the “composite-of-transformations” approach would be much greater. See [Gold90] for efficient formulas for other transformations.

Finally, one topic not discussed much in this topic (other than in the documentation for the GM and SPACE program) is the user interface of a modeling program, even though this takes up a large percentage of the time needed to develop such a program in general. Certain aspects of such a discussion, if we had the space or time, would probably be most appropriate in the context of the topic of this topic. There are lots of interesting issues here as to how one can make it easier for the user to define the desired view of the world. How to best look at the world is often a major concern to a user. How does a user specify a view? How does one control panning and zooming? How does one specify a user’s or the camera’s arbitrary movement through the world? In a three-dimensional world this is not always easy if all one has is a keyboard and a mouse.

Next post:

Previous post: