CS计算机代考程序代写 data structure 3D Modelling Transformations

3D Modelling Transformations
1

Intended Learning Outcomes
 Understand the use of homogeneous coordinates
 Learn different types of 3D transforms and the concept
of composite transform
 Able to use coordinate transform to switch between one
coordinate frame to another
 Able to use OpenGL to implement coordinate transform
2

Homogeneous coordinates
 Represent a n-dimensional entity as a (n+1)- dimensional entity
 Allow all linear transforms to be expressed as matrix multiplications; eliminate matrix addition/subtraction
3

Linear Transform
 P2 =M1P1 +M2
P1 n-dimensional points (n x 1 column vector) P2 Transformed n-dimensional points
(n x 1 column vector)
M1 n x n square transform matrix M2 n x 1 column transform vector
 Homogeneous coordinates allow us to express the multiplicative term M1 and the addition term M2 in a common 4 x 4 matrix. This is achieved by adding one dimension w.
4

3D Point
A 3D point (n = 3) can be expressed as
 (X, Y, Z) Euclidean coordinates
 (XW, YW, ZW, W) Homogeneous coordinates WWW
X=X Y=Y Z=Z WWW
 W can be any non-zero value.
5

3D Translation
 Euclidean
P2 = P1 + T(tX, tY, tZ)
 Homogeneous P2 = T(tX, tY, tZ)P1
Note : W2 = W1=1
X2 1 0 0X1 tX Y =0 1 0Y +t 
 2    1   Y  Z2 0 0 1Z1 tZ
X2 1 0 0 tXX1 Y  0 1 0 t Y 
 2 = Y  1  Z2 0 0 1 tZZ1
W2 0 0 0 1W1 6

3D Rotations
 Rotation about an axis
CCW ⇒ POSITIVE rotation Right Hand Rule
7

2D Rotations about the origin
 About a common coordinate system X-Y Y
(X2, Y2)
(X1, Y1)
X2 cosθ −sinθX1 Y =sinθ cosθ Y 
(0, 0)
 2    1  X
Equivalent to rotation about Z axis, which is pointing out of paper
8

Rotation about Z
 Euclidean P2=RZ(θ)P1
X2 cosθ −sinθ 0X1 Y =sinθ cosθ 0Y 
 Homogeneous
P =R (θ)P 2Z1
X  cosθ −sinθ 0 0X  2 1
 2    1  Z20 0 1Z1
Y =sinθ cosθ 0 0Y 
2 1 Z2  0 0 1 0Z1
W0001W
 2   1
9

Rotation about X
 Euclidean P2=RX(θ)P1
X2 1 0 0 X1 Y =0 cosθ −sinθY 
 Homogeneous
P =R (θ)P 2X1
X1 0 0 0X 2 1
 2    1  Z2 0 sinθ cosθZ1
Y =0 cosθ −sinθ 0Y  2 1
Z2 0 sinθ cosθ 0Z1 W0001W
 2   1
10

Rotation about Y
 Euclidean P2=RY(θ)P1
X2 cosθ 0 sinθX1 Y=0 1 0Y
 Homogeneous
P =R (θ)P 2Y1
X cosθ 0 sinθ 0X 2 1
 2    1  Z2 −sinθ 0 cosθZ1
Y=0100Y 2 1
 Z2  −sinθ 0 cosθ 0 Z1  W0001W
 2   1
11

Scaling about the origin
 Euclidean P2=S(sX, sY, sZ)P1
 Homogeneous
P =S(s , s , s )P 2 XYZ1
Xs 000X 2X 1
 X 2   s X 0 0  X 1   Y  =  0 s 0  Y 
2 Y 1 Z2 0 0 sZZ1
Y=0s00Y 2 Y 1 Z200sZ 0Z1
W0001W
 2   1
12

Reflection about the X-Y plane
 Euclidean P2=RFZP1
 Homogeneous
P =RF P 2Z1
X 1 0 0 0X 2 1
X2 1 0 0X1 Y=0 1 0Y
 2    1  Z2 0 0 −1Z1
Y=0100Y 21 Z2 0 0 −1 0Z1
W 0001W
 2   1
13

