Quaternions and spatial rotation

From Wikipedia, the free encyclopedia

Unit quaternions provide a convenient mathematical notation for representing orientations and rotations of objects in three dimensions. Compared to Euler angles they are simpler to compose and avoid the problem of gimbal lock. Compared to rotation matrices they are more efficient and more numerically stable. Quaternions have found their way into applications in computer graphics, robotics, navigation, and orbital mechanics of satellites.^[1]

1 Quaternion rotation operations
2 Quaternion non-commutativity and rotations
3 Quaternions versus other representations of rotations
- 3.1 Performance comparisons with other rotation methods
4 Pairs of unit quaternions as rotations in 4D space
5 See also
6 References
7 External links and resources

[edit] Quaternion rotation operations

A very strict explanation of the properties used in this section is given by Altmann.^[2]

[edit] Visualizing the space of rotations

Unit quaternions represent in a very straightforward way the mathematical space of rotations in three dimensions. The correspondence between rotations and quaternions can be understood by first visualizing the space of rotations itself.

Any rotation in three dimensions is a rotation by some angle about some axis. When the angle is zero the axis does not matter, so rotation by zero degrees is a single point in the space of rotations (the identity rotation). For a tiny but nonzero angle, the set of possible rotations is like a small sphere surrounding the identity rotation, where each point on the sphere represents an axis pointing in a particular direction (compare the celestial sphere). Rotations through increasingly large angles are increasingly far from the identity rotation, and we can think of them as concentric spheres of increasing radius. Thus, near the identity rotation, the abstract space of rotations looks similar to ordinary three-dimensional space (which can also be seen as a central point surrounded by concentric spheres of every radius). However, as the rotation angle increases toward 360°, rotations about different axes stop diverging and become more similar to each other, becoming identical (and equal to the identity rotation) when the angle reaches 360°.

We can see similar behavior on the surface of a sphere. If we start at the north pole and draw straight lines (that is, lines of longitude) in many directions, they will diverge but eventually converge again at the south pole. Concentric circles of increasing radius drawn around the north pole (lines of latitude) will eventually collapse to a point at the south pole once the radius reaches the distance between the poles. If we think of different directions from the pole (that is, different longitudes) as different rotation axes, and different distances from the pole (that is, different latitudes) as different rotation angles, we have an analogy to the space of rotations. Since the sphere's surface is two dimensional while the space of rotations is three dimensional, we must actually model the space of rotations as a hypersphere; however, we can think of the ordinary sphere as a slice through the full hypersphere (just as a circle is a slice through a sphere). We can take the slice to represent, for example, just the rotations about axes in the xy plane. Note that the angle of rotation is twice the latitude difference from the north pole: points on the equator represent rotations of 180°, not 90°, and the south pole represents a rotation of 360°, not 180°.

The north pole and the south pole represent the same rotation, and in fact this is true of any two antipodal points: if one is a rotation by α around the axis v, the other is a rotation by 360° − α around the axis −v. In fact, then, the space of rotations is not the (hyper)sphere itself but the (hyper)sphere with antipodal points identified. But for many purposes we can think of rotations as points on the sphere, even though they are twofold redundant (a so-called double cover).

[edit] Parameterizing the space of rotations

We can parameterize the surface of a sphere with two coordinates, such as latitude and longitude. But latitude and longitude are ill-behaved (degenerate) at the north and south poles, though the poles are not intrinsically different from any other points on the sphere. It can be shown that no two-parameter coordinate system can avoid such degeneracy (the hairy ball theorem). We can avoid such problems by embedding the sphere in three-dimensional space and parameterizing it with three Cartesian coordinates (here w,x,y), placing the north pole at (w,x,y) = (1,0,0), the south pole at (w,x,y) = (−1,0,0), and the equator at w = 0, x² + y² = 1. Points on the sphere satisfy the constraint w² + x² + y² = 1, so we still have just two degrees of freedom though there are three coordinates. A point (w,x,y) on the sphere represents a rotation around the (x,y,0) axis by an angle $\alpha= 2 \cos^{-1} w = 2 \sin^{-1} \sqrt{x^2+y^2}$ .

In the same way the hyperspherical space of 3D rotations can be parameterized by three angles (Euler angles), but any such parameterization is degenerate at some points on the hypersphere, leading to the problem of gimbal lock. We can avoid this by using four Euclidean coordinates w,x,y,z, with w² + x² + y² + z² = 1. The point (w,x,y,z) represents a rotation around the (x,y,z) axis by an angle $\alpha = 2 \cos^{-1} w = 2 \sin^{-1} \sqrt{x^2+y^2+z^2}$ .

