Parallelising Contour Tree Computation
02: Quaternions
Dr. Hamish Carr
COMP 5812M: Foundations of Modelling & Rendering
Euler angles: rotate around global x, y, z
But we get gimbal lock: ambiguous roll & yaw
interpolation becomes degenerate
Euler Angles
COMP 5812M: Foundations of Modelling & Rendering
Rotation around x, y, z in fixed order
180º pitch + 180º yaw = 180º roll
Cardan Angles
COMP 5812M: Foundations of Modelling & Rendering
Keyframe Interpolation
Initial Rotation:
Pitch = 0
Yaw = 0
Roll = 0
Final Rotation:
Pitch = 180
Yaw = 180
Roll = 0
Intermediate Rotation:
Pitch = n
Yaw = n
Roll = 0
COMP 5812M: Foundations of Modelling & Rendering
Cardan Interpolation
Cardan angles are not unique
One orientation, multiple representations
Worst-case behaviour is pretty awful
COMP 5812M: Foundations of Modelling & Rendering
Great Circle Rotation
A great circle goes through the origin
it cuts the sphere in half
one point rotates to a second
so actually, two vectors
convert to orthonormal basis
transform into basis
and rotate around n
But what about roll?
COMP 5812M: Foundations of Modelling & Rendering
Quaternions
Homogeneous rotation coordinates
Based on complex numbers:
a+bi
a is the real part
b is the imaginary part
COMP 5812M: Foundations of Modelling & Rendering
Complex Operations
Addition:
Multiplication:
Conjugation:
COMP 5812M: Foundations of Modelling & Rendering
Spatial Interpretation
Treat as points in 2D:
COMP 5812M: Foundations of Modelling & Rendering
Spatial Addition
Complex Addition:
Is translation!
(or vector addition)
COMP 5812M: Foundations of Modelling & Rendering
Polar Multiplication
COMP 5812M: Foundations of Modelling & Rendering
Polar Multiplication
COMP 5812M: Foundations of Modelling & Rendering
What about Theta?
COMP 5812M: Foundations of Modelling & Rendering
Geometric Interpretation
Multiplication gives
Scaling
Rotation
Based on polar notation
COMP 5812M: Foundations of Modelling & Rendering
Extending to 3-D
We’ll look at complex conjugates:
Does this work for 3 coordinates?
COMP 5812M: Foundations of Modelling & Rendering
The Fourth Coordinate
We need bcij and bcji to cancel out
So we add a fourth coordinate:
And get quaternions with four coordinates:
a + bi + cj + dk
COMP 5812M: Foundations of Modelling & Rendering
With Quaternions
Now it all works!
COMP 5812M: Foundations of Modelling & Rendering
Quaternion Operations
Addition:
Multiplication:
COMP 5812M: Foundations of Modelling & Rendering
Geometric Interpretation
i,j,k are different from 1:
i becomes j becomes k becomes i
looks like rotating between x, y, z
In a quaternion q=(w,x,y,z)
w is the scalar part
(x,y,z) is the vector part
COMP 5812M: Foundations of Modelling & Rendering
Notation
Scalar s:
Vector v:
Quaternion q:
COMP 5812M: Foundations of Modelling & Rendering
Properties
Scalar multiplication:
Associativity & Distributivity:
Anti-commutativity:
COMP 5812M: Foundations of Modelling & Rendering
Conjugation
COMP 5812M: Foundations of Modelling & Rendering
Vector Multiplication
COMP 5812M: Foundations of Modelling & Rendering
More Multiplication
COMP 5812M: Foundations of Modelling & Rendering
Norm & Inverse
COMP 5812M: Foundations of Modelling & Rendering
Action of a Quaternion
COMP 5812M: Foundations of Modelling & Rendering
Lemma 1
COMP 5812M: Foundations of Modelling & Rendering
Lemma 2
For any s≠0, q and sq have the same action
I.e. quaternions are homogeneous in nature
COMP 5812M: Foundations of Modelling & Rendering
Lemma 3
Assume q is a unit quaternion. It’s action on a scalar is:
COMP 5812M: Foundations of Modelling & Rendering
Lemma 4
COMP 5812M: Foundations of Modelling & Rendering
Lemma 5
COMP 5812M: Foundations of Modelling & Rendering
Theorem
COMP 5812M: Foundations of Modelling & Rendering
Finding a Basis
COMP 5812M: Foundations of Modelling & Rendering
Action on
COMP 5812M: Foundations of Modelling & Rendering
Action on
COMP 5812M: Foundations of Modelling & Rendering
Interpretation
COMP 5812M: Foundations of Modelling & Rendering
Action in General
COMP 5812M: Foundations of Modelling & Rendering
Uniqueness
COMP 5812M: Foundations of Modelling & Rendering
Quaternion to Matrix
COMP 5812M: Foundations of Modelling & Rendering
Left-Multiplication
COMP 5812M: Foundations of Modelling & Rendering
Right-Multiplication
COMP 5812M: Foundations of Modelling & Rendering
Full Action
COMP 5812M: Foundations of Modelling & Rendering
Rot. Matrix to Quaternion
COMP 5812M: Foundations of Modelling & Rendering
Finding x, y, z:
COMP 5812M: Foundations of Modelling & Rendering
Spherical Interpolation
Quaternions rotate on great circles
Assume that:
q defines the entire rotation
we want to interpolate in n steps
COMP 5812M: Foundations of Modelling & Rendering
Exponential Solution
COMP 5812M: Foundations of Modelling & Rendering
Interpolation Hack
COMP 5812M: Foundations of Modelling & Rendering
Arcball Controller
An arcball rotation consists of two mouse-clicks: start (u) and end (v)
This gives a rotation along the great circle between u and v
COMP 5812M: Foundations of Modelling & Rendering
2D to 3D
COMP 5812M: Foundations of Modelling & Rendering
Computing a Quaternion
COMP 5812M: Foundations of Modelling & Rendering
Arcball Version
COMP 5812M: Foundations of Modelling & Rendering
r
u
r
v
r
n
r
u
r
v
r
n
Brief Article
The Author
September 28, 2017
p = (a, b)[Cartesian]
= a+ bi[Complex]
= (r, ✓)[Polar]
r =
p
a2 + b2
=
p
pp⇤
✓ = arctan(
b
a
)
p3 = p1 + p2
p3 = p1 + p2
p3 = p1 + p2
1
Brief Article
The Author
September 28, 2017
p = (a, b)[Cartesian]
= a+ bi[Complex]
= (r, ✓)[Polar]
r =
p
a2 + b2
=
p
pp⇤
✓ = arctan(
b
a
)
p3 = p1 + p2
= (a1 + b1i) + (a2 + b2i)
= (a1 + a2) + (b1 + b2)i
a3 = a1 + a2
b3 = b1 + b2
p3 = p1 + p2
p3 = p1 + p2
1
p3 = p1p2
= (a1 + b1i)(a2 + b2i)
= (a1a2 � b1b2) + (a1b2 + b1a2)i
a3 = a1a2 � b1b2
b3 = a1b2 + b1a2
What is the spatial interpretation of p3?
Consider the polar form (r3, ✓3), where
r3 =
q
a23 + b
2
3
✓3 = arctan(
b3
a3
)
2
p3 = p1p2
= (a1 + b1i)(a2 + b2i)
= (a1a2 � b1b2) + (a1b2 + b1a2)i
a3 = a1a2 � b1b2
b3 = a1b2 + b1a2
What is the spatial interpretation of p3?
Consider the polar form (r3, ✓3), where
r3 =
q
a23 + b
2
3
✓3 = arctan(
b3
a3
)
2
p3 = p1p2
= (a1 + b1i)(a2 + b2i)
= (a1a2 � b1b2) + (a1b2 + b1a2)i
a3 = a1a2 � b1b2
b3 = a1b2 + b1a2
What is the spatial interpretation of p3?
Consider the polar form (r3, ✓3), where
r3 =
q
a23 + b
2
3
✓3 = arctan(
b3
a3
)
2
p3 = p1p2
= (a1 + b1i)(a2 + b2i)
= (a1a2 � b1b2) + (a1b2 + b1a2)i
a3 = a1a2 � b1b2
b3 = a1b2 + b1a2
What is the spatial interpretation of p3?
Consider the polar form (r3, ✓3), where
r3 =
q
a23 + b
2
3
✓3 = arctan(
b3
a3
)
r3 =
q
a23 + b
2
3
=
p
(a1a2 � b1b2)2 + (a1b2 + b1a2)2
=
q
a21a
2
2 � 2a1a2b1b2 + b
2
1b
2
2 + a
2
1b
2
2 + 2a1a2b1b2 + a
2
2b
2
1
=
q
a21a
2
2 + b
2
1b
2
2 + a
2
1b
2
2 + a
2
2b
2
1
=
q
a21a
2
2 + a
2
1b
2
2 + b
2
1a
2
2 + b
1
2b
2
2
=
q
a21(a
2
2 + b
2
2) + b
2
1(a
2
2 + b
2
2)
=
q
(a21 + b
2
1)(a
2
2 + b
2
2)
=
q
(a21 + b
2
1)
q
(a22 + b
2
2)
= r1r2
=
=
2
✓3 = arctan
✓
b3
a3
◆
= arctan
✓
a1b2 + a2b1
a1a2 � b1b2
◆
= arctan
a1b2
a1a2
+
a2b1
a1a2
a1a2
a1a2
� b1b2a1a2
!
= arctan
b2
a2
+
b1
a1
1� b1a1
b2
a2
!
= arctan
✓
tan ✓1 + tan ✓2
1� tan ✓1 tan ✓2
◆
= arctan (tan (✓1 + ✓2))
= ✓1 + ✓2
=
=
=
=
=
=
3
✓3 = arctan
✓
b3
a3
◆
= arctan
✓
a1b2 + a2b1
a1a2 � b1b2
◆
= arctan
a1b2
a1a2
+
a2b1
a1a2
a1a2
a1a2
� b1b2a1a2
!
= arctan
b2
a2
+
b1
a1
1� b1a1
b2
a2
!
= arctan
✓
tan ✓1 + tan ✓2
1� tan ✓1 tan ✓2
◆
= arctan (tan (✓1 + ✓2))
= ✓1 + ✓2
(a+ bi)(a+ bi)⇤ = (a2 + b2)
= r2
(a+ bi+ cj)(a+ bi+ cj)⇤ = (a+ bi+ cj)(a� bi� cj)
= a2 � abi� acj + abi� b2i2 � bcij + acj � bcji� c2j2
= a2 � b2i2 � c2j2 � bcij � bcji
= a2 + b2 + c2 � bcij � bcji
=
=
=
3
✓3 = arctan
✓
b3
a3
◆
= arctan
✓
a1b2 + a2b1
a1a2 � b1b2
◆
= arctan
a1b2
a1a2
+
a2b1
a1a2
a1a2
a1a2
� b1b2a1a2
!
= arctan
b2
a2
+
b1
a1
1� b1a1
b2
a2
!
= arctan
✓
tan ✓1 + tan ✓2
1� tan ✓1 tan ✓2
◆
= arctan (tan (✓1 + ✓2))
= ✓1 + ✓2
(a+ bi)(a+ bi)⇤ = (a2 + b2)
= r2
(a+ bi+ cj)(a+ bi+ cj)⇤ = (a+ bi+ cj)(a� bi� cj)
= a2 � abi� acj + abi� b2i2 � bcij + acj � bcji� c2j2
= a2 � b2i2 � c2j2 � bcij � bcji
= a2 + b2 + c2 � bcij � bcji
=
=
=
3
✓3 = arctan
✓
b3
a3
◆
= arctan
✓
a1b2 + a2b1
a1a2 � b1b2
◆
= arctan
a1b2
a1a2
+
a2b1
a1a2
a1a2
a1a2
� b1b2a1a2
!
= arctan
b2
a2
+
b1
a1
1� b1a1
b2
a2
!
= arctan
✓
tan ✓1 + tan ✓2
1� tan ✓1 tan ✓2
◆
= arctan (tan (✓1 + ✓2))
= ✓1 + ✓2
(a+ bi)(a+ bi)⇤ = (a2 + b2)
= r2
(a+ bi+ cj)(a+ bi+ cj)⇤ = (a+ bi+ cj)(a� bi� cj)
= a2 � abi� acj + abi� b2i2 � bcij + acj � bcji� c2j2
= a2 � b2i2 � c2j2 � bcij � bcji
= a2 + b2 + c2 � bcij � bcji
ij = k = �ji
jk = j(�ji) = �j2i = �(�1)i = i = �kj
ki = (�ji)i = �ji2 = �j(�1) = j = �ik
=
=
=
3
✓3 = arctan
✓
b3
a3
◆
= arctan
✓
a1b2 + a2b1
a1a2 � b1b2
◆
= arctan
a1b2
a1a2
+
a2b1
a1a2
a1a2
a1a2
� b1b2a1a2
!
= arctan
b2
a2
+
b1
a1
1� b1a1
b2
a2
!
= arctan
✓
tan ✓1 + tan ✓2
1� tan ✓1 tan ✓2
◆
= arctan (tan (✓1 + ✓2))
= ✓1 + ✓2
(a+ bi)(a+ bi)⇤ = (a2 + b2)
= r2
(a+ bi+ cj)(a+ bi+ cj)⇤ = (a+ bi+ cj)(a� bi� cj)
= a2 � abi� acj + abi� b2i2 � bcij + acj � bcji� c2j2
= a2 � b2i2 � c2j2 � bcij � bcji
= a2 + b2 + c2 � bcij � bcji
ij = k = �ji
jk = j(�ji) = �j2i = �(�1)i = i = �kj
ki = (�ji)i = �ji2 = �j(�1) = j = �ik
(a+ bi+ cj + dk)(a+ bi+ cj + dk)⇤ = (a+ bi+ cj + dk)(a� bi� cj � dk)
= a2 � abi� acj � adk
+abi� b2i2 � bcij � bdik
+acj � bcji� c2j2 � cdjk
adk � bdki� cdkj � d2k2
= a2 + b2 + c2 + d2
�abi+ abi� cdjk � cdkj
�acj � bdik + acj � bdki
�adk � bcij � bcji+ adk
= a2 + b2 + c2 + d2
3
q1 + q2 = (a1 + b1i+ c1j + d1k) + (a2 + b2i+ c2j + d2k)
= (a1 + a2) + (b1 + b2)i+ (c1 + c2)j + (d1 + d2)k)
=
=
=
=
4
q1 + q2 = (a1 + b1i+ c1j + d1k) + (a2 + b2i+ c2j + d2k)
= (a1 + a2) + (b1 + b2)i+ (c1 + c2)j + (d1 + d2)k)
q1q2 = (a1 + b1i+ c1j + d1k)(a2 + b2i+ c2j + d2k)
= (a1a2 � b1b2 � c1c2 � d1d2)1
(a1b2 + b1a2 + c1d2 � d1c2)i
(a1c2 � b1d2 + c1a2 + d1b2)j
(a1d2 + b1c2 � c1b2 + d1a2)k
s = (s,
~
0)
= (s, 0, 0, 0)
~v = (0,~v)
= (0, x, y, z)
q = (w,~v)
(w, x, y, z)
sq = qs
= (s,
~
0)(w.~v)
= (sw, s~v)
pq(r) = p(qr)
p(q + r) = pq + pr
(pq)
⇤
= q
⇤
p
⇤
4
q1 + q2 = (a1 + b1i+ c1j + d1k) + (a2 + b2i+ c2j + d2k)
= (a1 + a2) + (b1 + b2)i+ (c1 + c2)j + (d1 + d2)k)
q1q2 = (a1 + b1i+ c1j + d1k)(a2 + b2i+ c2j + d2k)
= (a1a2 � b1b2 � c1c2 � d1d2)1
(a1b2 + b1a2 + c1d2 � d1c2)i
(a1c2 � b1d2 � c1a2 � d1b2)j
(a1c2 � b1d2 � c1a2 � d1b2)k
s = (s,
~
0)
= (s, 0, 0, 0)
~v = (0,~v)
= (0, x, y, z)
q = (w,~v)
(w, x, y, z)
=
=
=
4
q1 + q2 = (a1 + b1i+ c1j + d1k) + (a2 + b2i+ c2j + d2k)
= (a1 + a2) + (b1 + b2)i+ (c1 + c2)j + (d1 + d2)k)
q1q2 = (a1 + b1i+ c1j + d1k)(a2 + b2i+ c2j + d2k)
= (a1a2 � b1b2 � c1c2 � d1d2)1
(a1b2 + b1a2 + c1d2 � d1c2)i
(a1c2 � b1d2 � c1a2 � d1b2)j
(a1c2 � b1d2 � c1a2 � d1b2)k
s = (s,
~
0)
= (s, 0, 0, 0)
~v = (0,~v)
= (0, x, y, z)
q = (w,~v)
(w, x, y, z)
sq = qs
= (s,
~
0)(w.~v)
= (sw, s~v)
=
=
4
q1 + q2 = (a1 + b1i+ c1j + d1k) + (a2 + b2i+ c2j + d2k)
= (a1 + a2) + (b1 + b2)i+ (c1 + c2)j + (d1 + d2)k)
q1q2 = (a1 + b1i+ c1j + d1k)(a2 + b2i+ c2j + d2k)
= (a1a2 � b1b2 � c1c2 � d1d2)1
(a1b2 + b1a2 + c1d2 � d1c2)i
(a1c2 � b1d2 � c1a2 � d1b2)j
(a1c2 � b1d2 � c1a2 � d1b2)k
s = (s,
~
0)
= (s, 0, 0, 0)
~v = (0,~v)
= (0, x, y, z)
q = (w,~v)
(w, x, y, z)
sq = qs
= (s,
~
0)(w.~v)
= (sw, s~v)
pq(r) = p(qr)
p(q + r) = pq + pr
=
4
q1 + q2 = (a1 + b1i+ c1j + d1k) + (a2 + b2i+ c2j + d2k)
= (a1 + a2) + (b1 + b2)i+ (c1 + c2)j + (d1 + d2)k)
q1q2 = (a1 + b1i+ c1j + d1k)(a2 + b2i+ c2j + d2k)
= (a1a2 � b1b2 � c1c2 � d1d2)1
(a1b2 + b1a2 + c1d2 � d1c2)i
(a1c2 � b1d2 � c1a2 � d1b2)j
(a1c2 � b1d2 � c1a2 � d1b2)k
s = (s,
~
0)
= (s, 0, 0, 0)
~v = (0,~v)
= (0, x, y, z)
q = (w,~v)
(w, x, y, z)
sq = qs
= (s,
~
0)(w.~v)
= (sw, s~v)
pq(r) = p(qr)
p(q + r) = pq + pr
(pq)
⇤
= q
⇤
p
⇤
4
(w, x, y, z)
⇤
= (w,�x,�y,�z)
(w,~v)
⇤
= (w,�~v)
(pq)
⇤
= q
⇤
p
⇤
(w,~v) + (w,~v)
⇤
= (w + w,~v + (�~v))
= (2w,
~
0)
=
=
=
=
=
=
5
(w, x, y, z)
⇤
= (w,�x,�y,�z)
(w,~v)
⇤
= (w,�~v)
(pq)
⇤
= q
⇤
p
⇤
(w,~v) + (w,~v)
⇤
= (w + w,~v + (�~v))
= (2w,
~
0)
~v1 ~v2 = (0 + x1i+ y1j + z1k)(0 + x2i+ y2j + z2k)
= (0� x1x2 � y1y2 � z1z2)
(0 + 0 + y1z2 � z1y2)i
(0� x1z2 � 0� z1x2)j
(0� x1y2 � y1x2 � 0)k
= (�x1x2 � y2y2 � z1z2)
+(y1z2 � z1y2)i
+(�x1z2 + z1x2)j
(x1y2 � y1x2)k
= (� ~v1 · ~v2, ~v1 ⇥ ~v2)
=
=
=
=
5
(w, x, y, z)
⇤
= (w,�x,�y,�z)
(w,~v)
⇤
= (w,�~v)
(pq)
⇤
= q
⇤
p
⇤
(w,~v) + (w,~v)
⇤
= (w + w,~v + (�~v))
= (2w,
~
0)
~v1 ~v2 = (0 + x1i+ y1j + z1k)(0 + x2i+ y2j + z2k)
= (0� x1x2 � y1y2 � z1z2)
(0 + 0 + y1z2 � z1y2)i
(0� x1z2 � 0� z1x2)j
(0� x1y2 � y1x2 � 0)k
= (�x1x2 � y2y2 � z1z2)
+(y1z2 � z1y2)i
+(�x1z2 + z1x2)j
(x1y2 � y1x2)k
= (� ~v1 · ~v2, ~v1 ⇥ ~v2)
q1q2 = (w1,~v1)(w2,~v2)
=
⇣
(w1,
~
0) + (0,~v1)
⌘⇣
(w2,
~
0) + (0,~v2)
⌘
= (w1,
~
0)(w2,
~
0) + (w1,
~
0)(0,~v2) + (0,~v1)(w2,
~
0) + (0,~v1)(0,~v2)
= (w1w2,
~
0) + ((0, w1~v2) + (0, w2~v1) + (� ~v1 · ~v2, ~v1 ⇥ ~v2)
= (w1w2 � ~v1 · ~v2, , ~v1 ⇥ ~v2 + w1~v2 + w2~v1)
=
=
5
N(q) = qq
⇤
= q
⇤
q
= w
2
+ x
2
+ y
2
+ z
2
= w
2
+ ~v · ~v
N(pq) = N(p)N(q)
N(q
⇤
) = N(q)
q
�1
= q
⇤
/N(q)
�1
= qq
⇤
/N(q)
= N(q)/N(q)
= 1
=
=
=
6