Transcript Andries van Dam September 5, 2000 Introduction to

INTRODUCTION
TO
COMPUTER
G RAPH I C S
Transformations
Andries van Dam
September 14, 2004
Transformation 1/32
INTRODUCTION
•
TO
COMPUTER
G RAPH I C S
How Are Geometric
Transformations (T,R,S) Used in
Computer Graphics?
Object construction using assemblies/hierarchy of parts à la
Sketchpad’s masters and instances; leaves contain primitives
“is composed of hierarchy”
transformation
ROBOT
upper body
lower body
stanchion
head trunk
•
base
arm
Scenegraph
(see Sceneview assignment)
Aid to realism
– objects, camera use realistic motion
•
Help form 3D “object hypothesis” (James Gibson)
– kinesthetic feedback as user manipulates objects or synthetic
camera
•
Synthetic camera/viewing
– definition
– normalization (from arbitrary to canonical view)
•
Note: Helpful applets
– try out some of the concepts touched on here by following the links
on our webpage for Applets->Linear Algebra and Applets>Scenegraphs
Andries van Dam
September 14, 2004
Transformation 2/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
2D Object Definition (1/3)
Lines and Polylines
•
Lines drawn between ordered points to create more
complex forms called polylines
• Same first and last point make closed polyline or
polygon
• If it does not intersect itself, called simple polygon
Convex vs. Concave Polygons
Convex: For every pair of
points in the polygon, the line
between them is fully contained
in the polygon.
Concave: Not convex: some two
points in the polygon are joined
by a line not fully contained in
the polygon.
Andries van Dam
September 14, 2004
Transformation 2/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
2D Object Definition (2/3)
Special polygons
triangle
square
rectangle
Circles
• Consist of all points equidistant from one
predetermined point (the center)
• (radius) r = c, where c is a constant
P1
y
r
r
P0
0 x
• On a Cartesian grid with center of circle at
origin equation is r2 = x2 + y2
Andries van Dam
September 14, 2004
Transformation 4/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
2D Object Definition (3/3)
Circle as polygon
•
Informally: a regular polygon with > 15 sides
(Aligned) Ellipses
A circle scaled along the x or y axis
6
6
5
5
4
4
3
3
2
2
1
1
0
0
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
Example: height, on y-axis, remains 3, while length, on x-axis,
changes from 3 to 6
Andries van Dam
September 14, 2004
Transformation 5/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
2D to 3D Object Definition
Vertices in motion (“Generative object description”)
•
Line is drawn by tracing path of a point as it moves
(one dimensional entity)
•
Square drawn by tracing vertices of a line as it moves
perpendicularly to itself (two dimensional entity)
•
Cube drawn by tracing paths of vertices of a square as
it moves perpendicularly to itself (three-dimensional
entity)
•
Circle drawn by swinging a point at a fixed length
around a center point
Andries van Dam
September 14, 2004
Transformation 6/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Building 3D Primitives
•
Triangles and tri-meshes
•
Often parametric polynomials, called splines
Curves
Patches
Boundaries are
Polynomial curves
In 3D
Andries van Dam
September 14, 2004
Transformation 7/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Useful concepts from Linear
Algebra
•
•
•
•
•
•
•
•
•
3D Coordinate geometry
Vectors in 2 space and 3 space
Dot product and cross product – definitions and uses
Vector and matrix notation and algebra
Properties (associativity but NOT commutativity)
Matrix transpose and inverse – definition, use, and
calculation
Homogeneous coordinates
You will need to understand these concepts
If you don’t think you do, go to the linear algebra
help session on Wednesday!
Andries van Dam
September 14, 2004
Transformation 8/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Short Linear Algebra
Digression: Vector and Matrix
Notation, A non-Geometric
Example (1/2)
Let’s Go Shopping
•
•
Need 6 apples, 5 cans of soup, 1 box of tissues, and 2
bags of chips
Stores A, B, and C (East Side Market, Whole Foods,
and Store 24) have following unit prices respectively
1 apple
1 can of
soup
1 box of
tissues
1 bag of
chips
East Side
$0.20
$0.93
$0.64
$1.20
Whole Foods
$0.65
$0.95
$0.75
$1.40
Store 24
$0.95
$1.10
$0.90
$3.50
Andries van Dam
September 14, 2004
Transformation 9/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
A Non-Geometric Example (2/2)
•
Let’s use a shorthand to represent the situation
(assuming we can remember order of items and
corresponding prices):
6 
5 
 