Shearing about the Z axis
 Euclidean P2=Shz(a,b)P1
 Homogeneous
P =Sh (a,b)P 2 Z 1
X 1 0 a 0X 2 1
X2 1 0 aX1 Y =0 1 bY 
 2    1  Z2 0 0 1Z1
Y=01b0Y 2 1 Z2 0 0 1 0Z1
W 0001W
 2   1
14

Affine Transform
x a a  2   11 12
a x b 13  1   1 
 y2  =  a21 a22 zaaazb
a23  y1  +  b2   2   31 32 33  1   3 
 aij and bi are constants.
 a linear transformation
 // lines are transformed to // lines
 Translation, rotation, scaling, reflection, shearing are special cases
 Any affine transform can be expressed as composition of the above 5 transforms
15

Composite Transformation
 A number of (relative) transformations applied in sequence
 Models the complex movement of an object in the world coordinate system
 The transformation is pre-computed where possible.
 In practice, ONLY the final 4 x 4 composite transformation needs to be stored.
16

E.g. 1 Rotation about an axis // to X axis.
 Let (Xf, Yf, Zf) be a point on the axis. The composite rotation is
P2 = T-1Rx(θ)T P1 T = T(-Xf, -Yf, -Zf)
17

 For the composite transformation
1 0 0 Xf1 0 0 01 0 0 −Xf
0 1 0 Y0 cosθ −sinθ 00 1 0 −Y  f  f
0 0 1 Zf 0 sinθ cosθ 00 0 1 −Zf  000100 010001
 Only the product
100 0
0 cosθ −sinθ −Y cosθ+Z sinθ+Y  fff
0 sinθ cosθ −Yf sinθ −Zf cosθ +Zf  000 1
is stored
18

E.g.2 Scalingabout(Xf,Yf,Zf)
 P2 = T-1S(sX, sY, sZ)T P1 T = T(-Xf, -Yf, -Zf)
Similarly, only the final 4 x 4 composite transformation is stored
19

Concept
 A composite transformation may have two physical meaning:
 Either
It represents a physical action
 Or
It represents a change of coordinate system
20

3 Kinds of Coordinate System in CG
 Each object defined in their own natural coordinate system – Modelling coordinate system (MC)
 All objects being placed in a common world coordinate system (WC)
 For correct viewing by a camera, objects need to be expressed in a common viewer or camera coordinate system (VC, CC)
MC → WC → VC/CC
21

A point in two different coordinate sy.
 The SAME point has DIFFERENT coordinates in DIFFERENT coordinate systems
Y2
Y1
P(2) =R(−θ)P(1)
X2 cos(−θ) −sin(−θ)X1
X1
θ
Y =sin(−θ) cos(−θ) Y   2    1 
(X2, Y2) ~ (X1, Y1) X2
22

 P(i) A point in coordinate system i
 Mj←i 4 x 4 transformation that transforms a point in coordinate system i to
coordinate system j  P(j) = Mj←i P(i)
23

 Rule 1 for computing Mj←i :
Mj←i is the inverse of the transformation that takes the ith coordinate system frame as if it is an object to the jth
coordinate system frame position, all the time using the ith coordinate system as the reference coordinate system
As Mj←i = Mi←j-1, we have the alternative rule: 24

 Alternative rule (rule 2) for computing Mj←i :
Mj←i is the transformation that takes the jth coordinate system frame as if it is an object to the ith coordinate system frame position, all the time using the jth
coordinate system as the reference coordinate system
 which rule to use depends on which coordinate system is easier to get on hand
25

