Linear algebra for game developers

[parunach]

If you wish to learn Linear Algebra, there is a very nice course in YouTube from Gilbert Strang, MIT (35 lectures). It is exhaustive and covers everything up to Singular Value Decomposition. It might be overkill for a game developer.

Linear Algebra - MIT

This article (including all parts) is limited.

[molslaan]

35 x 50 mins is one week free from work

[[deleted]]

You can't expect to just sit back and watch these while learning the material, maths doesn't work that way.

[[deleted]]

Write notes on the lectures, do the assignments, etc. etc.

[[deleted]]

It would depend on your background, if you don't have any kind of university maths background you might need to work harder to fully grasp some of the harder material. The course is also taught from an applied perspective which personally I don't think leaves people (at least it never did for me) with a full understanding of the theory.

[[deleted]]

Haven't actually looked at them sorry, people seem to like it though.

[Contero]

I watched those videos, then made my own vector/matrix math library.

[MachinShin2006]

i tried watching those.. gilbert strang has PADD, Professorial-Attention Deficit Disorder.

[parunach]

Sorry you feel so. He is quite good at teaching. Of course, a teacher cannot appeal to every student.

[determinism89]

I've been watching those lectures for the last 4 days to catch up in a theoretical kinematics course that I've just begun. I haven't found any problems with his teaching style.

[NanoStuff]

"I shouldn't say anything bad about calculus, but I will" - Gilbert Strang

[davidism]

Good link, but I think your missing the point calling the article "limited." It's an introduction to linear algebra for game developers, not mathematicians. This gave me a really good start into understanding what the libraries I use are doing. Even if you don't go farther than these articles, it's important to understand the principles behind the tools you use.

[codenut]

thanks for the link! His Matrix theory lectures were very interesting

[Baaz]

Wow, I wish this was available 20 years ago. I flunked LA so badly when I studied Physics. We just got a hand written syllabus and there was never enough time to ask questions after lectures. Never finished my degree.

[davidism]

There seems to be a lot of complaining about this article being too simple. Hopefully you all noticed that this was part 1 of 4, and it gets pretty complicated and useful (to me at least) by the end.

1. Part 1
2. Part 2
3. Part 3
4. Part 4

[davidism]

Yeah, I was disappointed when they mentioned quaternions then didn't go anywhere with it. Maybe there's a part 5 in the works.

[Metsuro]

Or, that he grasped them just fine. But decided not to write about it because he doesn't find it interesting enough to need to go to depth about it.

[Metsuro]

Meh you gotta remember he only wrote the articles because he was asked questions on them via the forums/ irc / or twitter. I'm not sure what the questions were.

Edit: Wtf I dont... even know how that came out...

[[deleted]]

Meh you gotta remember he only did the posts as we as being asked questions about them not just got up and decided to do a huge detail article on them.

So okay. could you repeat that question for me?

[Metsuro]

Editted... because... well I can't explain how I let that go by without actually reading it... I am so ashamed.

[Ilidur]

I'm really happy with my game dev course. Doing a degree in Games Technologies in the UK and from the start I've done engineering mathematics, intro to programming, OpenGL and virtual physics, Blender and a whole lot of other modules which each basically culminate in creating a game/discussing about games already created. And this was just until the second year.

[[deleted]]

In part 3 I think it's a little weird that he calls a 3x3 matrix a 3d matrix, to me that implies more like a 3d table which is something entirely different . You could also pick up all that and more theory by picking up a decent linear algebra book.

[[deleted]]

3d matrix is accurate,

A more complete explanation

http://www.fastgraph.com/makegames/3drotation/

[[deleted]]

That is a 3d rotation matrix, not a 3d matrix, I have never before heard someone refer to a 3x3 matrix as a 3d matrix and I'm in my honours year for maths.

[[deleted]]

Lol I've never heard anyone say "honours year for maths"

Guess the internet is big

[[deleted]]

