Vectors? Matrices?
(unfortunately latex isn't working here, so this will have to do)
Alright, how about a short, mathematical crash course in Linear Algebra in the real numbers? You should at least know how to solve simple linear equation systems. If you don't, research how to solve them! I strongly advise you to -- if you really want to understand matrix operations, you need to know this. Personally I think that the foundations are very important, because most of application-based linear algebra has a very logical structure that you can "get" if you try to spend a bit of time with math.
First things first: Forget about all diffuse concepts you already know about vectors and matrizes. You will (hopefully) uncover them on your way through here. That being said, let's start!
What are vectors?
A vector at its core is just a list of numbers. The number of entries can be arbitrary, but cannot change for a single vector. In this way, a vector is like a C/C++ variable with a fixed type; e.g. Vector2 for 2 numbers, Vector3 for 3 numbers, Vector4 for 4 numbers, and so on.
In math, we say that the vector "lives in" or "belongs to" Rd, where d is called the dimension. So it is the same to say a vector has 3 numbers/ has 3 entries/is an element of R3 / is 3-dimensional.
The most common way to write down vectors in math is vertically. For instance, look at this 3-dimensional vector:
(You should put the whole packet of numbers into brackets, but I can't do that here, so we have to go with this instead)
| v_1 |
v = | v_2 |
| v_3 |
By now you're probably thinking "But what about positions? What about directions? I've heard these can be represented as vectors.". Yes, in some way they can -- but vectors are not positions or directions in some space with any number of dimensions. A vector is a list of numbers. To give it meaning we have to know the context we're using it in. Math makes no such distinction by itself, so it is a frequent source of confusion.
Right now I am, in fact, confused. How about an example?
Imagine you want to describe positions on a piece of paper. Put your finger on it and see how you can move without leaving the paper. You can only go left/right or up/down with your finger, but never out of or right through the paper unless you stop touching it. What does this mean? The sheet is two-dimensional; you can move in 2 distinct directions and still have your finger on the paper! The dimensions are "horizontal movement" and "vertical movement".
Now let us think of a way to encode arbitrary positions of your finger on the paper. Think about it, how would you describe a position on a sheet of paper? You have your trusty ruler, your trusty finger and your sheet of paper. Just measure distances from some point to your finger! To make things easy, we will take the bottom left corner. Just measure the distance from the left edge and the distance from the bottom edge. Make sure you don't measure in some arbitrary direction, but perpendicular to the edges you're measuring from. You can uniquely describe points on your sheet of paper by giving to me the following pieces of information: the corner you're measuring from, the horizontal distance, the vertical distance, and the unit you're measuring the distance in.
Now to the fun part: you can use a vector to encode 2 of these 4 pieces. Just remember that a vector is a list of numbers! Distances are numbers decorated with some unit of measurement (e.g. cm or in). The process is simple now: You tell me that I should measure in cm from the bottom left corner and give me your measured positions. For instance you want both of us to agree on the point that is 3.4cm from the left and 2.1cm from the bottom, so you tell me to look at the position
| 3.4 |
p = | 2.1 |.
"Wait a minute", you may think, " you have just told me time and time again that a vector is just a list of numbers! Now you're giving me a list of numbers and telling me it is a position!". Correct. That is the concept of context I was talking about earlier. Without your additional information "distances measured from bottom left in cm", this vector could describe the size of your pinkies, for all I know. I hope you can see now how vectors don't make much sense without a specific meaning behind them. We have already talked about one interpretation: We can interpret vectors as points within a 2-dimensional space! Of course we can take the same concepts and expand them to 3 dimensions (a point in 3 dimensions, what we're usually interested in) or 4 dimensions (e.g. a point in space and time) or 5 dimensions (e.g. a point in space, time and the number of cereals I've eaten this night, completely up to your interpretation as long as I tell you otherwise).
As you can see, vectors only make sense within context -- if you tell others what to do with them and how to interpret them. Here, we'd like to develop a way to describe some observer looking through a two-dimensional screen of a camera into a three-dimensional world. That's what graphics programming is about.
Of course, there are common contexts; interpretations people usually think about when talking about vectors. You have already heard about one! Vectors can be used to describe positions in a "vector space", which is this Rd thing (e.g. R2 -- vectors with 2 entries) we've already talked about. Unfortunately there is another one and people freely switch between these two interpretations at will, which is confusing if you're not 100% sure what they're talking about. From a mathematical point of view this is legit, because math itself makes no such distinction! Math in its pure form doesn't care about context. That is your job. Math will give you the tools to do stuff, but at the end of the day you have to sit down and intepret the results it has given you.
The other common interpretation of vectors
You're walking around in New York city and a stranger approaches you, asking you for the way to get to something? How would you describe it? Usually something akin to this: go straight, then go left at the 3rd intersection, then go right at the 2nd intersection, and so on. Another way would be to say "go straight for 1km, then turn left and go stright for another 0.4km, then turn right and follow the road for 0.7km,..." You can see that there is a list of numbers again, this time describing directions. Imagine a city map in front of you and someone tells you to go 100m east, 300m north, then 100m east again. You are eager to apply your new knowledge about vectors (remember, list of numbers) and put this into vectors:
| 300 | | 0 | | 100 |
d_1 = | 0 |, d_2 = | 100 |, d_3 = | 0 |
Ok, maybe this makes sense to you. But to everyone else it doesn't. "I go 300 what and 0 what?" You have to tell them how to interpret these vectors. In this case these 3 vectors describe directions to follow; the upper entry gives the movement to the east (or west if negative), the lower entry gives the movement to north/south, all in m. Alright, now you've encoded your directions. But where do you start? If you don't tell me where to start, I could start anywhere! Maybe in North Carolina, although I then wouldn't reach NYC at all.
You see that a critical piece of information is missing: The starting point! To make sense of these directions we need a starting point. This is again a matter of context; by themselves directions do not encode some absolute (definite) point in space, they simply tell you where to move.
The mathematical description is the same; directions are just a list of numbers, the same way as points are, but they mean different things. This is often intermingled and exchanged.
From a mathematical point of view, there is no distinction between positions and distances or directions; the operations you can perform with them are completely, 100% identical. The interpretation makes the difference, and most concepts of math are not up to interpretation.
This is too much to absorb at once. What should I take away from this?
Vectors are a fixed-size list of numbers. If a vector has 2 numbers in it we call it a 2-dimensional vector (an element of R2), if it has 3 numbers in it we call it a 3-dimensional vector (an element of R3), and so on.
By itself a vector is neither a position nor a direction. This is up to the context we're working in. Don't fret too much about it; default to a position in space (relative to some origin, which is the vector containing all 0s) and you're fine most of the time. The mathematical operations work the same either way. This distinction is made by humans, not by the underlying math.
The default way to write vectors is as a list of numbers arranged in a column:
| v_1 |
v = | v_2 |
| v_3 |
If the distinction is important we call them column-vectors. I hope by now you can easily imagine that all the stuff we've gone through also works if we simply write the numbers in a row and call them row-vectors:
v = | v_1 v_2 v_3 |
I mention this here because this distinction becomes important if we're talking about combining matrices and vectors, and there is tons of confusion mixing the mathematical concepts row and column vectors with the programming concept of memory layout -- We'll talk about this later.
What kind of basic operations can I perform with vectors?
I will only talk about the basic operations we will need; there are more complex operations that are really useful later on -- we will come to this later.
Note that these are mathematical operations; they make no distinctions between different interpretations of vectors. They simply describe how to handle the numbers.
You can add (or subtract) two vectors:
| u_1 | | v_1 | | u_1 + v_1 |
u + v = | u_2 | + | v_2 | = | u_2 + v_2 |
| u_3 | | v_3 | | u_3 + v_3 |
You can multiply a vector by a real number (also called scale a vector):
| v_1 | | a * v_1 |
a * v = a * | v_2 | = | a * v_2 |
| v_3 | | a * v_3 |
That's all there is to it. These are the basic building blocks of most engineering applications. Most stuff in the world boils down to operations on vectors and matrices, and you already know half of it. Time to design (half) a plane!
Notice how I didn't make a distinction between "add a direction to a position vector" or "add a direction to a direction" or "add two positions". I can't stress this enough: don't fret about it! This distinction is not important at all. You don't have to care if you add a direction to a position; the math works the same way every time! Of course from an applicating point of view you could think about it -- for instance, adding to positions doesn't make much sense. Mathematicians ignore this completely and you should too. You only have to know how to interpret the final result, because math makes no distinction in the way you arrive at it. So let's forget about that whole direction/position stuff for a moment. Time to talk about matrices.
Matrices?
You see, vectors by themselves are useful to describe positions in space. Unfortunately the amount of operations we can perform on them is severely limited and doesn't allow us to do a lot. To understand how matrices came about and what they describe we have to look at systems of equations. If you don't want to know that much about matrices, you can skip this part and still happily run along, as the matrices we will use have a well defined and intuitive interpretation to them. I think it is good to know why they have that interpretation, though.
Let us recall systems of equations from math tought in school: Say you want to find the value of two variables x and y, so that the following 2 equations are valid at the same time:
2*x + y = 4
x + y = 3
You should be able to find the values of x and y. If you are not, you should brush up on your knowledge about systems of equations. This stuff is important for what we're about to do.
Solved it? Alright! Now that we know about vectors we could be tempted to formulate this with vectors, maybe something like this:
| 2*x | | y | | 4 | | 2*x + y | | 4 |
| x | + | y | = | 3 | <=> | x + y | = | 3 |
Now we have a single equation with three or two vectors in it. This still encodes the same equation system as before: vectors are only considered equal if all of their entries are equal. Now we could wonder if this can be written in a more concise, better way. For instance, what if we want to absolutely make clear that we're searching for x and y in this vector equation? We would like to pack our variables into a single vector:
| x |
u = | y |
Now we can say "we want to find u" instead of "we want to find x and y", which becomes cumbersome if we had 100 equations with 100 variables to name. We simply can enumerate them u_1, u_2, ... and call the whole thing u. Now how do we write this equation with this vector? We only know how to add and scale vectors! This isn't enough there are several problems:
- We have to find a way to add x and y together within a single entry, also named row, of the vector
- We have to multiply only x by 2 in the upper equation.
Vectors by themselves can't do these operations if we only want to work with a single vector u, so we have to invent something new for that - a way to combine entries of the same vector to form a new vector. We're looking for a transformation
| 2*x + y |
f( u ) = | x + y |.
It turns out that this is exactly the thing matrices do. A matrix maps (transforms) a vector to another vector in a well-defined fashion. What is a matrix? Similar to vectors, it is just a "field" of numbers:
| a_11 a_12 |
A = | a_21 a_22 |
These are 4 numbers arranged in 2 rows and 2 columns. We call this a 2x2 matrix, or (similarly to vectors) a matrix in R2x2. In an mxn matrix the m gives the number of (horizontal) rows, while the n gives the number of (vertical) columns. A matrix describes how to combine the entries of a vector to build a new vector. So, how does this work?
Matrix-vector multiplication: The core of linear algebra
How do we combine a matrix and a vector? By matrix-vector multiplication. This is an operation that you have to know by heart; everytime we write matrix * vector this operation is executed:
| a_11 a_12 | | x | | a_11 * x + a_12 * y |
A * u = | a_21 a_22 | * | y | = | a_21 * x + a_22 * y |
You can remember this by the "row times column" rule. Grab the topmost row of the matrix and the column of the vector:
| x |
| a_11 a_12 | * | y | = a_11 * x + a_12 * y
See how you simply multiply the entries to form a single number? You go through every row from top to bottom and the vector column and write the resulting numbers in a new vector from top to bottom. This works in all dimensions, as long as the number of entries in a row is identical to the number of entries in the vector. Think about it, how would you calculate
| x |
| a_11 a_12 | * | y | = ?
| z |
That doesn't make sense. What would I do with z in the first place?
Note that there are probably millions of animations regarding matrix-vector multiply on the internet, which help you understand how to combine matrix and vector. This is the core operation of linear algebra. This is the operation that allows engineers to create buildings, bridges, planes, flow of water/air, solve elementary particle problems and everything else that you do on computers. It all boils down to matrix-vector products and solving systems of equations.
Back to our system of equations. Try to figure out how the matrix should look that replicates our system of equations. We're looking for A so that
| a_11 a_12 | | x | | a_11 * x + a_12 * y | | 2*x + 1*y |
A * u = | a_21 a_22 | * | y | = | a_21 * x + a_22 * y | = | 1*x + 1*y |.
The rules work out in such a way that we can find A very easily from this; A simply reads
| 2 1 |
A = | 1 1 |
You maybe have recognized that I have written factors of 1 explicitely in the above equation. The reason is simple: It is extremely easy to find a matrix given a system of equations:
| 2*x + y | | 2*x + 1*y | | 2 1 | | x |
| x + y | = | 1*x + 1*y | = | 1 1 | * | y |
See? Simply sort your variables x and y so that they are written in a "stacked" fashion. The matrix is then given by the multiplicative factors in front of the variables. Of course, this again works in any dimension. We'll soon talk about the interesting cases: R3 and R4. There is one important piece of the puzzle still missing.
Matrix-Matrix multiplication
What if we wanted to apply two matrices (or transformations) to a single vector, in succession? Say we have these two matrices:
| 0 1 | | 0 1 |
A = | 1 0 |, B = | 0 0 |
Try to figure out what these do individually, i.e. compute A*u and B*u for our vector u and look at the results.
All set? Good, let's look at it in more detail. We want to compute A * B * u. We can do this with our current knowledge, B * u gives some vector which we can then multiply by A:
| 0 1 | | 0 1 | | x | | 0 1 | | y | | 0 |
A * (B * u) = | 1 0 | * ( | 0 0 | * | y | ) = | 1 0 | * | 0 | = | y |
You should be able to understand this by now.
Suppose you want to calculate A * B * u for thousands of different u and some arbitrary A and B. Wouldn't it be easier to define a new matrix C that does the same oepration as A and B combined so we only have to multiply matrix-vector once for every value of u? That's what the matrix-matrix product does. It gives you a new matrix that combines both operations of the individual matrices. Its similar to the matrix-vector product, only that you now have multiple columns in B instead of a single column for the vector u.
If we want to compute C = A * B, the entries are defined as follows (following the common convention mentioned above):
c_ij = a_i1 * b_1j + a_i2 * b_2j + ...
This is nothing more than multiplying the i-th row of A by the j-th column of B like in the matrix-vector product. You will certainly find animations on how to do this on the internet, too. It is quite easy if you get in the rythm row * column, row * column, ....
As an example, let's compute A*B from above:
| 0 1 | | 0 1 | | 0*0 + 1*0 0*1 + 1*0 | | 0 0 |
A * B = | 1 0 | * | 0 0 | = | 1*0 + 0*0 1*1 + 0*0 | = | 0 1 |
Let's check:
| 0 0 | | x | | 0 |
| 0 1 | * | y | = | y |
Only one matrix-vector product, same result!
Now notice what happens if you multiply B * A instead. Try it! You will see that the result differs:
| 0 1 | | 0 1 | | 0*0 + 1*1 0*1 + 1*0 | | 1 0 |
| 0 0 | * | 1 0 | = | 0*0 + 0*1 0*1 + 0*0 | = | 0 0 |
Therefore
| 1 0 | | x | | x |
| 0 0 | * | y | = | 0 |
Which is strikingly different from our result before. In math terms we say that matrix multiplication is not commutative -- order of operations is important.
Ok, what's important?
You should know how to calculate matrix-vector. You can multiply several matrices into a single new matrix that works in the same way as applying both matrices in succession. Note that the order in which you apply is important; always think of executing matrix-vector first, then the next matrix-vector and so on. So this:
A * B * C * u = A * B * (C * u) = A * (B * v) = A * w,
where v and w are the intermediate results.
Alright, I'm out of time for now. I'll expand on this later and tell you about the non-math stuff next -- the interpretation of these matrix multiplications. It turns out that there are several classes of matrices that have nice geometric interpretations. That's the matrices you usually talk about in 3d rendering. Then I'll tell you why we're using 4-dimensional vectors and matrices instead of 3-dimensional vectors and matrices and tell you what's up with the row/column discussion so many people are confused about.