Mj←i is the INVERSE of the transformation that takes the ith coordinate system frame as if it is an object to the jth coordinate system frame Proof
Suppose we have two coordinate systems xi-yi-zi and xj-yj-zj. defined in the xi-yi-zi coordinate system. Let
xi =(1,0,0)T → xj =(a11,a21,a31)T +(tx,ty,tz)T yi =(0,1,0)T → yj =(a12,a22,a32)T +(tx,ty,tz)T zi = (0, 0, 1)T → zj = (a13, a23, a33)T + (tx, ty, tz)T
Treat xi-yi-zi and xj-yj-zj as two objects that consist of two sets of points, both
where all the coordinates are defined in the xi-yi-zi coordinate system. → means “corresponds to”.
The transformation T that transforms the three points xi, yi, zi to xj, yj, zj in the xi-yi-zi coordinate system is thus
a11 T = a21 a31
a12 a13 a22 a23 a32 a33
tx  ty  tz 
0001
However, it can also be interpreted as changing from coordinate system j to coordinate system i. Thus
P(j) = (1, 0, 0)T → P(i) = (a11, a21, a31)T + (tx, ty, tz)T P(j) = (0, 1, 0)T → P(i) = (a12, a22, a32)T + (tx, ty, tz)T P(j) = (0, 0, 1)T → P(i) = (a13, a23, a33)T + (tx, ty, tz)T
Since any arbitrary P(j) can be written as λ1(1,0,0)T +λ2(0,1,0)T +λ3(0,0,1)T , where λ1,λ2,λ3 are constants, it follows that Mi←j =T
Since M = M −1 , j←i i← j
Mj←i =T−1
This gives the rule
Mj←i is the INVERSE of the transformation that takes the ith coordinate system frame as if it is an object to the jth coordinate system frame
26

OpenGL Geometric Transformations
 4 x 4 translation matrix glTranslatef (tx, ty, tz);
 4 x 4 rotation matrix
glRotatef (theta, vx, vy, vz);
 4 x 4 scaling matrix glScalef (sx, sy, sz);
 4 x 4 reflection matrix
glScalef (1, 1, -1); // reflection about Z axis
 4 x 4 shearing matrix
glMultMatrixf (matrix); // matrix is a 16 element
// matrix in column-major order
27

OpenGL Matrix Operations
 Calls the current matrix, responsible for geometrical transformation
glMatrixMode (GL_MODELVIEW);
(do not confuse with glMatrixMode (GL_PROJECTION),
which is responsible for projection transformation)  Assign identity matrix to current matrix
glLoadIdentity ( );
28

 Current matrix is modified by (relative) transformations  E.g. glTranslatef, glScalef, glRotatef …
 The meaning of the relative transformations may either be physical action or coordinate transformations
 Current matrix are postmultiplied. Last operation specified is first operation performed, like a LIFO stack
29

Let C be the composite matrix
 Example 1
glMatrixMode (GL_MODELVIEW) glLoadIdentity ( ); // C = identity matrix
glTranslatef (-25, 50, 25); // C = T(-25,50,25)
glRotatef (45, 0, 0, 1); // C = T (-25,50,25)RZ(45o) glScalef (1, 2, 1); // C = T (-25,50,25)RZ(45o) S(1,2,1)
30

 Example 2
glMatrixmode (GL_MODELVIEW) glLoadIdentity ( );
glScalef (1, 2, 1);
glRotatef (45, 0, 0, 1);
glTranslatef (-25, 50, 25); // C = S(1,2,1)RZ(45o)T(-25,50,25)
Note: the order of the transformation is important
31

OpenGL Matrix Stacks
 OpenGL has a stack for storing the relative transformations
 Stack is a LIFO data structure
 Stores intermediate results
 Push the current matrix into the stack glPushMatrix ( );
 Pop the current matrix from the stack glPopMatrix ( );
Note: Very useful for modelling hierarchical structures
32

 Example
glMatrixMode (GL_MODELVIEW)
glLoadIdentity ( ); // MV = identity matrix
glTranslatef (-25, 50, 25); // MV = T(-25,50,25) glRotatef (45, 0, 0, 1); // MV = T (-25,50,25)RZ(45o)
glPushMatrix ( );
glScalef (1, 2, 1); glTranslatef (0, 0, 10); glPopMatrix ( );
// MV is pushed to the stack
// MV = T (-25,50,25)RZ(45o) S(1,2,1) // MV = T RZ(45o)S(1,2,1) T(0, 0, 10)
// MV = T (-25,50,25)RZ(45o)
33

References
 Text: Sec 7.2 -7.3, 9.1 – 9.7 (except quaternion method), 9.8. The text uses a different exposition of the coordinate transformation method.
 Our discussion of coordinate transformation follows: Foley et. al., Computer Graphics, 2nd Ed., 222-226
 The two methods of coordinate transformation are conceptually the same.
34