CSCI 520 Computer Animation and Simulation
Quaternions and Rotations
Jernej Barbic
University of Southern California
1
Rotations
• Veryimportantincomputeranimation and robotics
• Jointangles,rigidbodyorientations, camera parameters
• 2Dor3D
2
Rotations in Three Dimensions • Orthogonal matrices:
RRT =RTR=I det(R) = 1
3
Representing Rotations in 3D
• Rotationsin3Dhaveessentiallythree parameters
• Axis+angle(2DOFs+1DOFs)
– How to represent the axis?
Longitude / lattitude have singularities
• 3x3matrix
– 9 entries (redundant)
4
Representing Rotations in 3D
• Euler angles
– roll, pitch, yaw
– no redundancy (good) – gimbal lock singularities
• Quaternions
– generally considered the “best” representation
Source: Wikipedia
– redundant (4 values), but only by one DOF (not severe) – stable interpolations of rotations possible
5
Euler Angles
1. Yaw
rotate around y-axis
2. Pitch
rotate around (rotated) x-axis
3. Roll
rotate around (rotated) y-axis
Source: Wikipedia
6
1
Gimbal Lock
When all three gimbals
are lined up (in the same plane), the system can only move in two dimensions from this configuration,
not three, and is
in gimbal lock.
Source: Wikipedia 7
Gimbal Lock
When all three gimbals
are lined up (in the same plane), the system can only move in two dimensions from this configuration,
not three, and is
in gimbal lock.
Source: Wikipedia 8
Choice of rotation axis sequence for Euler Angles
• 12choices:
XYX, XYZ, XZX, XZY, YXY, YXZ, YZX, YZY, ZXY, ZXZ, ZYX, ZYZ
• Eachchoicecanusestaticaxes,or rotated axes, so we have
a total of 24 Euler Angle versions!
9
Example: XYZ Euler Angles
• First rotate around X by angle q1, then around Y by angle q2,
then around Z by angle q3 .
• Used in CMU Motion Capture Database AMC files
• Rotation matrix is:
10
Outline
• Rotations
• Quaternions
• QuaternionInterpolation
11
Quaternions
• Generalizationofcomplexnumbers
• Threeimaginarynumbers:i,j,k i2 = -1, j2 = -1, k2 = -1,
ij = k, jk = i, ki = j, ji = -k, kj = -i, ik = -j
• q=s+xi+yj+zk, s,x,y,zarescalars
12
2
Quaternions
• InventedbyHamiltonin1843inDublin,Ireland
• Hereashewalkedby on the 16th of October 1843 Sir William Rowan Hamilton in a flash of genius discovered the fundamental formula for quaternion multiplication i2 =j2 =k2 =ijk=−1
& cut it on a stone of this bridge.
Source:Wikipedia
13
Quaternions
• Quaternions are not commutative!
q1 q2 1 q2 q1
• However, the following hold:
(q1 q2) q3 = q1 (q2 q3)
(q1 +q2)q3 =q1 q3 +q2 q3
q1(q2 +q3)=q1 q2 +q1 q3
a(q1 +q2)=aq1 +aq2 (aisscalar) (aq1) q2 = a (q1q2) = q1 (aq2) (a is scalar)
• I.e., all usual manipulations are valid, except cannot reverse multiplication order.
14
Quaternions
• Exercise:multiplytwoquaternions
(2 – i + j + 3k) (-1 + i + 4j – 2k) = …
15
Quaternion Properties
• q=s+xi+yj+zk
• Norm:|q|2 =s2 +x2 +y2 +z2
• Conjugatequaternion:q=s-xi-yj-zk
• Inverse quaternion: q-1 = q / |q|2
• Unit quaternion: |q| =1
• Inverse of unit quaternion: q-1 = q
16
Quaternions and Rotations
• Rotationsarerepresentedbyunitquaternions
• q=s+xi+yj+zk s2 +x2 +y2 +z2=1
• Unitquaternionsphere (unit sphere in 4D)
Source: Wolfram Research
unit sphere
in 4D
17
Rotations to Unit Quaternions
• Let(unit)rotationaxisbe[ux,uy,uz],andangleq
• Correspondingquaternionis q = cos(q/2) +
sin(q/2) ux i + sin(q/2) uy j + sin(q/2) uz k
• Composition of rotations q1 and q2 equals q = q2 q1
• 3Drotationsdonotcommute!
18
3
Unit Quaternions to Rotations
• Let v be a (3-dim) vector and let q be a unit quaternion
• Then, the corresponding rotation transforms vector v to q v q-1
(v is a quaternion with scalar part equaling 0, and vector part equaling v)
For q = a + b i + c j + d k R=
19
Quaternions
• Quaternionsqand-qgivethesamerotation!
• Otherthanthis,therelationshipbetween rotations and quaternions is unique
20
Outline
• Rotations
• Quaternions
• QuaternionInterpolation
21
Quaternion Interpolation
• Betterresultsthan Euler angles
• Aquaternionisapoint on the 4-D unit sphere
• Interpolatingrotations corresponds to curves on the 4-D sphere
Source: Wolfram Research
22
Spherical Linear intERPolation (SLERPing)
• Interpolatealongthegreat circle on the 4-D unit sphere
• Movewithconstantangular velocity along the great circle between the two points
• Anyrotationisgivenby
two quaternions, so there are two SLERP choices; pick the shortest
San Francisco to London
23
SLERP
• uvariesfrom0to1
• qm =sm +xm i+ym j+zm k, form=1,2
• Theaboveformulaautomaticallyproducesa
unit quaternion (not obvious, but true).
24
4
Interpolating more than two rotations
• Simplestapproach: connect consecutive quaternions using SLERP
• Continuousrotations
• Angularvelocity
not smooth at the joints
25
Interpolation with smooth velocities
• Usesplinesonthe unit quaternion sphere
• Reference:KenShoemake in the SIGGRAPH ’85 proceedings (Computer Graphics, V. 19, No. 3,
P. 245)
26
Bezier Spline
• Fourcontrolpoints
– points P1 and P4 are on the curve
– points P2 and P3 are off the curve;
they give curve tangents at beginning and end
27
Bezier Spline
• p(0)=P1,p(1)=P4,
• p'(0)=3(P2-P1)
• p'(1)=3(P4-P3)
• ConvexHullproperty: curve contained within the convex hull of control points
• Scalefactor“3”ischosento make “velocity” approximately constant
28
The Bezier Spline Formula
• [x,y,z] is point on spline corresponding to u • u varies from 0 to 1
•P1=[x1 y1 z1] P2=[x2 y2 z2] •P3=[x3 y3 z3] P4=[x4 y4 z4]
Bezier basis
Bezier control matrix
29
DeCasteljau Construction
Efficient algorithm to evaluate Bezier splines. Similar to Horner rule for polynomials.
Can be extended to interpolations of 3D rotations.
30
5
DeCasteljau on Quaternion Sphere
Given t, apply DeCasteljau construction:
Q0 = Slerp(P0,P1,t) Q2 = Slerp(P2,P3,t) R1 = Slerp(Q1,Q2,t)
Q1 = Slerp(P1,P2,t) R0 = Slerp(Q0,Q1,t) P(t)= Slerp(R0,R1,t)
31
Bezier Control Points for Quaternions
• Givenquaternionsqn-1,qn,qn+1,form:
an = Slerp(Slerp(qn-1, qn, 2.0), qn+1, 0.5) an = Slerp(qn , an , 1.0 / 3)
bn = Slerp(qn ,an , -1.0 / 3)
32
Interpolating Many Rotations on
Quaternion Sphere
• Givenquaternionsq1,…,qN,
form Bezier spline control points (previous slide)
• Spline1:q1,a1,b2,q2
• Spline 2: q2, a2, b3, q3 etc.
• Need a1 and bN; can set
a1 = Slerp(q1, Slerp(q3, q2, 2.0), 1.0 / 3)
bN = Slerp(qN, Slerp(qN-2, qN-1, 2.0), 1.0 / 3)
• Toevaluateasplineatanyt,useDeCasteljau construction
33
6