Linear algebra for game developers ~ part 3

I introduced vectors in Part 1, and a toolset for working with them in Part 2. However, today I would like to talk about perhaps the most important concept for game developers. This is the concept of the transformation matrix.

Let's start by looking at the building blocks of the transformation matrix:

Basis Vectors

Let's say we're making an Asteroids game on really old hardware, and we want to have a simple 2D space ship that can rotate freely. The ship model looks like this:

So how do we draw it when the player rotates by an arbitrary amount, like 49 degrees counter-clockwise? Well, trigonometry we can create a function for 2D rotation that inputs a point and an angle, and outputs a rotated point:

   vec2 rotate(vec2 point, float angle){
           vec2 rotated_point;
           rotated_point.x = point.x * cos(angle) - point.y * sin(angle);
           rotated_point.y = point.x * sin(angle) + point.y * cos(angle);
           return rotated_point;
   }
   

Cosine and sine operations are pretty slow, but we're only doing them on three points, so it can smoothly on our old hardware. But now we decide to upgrade the ship to look like this:

Now our old method is too slow! We don't have enough sine and cosine operations to rotate this many points. There are many ways to solve this problem, but an elegant solution comes to us like this: "What if instead of rotating each point in the model, we just rotate the model's x and y axes instead?"

How does this work? Well, let's look at what coordinates mean. When we talk about the the point (3,2), we are saying that its position is three times the x-axis plus two times the y-axis. The default axes are (1,0) for the x-axis and (0,1) for the y-axis, so we get the position 3(1,0) + 2(0,1). But the axes don't have to be (1,0) and (0,1). If we rotate these axes, then we can rotate every point at the same time.

To get the rotated x and y axes we just use the trigonometric function above. For example, if we are rotating by 49 degrees, then we get the new x-axis by rotating (1,0) by 49 degrees and we get the y-axis by rotating (0,1) by 49 degrees. Our new x-axis is (0.66, 0.75), and our new y-axis is (-0.75, 0.66). We can do this by hand for our 3-point model to prove that it works:

The top point is (0,2), which means its new position is zero times the rotated x-axis plus twice the rotated y-axis.

The bottom-left point is (-1,-1), which means its new position is negative one times the rotated x-axis plus negative one times the rotated y-axis.

The bottom-right point is (1,-1), which means its new position is one times the rotated x-axis plus negative one times the rotated y-axis.

What we are doing here is using the ship coordinates as if they exist in a separate coordinate system with rotated axes (or 'basis vectors'). This is useful in this case because it separates the cost of manipulating the orientation of the ship from the cost of applying the orientation to the model points.

Whenever you have modified the basis vectors (1,0) and (0,1) to (a,b) and (c,d), then the modified point (x,y) can be found using this expression:

Normally the basis vectors are (1,0) and (0,1) so you just get x(1,0) + y(0,1) = (x,y), and you don't have to bother with this. However, it's important to remember that you can use other bases (plural of basis) as well.

Matrices

Matrices are like 2-dimensional vectors. For example, a typical 2x2 matrix might look like this:

   [a c 
    b d]
   

Written another way, this is:

Look familiar? This is the exact same expression that we use when changing the basis vectors! This means that multiplying a 2x2 matrix with a 2D vector is the same thing as changing its basis vectors. For example, if we plug the standard basis vectors (1,0) and (0,1) into the matrix columns, we get:

[1 0 
 0 1]

[0.66 -0.75 
 0.75  0.66]
 

This matrix will rotate any 2D vector counter-clockwise by 49 degrees. We could write our asteroids program with a lot more elegance by using matrices like this. For example, our ship-rotation function could look like this:

void RotateShip(float degrees){
        Matrix2x2 R = GetRotationMatrix(degrees);
        for(int i=0; i<num_points; ++i){
                rotated_point[i] = R * point[i];
        }
}

[a c e 
 b d f 
 0 0 1]
 

3D Matrices

[a d g 
 b e h 
 c f i]

[a d g j 
 b e h k 
 c f i l 
 0 0 0 1]