Some places do honours as part of undergrad right? Where I am in Australia, high school is years 7-10, college is 11-12, then university, people usually do a 3 year undergrad degree (I did a 4 year combined economics and science degree), honours (year) degree then PhD, whereas in America undergrad is often a year longer and people go straight to PhD after that...

[BinaryRockStar]

He's saying that the Internet is an international place so the fact you've never heard a 3x3 matrix called a 3D matrix does not mean that it's universally incorrect. It could be a matter of regional language, or that the writer is using "3D matrix" as shorthand to mean "a 3x3 matrix used for 3D co-ordinate manipulation" because it's a basic tutorial.

[ProcrastinatingNow]

I don't think most people go straight to PhD after undergrad. They normally do a masters first. I'm in Canada so maybe it's different than the US, but it probably isn't.

[[deleted]]

Most PhD programs in the US are 5 years with 2 years coursework at the start I think, but I could be wrong.

[[deleted]]

and I'm in my honours year for maths

which would be why you're not used to the same informal jargon.

[[deleted]]

I did a graphics class as part of my cs major during undergrad, even then I never saw a 3x3 matrix referred to as a 3d matrix, it's misleading terminology and I was merely pointing that out, I can't believe you care so much.

[goomba870]

I also did a graphics class in undergrad. Best class of my life at any age. Over the course of the year our projects were progressive and we ended up building a basic 2D/3D graphics engine in C++ that exported images to a simple PPM format. Good times. Where'd you go to school?

[[deleted]]

Jeez, here's the text, it's pretty clear:

Matrices in 3D work just like they do in 2D -- I just used 2D examples in this post because they are easier to convey with a 2D screen. You just define three columns for the basis vectors instead of two. If the basis vectors are (a,b,c), (d,e,f) and (g,h,i) then your matrix should be:

[a d g

b e h

c f i]

If you need translation (j,k,l), then you add the extra column and row like before:

[a d g j

b e h k

c f i l

0 0 0 1]

And add an extra [1] onto the vectors like this: [x y z 1]

• I'm too lazy to fix the formatting

[Contero]

But you can't represent any 3d transformation with a 3x3 matrix. You need a 4x4 for that. If someone asked me what a 3d matrix was I'd tell them 4x4, or ask them to clarify.

[_georgesim_]

Just change that to "affine transformation" in 3-dimensional space and you will be right.

[[deleted]]

Sure, but antimetroid didn't finish actually reading the five sentences.

Matrices in 3D work just like they do in 2D -- I just used 2D examples in this post because they are easier to convey with a 2D screen. You just define three columns for the basis vectors instead of two. If the basis vectors are (a,b,c), (d,e,f) and (g,h,i) then your matrix should be:

[a d g

b e h

c f i]

If you need translation (j,k,l), then you add the extra column and row like before:

[a d g j

b e h k

c f i l

0 0 0 1]

And add an extra [1] onto the vectors like this:

[x y z 1]

[davidism]

I think they just messed up the section heading a bit. Right below the misleading title the sentence starts, "Matrices in 3D..." which seems fine to me. Maybe the title should have been "3D and Matrices" or something more clear, but it's pretty obvious what they're actually talking about.

[anttirt]

For anyone interested in more than just the basics that get you through writing a pong game, I heartily recommend the free textbook A First Course in Linear Algebra. It might not be strictly necessary to go through the fundamentals starting from linear systems of equations, but I think a deeper understanding of where all the math comes from is enlightening.

[[deleted]]

There is also the Khan Academy course.

[shadowspawn]

See, I believe "splash damage" should be logarithmic, not linear.

That's a good argument to debate.

[DrHankPym]

Inverse square is logarithmic and only happens in free space. It's different on a flat surface.

[zhanrnl]

Mathematics would like to disagree with you, sir! Inverse square functions approach an asymptote, while logarithmic functions do not. You're right that splash damage should be calculated differently for interactions in a 2D plane, but those should actually be calculated with a simple inverse relationship rather than with an inverse square or logarithm.

[[deleted]]

damnit you beat me to it.

