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 vectorsare now denoted by 1, i, j, k, respectively. The subspace generated by i, j, and k is identified with R3 by mapping the quaternion 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

Conversely, letbe    a    unit    quaternionand express q in the form

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

 

thenand    the map of R3 that sendsis    a    rotationabout    the line through the origin with direction vector n through the angle 2Θ.

 

Figure 4.26. Interpolating between two quaternions.

This mapping

has the property that

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

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 of with each other, that is,Then the unit quaternion c(t) that

lies in the plane spanned by a and b and which makes an anglewithis defined by the equation

Proof. By hypothesis,

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

and

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

Example. Let ^be    the    positively    directed    x- and y-axis, respectively.

Let R0 and R1 be the rotations about the directed linesrespectively, through

anglebe the matrices that represent them.Ifis the 1-parameter family of in-betweening matrices in SO(3) betweenthen what is

Solution. The unit direction vectors for respectively. Therefore, by equation (4.25)

and

are the unit quaternions corresponding to rotationThe angle Θ  between q0 and q1 is defined by

It follows that

Using equation (4.28), let

Finally, equation (4.27) implies that

We can also see from the expression forand equation (4.26) thatdefines a rotation about the directed line through the origin with direction vector (1,1,0) and anglewhere

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

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

where I is the 3 x 3 identity matrix,

and

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.