[edit] Quaternions briefly

The complex numbers can be defined by introducing an abstract symbol i which satisfies the usual rules of algebra and additionally the rule i² = −1. This is sufficient to reproduce all of the rules of complex number arithmetic: for example, $(a+b\mathbf{i})(c+d\mathbf{i}) = ac + ad\mathbf{i} + b\mathbf{i}c + b\mathbf{i}d\mathbf{i} = ac + ad\mathbf{i} + bc\mathbf{i} + bd\mathbf{i}^2 = (ac - bd) + (bc + ad) \mathbf{i}$ .

In the same way the quaternions can be defined by introducing abstract symbols i, j, k which satisfy the rules i² = j² = k² = ijk = −1 and the usual algebraic rules except the commutative law of multiplication (a familiar example of such a noncommutative algebra is matrix algebra). From this all of the rules of quaternion arithmetic follow: for example, one can show that $(a + b\mathbf{i} + c\mathbf{j} + d\mathbf{k}) (e + f\mathbf{i} + g\mathbf{j} + h\mathbf{k}) = (ae - bf - cg - dh) + (af + eb + ch - dg) \mathbf{i} + (ag + ce + df - bh) \mathbf{j} + (ah + de + bg - cf) \mathbf{k}$ .

The imaginary part $b\mathbf{i} + c\mathbf{j} + d\mathbf{k}$ of a quaternion behaves like a vector $(b, c, d) \in \mathbb{R}^3$ , and the real part a behaves like a scalar in $\mathbb{R}$ . When quaternions are used in geometry, it is more convenient to define them as a scalar plus a vector and use the modern language of vector cross and dot products (which were originally inspired by the quaternions). In place of the rules i² = j² = k² = ijk = −1 we have the vector multiplication rule $\mathbf{vw} = \mathbf{v} \times \mathbf{w} - \mathbf{v} \cdot \mathbf{w}$ . Vector multiplication is noncommutative (because of the cross product), while scalar-scalar and scalar-vector multiplications commute. From these rules it follows immediately that $(s + \mathbf{v}) (t + \mathbf{w}) = (st - \mathbf{v} \cdot \mathbf{w}) + (s\mathbf{w} + t\mathbf{v} + \mathbf{v} \times \mathbf{w})$ .

The (left and right) multiplicative inverse of a nonzero quaternion is $(s + \mathbf{v})^{-1} = \frac{s - \mathbf{v}}{s^2 + |\mathbf{v}|^2}$ , as can be verified by direct calculation.

[edit] Parametrizing the space of rotations with quaternions

Let (w,x,y,z) be the coordinates of a rotation as previously described. Define the quaternion

$q = w + x\mathbf{i} + y\mathbf{j} + z\mathbf{k} = w + (x,y,z) = \cos (\alpha/2) + \mathbf{u} \sin (\alpha/2)$

where u is a unit vector. Then it can be shown (see next section) that the quaternion product

$q \mathbf{v} q^{-1}$

yields the vector v rotated by an angle α around the u axis. The rotation is clockwise if our line of sight points in the direction u. This operation is known as conjugation by q.

It follows that quaternion multiplication is composition of rotations, for if p and q are quaternions representing rotations, then rotation (conjugation) by pq is

$p q \mathbf{v} (p q)^{-1} = p q \mathbf{v} q^{-1} p^{-1}$ ,

which is the same as rotating (conjugating) by q and then by p.

The quaternion inverse of a rotation is the opposite rotation, since $q^{-1} (q \mathbf{v} q^{-1}) q = \mathbf{v}$ . The square of a quaternion rotation is a rotation by twice the angle around the same axis. More generally qⁿ is a rotation by n times the angle around the same axis as q. This can be extended to arbitrary real n, allowing for smooth interpolation between spatial orientations; see Slerp.

[edit] Proof of the quaternion rotation identity

Let u be a unit vector (the rotation axis) and let $q = \cos \frac{\alpha}{2} + \mathbf{u} \sin \frac{\alpha}{2}$ . Our goal is to show that

$\mathbf{v}' = q \mathbf{v} q^{-1} = \left( \cos \frac{\alpha}{2} + \mathbf{u} \sin \frac{\alpha}{2} \right) \, \mathbf{v} \, \left( \cos \frac{\alpha}{2} - \mathbf{u} \sin \frac{\alpha}{2} \right)$

yields the vector v rotated by an angle α around the axis u. Expanding out, we have

