Get into GameDev:
​cheat-codes for gamedev interviews

​━ Maths ━

Introduction

Work - In - Progress

Hi, you're early! I haven't ported this page over from my draft just yet but you can preview it at the link below for early-access:
​tinyurl.com/gamedevStudySheet

Matrices

Matrices are multidimensional number structures. They are extremely important to game development and you need to be very good friends with them, if not lovers.

Matrix Mulitplication
  • It is associative aka (AB)C = A(BC)
  • ​It is not commutative AB != BA​
When we refer to matrices we often reference their bounds as MxN. MxN stands for the "row count by column count" aka "height by width".

​If you take a matrix A that is MxN then it can only be multiplied against a matrix B if that matrix has N rows. In other words, if A's dimension are ExF and B's are MxN then when we put them together like this (ExF)(MxN), F and M (the two touching numbers) need to be equal. And we also know that the resulting matrix will be of dimension ExN. So if I told you we have a 3x1 and a 1x7, you immediately know that multiplying them is valid (because the 1's are equal) and that the result will be 3x7 (because those are the values on either end).

To obtain the result of a cell within the resulting matrix of AB, you first determine the row of A and the column of B that correspond to that cell. Then go left to right through each entry of A's row and each entry of B's column to create a series of pairs. Multiply each of the pairs and then sum the result for the cell's value.
Rotation Matrices
Rotations can be used to represent rotational data. However, this is usually for storage and not for runtime interpolation purposes because Euler angle representations are susceptible to gimble lock. However these matrices are still very common because they are easy to reason with when you need to apply a known rotation to object or when you want to transform a object transform's rotation between world and local space.

I have been asked on interviews before to construct rotation matrices from scratch so this is a skill you may need to invest in. The image below shows the 2D-rotation-matrix construction and how, using matrix multiplication, it can transform [y, x]^T into a new vector. Specifically, the below rotation matrix represents a rotation in the xy-plane counterclockwise through an angle θ about the origin. Here's a nice Khan Academy lecture on 2D-rotation-matrix construction: Video Link.
By the way... that "^T" term in the previous paragraph means transpose and it will always refer to a counter-clockwise rotation of the data so that I can reference vertical columns in text where sadly I can only write them out to appear as rows.
​
Things get a little more tricky in 3D where you will need to use a separate formula to represent each of the axis of rotation.
Practice Question: Construct a rotation matrix that represents a rotation of 90-degrees counter-clockwise through the xy-plane.

You can multiply rotation matrices together to represent to yield a new valid rotation matrix that is the result of both rotations. The order of this operation matters because unlike scalar multiplication, matrix multiplication is not commutative AB != BA. Rotations are applied from right to left, the input always will go on the right hand side of an equation like the one shown in the 2D case above (the xy vector is on the right of the rotation matrix).
Practice Question: Construct a rotation matrix that represents a rotation of 90-degrees counter-clockwise through the xy-plane followed by a rotation of 45-degrees counter-clockwise through the yz-plane.

​Something that is really cool about rotation matrices is that each column of the matrix represents an axis vector and together they define a basis. This is really important so I a have illustrated the concept below. On the left we have the standard basis and on the right we have a 90 degree counter clockwise rotation around the Z axis. As you can see, the vectors representing each of these columns illustrate the rotation. The red vector has moved on the right side of the image to be where the green was. I used this plotter for the visualization. I recommend you take some time to explore the tool and see how rotation matrices can affect vectors by playing with the values and plugging them in.
By the way... I  specifically used the colors red, green, and blue to represent x, y, and z. This is fairly typical and you can remember the relationship by remembering the order RGB = XYZ. Whenever I forget what a green vector represents in a transform visualization I think in my head "RGB" and then realize green is the middle one and therefore must be Y.
​
Determinant
The determinant of a matrix is a scalar of the volume/area represented by a matrix. If the determinant of a rotation matrix (or any transformation matrix) is positive, then that means the transformation will maintain the orientation or “handedness” of the input, otherwise it will reverse the handedness. The main role of the determinant is for determining a matrix's inverse. A determinant is denoted by vertical bars around a matrix such as |A|. Below are the determinant formulae for a 2D and 3D matrix.
Orthogonal Matrices
All rotation matrices are orthogonal matrices, this means they are real square matrices whose columns and rows are orthonormal vectors. Two vectors are orthogonal if their dot product is 0. Two vectors are orthonormal if they are orthogonal and their lengths are both 1.
Orthogonal matrices have the following properties:
  • Each column/row vector is unit length. Therefore if you take anyone of the vectors v, then v • v = 1
  • Each column/row vector is orthogonal to all other columns/rows. Therefore if you take one row vector v, and any other row vector y, then v • y = 0. Furthermore, the collection of orthogonal columns/rows forms a basis. 
  • They are square (their row count equals their column count).
  • Their inverse is their transpose aka M^T = M^-1 which is a huge deal! We are going to go into more details about matrix inverses later, but for now, just know that the inverse of a matrix is expensive to calculate! So calculating the transpose instead means major savings.
  • Their determinant is either +1 or -1. This implies that the magnitude of a vector's scale is unchanged by a rotation but the direction may be changed which intuitively makes sense (thing don't become smaller when you turn them but they may change direction).
  • The product of an orthogonal matrix M with it's transpose will yield the identity matrix aka M • M^T = I
