﻿ Game Programming Gurus

Free JavaScript Editor     Ajax Editor ﻿

Main Page

### Introduction to Matrices

When we start talking about 3D graphics, I'm really going to drown you in vectors, matrices, and other mathematical concepts. However, at this point, I just want to show you a few things about matrices and how they can be used in relation to the simple 2D transformations you've been doing the longhand way. Sound like a plan?

A matrix is nothing more than a rectangular array of numbers with a given number of rows and columns. We usually say that a matrix is mxn, meaning it has m rows and n columns. The mxn is also referred to as the dimension of the matrix. For example, here's a matrix A that is 2x2:

```A = |1  4|
|9 –1|
```

Notice that I use the capital letter A to denote the matrix. In general, most people use capital letters to denote matrices and bold letters for vectors. In the previous example, the first row is <1 4> and the second row is <9 –1>. Here's a 3x2 matrix:

```    |5     6|
B = |2     3|
|100 -7|
```

And here's a 2x3 matrix:

```C = | 3  5 0 |
|-8 12 4 |
```

To locate the <i,j>th element in the matrix, you simply go to the ith row and the jth column and look up the value. However, there is a gotcha…most math books start counting matrix elements with 1, rather than 0 as you do in computer programs, so keep that in mind. You're going to start counting with 0 because this will make using C/C++ matrices work more naturally. For example, here's the labeling of a 3x3 matrix:

```    |a00 a01 a02|
A = |a10 a11 a12|
|a20 a21 a22|
```

Easy enough. So that's all there is to the actual matrix itself and the labeling conventions. But you might ask, "Where do matrices come from?" Matrices are simply mathematical tools for lazy mathematicians, I kid you not. Basically, if you have a system of equations like

```3*x + 2*y = 1
4*x – 9*y = 9
```

then that's a lot of work writing all the variables down. You know that they're (x,y), so why keep writing them? Why not just create a compact format that contains only the stuff you want to work with? This is how matrices came to be. In the previous example, there are three different sets of values that you can dump into matrices. You can work with these values together or separately.

Here are the coefficients:

```3*x + 2*y = 1
4*x – 9*y = 9

A = |3   2|
|4  -9|

Dimension is 2x2
```

Here are the variables themselves:

```3*x + 2*y = 1
4*x – 9*y = 9

X = |x|
|y|

Dimension is 2x1
```

And finally, here are the constants to the right:

```3*x + 2*y = 1
4*x – 9*y = 9

B = |1|
|9|

Dimension is 2x1
```

With all these nice matrices, you can focus on, say, the coefficient matrix A without all the other stuff. Moreover, you can write matrix equations like

```A*X = B
```

If you perform the math, you get

```3*x + 2*y = 1
4*x – 9*y = 9
```

But how to perform the math? That's our next topic.

#### The Identity Matrix

The first thing you need to define in any mathematical system is 1 and 0. In matrix mathematics, there are analogs of both of the values. The analog of 1 is called the identity matrix and is created by placing all 1s in the main diagonal of the matrix and 0s everywhere else. Furthermore, because matrices can be any size, there are obviously an infinite number of identity matrices. However, there is one constraint: All identity matrices must be square, or in other words mxm, where m >= 1. Here are a couple of examples:

```I2 = |1 0|
|0 1|

Dimension 2x2

|1 0 0 |
I3 = |0 1 0 |
|0 0 1 |

Dimension 3x3
```

Ironically, the identity matrix isn't exactly the analog of 1, but is under matrix multiplication (which we'll get to in a second).

The second type of fundamental matrix is called the zero matrix, and it's 0 under both addition and multiplication. It's nothing more than a matrix of dimension mxn with all entries 0. Other than that, there are no special constraints:

```      |0 0 0|
Z3x3 = |0 0 0|
|0 0 0|

Z1x2 = |0 0|
```

The only interesting thing about the zero matrix is that it has the standard properties of scalar 0 for both matrix addition and multiplication. Other than that, it's pretty useless.