1 
 
2
•
Column vector for quantities, q:
•
Row vector for corresponding prices at the stores (P):
store A (East Side)
[0.20 0.93 0.64 1.20]
store B (Whole Foods)
[0.65 0.95 0.75 1.40]
store C (Store 24)
[0.95 1.10 0.90 3.50]
Andries van Dam
September 14, 2004
Transformation 10/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
What do I pay?
Let’s calculate for each of the three stores.
•
Store A:
4
totalCostA =
S PAiqi
i=1
= (0.20 • 6) + (0.93. • 5) + (0.64 • 1) + (1.20 • 2)
= (1.2 + 4.65 + 0.64 + 2.40)
= 8.89
•
Store B:
4
totalCostB =
S PBiqi = 3.9 + 4.75 + 0.75 + 2.8 = 12.2
i=1
•
Store C:
4
totalCostC =
Andries van Dam
S PCiqi = 5.7 + 5.5 + 0.9 + 7 = 19.1
i=1
September 14, 2004
Transformation 11/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Using Matrix Notation
•
We can express these sums more compactly:
6 
totalCost

0.20 0.93 0.64 1.20  
A
5
P( All )  totalCostB   0.65 0.95 0.75 1.40  
1 
totalCostC  0.95 1.10 0.90 3.50  
 2
•
The totalCost vector is determined by row-column
multiplication where row = price, column =
quantities, i.e. dot product of price row with
quantities column
– dot product is the sum of the pairwise multiplications
x 
y 
a b c d     ax  by  cz  dw
z 
 
 w
Andries van Dam
September 14, 2004
Transformation 12/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
2D Translation
•
Component-wise addition of vectors
x 
 x' 
dx 
v’ = v + t where v   , v'   , t   
 y
 y '
dy 
and
•
•
•
x’ = x + dx
y’ = y + dy
To move polygons: just translate vertices (vectors) and then
redraw lines between them
Preserves lengths (isometric)
Preserves angles (conformal)
Y
6
4
4
 
5
4
dx = 2
dy = 3
3
2
2
1 
 
1
0
1
2
3
4
5
6
7
8
9
10
X
Note: House shifts position relative to origin
NB: A translation by (0,0), i.e. no translation at all, gives us the identity matrix, as it should
Andries van Dam
September 14, 2004
Transformation 13/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
2D Scaling
•
Component-wise scalar multiplication of vectors
v’ = Sv where
x 
 x' 
v   , v'   
 y
 y '
and
sx 0 
S

0
s
y

x'  s x x
y'  s y y
•
•
Does not preserve lengths
Does not preserve angles (except when scaling is
uniform)
Y
6
5
sx  3
4
sy  2
3
2
2
1 
 
1
6 
2
 
3
1
 
9 
2
 
0
1
2
3
4
5
6
7
8
9
10
X
Note: House shifts position relative to origin
Andries van Dam
September 14, 2004
Transformation 14/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
2D Rotation
•
Rotation of vectors through an angle q
x 
 x' 
v   , v'   
 y
 y '
v’ = Rq v where
cosq
Rq  
sin q
 sin q 
cosq 
and
x’ = x cos q – y sin q
y’ = x sin q + y cos q
•
•
Proof is by double angle formula
Preserves lengths and angles
Y
6
5
q

6
5
6
4
3
2
q
1
0
1
•
2
3
4
7
8
9
10
X
Note: house shifts position relative to the origin
NB: A rotation by 0 angle, i.e. no rotation at all, gives us the identity matrix, as it should
Andries van Dam
September 14, 2004
Transformation 15/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
2D Rotation and Scale are
Relative to Origin
• Suppose object is not centered at origin?
• Solution: move it to the origin, then scale and/or
rotate, then move it back.
• We’d like to be able to compose successive
transformations…
Andries van Dam
16/32
September 14, 2004
Transformation
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Homogenous Coordinates
•
•
•
Translation, scaling and rotation are expressed (nonhomogeneously) as:
translation:
v’ = v + t
scale:
v’ = Sv
rotation:
v’ = Rv
Composition is difficult to express, since translation
not expressed as a matrix multiplication
Homogeneous coordinates allow all three to be
expressed homogeneously, allowing composition via
multiplication by 3x3 matrices
P2 d ( x, y )  Ph ( wx, wy, w), w  0
Ph ( x' , y ' , w), w  0
 x' y ' 
