A Graphics Programmer's Toolbox, part 2 (Matrices and Coordinate Systems)

The second round of "what's in your mathematical toolbox".

If you missed the previous part, consider part 1 first.

Coordinate Systems

A vector (u, v, w) can be expressed as ui + vj + wk, which is the representation of the vector in the standard coordinate system. We can define other coordinate systems with different basis vectors. For example, if we take a mirrored coordinate system in which the basis vectors are -i, -j and -k, then the point whose coordinates in that system are (-u, -v, -w) matches the same point:

(-u)(-i) + (-v)(-j) + (-w)(-k) = ui + vj + wk.

Co-ordinates of a point in a system are simply the multipliers of the basis vectors: if the basis vectors are i', j' and k' and the coordinates are (u, v, w), then, if the the coordinate system's origin is at zero, the point matching those coordinates is ui' + vj' + wk'. If the coordinate system's origin is not at zero, we have to take that into account. In that case, if the origin is at p, the point becomes ui' + vj' + wk' + p.


Now if the vectors p, i', j' and k' are known in the standard basis, we can calculate the coordinates of the point in the standard coordinate system:

(u i'.x + v j'.x + w k'.x + p.x, 
 u i'.y + v j'.y + w k'.y + p.y, 
 u i'.z + v j'.z + w k'.z + p.z),

or simply

u i' + v j' + w k' + p.

Often the basis vectors i', j' and k' are of unit-length and orthogonal to each other. The mathematical notation for this is |i'| = 1, |j'| = 1, |k'| = 1 and i'·j' = 0, j'·k' = 0 and k'·i' = 0, where · is the dot product. If all these hold, the coordinate system is called orthonormal. If the basis vectors are only orthogonal but not necessarily normalized, then the coordinate system is called just orthogonal.


Matrices

A matrix is simply an array of numbers. Another fancy term here. That's all.


Matrix notation

There are different sizes of arrays matrices of course, although the 3x3 and 4x4 arrays matrices are the most useful in 3d graphics. Like in many programming languages, the first number is the height number of horizontal lines rows, and the last number is the width number of vertical lines columns. An example for a 3x4 array matrix in C would be float matrix[3][4].

Like vectors, arrays matrices can be summed. It's just the componentwise sum. The difference of matrices is the same componentwise difference as for vectors. Like vectors, you can multply and divide them by numbers scalars. There's also the Hadamard product (componentwise product), but that's not so common. Like for vectors, the most useful array matrix multiplications are something different. I'll come back to that later.

Elements of an array a matrix are usually denoted by subscript notation; first the row and then the column:

      [A1,1 A1,2 A1,3 A1,4]
 A =  [A2,1 A2,2 A2,3 A2,4]
      [A3,1 A3,2 A3,3 A3,4]

For example, if

     [11 12] 
 A = [21 22] 
     [31 32],

then A_1,2 = 12, A_2,1 = 21 and A_3,2 = 32.


Matrices and Coordinate Systems

Let's go back to the coordinate systems and take one whose origin is at zero and whose basis vectors are i', j' and k', not necessarily orthogonal nor unit-length. Let's store these vectors as a 3x3 matrix:

    [i'.x  j'.x  k'.x] 
M = [i'.y  j'.y  k'.y].
    [i'.z  j'.z  k'.z] 

This matrix is often called the base of the coordinate system since it contains the basis vectors. Next, let's make the vector (u, v, w) a matrix too:

            [u] 
(u, v, w) = [v].
            [w] 

Let's call that previous point (u, v, w) with the name p and let's suppose that these coordinates are given with respect to the previously given base. To get the coordinates of p in the standard coordinate system, we need to know the vectors i', j' and k' in the standard coordinate system. If we do, we have

                     (u i'.x + v j'.x + w k'.x, 
p = ui' + vj' + wk' = u i'.y + v j'.y + w k'.y, 
                      u i'.z + v j'.z + w k'.z).

According to the previously introduced scheme, let's make this vector a matrix too:

    [u i'.x + v j'.x + w k'.x] 
p = [u i'.y + v j'.y + w k'.y].
    [u i'.z + v j'.z + w k'.z] 

After all, vectors are matrices too. Now let's introduce the matrix product for a 3x3 array matrix and a 3-vector 3x1 matrix (which is often called a column vector):

[i'.x j'.x k'.x]   [u]   [u i'.x + v j'.x + w k'.x]
[i'.y j'.y k'.y] * [v] = [u i'.y + v j'.y + w k'.y]
[i'.z j'.z k'.z]   [w]   [u i'.z + v j'.z + w k'.z]

     [i'.x]     [j'.x]     [k'.x]                   
 = u [i'.y] + v [j'.y] + w [k'.y] = ui' + vj' + wk'.
     [i'.z]     [j'.z]     [k'.z]                   

In other words, matrix * vector transforms the vector from another coordinate system to the standard coordinate system.


Matrix Times a Matrix

Well then, how about matrix * matrix? It's simple. Really, just multiply with the columns of the second matrix one by one and collect the results. Denoting the columns of the second matrix as a1, a2 and a3 and the first matrix as M, we have

    [i'.x j'.x k'.x]                    [a1.x a2.x a3.x] 
M = [i'.y j'.y k'.y],  A = [a1 a2 a3] = [a1.y a2.y a3.y].
    [i'.z j'.z k'.z]                    [a1.z a2.z a3.z] 

Now then, the multiplication is done to the column vectors one by one and collected:

M * [a1 a2 a3] = [M a1  M a2  M a3].

The column vectors of the result matrix are, like we had it before, just the three vectors transformed one by one. The result is a 3x3 matrix

[(M a1).x  (M a2).x  (M a3).x] 
[(M a1).y  (M a2).y  (M a3).y].
[(M a1).z  (M a2).z  (M a3).z] 

Now we're able to transform points to the standard coordinate system by matrix multiplication. But how about the inverse? Surprisingly, that's done by multiplying by the inverse matrix; more about that later.

That's all, folks!

The Future ...
Please ask for details in the comments. The next topic might be 4x4 matrices, homogenous coordinates and coordinate systems whose origin is not at zero. Probably also discussing matrix transpose and inverse. Please comment and request for a topic if you want.

You might want to read more about matrix multiplication or coordinate systems. ;)

A Graphics Programmer's Toolbox, part 1 (Vectors)

Everyone needs to know the basic tools of their art. I thought I'd like to share with you my equivalents of a screwdriver, a hammer and maybe a saw, some of the everyday tools of a graphics programmer.

Vectors

A vector is just a fancy word for a point in space. So in 2d, a vector is just a co-ordinate pair (x, y). In 3d it's (x, y, z) and in 4d it's (x, y, z, w). A mental image of four dimensions is not important here - don't even try.

Some vectors are given a special name. The vector in the middle of the space, the zero-vector, is called the origin. In 3d, that's (0, 0, 0). The vector to the right, (1, 0, 0), is called i. The up-vector, (0, 1, 0) is j. The remaining vector, (0, 0, 1), is named k and it's the backwards-vector.

Sum, Difference and Multiplication

These points, or vectors, can be added and subtracted. Adding a vector to another is just summing the coordinates of the vectors; if a = (X, Y) and b = (x, y), then a + b = (X+x, Y+y). Subtracting is done in a similar way, a - b = (X-x, Y-y). Multi-dimensional calculation is not really that much more complicated. It's basically just the same, but doing the operations to all co-ordinates, instead of just one.

Sum and difference are easy, but with multiple components (co-ordinates) there are many kind of vectors multiplications with different meanings. Complicated? I didn't say anything; not yet.

Multiplying by a scalar just multiplies the distance of the point with respect to the origin. This scalar is just a fancy name for a real number; you might have noticed mathematicians love fancy words. So in other words, if a = (x, y, z) and r is a real number, then a*r = (x*r, y*r, z*r). If r is negative, you can see that the point will also be mirrored with respect to the origin.

The componentwise product works the same way as sum and addition, but it's a bit rarer in the mathematical context. It's very useful in computer graphics though, mostly in lighting calculations. This product is denoted with ○, and if a = (R, G, B, A) and b = (r, g, b, a), then a ○ b = (R*r, G*g, B*b, A*a). Mathematicians call this product the Hadamard product (Jacques Hadamard, 1865 to 1963). Componentwise product is fine too.

There are also at least two more very useful products.

Dot and Cross Product

The dot product is the screwdriver of the toolbox. This product is written with the symbol •, and it's the sum of the components' products; if a = (X, Y, Z) and b = (x, y, z), then a • b = X*x + Y*y + Z*z. Notice that the result is a scalar, or a real number. The usefulness of this product comes mainly from the fact that if a and b are both unit-length (X² + Y² + Z² = 1²), then, denoting the angle between b and a with α, it holds that a • b = cos α. Generally, if a and b are not necessarily of unit length, then a • b / |a||b| = cos α, where |v| denotes the length of a vector.

In 3d there's the cross product. Its main purpose is outputting a vector that's orthogonal to two given vectors, i.e. getting their normal vector. It can also be used to calculate the sine of the angle between two vectors. A funny fact is that a cross product only exists in 3 and 7 dimensions. The formula for cross product is pretty symmetric; if a = (X, Y, Z) and b = (x, y, z), then a × b = (Yz - Zy, Zx - Xz, Xy - Yx). Notice that this product is a bit special in that a × b = - b × a, so you can't just switch the order mindlessly. It is also true, like stated before, that a × b is orthogonal to both a and b. In mathematical notation, (a × b) • a = 0 and (a × b) • b = 0. For the direction of the cross product vector there's the right-hand rule, well described in this wiki article.

Continuing soon...
It's a known fact that once you open a Wikipedia page, you just can't stop reading. I'll set here a trap for you and I bet you can't oppose it:
Euclidean vector
Unit vector
The Gram-Schmidt algorithm

I'm planning to continue with matrices, bases, coordinate transforms, quaternions and such. If you'd like to suggest a topic or ask a question, please comment! :)