CS580
Decomposing Transformations
and
Defining Spaces
Ulrich Neumann
CS580
Computer Graphics Rendering
Decomposing Transformations
Given a 4×4 view/projection matrix – we can decompose it into T R S or T S R (assume S is uniform scaling)
T is upper three elements of right column
M is 3×3 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
a b c xt
d e f yt
g h 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 3×3 M by K : R = (M)/K
R is a normalized (“unitary” or “pure”) 3×3 rotation matrix
S is a 3×3 diagonal matrix with elements = K : the scale factor extracted from M
M=RS
a b c xt
d e f yt
g h 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 (row•col = 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 4×4 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 0 1/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=11 Z=21
C B 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 = 1 zm = ½ 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)
Xiw camera position and orientation (per frame)
Xpi camera FOV (focal length or zoom) (per frame)
Xsp mapping 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
Op Stack STACK Behavior
Init stack [I] 0 setup I at Top Of Stack (TOS). TOS is an index into an array
Push [A] [J] 1 push 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] 2 Pop 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)
Xpi depends 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
*