程序代写代做代考 Parallelising Contour Tree Computation

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)

qq

�1
= qq


/N(q)

= N(q)/N(q)

= 1

=

=

=

6