**Listing 2: Quaternion-to-matrix conversion.** *([07.30.02] Editor's Note: the following QuatToMatrix function originally was published with a bug -- it reversed the row/column ordering. This is the correct version. Thanks to John Ratcliff and Eric Haines for pointing this out.)*

QuatToMatrix(QUAT * quat, float m[4][4]){

float wx, wy, wz, xx, yy, yz, xy, xz, zz, x2, y2, z2;

// calculate coefficients

x2 = quat->x + quat->x; y2 = quat->y + quat->y;

z2 = quat->z + quat->z;

xx = quat->x * x2; xy = quat->x * y2; xz = quat->x * z2;

yy = quat->y * y2; yz = quat->y * z2; zz = quat->z * z2;

wx = quat->w * x2; wy = quat->w * y2; wz = quat->w * z2;

m[0][0] = 1.0 - (yy + zz); m[1][0] = xy - wz;

m[2][0] = xz + wy; m[3][0] = 0.0;

m[0][1] = xy + wz; m[1][1] = 1.0 - (xx + zz);

m[2][1] = yz - wx; m[3][1] = 0.0;

m[0][2] = xz - wy; m[1][2] = yz + wx;

m[2][2] = 1.0 - (xx + yy); m[3][2] = 0.0;

m[0][3] = 0; m[1][3] = 0;

m[2][3] = 0; m[3][3] = 1;

}

This composition involves 27 multiplications and 18 additions, assuming 3x3 matrices. On the other hand, a quaternion composition can be represented as

q = q2q1 (rotation q1 followed by a rotation q2)

*(Eq. 8) *

As you can see, the quaternion method is analogous to the matrix composition. However, the quaternion method requires only eight multiplications and four divides (Listing 4), so compositing quaternions is computationally cheap compared to matrix composition. Savings such as this are especially important when working with hierarchical object representations and inverse kinematics.

Now that you have an efficient multiplication routine, see how can you interpolate between two quaternion rotations along the shortest arc. Spherical Linear intERPolation (SLERP) achieves this and can be written as

(Eq. 9)

where pq = cos(q) and parameter t goes from 0 to 1. The implementation of this equation is presented in Listing 5. If two orientations are too close, you can use linear interpolation to avoid any divisions by zero.

Figure 3. Quaternion rotations.

**Listing 3: Euler-to-quaternion conversion.**

EulerToQuat(float roll, float pitch, float yaw, QUAT * quat) { float cr, cp, cy, sr, sp, sy, cpcy, spsy; // calculate trig identities cr = cos(roll/2); cp = cos(pitch/2); cy = cos(yaw/2); sr = sin(roll/2); sp = sin(pitch/2); sy = sin(yaw/2); cpcy = cp * cy; spsy = sp * sy; quat->w = cr * cpcy + sr * spsy; quat->x = sr * cpcy - cr * spsy; quat->y = cr * sp * cy + sr * cp * sy; quat->z = cr * cp * sy - sr * sp * cy; }

The basic SLERP rotation algorithm is shown in Listing 6. Note that you have to be careful that your quaternion represents an absolute and not a relative rotation. You can think of a relative rotation as a rotation from the previous (intermediate) orientation and an absolute rotation as the rotation from the initial orientation. This becomes clearer if you think of the q2 quaternion orientation in Figure 3 as a relative rotation, since it moved with respect to the q1 orientation. To get an absolute rotation of a given quaternion, you can just multiply the current relative orientation by a previous absolute one. The initial orientation of an object can be represented as a multiplication identity [1, (0, 0, 0)]. This means that the first orientation is always an absolute one, because

q = qidentity q

*(Eq. 10) *

**Listing 4: Efficient quaternion multiplication. **

QuatMul(QUAT *q1, QUAT *q2, QUAT *res){ float A, B, C, D, E, F, G, H; A = (q1->w + q1->x)*(q2->w + q2->x); B = (q1->z - q1->y)*(q2->y - q2->z); C = (q1->w - q1->x)*(q2->y + q2->z); D = (q1->y + q1->z)*(q2->w - q2->x); E = (q1->x + q1->z)*(q2->x + q2->y); F = (q1->x - q1->z)*(q2->x - q2->y); G = (q1->w + q1->y)*(q2->w - q2->z); H = (q1->w - q1->y)*(q2->w + q2->z); res->w = B + (-E - F + G + H) /2; res->x = A - (E + F + G + H)/2; res->y = C + (E - F + G - H)/2; res->z = D + (E - F - G + H)/2; }

As I stated earlier, a practical use for quaternions involves camera rotations in third-person-perspective games. Ever since I saw the camera implementation in TOMB RAIDER, I've wanted to implement something similar. So let's implement a third-person camera (Figure 4).

To start off, let's create a camera that is always positioned above the head of our character and that points at a spot that is always slightly above the character's head. The camera is also positioned d units behind our main character. We can also implement it so that we can vary the roll (angle q in Figure 4) by rotating around the x axis.

As soon as a player changes the orientation of the character, you rotate the character instantly and use SLERP to reorient the camera behind the character (Figure 5). This has the dual benefit of providing smooth camera rotations and making players feel as though the game responded instantly to their input.

Figure 4. Third-person camera.

Figure 5. Camera from top.

You can set the camera's center of rotation (pivot point) as the center of the object it is tracking. This allows you to piggyback on the calculations that the game already makes when the character moves within the game world.

Note that I do not recommend using quaternion interpolation for first-person action games since these games typically require instant response to player actions, and SLERP does take time.

However, we can use it for some special scenes. For instance, assume that you're writing a tank simulation. Every tank has a scope or similar targeting mechanism, and you'd like to simulate it as realistically as possible. The scoping mechanism and the tank's barrel are controlled by a series of motors that players control. Depending on the zoom power of the scope and the distance to a target object, even a small movement of a motor could cause a large change in the viewing angle, resulting in a series of huge, seemingly disconnected jumps between individual frames. To eliminate this unwanted effect, you could interpolate the orientation according to the zoom and distance of object. This type of interpolation between two positions over several frames helps dampen the rapid movement and keeps players from becoming disoriented.

Another useful application of quaternions is for prerecorded (but not prerendered) animations. Instead of recording camera movements by playing the game (as many games do today), you could prerecord camera movements and rotations using a commercial package such as Softimage 3D or 3D Studio MAX. Then, using an SDK, export all of the keyframed camera/object quaternion rotations. This would save both space and rendering time. Then you could just play the keyframed camera motions whenever the script calls for cinematic scenes.

Listing 5: SLERP implementation.

QuatSlerp(QUAT * from, QUAT * to, float t, QUAT * res) { float to1[4]; double omega, cosom, sinom, scale0, scale1; // calc cosine cosom = from->x * to->x + from->y * to->y + from->z * to->z + from->w * to->w; // adjust signs (if necessary) if ( cosom <0.0 ){ cosom = -cosom; to1[0] = - to->x; to1[1] = - to->y; to1[2] = - to->z; to1[3] = - to->w; } else { to1[0] = to->x; to1[1] = to->y; to1[2] = to->z; to1[3] = to->w; } // calculate coefficients if ( (1.0 - cosom) > DELTA ) { // standard case (slerp) omega = acos(cosom); sinom = sin(omega); scale0 = sin((1.0 - t) * omega) / sinom; scale1 = sin(t * omega) / sinom; } else { // "from" and "to" quaternions are very close // ... so we can do a linear interpolation scale0 = 1.0 - t; scale1 = t; } // calculate final values res->x = scale0 * from->x + scale1 * to1[0]; res->y = scale0 * from->y + scale1 * to1[1]; res->z = scale0 * from->z + scale1 * to1[2]; res->w = scale0 * from->w + scale1 * to1[3]; }

After reading Chris Hecker's columns on physics last year, I wanted to add angular velocity to a game engine on which I was working. Chris dealt mainly with matrix math, and because I wanted to eliminate quaternion-to-matrix and matrix-to-quaternion conversions (since our game engine is based on quaternion math), I did some research and found out that it is easy to add angular velocity (represented as a vector) to a quaternion orientation. The solution (Eq. 11) can be represented as a differential equation.

*(Eq. 11) *

where quat(angular) is a quaternion with a zero scalar part (that is, w = 0) and a vector part equal to the angular velocity vector. Q is our original quaternion orientation.

To integrate the above equation (Q + dQ/dt), I recommend using the Runge-Kutta

order four method. If you are using matrices, the Runge-Kutta order five method achieves better results within a game. (The Runge-Kutta method is a way of integrating differential equations. A complete description of the method can be found in any elementary numerical algorithm book, such as Numerical Recipes in C. It has a complete section devoted to numerical, differential integration.) For a complete derivation of angular velocity

integration, consult Dave Baraff's SIGGRAPH tutorials.

Quaternions can be a very efficient and extremely useful method of storing and performing rotations, and they offer many advantages over other methods. Unfortunately, they are also impossible to visualize and completely unintuitive. However, if you use quaternions to represent rotations internally, and use some other method (for example, angle-axis or Euler angles) as an immediate representation, you won't have to visualize them.

**Nick Bobick is a game developer at Caged Entertainment Inc. and he is currently working on a cool 3D game. He can be contacted at [email protected]. The author would like to thank Ken Shoemake for his research and publications. Without him, this article would not have been possible. **