$\begin{array}{lll} \mathbf{v}' &=& \mathbf{v} \cos^2 \frac{\alpha}{2} + (\mathbf{uv} - \mathbf{vu}) \sin \frac{\alpha}{2} \cos \frac{\alpha}{2} - \mathbf{uvu} \sin^2 \frac{\alpha}{2} \\ &=& \mathbf{v} \cos^2 \frac{\alpha}{2} + 2 (\mathbf{u} \times \mathbf{v}) \sin \frac{\alpha}{2} \cos \frac{\alpha}{2} - (\mathbf{v} (\mathbf{u} \cdot \mathbf{u}) - 2 \mathbf{u} (\mathbf{u} \cdot \mathbf{v})) \sin^2 \frac{\alpha}{2} \\ &=& \mathbf{v} (\cos^2 \frac{\alpha}{2} - \sin^2 \frac{\alpha}{2}) + (\mathbf{u} \times \mathbf{v}) (2 \sin \frac{\alpha}{2} \cos \frac{\alpha}{2}) + \mathbf{u} (\mathbf{u} \cdot \mathbf{v}) (2 \sin^2 \frac{\alpha}{2}) \\ &=& \mathbf{v} \cos \alpha + (\mathbf{u} \times \mathbf{v}) \sin \alpha + \mathbf{u} (\mathbf{u} \cdot \mathbf{v}) (1 - \cos \alpha) \\ &=& (\mathbf{v} - \mathbf{u} (\mathbf{u} \cdot \mathbf{v})) \cos \alpha + (\mathbf{u} \times \mathbf{v}) \sin \alpha + \mathbf{u} (\mathbf{u} \cdot \mathbf{v}) \\ &=& \mathbf{v}_{\bot} \cos \alpha + (\mathbf{u} \times \mathbf{v}_{\bot}) \sin \alpha + \mathbf{v}_{\|} \end{array}$

where $\mathbf{v}_{\bot}$ and $\mathbf{v}_{\|}$ are the components of v perpendicular and parallel to u respectively. This is the formula of a rotation by α around the u axis.

[edit] Example

Consider the rotation f around the axis u = i + j + k, with a rotation angle of 120°, or ^2π⁄₃ radians.

$\alpha = \frac{2 \pi}{3} = 120^\circ$

The length of u is √3, the half angle is ^π⁄₃ (60°) with cosine ½, (cos 60° = 0.5) and sine ^√3⁄₂, (sin 60° = 0.866...). We are therefore dealing with a conjugation by the unit quaternion

$z = \cos\frac{\alpha}{2} + \sin\frac{\alpha}{2}\,\hat\mathbf{u}$

$z = \cos 60^\circ + \sin 60^\circ\,\hat\mathbf{u}$

$z = \frac{1}{2} + \frac{\sqrt{3}}{2}\cdot\,\hat\mathbf{u}$

$z = \frac{1}{2} + \frac{\sqrt{3}}{2}\cdot \frac{(i+j+k)}{\sqrt{3}}$

$z = \frac{1 + i + j + k}{2}$ .

Concretely,

f(ai + bj + ck) = z (ai + bj + ck) z^-1 .

Note that z^-1 = 1/z, as z has unit modulus; here z^-1 = (1−i−j−k)/2. This can be simplified, using the ordinary rules for quaternion arithmetic, to

f(ai + bj + ck) = ci + aj + bk,

as expected: the rotation corresponds to keeping a cube held fixed at one point, and rotating it 120° about the long diagonal through the fixed point (observe how the three axes are permuted cyclically).

[edit] Quaternion non-commutativity and rotations

The multiplication of quaternions is non-commutative. Since this operation corresponds to a three dimensional rotation, this property can be easily demonstrated by showing that three dimensional rotations are not commutative in general. A simple exercise of applying two rotations to an asymmetrical object (e.g., a book) can explain it. First, rotate a book 90 degrees clockwise around the z axis. Next rotate it 180 degrees clockwise around the x axis. Then restore the original orientation, so that the book title is again readable, and apply those rotations in opposite order. This shows that, in general, the composition of two different rotations around two distinct spatial axes will not commute.

[edit] Quaternions versus other representations of rotations

The representation of a rotation as a quaternion (4 numbers) is more compact than the representation as an orthogonal matrix (9 numbers). Furthermore, for a given axis and angle, one can easily construct the corresponding quaternion, and conversely, for a given quaternion one can easily read off the axis and the angle. Both of these are much harder with matrices or Euler angles.

