[SOLVED] CS database algorithm CSCI 520 Computer Animation and Simulation

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
Scalefactor3ischosento 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