P2 d ( x, y )  P2 d  , 
 w w
•
w is 1 for affine transformations in graphics
Andries van Dam
September 14, 2004
Transformation 17/32
INTRODUCTION
TO
COMPUTER
What is
•
x 
y
 
 w
G RAPH I C S
?
P2d is intersection of line determined by Ph with the
w = 1 plane
W
Ph (x,y,w)
1
P2d (x/w,y/w,1)
X
Y
•
So an infinite number of points correspond to (x, y, 1) :
they constitute the whole line (tx, ty, tw)
Andries van Dam
September 14, 2004
Transformation 18/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
2D Homogeneous Coordinate
Transformations (1/2)
•
For points written in homogeneous
x 
coordinates  y ,
 
1 
translation, scaling and rotation relative to the origin
are expressed homogeneously as:
Andries van Dam
September 14, 2004
Transformation 19/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
2D Homogeneous Coordinate
Transformations (2/2)
•
Consider the rotation matrix
cos 
R( )   sin 
 0
•
 sin 
cos 
0
0
0
1
The 2 x 2 submatrix columns:
– are unit vectors (length=1)
– are perpendicular (dot product=0)
– are vectors into which X-axis and Y-axis rotate (are
images of x and y unit vectors)
•
The 2 x 2 submatrix rows:
– are unit vectors
– are perpendicular
– rotate into X-axis and Y-axis (are pre-images of x and y
unit vectors)
•
These properties of rows and columns preserve
lengths and angles of the original geometry.
Therefore, this matrix is a “rigid body”
transformation.
Andries van Dam
September 14, 2004
Transformation 20/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Examples
•
Translate [1,3] by [7,9]
•
Scale [2,3] by 5 in the x direction and 10 in the Y
direction
•
Rotate [2,2] by 900
Andries van Dam
September 14, 2004
Transformation 21/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
The Translation Matrix is very
Useful for Matrix Compositions
•
With the T matrix, can avoid unwanted translation
introduced when we scale or rotate an object not
centered at origin: translate the object to the origin,
perform the scale or rotate, then translate back.
House ( H )
•
T (dx, dy ) H
T (dx,dy ) R(q )T (dx, dy ) H
How would you scale the house by 2 in “its” y and
rotate it through 900 ?
House ( H )
•
R(q )T (dx, dy ) H
S (1,2) H
R( / 2) S (1,2) H
Remember: matrix multiplication is not commutative!
Hence order matters! (refer to the Transformation
Game at Applets->Scenegraphs)
Andries van Dam
September 14, 2004
Transformation 22/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
3D Basic Transformations (1/2)
(right-handed coordinate system)
y
x
z
•
1
0
Translation 
0

0
•
sx
0

0

0
Scaling
Andries van Dam
0
1
0
0
0
sy
0
0
0 dx 
0 dy 
1 dz 

0 1
0
0
sz
0
0
0
0

1
September 14, 2004
Transformation 23/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
3D Basic Transformations (2/2)
(right-handed coordinate system)
•
Rotation about X-axis
•
Rotation about Y-axis
• Rotation about Z-axis
Andries van Dam
0
1
0 cosq

0 sin q

0
0
 cosq
 0

 sin q

 0
cosq
 sin q

 0

 0
September 14, 2004
0
 sin q
cosq
0
0
0
0

1
0 sin q
1
0
0 cosq
0
0
0
0
0

1
 sin q
cosq
0
0
0
0
1
0
0
0
0

1
Transformation 24/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Homogeneous Coordinates
Some uses we’ll be seeing later
• Construction: putting sub-objects in their parent’s
coordinate system to build a hierarchical scene
graph
– transforming primitives in their coordinate system
• View volume normalization
– mapping arbitrary view volume into canonical view
volume along the z-axis
• Parallel (orthographic and oblique) and perspective
projection
• Perspective transformation
Andries van Dam
September 14, 2004
Transformation 25/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Skew/Shear/Translate (1/2)
•
Take a scene and “skew” it to the side

