[SOLVED] CS CS580

CS580

Decomposing Transformations
and
Defining Spaces
Ulrich Neumann
CS580
Computer Graphics Rendering

Decomposing Transformations
Given a 44 view/projection matrix we can decompose it into T R SorT S R(assume S is uniform scaling)
T is upper three elements of right column
M is 33 in upper left corner and M = R S or S R
R is normalized M so all ||columns|| and ||rows|| = 1
S is built from the scale factor used for normalization

T
M=RS

ab cxt
de f yt
gh i zt
0 0 0 1

Normalizing R
R is normalized M so all ||columns|| and ||rows|| = 1
S is built from scale factor used for normalization

Compute any row or col magnitude of M as scale factor

K = ||Mrow|| = (a2 + b2 + c2)1/2(a,b,c, are top row of M, for example)
divide all elements of 33 M by K:R = (M)/K
R is a normalized (unitary or pure) 33 rotation matrix

S is a 33 diagonal matrix with elements = K : the scale factor extracted from M

M=RS

ab cxt
de f yt
gh i zt
0 0 0 1

Inverse Transformations
Given [Rac], its inverse [Rca] = [Rac]-1 = [Rac] T

transpose = inverse for unitary (pure) rotation
row and col vectors are orthogonal (rowcol = 0)
||row|| = ||col|| = 1

Given [Tac], its inverse [Tca] = [Tac]-1 = [-Tac]

negate 3 elements of translation matrix

Given [Sac], its inverse [Sca] = [Sac]-1 = [1/Sac]

replace 3 diagonal elements with their reciprocals

Inverse of General 44 Transformations

Given [Xac] = T S R
build the inverse : [Xac]-1 = R-1 S-1 T-1

it must be the inverse because:

I = [Xac]-1 [Xac] = [R-1 S-1 T-1] [T S R]

Perspective Projection
Perspective projection of (0,Y,Z) onto the Z=0 plane(view plane) occurs at point a=(0,y,0)
Camera focal point is at z = -d(0,0,-d)

Use similar triangles ratio to compute y-coord at point a
y/d = Y/(Z+d)
y = Yd/(Z+d) = Y/[(Z/d)+1]
Do the same for X and Y coords to find a projected point (x,y,0) on the image plane x=X/[(Z/d)+1]y=Y/[(Z/d)+1]

0,Y,Z
a
z= -d
y-axis within Z=0 plane
z-axis
(Figure drawn in X=0 plane)

Projection Transformation
X, Y, and Z are projected by a 4D transformation

[ X, Y, Z, (Z/d)+1 ] =

Divide by w = (Z/d)+1 to
get projected point[x, y, z] =

Note : projected 3D coords require divide after perspective transformation (divide by w = (Z/d)+1)
Note: other projection formulations are also used
e.g., view point is z=0, and image plane at z=d
Geometry and results are the same for any coordinate system

1 0 0 0
0 1 0 0
0 0 1 0
0 01/d 1

X
Y
Z
1
X
(Z/d)+1

Z
(Z/d)+1

Y
(Z/d)+1

, ,

Interpolating Z-Projections

Point B is the mid-point between edge points A and C
The projection b (for Z=11) is not at the mid-point of projected points a and c on the image plane
Linear interpolation of Z values from a (Z=21) to c (Z=1) would produce Z=11 at point b, not at point b
b is midpoint between a and c in the image plane
Interpolated Z value at b would be >11, and incorrect for a z buffer test at that pixel (e.g., the small square vertex)
For interpolation of Z during rasterization, we must do the perspective transformation of Z onto the Z = 0 plane and interpolate the transformed z-values z = Z/[(Z/d)+1]

Z=1 Z=11Z=21
CB A

a
bc
Z= -d
Z= 0

b

Z Interpolation Example
Setup known geometry with d = 1 (no loss of generality)
A = (0, -h, 0) B = (0, 2h, 3)Affine
a = (0, -h, 0)b = (0, 2h/4, 3/4) = (0, h, 3/4) Perspective

ZM = d = 1zm = from z = Z/(Z/d)+1

Interp (za, zb) = at zm
Interp (Za, Zb) = 2 at Zm

(blue dot does not project to M)

b
a
A
B
Y
d = 1
Z
h
2h
M
m
1
2
3

