Linear algebra for game developers(blog.wolfire.com)
blog.wolfire.com
Linear algebra for game developers
http://blog.wolfire.com/2009/07/linear-algebra-for-game-developers-part-1/
30 comments
I'm a game developer. My specialty is network programming, so I don't deal with this stuff a lot, but it's impossible to completely avoid it.
I also majored in CS at a college where the CS department was part of the Mathematics department (though it moved to Engineering in my last year.)
What I mainly remember of Linear Algebra was that it and I didn't get along. I struggled a lot with all the heavy math classes. When I started picking up matrix operations much later, from looking at other programmers' code, it didn't really occur to me to call it "Linear Algebra". When I saw the title of this article, I still didn't think that's what it was going to be about.
So, I'm a game developer and I'm with you, it's not what I'd think when I hear Linear Algebra either, though if I thought really hard and fought off the flashbacks, I could probably find matrix operations mixed in somewhere with my scant memories of Linear Algebra in college.
That said, this is a great series of articles for aspiring game developers. Everyone needs to know these basics these days (Ok, maybe not if you're making match 3 games or word puzzles or the like). I wish someone had just shown me this 15 years ago.
I also majored in CS at a college where the CS department was part of the Mathematics department (though it moved to Engineering in my last year.)
What I mainly remember of Linear Algebra was that it and I didn't get along. I struggled a lot with all the heavy math classes. When I started picking up matrix operations much later, from looking at other programmers' code, it didn't really occur to me to call it "Linear Algebra". When I saw the title of this article, I still didn't think that's what it was going to be about.
So, I'm a game developer and I'm with you, it's not what I'd think when I hear Linear Algebra either, though if I thought really hard and fought off the flashbacks, I could probably find matrix operations mixed in somewhere with my scant memories of Linear Algebra in college.
That said, this is a great series of articles for aspiring game developers. Everyone needs to know these basics these days (Ok, maybe not if you're making match 3 games or word puzzles or the like). I wish someone had just shown me this 15 years ago.
This is an awesome thread.
Since you asked:
Give me the shortest path in Khan videos, reading assignments, and exercises to LLL lattice reduction starting at "the first 20 minutes of a linear algebra class".
(You asked! Lattice basis reduction is used in several practical RSA attacks).
Since you asked:
Give me the shortest path in Khan videos, reading assignments, and exercises to LLL lattice reduction starting at "the first 20 minutes of a linear algebra class".
(You asked! Lattice basis reduction is used in several practical RSA attacks).
OK, I really don't know much about the LLL since it was invented at the time I was studying LinAlg and never got as far as our course work. It was being used by Conway, Norton and Parker when I was doing my PhD, so I heard something of it, but never implemented it, as I was working in a different area.
However ...
Here's (some/most of) my understanding.
We're working in R^n, and suppose you have n linearly independent vectors b_1 to b_n with integer coefficients in the obvious basis. These vectors span R^n, but you need to use real numbers as coefficients to do that. If you only take linear combinations using integer coefficients then you get a lattice in R^n.
Exercise: Prove that (1,5) and (2,3) are linearly independent in R^2
Exercise: plot a portion of the lattice spanned by (1,5) and (2,3) in R^2.
The same lattice might also be spanned by different vectors, and in particular, you may be able to find a collection of shorter vectors that span the same space.
Exercise: Find two shorter vectors v1 and v2 that span the same lattice as the one above.
The new vectors must also be in the same lattice, and so must be representable as an integer linear combination of the original vectors.
Exercise: Represent v1 and v2 as linear combinations of (1,5) and (2,3)
Basically LLL consists of a measurement of how well you're doing so far, and a way of replacing one of your existing vectors with a linear combination so as to make your collection improve.
I'll stop there - ask more questions if anything is unclear.
However ...
Here's (some/most of) my understanding.
We're working in R^n, and suppose you have n linearly independent vectors b_1 to b_n with integer coefficients in the obvious basis. These vectors span R^n, but you need to use real numbers as coefficients to do that. If you only take linear combinations using integer coefficients then you get a lattice in R^n.
Exercise: Prove that (1,5) and (2,3) are linearly independent in R^2
Exercise: plot a portion of the lattice spanned by (1,5) and (2,3) in R^2.
The same lattice might also be spanned by different vectors, and in particular, you may be able to find a collection of shorter vectors that span the same space.
Exercise: Find two shorter vectors v1 and v2 that span the same lattice as the one above.
The new vectors must also be in the same lattice, and so must be representable as an integer linear combination of the original vectors.
Exercise: Represent v1 and v2 as linear combinations of (1,5) and (2,3)
Basically LLL consists of a measurement of how well you're doing so far, and a way of replacing one of your existing vectors with a linear combination so as to make your collection improve.
I'll stop there - ask more questions if anything is unclear.
I understood much of this! :)
So then my next question is, relative to the whole of linear algebra, how advanced/deep/engaged-with-the-field is the LLL algorithm? Is this first-course-in-linear-algebra stuff? Is this "barely linear algebra" stuff?
So then my next question is, relative to the whole of linear algebra, how advanced/deep/engaged-with-the-field is the LLL algorithm? Is this first-course-in-linear-algebra stuff? Is this "barely linear algebra" stuff?
As I understand it, the actual algorithm is very straight-forward. There were several clever things that had to come together to have it work:
* Define some concept of how good you can expect things to get
* Find some way of improving what you've got
* Prove that you get to within some distance of "the best"
* Prove that it terminates in polynomial time.
I've not see the details of the proofs - they're likely to be mildly difficult, with a very nasty details. But I don't think they're especially deep. The really deep bit was getting the exact formulation right to make it work.
Things like the spectral theorems, diagonalization, eigenvalues and eigenvectors, these are all deeper results that have far-reaching implications. For example, the reason that when you tap the rim of a coffee-cup you get two different notes, blends of those notes, and no other notes is to do with eigenvectors.
Similarly for why Fourier transforms work (in part) the way they do. The reasons that the Sine and Cosine functions form an infinite-dimensional basis for the linear space of non-pathological functions, for example, let us then deal with frequency space as a dual space of function space.
These are deeper.
* Define some concept of how good you can expect things to get
* Find some way of improving what you've got
* Prove that you get to within some distance of "the best"
* Prove that it terminates in polynomial time.
I've not see the details of the proofs - they're likely to be mildly difficult, with a very nasty details. But I don't think they're especially deep. The really deep bit was getting the exact formulation right to make it work.
Things like the spectral theorems, diagonalization, eigenvalues and eigenvectors, these are all deeper results that have far-reaching implications. For example, the reason that when you tap the rim of a coffee-cup you get two different notes, blends of those notes, and no other notes is to do with eigenvectors.
Similarly for why Fourier transforms work (in part) the way they do. The reasons that the Sine and Cosine functions form an infinite-dimensional basis for the linear space of non-pathological functions, for example, let us then deal with frequency space as a dual space of function space.
These are deeper.
Your coffee cup example - if math were taught more that way rather than a dry list of mechanical actions I think less people would dread it. I have nothing but hatred and horrible memories towards my grade school maths education.
I can only study this stuff in my spare time so my knowledge is very patchy. But when I see stuff like eigenvectors I associate them towards a much more powerful concept of invariance - which I see everywhere. Recursion, programming, Machine Learning, dynamical systems, physics. And I feel on the edge of an epiphany but do not have sufficient knowledge to fully grasp it.
But it makes me think that all these things that appear over and over again in different guises, the subject is taught far too inefficiently. I feel there is a much simpler way to teach maths and have it flow and be holistic rather than a replay of history: disjointed and disconnected.
I can only study this stuff in my spare time so my knowledge is very patchy. But when I see stuff like eigenvectors I associate them towards a much more powerful concept of invariance - which I see everywhere. Recursion, programming, Machine Learning, dynamical systems, physics. And I feel on the edge of an epiphany but do not have sufficient knowledge to fully grasp it.
But it makes me think that all these things that appear over and over again in different guises, the subject is taught far too inefficiently. I feel there is a much simpler way to teach maths and have it flow and be holistic rather than a replay of history: disjointed and disconnected.
This is one of the reasons I'm creating a web site intended to show the connections between topics, and through that, how wide-spread the applications of the mathematical ideas are. Math should be taught with connections, applications, examples, demonstrations and, above all, by knowledgeable and enthusiastic teachers. Most high-school teachers don't know more than they have to teach, don't know the connections between topics, and don't have time to deviate from the prescribed curriculum.
The LLL algorithm seems pretty straight-forward looking at it on Wikipedia. It’s possible that proving things about it is tricky, but understanding the steps is pretty “first-course”.
The author jumps in to what I see as linear algebra (matrix manipulation) in part 3, and more heavily in part 4 (rotating axes).
The first two parts are a necessary foundation. Yes, it's basic vector stuff, but not everyone gets that vectors can be represented as matrices.
The first two parts are a necessary foundation. Yes, it's basic vector stuff, but not everyone gets that vectors can be represented as matrices.
Well, thing is, Linear Algebra isn't matrix manipulation. Matrices are just one aspect of Linear Algebra - it's like saying that symbols such as 'x', 'y' and 'z' are "Algebra."
Matrices are representations of (linear) transformations between Linear Spaces. Linear Algebra is talking about the Linear Spaces, and manipulating matrices is sort-of like finding roots of or factoring polynomials.
Which brings me to your second part. Vectors are elements of vector spaces. Matrices are transformations between vector spaces. The one is not the other, and while there are similarities and overlap (and sometimes identifying aspects of each to the other is useful), conflating the two at an early stage is a recipe for getting no further than simple matrix manipulation. If that's all you want then that's OK, but you miss out on a lot of insights that can be really valuable and make you stand out from the crowd.
But remember, I'm saying this as a mathematician, and my terminology will be different. I mostly want to make people aware that they are using terms in a different way, and open the opportunity for the kind of confusion I've suffered for decades.
Matrices are representations of (linear) transformations between Linear Spaces. Linear Algebra is talking about the Linear Spaces, and manipulating matrices is sort-of like finding roots of or factoring polynomials.
Which brings me to your second part. Vectors are elements of vector spaces. Matrices are transformations between vector spaces. The one is not the other, and while there are similarities and overlap (and sometimes identifying aspects of each to the other is useful), conflating the two at an early stage is a recipe for getting no further than simple matrix manipulation. If that's all you want then that's OK, but you miss out on a lot of insights that can be really valuable and make you stand out from the crowd.
But remember, I'm saying this as a mathematician, and my terminology will be different. I mostly want to make people aware that they are using terms in a different way, and open the opportunity for the kind of confusion I've suffered for decades.
For the programmers out there, it's a bit like the difference between writing code which takes concrete data types ('n-tuple of floats', 'n by m matrix of floats'), and writing more generic code which takes abstract datatypes (roughly: 'thing supporting addition and scalar multiplication' and 'function on said things which happens to satisfy a linearity property').
The abstraction brings some benefits, but also has some conceptual overhead for those new to the area.
In a sense the abstraction isn't technically necessary, at least for finite-dimensional vector spaces: every finite-dimensional real vector space is isomorphic to some R^n, so you can express all the results of finite-dimensional linear algebra in purely concrete terms (vectors, matrices) if you really want to. In particular, if you're only interested in doing geometry in R^2 and R^3, the abstract vector space treatment adds relatively little.
But (again perhaps analogously to programming) hiding away the lower-level details can make things clearer and more elegant if one invests some time in getting comfortable with the abstractions involved. It allows you to use whichever representation comes most naturally for your vectors, rather than tying you to representing in terms of some particular basis. And it does add some generality, especially when it comes to infinite-dimensional spaces, which turn out to be pretty useful things.
The abstraction brings some benefits, but also has some conceptual overhead for those new to the area.
In a sense the abstraction isn't technically necessary, at least for finite-dimensional vector spaces: every finite-dimensional real vector space is isomorphic to some R^n, so you can express all the results of finite-dimensional linear algebra in purely concrete terms (vectors, matrices) if you really want to. In particular, if you're only interested in doing geometry in R^2 and R^3, the abstract vector space treatment adds relatively little.
But (again perhaps analogously to programming) hiding away the lower-level details can make things clearer and more elegant if one invests some time in getting comfortable with the abstractions involved. It allows you to use whichever representation comes most naturally for your vectors, rather than tying you to representing in terms of some particular basis. And it does add some generality, especially when it comes to infinite-dimensional spaces, which turn out to be pretty useful things.
> ", thing is, Linear Algebra isn't matrix manipulation. Matrices are just one aspect of Linear Algebra - it's like saying that symbols such as 'x', 'y' and 'z' are 'Algebra.'"
Well, I see your point, but to many, x, y and z are algebra. When public schools teach solving strategies like substitution, polynomial factoring, or concepts like linear equations, series, and exponents, these are labeled "algebra" and are basic extensions of solving for some variable(s).
So it seems you are arguing that the public understanding of "Algebra" and a mathematician's understanding of "Algebra" are different. (And the same for "linear algebra".) ... because the public's understanding is based largely on a shared experience in public schools.
I'd be surprised if it weren't so, and I suspect the problem of a different interpretation of terms is the case in many fields.
Well, I see your point, but to many, x, y and z are algebra. When public schools teach solving strategies like substitution, polynomial factoring, or concepts like linear equations, series, and exponents, these are labeled "algebra" and are basic extensions of solving for some variable(s).
So it seems you are arguing that the public understanding of "Algebra" and a mathematician's understanding of "Algebra" are different. (And the same for "linear algebra".) ... because the public's understanding is based largely on a shared experience in public schools.
I'd be surprised if it weren't so, and I suspect the problem of a different interpretation of terms is the case in many fields.
To some people, that big TV with pictures in it is called a computer. To you, it's probably a monitor. Are they just as right as you are?
I'm with you. This is more geometry than it is linear algebra. When I think of linear algebra I think of vector spaces and determining their relationships, not simple vector math.
Hi Colin thank you for making this place so interesting. I struggle to teach myself maths but greatly enjoy it.
As I see it the most applicable branch of maths for games falls under the umbrella of Clifford/Geometric Algebra - stuff like quaternions, cross products and bivectors. Indeed graphics programmers would gain a lot of power and elegance from the unified view provided by geometric algebra - rather than the hodgepudge of seemingly unrelated concepts as it is currently presented.
Topics covered in a linear algebra class that are typically used in games are basic - vector arithmetic, dot products, linear and affine transformations and projection.
Below you note that a vector and a matrix are different things. But I think the word is polymorphic. Sometimes, the notation aspect - table based syntax for arranging numbers is the focus. So someone will say that matrices are made up of n column vectors. Other times the focus will be on the linear transformation aspect. Where a matrix is more like a higher order function and is evidently different from the entities it is transforming. It simply requires a change of frame.
As I see it the most applicable branch of maths for games falls under the umbrella of Clifford/Geometric Algebra - stuff like quaternions, cross products and bivectors. Indeed graphics programmers would gain a lot of power and elegance from the unified view provided by geometric algebra - rather than the hodgepudge of seemingly unrelated concepts as it is currently presented.
Topics covered in a linear algebra class that are typically used in games are basic - vector arithmetic, dot products, linear and affine transformations and projection.
Below you note that a vector and a matrix are different things. But I think the word is polymorphic. Sometimes, the notation aspect - table based syntax for arranging numbers is the focus. So someone will say that matrices are made up of n column vectors. Other times the focus will be on the linear transformation aspect. Where a matrix is more like a higher order function and is evidently different from the entities it is transforming. It simply requires a change of frame.
The ability to move freely between different conceptualizations is both important and useful, but if used too early it comes at a cost. Thinking of vectors as elements of the space and matrices as ways to transform the space gives a clear separation of concerns, and can make it easier to grasp what's going on.
Later you can discover that by dividing up the matrix the right way you can think of it as 1xN matrices, and then you can associate those with vectors and gain further insight as to what's, but trying to do that early can be very confusing.
After all, an int is a kind of number, and a float is a kind of number, and we can move between those, but there are dangers unless you've got the difference clear in your mind. How many people have complained that 5*0.2 isn't 1.0? Knowing what's happening underneath, and then creating the mappings in your understanding seems to be the fastest way to mastery.
Later you can discover that by dividing up the matrix the right way you can think of it as 1xN matrices, and then you can associate those with vectors and gain further insight as to what's, but trying to do that early can be very confusing.
After all, an int is a kind of number, and a float is a kind of number, and we can move between those, but there are dangers unless you've got the difference clear in your mind. How many people have complained that 5*0.2 isn't 1.0? Knowing what's happening underneath, and then creating the mappings in your understanding seems to be the fastest way to mastery.
Oh right I see. But don't you think introducing matrices as a type of transformation between vector spaces is too much too early? One reason maths is so difficult is that our brain simply has no point of comparison to bootstrap the concepts with. You just get used to it over time with effort. Starting so abstract would leave many people lost at sea.
But then again, a lot of why matrix algebra was so confusing at first is it all seemed so arbitrary. Just memorizing a bunch of boring human calculable unmotivated algorithms. I get angry thinking about it. It wasn't till I read about how they came about in 1800s and studied linear algebra did they start to make sense.
Maybe maths beyond basic probability,geometry and algebra - which can be readily motivated to everyday life - should not be taught to everyone. Then less people would find it useless and more people would not be so embittered towards the subject.
But then again, a lot of why matrix algebra was so confusing at first is it all seemed so arbitrary. Just memorizing a bunch of boring human calculable unmotivated algorithms. I get angry thinking about it. It wasn't till I read about how they came about in 1800s and studied linear algebra did they start to make sense.
Maybe maths beyond basic probability,geometry and algebra - which can be readily motivated to everyday life - should not be taught to everyone. Then less people would find it useless and more people would not be so embittered towards the subject.
I appreciate your response because I have spent many nights trying to connect the dots between linear algebra and game development. When I read about straight linear algebra I can not see the connection to make it useful for me. Now I understand that I have been focusing on the wrong things and really need to simplify it more. Thanks.
I don't see this thing described as "Linear Algebra". I see it described as "Linear algebra for game developers". To me that's two rather different things.
I think it's elementary vectors for game developers.
That's not to put it down, it's just to point out that for 20 years I've heard people saying that they want to learn Linear Algebra because it's needed in games programming, and this is the first time I've seen that perhaps they're talking about something completely different from what think of as Linear Algebra.
This really is vector geometry.
That's not to put it down, it's just to point out that for 20 years I've heard people saying that they want to learn Linear Algebra because it's needed in games programming, and this is the first time I've seen that perhaps they're talking about something completely different from what think of as Linear Algebra.
This really is vector geometry.
In my world (I'm not a mathematician) vector geometry is a subset of linear algebra. Consulting Wikipedia doesn't tell me otherwise:
Linear algebra has a concrete representation in analytic geometry ...
In classical mathematics, analytic geometry, also known as coordinate geometry, or Cartesian geometry, is the study of geometry using a coordinate system and the principles of algebra and analysis.
Regarding another comment of yours it also said:
Thus matrix theory is often considered as a part of linear algebra.
Linear algebra has a concrete representation in analytic geometry ...
In classical mathematics, analytic geometry, also known as coordinate geometry, or Cartesian geometry, is the study of geometry using a coordinate system and the principles of algebra and analysis.
Regarding another comment of yours it also said:
Thus matrix theory is often considered as a part of linear algebra.
I guess the point is that these are parts of a field that is significantly larger and deeper than just these parts.
Vector Geometry is a part of Linear Algebra, it's just not a very big part, just as arithmetic is not a very big part of calculus.
Matrix theory is a much bigger chunk, but the article submitted doesn't go into matrix theory, it just uses a piddling bit of a small amount of using matrices.
And these are valid questions - I don't know why someone down-voted you, and I've upvoted you for asking.
Vector Geometry is a part of Linear Algebra, it's just not a very big part, just as arithmetic is not a very big part of calculus.
Matrix theory is a much bigger chunk, but the article submitted doesn't go into matrix theory, it just uses a piddling bit of a small amount of using matrices.
And these are valid questions - I don't know why someone down-voted you, and I've upvoted you for asking.
I can only speak for myself, but when i hear of linear algebra, I think of my 'linear algebra for scientists/mathematicians' course in college.
The math behind signal processing; I only took 2 classes in college, and boith were pretty hand-wavey (granted, it's hard to rigorously cover S and Z transforms when you know 100% of the class hasn't taken and probably never will take complex analysis.
The math behind signal processing; I only took 2 classes in college, and boith were pretty hand-wavey (granted, it's hard to rigorously cover S and Z transforms when you know 100% of the class hasn't taken and probably never will take complex analysis.
note that this is just part 1 of 4.
(I am assuming you didn't read all four parts, because that material would have to be covered impressively quickly to fit in 20 minutes)
Well, 20 minutes was perhaps an exaggeration, but in our first lecture we covered everything up to the end of part 2 and most of part 3. I think in the second lecture we did a significant amount of part 4, but then we went in a different direction.
We certainly did changes of basis and arbitrary dimensional rotation in our first lecture. We didn't do quaternions, and in fact never did in the context of these sorts of things.
Of course, we had done basic vectors and matrices in secondary school - we certainly knew how to multiply N dimensional matrices, and were expected to invert 2-D matrices by hand and compute the determinant of 3-D matrices. They were on the final exam.
We certainly did changes of basis and arbitrary dimensional rotation in our first lecture. We didn't do quaternions, and in fact never did in the context of these sorts of things.
Of course, we had done basic vectors and matrices in secondary school - we certainly knew how to multiply N dimensional matrices, and were expected to invert 2-D matrices by hand and compute the determinant of 3-D matrices. They were on the final exam.
Very nice.
Linear algebra really is the bread & butter of game programming.
Showing the theory alongside examples of how it's actually used to make games 'do stuff' should be very helpful to those getting started. I could have really used a simple set of examples like this when I was first getting a sprite to flit about the screen.
Keep them coming :)
Linear algebra really is the bread & butter of game programming.
Showing the theory alongside examples of how it's actually used to make games 'do stuff' should be very helpful to those getting started. I could have really used a simple set of examples like this when I was first getting a sprite to flit about the screen.
Keep them coming :)
I would recommend following this blog if you like to see impressive progress and tech that no other game can show (from what i've seen)
If people are interested in learning about vectors in a visual programming environment, then I highly recommend this tutorial on 2D vectors by Daniel Shiffman (of processing fame) http://processing.org/learning/pvector/
Ah, I missed you by 8 hours in posting this.
So ...
I'm surprised to see this sort of thing described as "Linear Algebra" because to me it's just utterly basic vectors, pretty much the first 20 minutes of the Linear Algebra course I did. I've always been confused in the past when people have said that learning linear algebra is critical to games and similar, but if this is what they meant, the confusion is largely cleared.
So I'd ask the HN community:
* Is this what you all mean by Linear Algebra?
* What other topics do you want to know about?
Many thanks in advance, I always welcome the opportunity to learn, even when painful at the time.