1
Skewq  
0

•
•
•
•
1 
tan q 
1 
Squares become parallelograms - x coordinates skew
to the right, while y coordinates stay the same
900 between axes becomes q
Like taking a deck of cards and pushing top to the
side – each card shifts relative to the one below it
Hmmm… Notice that the base of the house (at y=1)
remains horizontal, but shifts to the right…
Y
6
5
q
4

4
3
2
1
q
0
1
2
3
4
5
6
7
8
9
10
X
NB: A skew of 0 angle, i.e. no skew at all, gives us the identity matrix, as it should
Andries van Dam
September 14, 2004
Transformation 26/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Skew/Shear/Translate (2/2)
•
•
•
•
In fact, everything along the line y=1 stays on the line
y=1, but is translated to the right
Also, distance between points on this line is preserved
A 1D homogeneous coordinate translation looks like
a 2D skew transformation

1
0

1  1 dx 
tan q   

1  0 1 
original y-axis
1 1
T 

0 1
Andries van Dam
September 14, 2004
Transformation 27/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Transforms in Scene Graphs (1/3)
• 3D scenes are typically stored in a directed acyclic graph
(DAG) called a scene graph
–
–
–
–
Open Scene Graph (used in the Cave)
Sun’s Java3D™
X3D ™ (aka VRML ™)
Sense8’s WorldToolKit ™ (also used in the Cave)
• Typical scene graph format (there are hundreds of
packages!)
– objects (cubes, sphere, cone, polyhedra etc.) with basic defaults
(located at the origin with unit area of volume) stored as nodes
– attributes (color, texture map, etc.) and transformations are also
nodes in scene graph (labeled edges on slide 2 are an abstraction)
• For your assignments, you will deal with a much simpler
scene graph format
– attributes of each object will be stored as a component of the
object node (no separate attribute node)
– transform node will affect its subtree, but not siblings (unlike in
X3D, Open Scene Graph)
– transform node can only have one child
– only leaf nodes are graphical objects
– all internal nodes that are not transform nodes are group nodes
Andries van Dam
September 14, 2004
Transformation 28/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Transforms in Scene Graphs (2/3)
Let’s look more closely at the Scenegraph from slide 2 …
5. To get final scene
ROBOT
4. Transform subgroups
upper body
3. To make sub-groups
lower body
2. We transform them
stanchion
head
trunk
base
arm
1. Leaves of tree are standard size object primitives
Andries van Dam
September 14, 2004
Transformation 29/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Transforms in Scene Graphs (3/3)
• In the scene graph below, transformation t0 will
affect all objects, but t2 will only affect obj2 and
one instance of group3 (which includes an
instance of obj3 and obj4)
– t2 doesn’t affect obj1, other instance of group3
group3
root
t5
t0
group1
t1
t6
obj3
obj4
t2
object nodes (geometry)
obj1
group3
group2
t3
obj2
transformation nodes
group nodes
t4
group3
• Note that if you want to use multiple instances
of a sub-tree, such as group3 above, you must
define it before it’s used
– this is so that it’s easier to implement
Andries van Dam
September 14, 2004
Transformation 30/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Composing Transformations in a
Scene Graph (1/2)
• Typically, transformation nodes contain at least
a matrix that handles the transformation;
additionally, it may contain individual
transformation parameters
– refer to scene graph hierarchy applet by Dave Karelitz
(URL on slide 2)
• To determine the final composite transformation
matrix (CTM) for an object node, you need to
compose all parent transformations during
prefix graph traversal
– exact detail of how this is done varies from package to
package, so be careful
Andries van Dam
September 14, 2004
Transformation 31/32
INTRODUCTION
TO
COMPUTER
G RAPH I C S
Composing Transformations in a
Scene Graph (2/2)
• An example:
g1
m1
m2
g2
o1
m3
g: group nodes
m4
g3
o2
m: matrices of the transform nodes
o: object nodes
m5
o3
- for o1, CTM = m1
- for o2, CTM = m2* m3
- for o3, CTM = m2* m4* m5
- for a vertex v in o3, its position in the world
(root) coordinate system is:
CTM v = (m2*m4*m5)v
Andries van Dam
September 14, 2004
Transformation 32/32