Examine projected value of z = Z/(Z/d+1)
For Z=0 (points in view plane): X=x, Y=y, z=0
Points in view plane (Z=0) project to themselves
For Z=-d, z = – (at Z of the focal point)
FP exceptions (singularity) occur with Z = -d !
Implement a clip (cull) plane at Z = 0 to discard any tri with a negative Z value at any vertex test Z sign before divide by w
For large Z ( distance), perspective z > d
Asymptotic curve of Z vs. z approaches d and causes resolution problems for points at high values of Z
different Z values map to the same z

See Graphics Hardware Workshop
1998 2002 for
Optimal Depth Buffer or
Low-Cost Graphics Hardware
papers

Z
z
d

*

Spaces : coordinate systems (1)
screen perspective (NDC) image (camera) world model
screen coords are pixel coords for FB

Origin in UL image corner (RHC)
Center of image plane is ~(xres/2, yres/2)
Visible range : x [0, xres-1], y [0, yres-1], z [0, MAXINT]

perspective a.k.a. NDC (Normalized Device Coords)
Origin at center of image plane (LHC)
Visible range : (x, y) [-1,1], and z [0,1]

image a.k.a. camera-space
Origin at center of image plane (LHC)
No meaningful range bounds on x, y, z

x
y
z-in

x
y
z-in

x
y
z-in

Spaces : coordinate systems (2)
screen perspective (NDC) image (camera) world model
world has app-defined origin/axis used as
reference for scene object locations(LHC)

No meaningful range bounds on x, y, z

model is a coord frame defined for
each model, and is LHC for teapot
No meaningful range bounds on x, y, z

Note that all HW coord systems
are left-handed except for
screen, which is right-handed

x
y
z-in

x
y
z-in

Transforms:
screen Xsp perspective (NDC) Xpi image Xiw world Xwm model
Transforms are defined between spaces
Renderer maintains the complete transformation Xsm
Application/animation controls each transform for
different purposes

Xwm object positions (per frame or per object/instance)
Xiwcamera position and orientation (per frame)
Xpi camera FOV (focal length or zoom)(per frame)
Xspmapping NDC image to frame-buffer (per frame)

Xwm is the transformation that changes many times per-frame so it should be easy to change

Managing Xforms
A stack structure is commonly used with push/pop operations
Push matrices in sequence, from screen to model
Pop as needed to allow pushes of new modified matrices
Complete all pop/pushes needed to build Xsm for an object
Top of stack (TOS) matrix is used during rendering and assumed to be the complete Xsm transform for triangle rendering

Stack concatenates transforms, rather than just storing them
Push A Top of stack = Q0 = (A)
Push B Top of stack = Q1 = (Q0B) = (AB)
Push C Top of stack = Q2 = (Q1C) = (ABC)
Pop Top of stack = Q1 = (AB)
Push D Top of stack = Q2 = (Q1D) = (ABD)

Matrix Stack Behavior
OpStackSTACK Behavior
Init stack[I] 0 setup I at Top Of Stack (TOS).TOS is an index into an array

Push [A][J] 1push computes [J] = [I] [A] and [J] is stored at new TOS
[I]0 Append A to right of prior TOS and save at TOS index 1

Push [B][K] 2[K] = [J] [B] Append B to right of prior TOS [J] and
[J] 1 save at new TOS index 2
[I]0

Push [C][L] 3[L] = [K] [C] Append C to right of prior TOS [K]
[K] 2 Note:L = concatenation of all pushed (A, B, C) matrices
[J] 1
[I]0

Pop [K] 2Pop simply decrements TOS back to prior TOS array index
[J] 1
[I]0

*

Initializating the Matrix Stack
The Renderer is responsible for creating and initializing Xsw
Convention is to build and use a transform stack
Application passes high-level parameters that enable the Renderer to build Xsw on the stack before any tris are drawn

Xsp depends on frame buffer params (xs, ys, MAXINT)
Xpidepends on camera FOV
Xiw depends on camera pose
Xwm is set by the Application after Renderer initialization of stack to Xsw when the application is ready to place and draw objects
The Renderer does not care how the Xwm matrices are created they are simply appended to the stack using push/pop commands
The application normally pushes at least one matrix Xwm before rendering any object

*