Rigid Body Transform Matrices
The RB transform matrix is the most iconic matrix in all of game development. I would advise you to memorize its structure on the right. Observe that the top left (red) 3x3 matrix contains both rotation and scaling data. This 3x3 is not quite a rotation matrix because, due to the scaling, its columns are not unit length. The translation data is stored separately in the bottom (blue) 1x3 row. The remainder of the 4x4 transform matrix is filled by a bottom-right (white) value of 1 and a top-right (grey) 3x1 zero vector.

We will soon discuss a few reasons why we often store and manipulate transform data in this format, but first I want to clarify that since the grey & white right hand column's values are static (they will always be a zero vector and a 1) we usually don't store that column at all. This 4x4 matrix is "dehydrated" and stored as a 4x3 (for a 20% space savings) and only rehydrated into its full glorious 4x4 form at runtime. For this reason, some developers refer to it as a "4x3" but it is, in reality, a 4x4.  
It's also important to know that depending on the convention of the engine, the (blue) translation vector and (grey) zero vector may be swapped. Later we will look at an example in this alternative format.
TODO: what convention does havok/ue4/unity use? Do they use 4x3 or 3x4?
Here's a great Twitter Thread which outlines some of the useful properties of the "4x3" structure:
  • Inverse of a "4x3" is always a "4x3"
  • Inverse rotation matrix is always a 3x3 in the top-left of a 4x4 with a 1 in the bottom right position.
  • Imagine the diagonal values of the (red) 3x3 rotation & scaling matrix are x, y, z  (starting from the top left and down to the bottom right of the 3x3). Using these values, we can easily derive...
    • An inverse scaling vector [ 1/x  1/y  1/z ]
    • An inverse translation vector [ -x  -y  -z ]

Due to these properties this is the most common way to store and manipulate the transform data of gameobjects. However, it has a glaring drawback which is that it mangles the rotation and scaling data into one 3x3 matrix. It can be difficult or impossible to separate that data once it has been mangled depending on what are acceptable rotation and scaling values. 
​
This was a major problem I ran into on Fortnite which led to objects rotating whenever they were scaled. To fix this issue, I ultimately had to save the scale vector into a separate data structure so that the red 3x3 only held rotation data. That's because though we know each column of a rotation matrix will have a unit length vector, we do not know if that vector will point one direction or another. If scaling is only ever positive then this is not an issue but if we store negative scaling data within a transform matrix then it is unrecoverable, there will be no way to differentiate the direction of the rotational basis vectors from the sign of the scaling factor. As a stack overflow contributor explains, "Sometimes you can't tell flip (negative scale) from rotation, e.g. an image flipped horizontally and vertically is identical to the image rotated by 180 degrees." Sometimes in videogames we often don't include scaling within the transform data at all. For example in Call of Duty, the soldiers are never going to scale in size so the transform data does not need to hold scaling data.

Matrix Inverses
One of the most useful properties of the RB transform matrix is that, similar to rotation matrices, we can vastly simplify the inverse calculation. But first, here are a two formulae relative to the inverse. The one on the left is for 2x2 matrices and the one on the right is for arbitrary block upper triangular matrices. Upper triangular in this 2x2 case just means that the bottom left value is zero.
Additional matrix inverse facts:
  • If M = R * T then M^-1 = T^-1 * R^-1 meaning that taking the inverse reverses the order of the matrix operands.
  • If a matrix is orthonormal (which all rotation matrices are) then its transpose is its inverse.

So combining these factors together, when we remove the scaling factor, we can use both the orthonormal rule and the right hand formulae above to prove that if we can break a matrix, M into a product of it's translation and rotation components (aka M=TR) then M^-1 can be expressed using block-matrix-form with only t (the vector defined by the xyz translation of T) and R3^T where R3 is the top left 3x3 of R. Here is the full derivation: Youtube Link. See the summary below to the left and a walkthrough video I made below to the right.
​For completeness, below I've included the big bad 3x3 matrix inverse calculation we just spent so long trying to avoid. As you can see, it's mainly just a buttload of determinants which add up to an overall very expensive computation. The small "a" values correspond to values you would need to take from the matrix. Take a peek at what the code for this looks like here: Link. Sometimes we just can't avoid this formula but tricks like our derivation above can often save us lots of computation.
Local Space to Model Space Transformations
So we just spent a lot of time establishing inverses are no bueno. Why would we even want to compute them? The MVP is a great example to motivate....

Example

X
Practice Question: ​Example Question?

Example

X
Practice Question: ​Example Question?