Addition and subtraction of matrices is performed by adding or subtracting each element in two matrices and coming up with a result for each entry. The only rule to addition and subtraction is that the matrices that the operation is being performed on must be of the same dimension. Here are two examples:

```A = |1  5|          B = |13 7 |
|-2 0|              |5 –10|

A + B = |1  5| + |13 7 | = |(1+13) (5+7)| = |14  12|
|-2 0|   |5 –10|   |(-2+5) (0-10|   |3  -10|

A – B = |1  5| + |13 7 | = |(1-13) (5-7)    | = |-12 –2|
|-2 0|   |5 –10|   |(-2-5) (0-(-10))|   |-7  10|
```

Note that both addition and subtraction are associative; that is, A + (B + C) = (A + B) + C. However, they're not commutative under subtraction. (A – B) may not equal (B – A).

#### Matrix Multiplication

There are two forms of matrix multiplication: scalar and matrix. Scalar matrix multiplication is simply the multiplication of a matrix by a scalar number. You simply multiply each element of the matrix by the number. The matrix can be mxn at any size.

Here's a general description for a 3x3 matrix. Let k be any real constant:

```        |a00 a01 a02|
Let A = |a10 a11 a12|
|a20 a21 a22|

|a00 a01 a02|   |k*a00 k*a01 k*a02|
Then k*A = k*|a10 a11 a12| = |k*a10 k*a11 k*a12|
|a20 a21 a22|   |k*a20 k*a21 k*a22|
```

Here's an example:

```3*| 1 4| = |(3*1)    (3*4)| = |3  12|
|-2 6|   |(3*(-2)) (3*6)|   |-6 18|
```

MATH

Scalar multiplication is also valid for matrix equations, as long as you perform the multiplication on both sides. This is true because you can always multiply the coefficients of any system by a constant as long as you do so to both the RHS (right hand side) and LHS (left hand side) of the system.

The second type of multiplication is true matrix multiplication. Its mathematical basis is a bit complex, but you can think of a matrix as an "operator" that operates on another matrix. Given two matrices, A and B, that you want to multiply, they must have the same inner dimension. In other words, if A is mxn, B must be nxr. m and r may or may not be equal, but the inner dimension must be. For example, you can multiply a 2x2 by a 2x2, a 3x2 by a 2x3, and a 4x4 by a 4x5, but you can't multiply a 3x3 by a 2x4 because the inner dimensions aren't equal. The resulting matrix will have a size that is equal to the outer dimension of the multiplier and multiplicand matrix. For example, a 2x3 multiplying a 3x4 would have dimension 2x4.

Matrix multiplication is one of those things that's very hard to describe with words. I always end up waving my hands a lot to show what I'm saying, so take a look at Figure 8.25 while I give you the technical description of the multiplication algorithm.

##### Figure 8.25. The mechanics of matrix multiplication.

Given a matrix A and B, or AxB, and to multiply them together to compute each element of the result matrix C, you must take a row of A and multiply it by a column in B. To perform the multiplication, you sum the products of each element, which is also called the dot product. Here's an example for a 2x2 multiplying a 2x3—order counts!

```Let A = |1 2|      B = |1 3 5|
|3 4|          |6 0 4|
C = A x B = |(1*1 + 2*6) (1*3 + 2*0) (1*5 +2*4)|
|(3*1 + 4*6) (3*3 + 4*0) (3*5 +4*4)|

= |13 3 13|
|27 9 31|
```

As an aside, I want to bring your attention to the bolded sum of products (1*1 + 2*6). This product and all the others are really vector dot products (a vector is just a collection of values, like a matrix with one row). A dot product has a very explicit mathematical meaning, which we'll get to later, but in general, you can compute the dot product of two vectors that are each 1xn by simply summing up the products of the independent components. Or, mathematically:

```Let a = [1 2 3] b = [4 5 6]

a.b = [(1*4) + (2*5) + (3*6)]
= [32]
1x1
```

Or, if you want to be a little wet 'n' wild, it's just a scalar.

WARNING

I'm being a little cavalier right now with dot products; technically, they're only valid for vectors, but a column or row of a matrix is really a vector. Basically, I'm in a transitional period and I don't want to kill you. I want to help you…

