Transcript 2: Geometry & Homogeneous Coordinates

#2: Geometry &
Homogeneous Coordinates
CSE167: Computer Graphics
Instructor: Ronen Barzel
UCSD, Winter 2006
Outline for Today
More math…
n Finish linear algebra: Matrix composition
1. Points, Vectors, and Coordinate Frames
2. Homogeneous Coordinates
1
Matrix Multiplication

Each entry is dot product of row of M with column of N
 mxx

M   myx
 mzx

mxy
myy
mzy
mxz 

myz 
mzz 
 nxx

N   nyx
 nzx

nxy
nyy
nzy
nxz 

nyz 
nzz 
LM N
l xx

l yx
 lzx

lxy
lyy
lzy
lxz 

lyz  
lzz 
 mxx

 myx
 mzx

mxy
myy
mzy
mxz   nxx
 
myz    nyx
mzz   nzx
nxy
nyy
nzy
nxz 

nyz 
nzz 
l xy  mxx nxy  mxy nyy  mxz nzy
2
Matrix Multiplication
 mxx

M   myx
 mzx

mxy
myy
mzy
MN ij   mik nkj
  mxk nkx

MN    myk nkx

  mzk nkx



mxz 

myz 
mzz 
m
m
m
 nxx

N   nyx
 nzx

n
xk ky
n
yk ky
n
zk ky
m
m
m
 mxx nxx  mxy nyx  mxz nzx

MN   myx nxx  myy nyx  myz nzx

 mzx nxx  mzy nyx  mzz nzx

nxy
nyy
nzy
nxz 

nyz 
nzz 
n 

yk nkz 

zk nkz 
xk kz
 m
 m
 m
n  mxy nyy  mxz nzy
xx xy
n  myy nyy  myz nzy
yx xy
n  mzy nyy  mzz nzy
zx xy
 m
 m
 m



n  mxy nyz  mxz nzz 


yx n xz  m yy n yz  m yz nzz


zx n xz  mzy nyz  mzz nzz 
xx xz
3
Multiple Transformations

If we have a vector v, and an x-axis rotation matrix Rx, we can
generate a rotated vector v′:
v  R x  v

If we wanted to then rotate that vector around the y-axis, we could
multiply by another matrix:
v   R y   v 
v   R y   R x   v 
4
Multiple Transformations

We can extend this to the concept of applying any sequence of
transformations:


v  M4 M3 M2 M1 v 

Because matrix algebra obeys the associative law, we can regroup this as:
v   M 4 M 3 M 2 M1  v

This allows us to compose them into a single matrix:
Mtotal  M4 M3 M2 M1
v  Mtotal v
5
Order matters!

Matrix multiplication does NOT commute:
MNN M



(unless one or the other is a uniform scale)
Try this:
rotate 90 degrees about x then 90 degrees about z, versus
rotate 90 degrees about z then 90 degrees about x.
Matrix composition works right-to-left.

Compose:
MA B C
Then apply it to a vector:
v  M v
v   A B C  v
v   A B C v 
It first applies C to v, then applies B to the result, then applies A to the result of that.
6
Quick Matrix algebra summary
linearity:
M (sb)  s M b 
M a  b   M a   M b 
M 1 is inverse of M : (when it exists)
M 1 M a   a
M 1M  I
MM 1  I
MPQ1  Q1P1M1
for a rotation: R 1  R T
determinant M :
M 1 
scales up
 M 1

pure rotation
M 1

 0< M  1 scales down
M 0
"flattens": singular matrix, no inverse

 M  0
reflects
1
M
7
What good is this?

Composition of transformations, by matrix multiplication,
is a basic technique




Used all the time
You’ll probably use it for Project 1
All linear operations on vectors can be expressed as composition
of rotation and scale (even “shear”)
But there’s a limit to what we can do only having linear
operations on vectors….
8
Outline for Today
1.
2.
3.
Finish linear algebra: Matrix composition
Points, Vectors and Coordinate Frames
Homogeneous Coordinates
9
Geometric objects

Interesting Objects
Points
 Vectors
 Transformations
 Coordinate Frames
 Also: Lines, Rays, Planes, Normals, …

10
Points and vectors



You know linear algebra, vector spaces
Why am I talking about this?
Emphasize differences:


between a point and a vector
between a point or vector and the representation of
a point or vector
11
Points and vectors



in R3, can represent point as 3 numbers
in R3, can represent vector as 3 numbers
Easy to think they’re the same thing…




…but they’re not!
different operations, different behaviors
many program libraries make this mistake
easy to have bugs in programs
12
In 1D, consider time



point in time: a class meets at 2PM
duration of time: a class lasts 2 hours
operations:







class at 2PM + class at 3PM ≠ class at 5PM !!
2 hour class + 3 hour class = 5 hours of classes
class ends at 5PM – starts at 2PM = 3 hour class
class starts at 2PM + lasts 3 hours = ends at 5PM
2 classes at 3PM ≠ one class at 6PM !!
2 classes last 3 hours = 6 hours of classes
1
1
2
PM
+
Class from 2PM to 10PM, half done at   6PM  = 4PM
2
2
("affine combination")
13
“Coordinate Systems” for time
Knowing just the hour number doesn’t tell you everything…