In computer games and other applications, one is often interested in “smooth rotations”, meaning that the scene should slowly rotate and not in a single step. This can be accomplished by choosing a curve such as the spherical linear interpolation in the quaternions, with one endpoint being the identity transformation 1 (or some other initial rotation) and the other being the intended final rotation. This is more problematic with other representations of rotations.

When composing several rotations on a computer, rounding errors necessarily accumulate. A quaternion that’s slightly off still represents a rotation after being normalised—a matrix that’s slightly off need not be orthogonal anymore and therefore is harder to convert back to a proper orthogonal matrix.

Quaternions also avoid a phenomenon called gimbal lock which can result when, for example in pitch/yaw/roll rotational systems, the pitch is rotated 90° up or down, so that yaw and roll then correspond to the same motion, and a degree of freedom of rotation is lost. In a gimbal-based aerospace inertial navigation system, for instance, this could have disastrous results if the aircraft is in a steep dive or ascent.

The orthogonal matrix corresponding to a rotation by the unit quaternion z = a + bi + cj + dk (with |z| = 1) is given by

$\begin{pmatrix} a^2+b^2-c^2-d^2&2bc-2ad &2ac+2bd \\ 2ad+2bc &a^2-b^2+c^2-d^2&2cd-2ab \\ 2bd-2ac &2ab+2cd &a^2-b^2-c^2+d^2\\ \end{pmatrix}$

Beware the vector convention: There are two conventions for rotation matrices: one assumes row vectors on the left; the other assumes column vectors on the right; the two conventions generate matrices that are the transpose of each other. In general, a matrix for vertex transpose is ambiguous unless the vector convention is also mentioned. Historically, the column-on-the-right convention comes from math and classical mechanics, whereas row-vector-on-the-left comes from computer graphics, where typesetting row vectors was easier back in the early days.

(Compare the equivalent general formula for a 3 × 3 rotation matrix in terms of the axis and the angle.)

Note that quatenions, like any other rotation or linear transform, are not "handed" (as in left-handed vs right-handed). Handedness of a coordinate system comes from the interpretation of the numbers in physical space. No matter what the handedness convention, rotating the X vector 90 degrees around the Z vector will yield the Y vector -- the math and numbers are the same.

See also: Charts on SO(3), Euler angles, axis angle

[edit] Performance comparisons with other rotation methods

This section discusses the performance implications of using quaternions versus other methods (axis/angle or rotation matrices) to perform rotations in 3D. A brief summary:

Performance comparison of rotation chaining operations
Method	Storage	# multiplies	# add/subtracts	total operations
Rotation matrix	9	27	18	45
Quaternions	4	16	12	28

Performance comparison of various rotation operations
Method	Storage	# multiplies	# add/subtracts	# sin/cos	total operations
Rotation matrix	9	9	6	0	15
Quaternions	4	21	18	0	39
Angle/axis	4*	23	16	2	41

* Note: angle-axis can be stored as 3 elements by multiplying the unit rotation axis by the rotation angle; however, before using it the unit axis and angle must be recovered by normalizing, costing additional math operations.

There are three basic approaches to rotating a vector v:

Compute the matrix-vector product of a 3x3 rotation matrix R and the original 3x1 vector v, giving $v_{new} = \mathbf{R}v$ . This requires 3*(3 multiplications + 2 additions) = 9 multiplications and 6 additions, the most efficient method for rotating a vector.
Use the quaternion rotation formula derived above of $v_{new}= z \mathbf{v} z^{-1}$ . Computing this result is equivalent to transforming the quaternion to a rotation matrix R using the formula above then multiplying with a vector. Performing some common subexpression elimination yields an algorithm that costs 21 multiplies and 18 adds. As a second approach, the quaternion could first be converted to its equivalent angle/axis representation then the angle/axis representation used to rotate the vector. However, this is both less efficient and less numerically stable when the quaternion nears the no rotation point.
Use the angle-axis formula to convert an angle/axis to a rotation matrix R then multiplying with a vector. Converting the angle/axis to R using common subexpression elimination costs 14 multiplies, 2 function calls (sin, cos), and 10 add/subtracts; from item 1, rotating using R adds an additional 9 multiplications and 6 additions for a total of 23 multiplies, 16 add/subtracts, and 2 function calls (sin, cos).

Pseudo-code for rotating using a quaternion: given a quaternion z = a + bi + cj + dk (with |z| = 1) and a vector v with elements v1, v2, and v3, the following code performs a rotation. Note the use of temporary variables txx. Also note one optimization of the diagonal entries of the R matrix: since $a 2 + b 2 + c 2 + d 2 = 1$ , rewrite the top-left entry as $a 2 + b 2 + c 2 + d 2 - 2 c 2 - 2 d 2 = 1 - 2 c 2 - 2 d 2$ ; the other two diagonal entries can be similarly rewritten.