So that's how you multiply matrices. Another way to think of it is that if you want to compute the product of AxB, call it C. You can do this element by element. Hence, if you want the cijth element (where both i and j are zero-based), you can find it by taking the ith row of A and doting (summing the products) with the jth column of B.

At this point, I think you get the general idea of what's going on. Let's take a look at some code that performs matrix multiplication. First, let's define a matrix type:

```// here's a 3x3, useful for 2D stuff and some 3D
typedef struct MATRIX3X3_TYP
{
float M[3][3]; // data storage
} MATRIX3X3, *MATRIX3X3_PTR;

int Mat_Mul_3X3(MATRIX3X3_PTR ma,
MATRIX3X3_PTR mb,
MATRIX3X3_PTR mprod)
{
// this function multiplies two matrices together and
// stores the result

for (int row=0; row<3; row++)
{
for (int col=0; col<3; col++)
{
// compute dot product from row of ma
// and column of mb

float sum = 0; // used to hold result

for (int index=0; index<3; index++)
{
// add in next product pair
sum+=(ma->M[row][index]*mb->M[index][col]);
} // end for index

// insert resulting row,col element
mprod->M[row][col] = sum;

} // end for col

} // end for row

return(1);

} // end Mat_Mul_3X3
```

You'll notice that there's a lot of math going on. In general, matrix multiplication is an N3 operation, meaning that there are three nested loops. However, a number of optimizations can be used, such as testing either the multiplier or multiplicand for 0 and not performing the multiplication.

#### Transformations Using Matrices

Using matrices to perform 2D/3D transformations is a snap. Basically, what you're going to do is multiply the point you want to be transformed against the desired transformation matrix. Or, mathematically:

```p' = p*M
```

where p' is the transformed point, p is the original point, and M is the transformation matrix. If I haven't mentioned that matrix multiplication is not commutative, let me do so now:

```(A*B) NOT EQUAL (B*A)
```

This statement is generally true unless A or B is the identity matrix or the zero matrix, or they're the same matrix. Order counts when you're matrix multiplying.

In this case, you're going to convert a single (x,y) point into a single row matrix with dimension 1x3, and then pre-multiply it by a 3x3 transformation matrix. The result will also be a 1x3 row matrix, and you can pick off the first two components as the transformed x',y'. Alas, you should have a slight problem with all this—what is the last component of the initial matrix p there for, if only two pieces of data, x and y, are needed?

In general, you're going to represent all points like this:

```[x y 1.0]
```

The factor 1.0 is to make the matrix into what are called homogenous coordinates. This allows any transformed point to be scaled, and it also allows for translations in transformations. Other than that, the mathematical basis for it is unimportant. Just think of it as a dummy variable that you need. Hence, you're going to create a matrix that's 1x3 to hold your input point and then post-multiply it by the transformation matrix. Here are the data structures for the point or 1x3 matrix:

```typedef struct MATRIX1X3_TYP
{
float M[3]; // data storage
} MATRIX1X3, *MATRIX1X3_PTR;
```

And here's a function to multiply a point against a 3x3 matrix:

```int Mat_Mul_1X3_3X3(MATRIX1X3_PTR ma,
MATRIX3X3_PTR mb,
MATRIX1X3_PTR mprod)
{
// this function multiplies a 1x3 matrix against a
// 3x3 matrix – ma*mb and stores the result
for (int col=0; col<3; col++)
{
// compute dot product from row of ma
// and column of mb

float sum = 0; // used to hold result

for (int index=0; index<3; index++)
{
// add in next product pair
sum+=(ma->M[index]*mb->M[index][col]);
} // end for index

// insert resulting col element
mprod->M[col] = sum;

} // end for col
return(1);

} // end Mat_Mul_1X3_3X3
```

And to create a point p with components x and y, you would do the following:

```MATRIX1X3 p = {x,y,1};
```

With all that in mind, let's take a look at the transformation matrices for all the operations you've performed manually.

﻿

Ajax Editor     JavaScript Editor