AM vs. PM (or use 8h00 vs 20h00)
Time zones: same point, many representations



If always staying in local time zone, not important



if scheduling globally, must be careful.
convert from one time zone to another.
(Also, hours only good within one day



10 (Paris) == 9 (London)
to remove ambiguity, often use GMT
need to specify date & time
UNIX time: seconds since 01/01/1970, 00h00 GMT)
Notice: time durations are unaffected by all this!
14
Geometry, analogously

Point describes a location in space



Vector describes a displacement in space




can subtract points to get a vector
can take weighted average of points to get a point
has a magnitude and direction
can add, subtract, scale vectors
can add vector to a point to get a point
To represent them as three numbers, you must specify
which coordinate system
15
Vector and point arithmetic

w  uv
vwu
us v
vector+vector  vector
vector-vector  vector
scale a vector
qpv
v  qp
point+vector  point
point-point  vector
1
3
r p q
4
4
weighted average of points  point
C++ classes can support these operations
16
Coordinate Frames

Origin point, and 3 orthonormal vectors for x,y,z axes (right-handed)
b
c
y
a
p, a, b, c
h
P
o,x, y,z
O
x
g
q, f, g, h
Q
f
z

In CG, often work with many different frames simultaneously
17
Coordinates

If you have coordinate triples such as:
 3
6 
 
 1 

or
9
 2 
 
 5 
Then, with frame such as o,x, y,z you can construct a point or vector:
p  o  3x  6y  z
v
9x  2y  5z

Same coordinates, different frame  different point or vector


Coordinates have no real meaning without a frame
CG programs often have lots of frames--you have to keep track!
• (It’s possible to write C++ classes that keep track of frames. But it’s hard for them to
be time- and memory-efficient, so it’s rarely done in practice.)


Typically have “World Coordinates” as implicit base frame
Notice: vectors don’t depend on the origin of the frame, only the axes
18
Coordinates of a Frame


Suppose you have a frame p, a, b, c
In world coordinates, might have
10 
p   3 
 3 

0
a   1
 1 
 0.707 
b   0 
 0.707 
 0.707 
c   0 
 0.707 
But in itself p, a, b, c always have coordinates:
0 
p   0 
 0 
1 
a   0 
 0 
0 
b   1 
 0 
0 
c   0 
 1 
19
Coordinate equivalences

Given a frame:




o,x, y,z
y
Can have a point with some coords:
a 
p   b 
 c 
p
v
Can have a vector with same coords:
a 
v   b 
 c 
O
a
b
c
x
z
Formally, we have:
pov
vpo
Informally, p and v look and act about the same
• People often sloppy, don’t distinguish point from vector
• Can only get away with it if you stay in same frame!
• And even then need to be careful…
20
Outline for Today
Finish linear algebra: Matrix composition
Points, Vectors and Coordinate Frames
Homogeneous Coordinates
1.
2.
3.

But first: transforming points
21
Linear Transformations
Matrix-vector
multiplication
M
Rotation matrix
Scale matrix
 mxx

Mv   myx
 mzx

mxy
myy
mzy
mxz   vx 
 
myz   vy 
mzz   vz 
Matrix-point
multiplication
 mxx

Mp   myx
 mzx

mxy
myy
mzy
mxz   px 
 
myz   py 
mzz   pz 
Rotates vector direction
Moves point by rotating
about origin of frame
Scales vector magnitude
Moves point
towards or away from
origin of frame
22
Rotating an object


Object defined as collection of points p1
Apply rotation matrix to every point:
pN
pi  R p i , for all i

Rotates object about origin of frame

Also rotates all vectors in object:
v  p 2  p1
v   p2  p1  Rp 2   Rp1   R(p 2  p1 )  Rv
23
Scaling an object

Apply scale matrix to every point:
pi  S p i , for all i

Scale object about origin of frame

Also scales all vectors in object
v  p 2  p1
v   p2  p1  Sp 2   Sp1   S(p 2  p1 )  Sv
24
Moving an object

Add displacement vector to each point:
pi  pi  d,

for all i
Translates the object:
d

Vectors don’t change:
v  p 2  p1

 

v   p2  p1  p 2  d  p1  d  (p 2  p1 )  (d  d)  v  0  v
25
General Object Transformation

Some matrix M and displacement d:
p  M p  d
v  M v

Math note: the transformation for p isn’t linear
• It’s an affine transformation
• Points and their transforms form an affine space
• Not a vector space
26
But it’s very inconvenient

Different rule for points vs. vectors

Hard to compose transformations:
p  Mp  d

p  Np  e  NM p  Nd  e


p  Qp  f  QNM p  QN d  Qe  f


Hard to invert, etc.
…so introduce Homogeneous Coordinates
27
Homogeneous coordinates

Basic: a trick to unify/simplify computations.

Deeper: projective geometry



Interesting mathematical properties
Good to know, but less immediately practical
We will use some aspect of this when we do
perspective projection (in a few weeks)
28
Homogeneous coordinates

Add an extra component. 1 for a point, 0 for a vector:
 px 