t2 =   a*b
t3 =   a*c
t4 =   a*d
t5 =  -b*b
t6 =   b*c
t7 =   b*d
t8 =  -c*c
t9 =   c*d
t10 = -d*d
v1new = 2*( (t8 + t10)*v1 + (t6 -  t4)*v2 + (t3 + t7)*v3 ) + v1
v2new = 2*( (t4 +  t6)*v1 + (t5 + t10)*v2 + (t9 - t2)*v3 ) + v2
v3new = 2*( (t7 -  t3)*v1 + (t2 +  t9)*v2 + (t5 + t8)*v3 ) + v3

Pseudo-code for creating an angle/axis matrix where the unit axis is (v1, v2, v3) and the angle is θ:

t1 =  cos(theta)
t2 =  1 - t1
t3 =  v1*v1
t6 =  t2*v1
t7 =  t6*v2
t8 =  sin(theta)
t9 =  t8*v3
t11 = t6*v3
t12 = t8*v2
t15 = v2*v2
t19 = t2*v2*v3
t20 = t8*v1
t24 = v3*v3
R[1, 1] = t1 + t2*t3
R[1, 2] = t7 - t9
R[1, 3] = t11 + t12
R[2, 1] = t7 + t9
R[2, 2] = t1 + t2*t15
R[2, 3] = t19 - t20
R[3, 1] = t11 - t12
R[3, 2] = t19 + t20
R[3, 3] = t1 + t2*t24

[edit] Pairs of unit quaternions as rotations in 4D space

A pair of unit quaternions z_l and z_r can represent any rotation in 4D space. Given a four dimensional vector v, and pretending that it is a quaternion, we can rotate the vector v like this:

$f(v)=z_lvz_r= \begin{pmatrix} a_l&-b_l&-c_l&-d_l\\ b_l&a_l&-d_l&c_l\\ c_l&d_l&a_l&-b_l\\ d_l&-c_l&b_l&a_l \end{pmatrix}\begin{pmatrix} a_r&-b_r&-c_r&-d_r\\ b_r&a_r&d_r&-c_r\\ c_r&-d_r&a_r&b_r\\ d_r&c_r&-b_r&a_r \end{pmatrix}\begin{pmatrix} w\\x\\y\\z \end{pmatrix}.$

It is straightforward to check that for each matrix M M^T = I, that is, that each matrix (and hence both matrices together) represents a rotation. Note that since (z^l v) z^r = z^l (v z^r), the two matrices must commute. Therefore, there are two commuting subgroups of the set of four dimensional rotations. Arbitrary four dimensional rotations have 6 degrees of freedom, each matrix represents 3 of those 6 degrees of freedom.

Since an infinitesimal four-dimensional rotation can be represented by a pair of quaternions (as follows), all (non-infinitesimal) four-dimensional rotations can also be represented.

$z_lvz_r=\begin{pmatrix} 1 &-dt_{ab}&-dt_{ac}&-dt_{ad}\\ dt_{ab}&1 &-dt_{bc}&-dt_{bd}\\ dt_{ac}& dt_{bc}&1 &-dt_{cd}\\ dt_{ad}& dt_{bd}& dt_{cd}&1 \end{pmatrix}\begin{pmatrix} w\\ x\\ y\\ z \end{pmatrix}$

$z_l= \left(1+{dt_{ab}+dt_{cd}\over 2}i+{dt_{ac}-dt_{bd}\over 2}j+{dt_{ad}+dt_{bc}\over 2}k\right)$

$z_r= \left(1+{dt_{ab}-dt_{cd}\over 2}i+{dt_{ac}+dt_{bd}\over 2}j+{dt_{ad}-dt_{bc}\over 2}k\right)$

[edit] See also

Slerp — spherical linear interpolation
conversion between quaternions and Euler angles
rotation group
coordinate rotations
Clifford algebras
spinor group
covering map
3-sphere
SO(4)

[edit] References

^ Quaternions and rotation Sequences: a Primer with Applications to Orbits, Aerospace, and Virtual Reality. Kuipers, Jack B., Princeton University Press copyright 1999.
^ Rotations, Quaternions, and Double Groups. Altmann, Simon L., Dover Publications, 1986.

[edit] External links and resources

Categories: Quaternions | Rotational symmetry | 3D computer graphics