Friday, January 7, 2011

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 A1,2 = 12, A2,1 = 21 and A3,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. ;)