p 
y
p 
 pz 
 
1

combine M and d into single 4x4 matrix:
 mxx
m
 yx
 mzx

 0

 vx 
v 
y
v 
 vz 
 
0
mxy
mxz
myy
myz
mzy
mzz
0
0
dx 
dy 

dz 

1
And see what happens when we multiply…
29
Homogeneous point transform

Transform a point:
 px   mxx
 p   m
 y    yx
 pz   mzx
  
1  0
mxy
myy
mzy
0
mxz
myz
mzz
0
d x   px   mxx px  mxy py  mxz pz  d x 
d y   py   myx px  myy py  myz pz  d y 
   

dz   pz   mzx px  mzy py  mzz pz  dz 
  

1  1  
0  0  0 1

 px 
 
M  py 
 pz 



d
Top three rows are the affine transform!
Bottom row stays 1
30
Homogeneous vector transform

Transform a vector:
 vx   mxx
 v   m
 y    yx
 vz   mzx
  
0  0
mxy
myy
mzy
0
mxz
myz
mzz
0
d x   vx   mxx vx  mxy vy  mxz vz  0 
d y   vy   myx vx  myy vy  myz vz  0 
   

dz   vz   mzx vx  mzy vy  mzz vz  0 
  

1  0  
0000

 vx 
 
M  vy 
 vz 

Top three rows are the linear transform
• Displacement d is properly ignored

Bottom row stays 0
31
Homogeneous arithmetic

Legal operations always end in 0 or 1!
vector+vector:
     
0   0   0 
     
vector-vector:
     
0   0   0 
     
scalar*vector:
   
s    
0  0 
point+vector:
     
1   0   1
     
point-point:
     
1  1   0 
     
point+point:
     
1  1   2 
     
scalar*point:
   
s    
1  s 
 weighted average 
1  2   

 of points:
1  3 1  1
affine
combination
3
 
   


32
Homogeneous Transforms

Rotation, Scale, and Translation of points and
vectors unified in a single matrix transformation:
p  M p

Matrix has the form:


Last row always 0,0,0,1
 mxx
m
 yx
 mzx

 0
mxy
mxz
myy
myz
mzy
mzz
0
0
dx 
dy 

dz 

1
Transforms compose by matrix multiplication!


Same caveat: order of operations is important
Same note: Transforms operate right-to-left
33
Primitive Transforms
1
0
I
0

0
 sx
0
S(sx , sy , sz )  
0

0
1
0
R x( )  
0

0
1
0
T(d)  
0

0
0 0 0
1 0 0

0 1 0

0 0 1
0 0 0
sy 0 0 

0 sz 0 

0 0 1
0
0
0
 cos( )
 0
cos( )  sin( ) 0 
 R ( )  
  sin( )
sin( ) cos( ) 0  y


0
0
1
 0
0 0 dx 
1 0 dy 

0 1 dz 

0 0 1
0
 cos( )  sin( )
 sin( ) cos( )
1
0
0
 R ( )  
 0
0 cos( ) 0  z
0


0
0
1
0
 0
0
sin( )
0 0
0 0

1 0

0 1
34
Programming in practice

Everyone uses homogeneous matrices.


built into low-level software, hardware
In practice, almost never explicitly use 4th
component of vector or point.


Waste of memory & computation
Instead, keep track of points vs. vectors explicitly
• E.g. by C++ classes

Separate matrix methods “transform point” and
“transform vector” that implicitly use the 1 or 0.
35
More Coordinate Equivalences

Translate an object by d 
Translate the coordinate frame by -d


Rotate object about the frame’s origin 
Rotate the frame oppositely out its own origin


Either way, get the same coordinates out
Either way, get the same coordinates out
Duality:



Matrix transforms objects vs. changes coordinates
Either can be handy (we’ll talk about next class)
Can be confusing, make sure you know which you want…
36
Transformation as coordinate frame

Build matrix from vectors a, b, c, point d
 ax
a
y
M
 az

0

cx
by
cy
bz
cz
0
0
dx 
dy 

dz 

1
Notice effect on coordinate frame:
1 
0 
a  M    Mx
0 
 
0 

bx
0 
1 
b  M    My
0 
 
0 
0 
0 
c  M    Mz
1 
 
0 
0 
0 
d  M   M o
0 
 
1 
Any transform M describes change of frame:
d, a, b, c  M o, x, y, z

If a,b,c are right-handed orthonormal, transformation is rigid


Pure rotation, pure translation, or mix of rotation and translation
No scale
37
Useful tidbit: Rotate about a “pivot”

Q: How to rotate about arbitrary pivot?


Rotation matrix always rotates about origin!
A: Sequence of operations:
Given desired pivot point p, same coords give vector from origin, v  p  o
Step 1. Translate object to move pivot point to origin: T(v)
Step 2. Rotate object by your rotation matrix: R
Step 3. Translate to move origin back to original spot: T(v)
Compose these: R p  T(v)RT(v)


This is a handy “primitive” to implement
Food for thought: what’s the structure of the resulting matrix?
38
Next class:


Hierarchical Transformations
Geometric Calculations
39