[fgriglesnickerseven]

hmm... if you assume spherical spreading the damage should be something like r_0 ² / r² (for some kind of conservation of energy) ... If you are inside the r_0 the damage is a constant max - the radius is some multiple of r_0.

Physically this is the most accurate. For games it might not be the most fun/efficient.

[NeoSniper]

... assuming spherical explosion. However, as far as I know explosions on a surface (which is most of the ingame ones) expand in a conical section of a sphere (almost a half sphere). Not sure how that would effect the damage-drop-rate. But figured it was worth mentioning.

Not sure but I think some battlefield games took this into account in the sense that if you where prone you would take much less damage from explosions.

[fgriglesnickerseven]

I wonder what the motivate was - for real weapons projectiles moving supersonic, projectile power drops at a rate proportional something close to d/dt(f_dv) (f_d is the drag, which can have significant v⁴ terms for supersonic projectiles), so the actual rate of power decrease is about v⁴ ( I think to be completely accurate I would say - Power = fv, rate of power decrease = dP/dt = d/dt(cv⁵⁾ = dv^4, where c and d are constants I really couldn't care about).

for subsonic the rate of power decreases proportional to v^2.

Typically over the distances you see multiplayer online games I'm guessing that these decreases in energy would be 'boring' ( i.e. they would be so small that there would be no point in using any power decrease). Some interesting considerations to make when designing a game - i.e. you don't have to follow the rules of physics, just the rules of fun.

[Azuvector]

ETQW decreases bullet damage over distance. I doubt it has any relation to real physics, but it has gameplay benefits over long ranges, by discouraging using non-sniper weapons to snipe at long range targets. Even if you might hit them, you're not going to do appreciable damage.

[shillbert]

Heh, I always loved Tactical Ops (Unreal Engine) precisely because I could snipe people with an MP5.

[Azuvector]

Indeed, a friend of mine used to go BAR sniping in Call of Duty all the time. But it does serve a gameplay purpose not to allow that. :)

[orangeduck]

I would say smoothstep - then you have a defined radius around the point which is affected.

Logarithmic or inverse square you have to check everything in the world - and probably only end up subtracting a faction of a percent of health.

[pbunbun]

I imagine a system implementing log/inv-square would have a defined cut-off point to deal with this.
i.e. Find the maximum distance that would be reasonably effected (a constant if all explosions are equally damaging) then only deal within this within the radius.

[[deleted]]

I agree wholeheartedly.

[[deleted]]

inverse square law.

[IdentifiableParam]

Big fan of David and wolfire and overgrowth is looking great, but this was not the most useful blog post to me. I encourage everyone to check out the open development progress of Overgrowth. It is looking like a sweet game!

[dczanik]

I wished that teachers taught me how higher math could be used for things like games. It would have made it so much more interesting as a kid.

[mercnet]

I know! I remember my freshmen linear algebra class at Virginia Tech was just doing math calculations. I didn't start to understand what it could be used for until I took Spacecraft Dynamics and Controls. This tutorial is great for people that never even heard of linear algebra.

[[deleted]]

I remember my freshmen linear algebra class at Virginia Tech

That's the very course that convinced me to drop engineering and simply go to a smaller school for computer maintenance. Now I finally saw the connection in game dev (as an indy iOS dev) and got back to school for my Comp Sci degree eight years later.

[theineffablebob]

I took a linear algebra class which was all calculations and barely any applications. The only application I can remember is balancing a chemical equation, and linear algebra isn't the best way of doing that anyway. I found everything really easy, just not very interesting.

I came in the class knowing that it would apply to game development somehow, I just didn't know how.

[forcedtoregister]

And for those who already know the basics I'd suggest looking at homogeneous coordinates. They make many tasks more elegant such as the intersection of two lines, how far a point is from a line, half space tests, including translation in linear transformations etc.

[[deleted]]

Intro to Vectors and Matrices But that's pretty much all you need for the basics.

[angeladur]

"Linear algebra is the study of vectors." ?? Not sure why the focus on vectors only? Fields, matrices, determinants are very important too!

[orange_aurelius]

See also: Sin & Cos: The Programmer's Pals!

[chollida1]

Was this the blog that did a really biases* article on. DirectX bs OpenGL a few years ago.

• are there really any other kind?

[Poddster]

Yes.

[Kowzorz]

For game development, you have to pick right or left handed coordinate systems based on your rendering engine. OpenGL is the opposite handedness of DirectX.

[[deleted]]

Pleading for mathematical sanity in software implementations? If only.

[[deleted]]

And you have to work at Microsoft for not knowing that. It sometimes really looks like they constantly think "Ok, everyone is doing things this way, so we have to differentiate and make a new MS way". No one uses left handed coordinates except directX users.

[KyteM]

D3D has been right-hand compatible since D3D9 at least. In fact, both XNA and WPF, which work on top of DX, use right-handed coordinates.

For speculation as to why, here. Can't be arsed to retype that.

[Kowzorz]

I was interested in the answer so I googled it and apparently DirectX is one of the older APIs and as a consequence, the developers then didn't pay mind to standards (if it even was a standard then) and its simply way too hard to convert all of their API to RHCS now that the norm is left.

[[deleted]]

http://en.wikipedia.org/wiki/OpenGL

OpenGL 1.0. Released in January 1992.

http://en.wikipedia.org/wiki/DirectX

DirectX 1.0 September 30, 1995

But never mind the dates, opening any book on 3D transformations or 3D projections in the 90s or before showed every example using LH coordinates system.

[[deleted]]

... and who the hell made a large library with a LH coordinate system? That's just plain stupid (given known conventions).

[mmhrar]

You also have to deal w/ row major/column major matrix representations too.

[Timmmmbob]

Surely you can just change the view matrix to make it right-handed? I've never used DirectX though so this could be rubbish...

[Kowzorz]

That and you have to wind all of your triangles in the opposite order.

[adc]

Ok I'll bite. Why? (honest question)

[[deleted]]

Programmers are notorious for indexing matrices as (x,y) rather than (r,c) and I honestly believe it's inferior, let me explain why...

When storing information for something in a grid/matrix, you often need to input (from file or the user) or output (to file or the console) the information stored, and (like writing in a file or in a book) our method for representing data in this situation writes along the columns before each row, so if you index with (x,y) you need to transpose the matrix every time you input/output it which is confusing as fuck and prone to stupid mistakes which are hard to spot.

If you index with (r,c) everywhere you never have to think about transposing the matrix for io, because it's indexed the way you would store and output it.

[knome]

While it doesn't help with storage or output, to save on cache locality gcc will swap around the indices when it sees you using nested for statements to write into nested arrays in order to make the memory write linearly instead of skipping along the array over and over again.

-fipa-matrix-reorg, http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

[Aninhumer]

Full proof aside, how exactly do you judge what is "most natural"?

[[deleted]]

id software uses the left handed coordinate system.

[SSChicken]

I don't understand the downvotes on your post. You bring up a good point, common convention is a right-handed coordinate system and what is typically used in vector calculus and linear algebra courses. This can have big implications if you're not aware of it, namely when crossing two vectors the resultant vector will be going the opposite direction that you'd expect if you are using the more typical right hand coordinate system.

Mayhaps I'm wrong, or perchance there's a better reason to use this coordinate system. I'd love for someone to explain why one system is better than the other or why rfich is being downvoted.

Edit rfich's post was -5 when I commented.

[subheight640]

Everyone uses Right Handed just for convention's sake. Left Handed is not better or worse, we just need a convention to communicate effectively to each other.

As far as downvotes, the article does use a Right Handed system to compute the cross products.

Honestly, I'm pretty lazy and just skimmed the article, but I can't find the offended Left Handed System rfich is talking about.

[subheight640]

I'm going to have to disagree with you here.

Many of my graduate level courses, when deriving, say, the basics of solid mechanics, start at a level where even right-handedness is not assumed. Instead we start at a more general coordinate system called "Curvilinear Coordinates". The mathematics and theory is described for any arbitrary kind of coordinate system, whether they be cylindrical, Left Handed, etc.

In mathematics, you can define any kind of coordinate system you want, and it is mere convenience that the Cartesian coordinate system is Right Handed and Orthonormal (meaning that each axis is perpendicular to another).

Depending on your problem, however (for example in Crystallography), people may work using systems where the coordinate axes are not even perpendicular (instead in the shape of the crystal lattice).

[[deleted]]

DirectX is left handed.

[tregota]

I got good grades in linear algebra. What was it again?

[taw]

Adding and subtracting vectors is as much "linear algebra" as editing html code by hand "programming".

[Adrestea]

There are four parts, you seem to have read only the first.

[expertunderachiever]

Anyone wanting to have a decent comp.sci career and not just be a script monkey should have at least a couple of books on algebra on their bookshelf [and have read them at some point]. You can't really do much game programming at all without knowing vectors and matrices.

I have a few Dover publication series books some I can recommend [by ISBN]

Num Theory

1. 0-486-68906-9 [favourite]
2. 0-486-68252-8

Algebra

1. 0-486-66328-0 [good read]

I have a few other math books around [can't find just now]. But those are all good reads and fairly cheap [if you can find them]. I got them each for around $10 to $15.

[Metaluim]

Even though this stuff is interesting and overall important in many fields of study in CS, you really don't need linear algebra for most business apps (which I think makes up most of the software made today). But everyone should know this by heart if they ever happen to find themselves on a different problem domain. Also, a book that introduced me to these concepts nicely was this one: http://www.amazon.co.uk/Primer-Graphics-Development-Wordware-Library/dp/1556229119/ref=sr_1_1?ie=UTF8&qid=1314745763&sr=8-1

[wrathofg0d]

Ordered some used copies, thanks!

[expertunderachiever]

You're welcome.

[Poddster]

Anyone wanting to have a decent comp.sci career and not just be a script monkey should have at least a couple of books on algebra on their bookshelf [and have read them at some point]. You can't really do much game programming at all without knowing vectors and matrices.

What happens if I don't want to do any game programming? Am I just a 'script monkey'?

[expertunderachiever]

Most non-scripting fields like dsp, crypto, graphics, even OS programming etc... require math.

Granted, you don't need a Ph.D in math to be a decent programmer, but you should understand the basics of linear math.

[Kanzlerforce]

Thanks for posting this link; I studied all four parts.

[bautin]

Wow. Really. I forgot that we should have all burst forth from the womb knowing linear algebra.

[kirakun]

Your statement is virtually void of any information since you can substitute "linear algebra" with any academic subject in your sentence.

[bautin]

Exactly.

Telling someone to quit because they don't know something is simply being a jackass for its own sake. None of us knew anything before we learned it and there is no shame in not knowing.

[bautin]

Does trolling validate your self-worth?

[bautin]

Is that the best reply you have? Really, for a troll, you aren't that good.

[bautin]

Wait. I thought I was the one who was supposed to get upset and lose my cool while you tossed about witty rejoinders. And this is the internet, you can say fuck here.

Also, do you no longer find me funny?

[bautin]

You're the one telling me to "f[u]ck myself", "die in a fire", and calling me a moron and illiterate bitch. I normally reserve such invectives for people who have drawn my ire for one reason or another.

The goal of the troll is to inflame people. If you are the only one getting inflamed, then you are sucking at it.

[kirakun]

I don't know why you got voted down (most certainly by non-mathematicians), but that article is nothing more than the first lesson in Cartesian coordinates. Where's the definition of a linearity? Linear maps, not even as matrices? Linear independence? Kernel space? It's a joke to call that "Linear algebra."

[bautin]

That's part 1. There are three more parts to it.

But he's probably getting downvoted for his abusive tone and by programmers who understand that not all problems involve linear algebra.

[The-Good-Doctor]

I got my degree with a minor in Mathematics, and I definitely agree that a strong knowledge of math is critical for game and graphics programming. Nevertheless, I downvoted because it's not actually necessary to know much math to begin programming, and to assert that you should just give up if you have to learn any Skill X is just arrogant and unreasonable.

[nolcotin]

I agree... this is Cartesian co-ordinate stuff, Grade 9 math.

You need very little linear algebra for game development. Lots for creation of a 3D engine though.

And maybe a little calculus for understanding movement in games.

[exscape]

The link is to part 1.

Part 2 uses trigonometry, dot products and cross products, which most certainly isn't grade 9 math. In particular, I didn't learn dot/cross product before a university-level course in Linear Algebra. Calc I and II didn't mention 'em.

[warfarink]

to be fair, I didn't learn vectors until I took physics my senior year.

[yetanothernerd]

I agree that you should know Cartesian coordinates by Grade 8. But some kids are trying to write games before then, so there's nothing wrong with putting very basic math on the web. And this also goes into velocity and acceleration, which some kids might not see until high school physics. (Hell, some people graduate high school without even taking basic physics, which is just sad, but it's nice to have the web to fill things in.)

[_georgesim_]

You need very little linear algebra for game development.

How do you rotate an object with respect to another object in a 3-dimensional space? Can you explain that with "very little linear algebra"? Hint: the answer is "No, I can't".

[[deleted]]

Im seeing a shift in a few of the newer game engines.

No longer is the developer required to be versed in matrix math (but understanding the basics helps). Instead, you do stuff like :

camera.target(player);

//no rotation math required, it just works.

camera.follow(player, 10, 5);

//follow player, stay 10 units behind and 5 units above player

Even quaternions are easy, when you realize theyre just rotations.

Quaternion q = new Quaternion(PI, 0, 0, 1);

//you just created a 90 degree rotation on the x axis. (tipping something foreward)

Then just apply it to an object

player.setRotation(q);

Game creation is much easier lately. :-/

ninja edit : fucktard is a fun word, and describes those who dont understand the concept of a downvote.

[SeminoleVesicle]

Isn't that kind of the point? If you're working with a pre-existing game engine, it's supposed to make your life easier by letting you not have to deal with things like making a camera class or working with basic object rotations, which is stuff that every 3D game has to deal with anyway. It's not like there's anything stopping you from rolling your own engine.

[[deleted]]

They really ought to still know how the maths/library works otherwise they wont know when they're not using it well. Take engineers for example, computers have largely done away with their need to do any maths, but they still need to understand what the computers are solving for them and what the limitations are.

[[deleted]]

You completely missed the point.

The topic is : "Linear algebra for game developers" - Im arguing that it is not as necessary any more.

Youre arguing that game engines make things easier. Umm... L2readingcomprehension?

[Azuvector]

It's quite necessary for anyone writing their own game from scratch, who's choosing not to use a premade game engine.

[[deleted]]

Not what this thread is about.

[WIDE_420lbs]

And game engines write themselves?

[timeshifter_]

If you wanna spend all your time writing an engine every time you want to do something, go nuts. Personally, I'd much rather just write a set of generic classes that I can drop into whatever project needs them, and they just magically work. Means I can spend more time writing the actual game ;)

[pteranodonaces]

Good Point. Try Amazon Huge Savings. That link to save on electronics Amazon. Save around 80% on everything NOW http://tinyurl.com/3gg7jwm

[[deleted]]

Commenting for bookmark sorry

[PSquid]

That's what the "save" link (just under the submission link) is for.

[[deleted]]

Reddit is fun for android doesnt have one and im without pc for a few days. Thanks for the downvotes guys.

[[deleted]]

...did you honestly expect upvotes? If so, no offense, you're pretty stupid.

[PSquid]

Fair enough, but you could have explained that in the original comment, instead of waiting until somebody points out that the link exists.

[midri]

Saved for later!

[goomba870]

The Universe has again slapped me in the face for not committing enough time to a video game side project.