Quaternion

From CGAFaq

Jump to: navigation, search

Originally titled “What’s the big deal with quaternions?” This could mean “Why do they evoke such heated debate?” or “What are their virtues?”

The heat of debate is hard to explain, but it’s been happening for many decades. When Gibbs first deprecated the quaternion product and split it into a cross product and a dot product, one outraged Victorian called the result a “hermaphrodite monster” — and that before the Internet’s flame wars. Generally, the quaternion advocates seem to feel the opponents are lazy or thick-headed, and that deeper understanding of quaternions would lead to deeper appreciation. The opponents don’t appreciate that attitude, and seem to feel the advocates are snooty or sheep, and that matrices and such are less abstract and do just fine. (Advocates of Clifford algebra would claim that both sides are mired in the past.) Passion aside, quaternions have appropriate uses, as do their alternatives.

Someone new to the debate first needs to know what quaternions are, and what they’re supposed to be good for. A quaternion is a quadruple of numbers, used to represent 3D rotations.

q = [x,y,z,w]
= [(x,y,z),w]
= [v,w]

The norm of a quaternion, N(q), is conventionally the sum of the squares of the four components. Some writers confuse this with the magnitude, which is the square root of the norm. Another common misconception is that only quaternions of unit norm can be used, those with the sum of the four squares equal to 1, but that is wrong (though they are preferred).

[u sin θ, cos θ] rotates by angle 2θ around unit vector u.

Popular non-quaternion options are 3×3 special orthogonal matrices (9 numbers with constraints), Euler angles (3 numbers), axis-angle (4 numbers), and angular velocity vectors (3 numbers). None of these options actually are rotations, which are physical; they represent rotations. The distinction is important because, for example, it is common to use an axis-angle with an angle greater than 360° to tell an animation system to spin an object more than a full turn, something a matrix cannot say. In mathematics, the usual meaning of a rotation would not allow the multiple spin version, which can lead to confusing debates.

q and −q represent the same rotation

Two rotations, the physical things, can be applied one after the other. Assuming the two rotation axes have a least one point in common, the result will be another rotation. Some rotation representations handle this gracefully, some don’t. For quaternions and matrices, forms of multiplication are defined such that the product gives the desired result. For Euler angles especially there is no simple computation.

q = q2 q1
= [v2, w2][v1, w1]
= [v2×v1 + w2 v1 + w1 v2, w2 w1 − v2·v1]

Every rotation has a reverse rotation, such that the combination of the two leaves an object as it was. (Rotations are an algebraic group.) Euler angles make reversals difficult to compute. Other representations, including quaternions, make them simple.

reverse([v,w]) = [v,−w]
q−1 = [−v,w] / (v·v + w2)

Two physical rotations are also more or less similar. Unit quaternions do a particularly good job of representing similar rotations with similar numbers.

similar(q1,q2) = |q1·q2|
= |x1 x2 + y1 y2 + z1 z2 + w1 w2|

Points in space, the physical things, are normally represented as 3 or 4 numbers. The effect of a rotation on a collection of points can be computed from the representation of the rotation, and here matrices seem fastest, using three dot products. Using their own product twice, quaternions are a bit less efficient. (They are usually converted to matrices at the last minute.)

p2 = q p1 q−1

Although a modest amount of extra computation is required to convert a quaternion to a matrix if it may have non-unit norm, the work tends to pay off in making the code more robust. Either way, the conversion requires only arithmetic, not special functions like sine and cosine or square root.

Nq ← x2 + y2 + z2 + w2
s ← if Nq > 0.0 then 2.0/Nq else 0.0
xs ← x ∗ s ys ← y ∗ s zs ← z ∗ s
wxs ← w ∗ xs wys ← w ∗ ys wzs ← w ∗ zs
xxs ← x ∗ xs xys ← x ∗ ys xzs ← x ∗ zs
yys ← y ∗ ys yzs ← y ∗ zs zzs ← z ∗ zs
return
[ 1.0−(yys+zzs) xys−wzs xzs+wys ]
[ xys+wzs 1.0−(xxs+zzs) yzs−wxs ]
[ xzs−wys yzs+wxs 1.0−(xxs+yys)]

Sequences of rotations can be interpolated, so that the object being turned is rotated to specific poses at specific times. This motivated Ken Shoemake's early use of quaternions in computer graphics, as published in 1985. He used an analog of linear interpolation (sometimes called lerp) that he called Slerp, and also introduced an analog of a piecewise Bézier curve. A few years later in some course notes he described another curve variation he called Squad, which still seems to be popular. Later authors have proposed many alternatives.

Slerp(q1,q2;t) = q1 sin (1−t)Ω) / sin Ω + q2 sin tΩ / sin Ω,    cos Ω = q1·q2
Squad(q1,a1,b2,q2;t) = Slerp(Slerp(q1,q2;t),
Slerp(a1,b2;t);
2t(1−t))

Physics simulation, aerospace control, and robotics are examples of computations which also depend on rotation representation. Constrained rotations like a wheel on an axle or the elbow bend of a robot typically use specialized representations, such as an angle alone. In many general situations, however, quaternions have proved valuable.

2 dq = ω q dt,    ω is the angular velocity vector

User interfaces for 3D rotation also require a representation. Direct manipulation interfaces typically use angles for jointed figures, but for freer manipulation may use quaternions, as in Arcball or through-the-lens camera control. As Shoemake's full Graphics Gems code for Arcball demonstrates (with the [CAPS LOCK] key), any rotation can be graphed as an arc on a sphere. (Not to be confused with the quaternion unit sphere in 4D.) Whether quaternions, or any other representation, are helpful for numeric presentation and input seems a matter of taste and circumstance.

q = u2 u1−1
= [u1×u2, u1·u2]

Because of their metric properties for representing rotations, unit quaternions are most common. Advocates frequently point out that it is far cheaper to normalize the length of a non-zero quaternion than to bring a matrix back to rotation form. Also Shoemake’s later conversion code, reproduced above, cheaply creates a correct rotation matrix from any quaternion (found with his Euler angle code from Graphics Gems, which does the same for all 24 variations of that representation).

Normalize(q) = q / √(q·q)}

Comparisons to Euler angles may mention gimbal lock (frequently misspelled) as a disadvantage quaternions avoid. In the physical world where gyroscopes are mounted on nested pivots, which are called gimbals, locking is a real problem quaternions cannot help. What’s usually meant is that because the similarity of rotations organizes them essentially like a sphere, while similarity of vectors is quite different, an inevitable misfit plagues Euler angles. This can show up in behavior much like physical gimbal lock, but also in other ways. The difficulties are topological, and aiming runs into them as well, even if quaternions are used. Quaternion authors who propose using curves in the vector space of quaternion logarithms often risk the misfit unawares. Frankly, you must pick through the literature carefully, whether informal and online or refereed and printed, because mistakes are tragically common.

To explore Graphics Gems code, see Graphics Source Code in this FAQ. To read more about quaternions, you have many options. Since they were discovered in 1843 by Hamilton (the same Irish mathematician and physicist whose name shows up in quantum mechanics), quaternions have found many friends, as a web search will reveal. Quaternions can be approached and applied in numerous different ways, so if you keep looking it’s likely you will find something that suits your taste and your needs.

[edit]

External links

Retrieved from "http://cgafaq.info/wiki/Quaternion"
Personal tools