Transcript Math for Programmers

Linear Transformations
and Matrices
Jim Van Verth ([email protected])
Lars M. Bishop ([email protected])
Transformation
• Have some geometric data
• How to apply functions to it?
• Also desired: combine multiple steps
into single operation
• For vectors: linear transformations
Essential Math for Games
Transformations
• A transformation T:VW is a function that
maps elements from vector space V to W
• The function
f(x, y) = x2 + 2y
is a transformation because it maps R2 into R
Essential Math for Games
Linear Transformation
• Two basic properties:
 T(x + y) = T(x) + T(y)
 T(ax) = aT(x)
• Follows that
 T(0) = 0
 T(ax+y) = aT(x) + T(y)
Essential Math for Games
Linear Transformations
• Basis vectors span vector space
• Know where basis goes, know where
rest goes
• So we can do the following:
 Transform basis
 Store as columns in a matrix
 Use matrix to perform linear transforms
Essential Math for Games
Linear Transforms
• Example:
• (1,0) maps to (1,2)
• (0,1) maps to (2,1)
• Matrix is
Essential Math for Games
What is a Matrix?
• Rectangular m x n array of numbers
• M rows by n columns
• If n=m, matrix is square
Essential Math for Games
Matrix Concepts
• Number at row i and column j of matrix
A is element Aij
• Elements in row i make row vector
• Elems in column j make column vector
• If at least one Aii (diagonal from upper
left to lower right) are non-zero and all
others are zero, is diagonal matrix
Essential Math for Games
Transpose
• Represented by AT
• Swap rows and columns along diagonal
• ATij = Aji
• Diagonal is invariant
Essential Math for Games
Transpose
• Transpose swaps transformed basis
vectors from columns to rows
• Useful identity
Essential Math for Games
Transforming Vectors
• Represent vector as matrix with one
column
• # of components = columns in matrix
• Take dot product of vector w/each row
• Store results in new vector
Essential Math for Games
Transforming Vectors
• Example: 2D vector
• Example: 3D vector to 2D vector
Essential Math for Games
Row Vectors
•
•
•
•
Can also use row vectors
Transformed basis stored as rows
Dot product with columns
Pre-multiply instead of post-multiply
• If column default, represent row vector by vT
Essential Math for Games
Row vs. Column
• Using column vectors, others use row
vectors
 Keep your order straight!
Column vector order (us, OpenGL)
Row vector order (DirectX)
• Transpose to convert from row to
column (and vice versa)
Essential Math for Games
Matrix Product
• Want to combine transforms
• What matrix represents
• Idea:
?
 Columns of matrix for S are xformed basis
 Transform again by T
Essential Math for Games
Matrix Product
or
• In general, element ABij is dot product
of row i from A and column j from B
Essential Math for Games
Matrix product (cont’d)
• Number of rows in A must equal
number of columns in B
• Generally not commutative
• Is associative
Essential Math for Games
Block Matrices
• Can represent matrix with submatrices
• Product of block matrix contains sums
of products of submatrices
Essential Math for Games
Identity
• Identity matrix I is square matrix with
main diagonal of all 1s
• Multiplying by I has no effect
 AI = A
Essential Math for Games
Inverse
• A-1 is inverse of matrix A such that
• A-1 reverses what A does
• A is orthogonal if AT = A-1
 Component vectors are at right
angles and unit length
 I.e. orthonormal basis
Essential Math for Games
Computing Inverse
•
•
•
•
Only square matrices have inverse
Inverse doesn’t always exist
Zero row, column means no inverse
Use Gaussian elimination or Cramer’s
rule (see references)
Essential Math for Games
Computing Inverses
• Most interactive apps avoid ever
computing a general inverse
• Properties of the matrices used in most
apps can simplify inverse
• If you know the underlying structure of
the matrix, you can use the following:
Essential Math for Games
Computing Inverse
• If orthogonal, A-1 =AT
• Inverse of diagonal matrix is diagonal
matrix with A-1ii = 1/Aii
• If know underlying structure can use
• We’ll use this to avoid explicit inverses
Essential Math for Games
Storage Format
• Row major
 Stored in order of rows
 Used by DirectX
Essential Math for Games
Storage Format (cont’d)
• Column Major Order
 Stored in order of columns
 Used by OpenGL, and us
Essential Math for Games
Storage Format (cont’d)
• Note: storage format not the same as
multiplying by row vector
• Same memory footprint:
 Matrix for multiplying column vectors in
column major format
 Matrix for multiplying row vectors in row
major format
• I.e. two transposes return same matrix
Essential Math for Games
System of Linear Equations
• Define system of m linear equations
with n unknowns
b1 = a11x1 + a12 x2 + … + a1n xn
b2 = a21x1 + a22 x2 + … + a2n xn
…
bm = am1x1 + am2 x2+ … + amn xn
Essential Math for Games
System of Linear Equations
• Matrix multiplication encapsulates
linear system
Essential Math for Games
System of Linear Equations
• Matrix multiplication encapsulates
linear system
• Solve for x
• Multiplying by inverse imprecise
• Use Gaussian elimination, or other
methods (see refs)
Essential Math for Games
References
• Anton, Howard and Chris Rorres,
Elementary Linear Algebra, 7th Ed,
Wiley & Sons, 1994.
• Axler, Sheldon, Linear Algebra Done
Right, Springer Verlag, 1997.
• Blinn, Jim, Notation, Notation, Notation,
Morgan Kaufmann, 2002.
Essential Math for Games