Graphics fundamentals - the why of "4-D" (homogenous) coordinates

(Note: This is not meant to be a comprehensive list of the why's of homogenous coordinates, just some of the bigger ones)

Apparently computer graphics is a bit of a black art when it comes to why things are represented the way they are, even if you "know" basic linear algebra.

This is a response to http://shawnpresser.blogspot.com/2010/10/how-to-become-game-programmer.html by way of http://www.mauriziopz.eu/from0togame/.

In this article the only prerequisite is knowing matrix multiplication is not commutative(i.e. order matters in multiplication of matrices) and how to multiply and add matrices.

If you've never been exposed to OpenGL or D3D you might assume everything is done with 3x3 matrices, but you'd be wrong.  Actually, everything is done in homogenous ("4-D") coordinates.  Now why the hell would you use "4-D" coordinate when you're going to be projecting 3-D objects onto a 2-D screen?  Well, it simplifies the math, that's why.

Suppose you have a line segment (from pt A=(1,1,1) to B=(0,0,0)) in space and you want to stretch it along the y-axis and move it out one unit from the origin on the x-axis. Well, using normal 3-D coordinates you'd need your scaling/stretching matrix (S) and your translation vector (T)

Translation is pretty straight forward just add how much you want to move it on each axis (negative for moving it closer to the origin, positive for further away).

T = (1, 0, 0)

The basic scaling matrix looks like this

  [stretches x 0 0]

S=[0 stretches y 0]

  [0 0 stretches z]

We'll stretch it along y by double, so we just make the second term 2 and the rest 1.

  [1 0 0]
S=[0 2 0]
  [0 0 1]

Then you apply it to your points (A and B).

(First stretch then move)
New A = SA + T and
New B = SB + T

Well, what's wrong with that? It seems simple enough. And it is until you realize that most graphics objects are going to be significantly more than two points and you need to apply those transformations (and usually many more) to each point in the same order (because remember multiplication is not commutative for matrices).

Now how can we make this process more fool proof? Well, if we had a way to represent all our transformations as a single object that would make it much easier to not make mistakes. And hey, while we're at it let's only have to worry about one type of object, matrices, for those transformations (rather than matrices and vectors/points).  It turns out that the 4x4 matrix space takes care of both of these problems for us. And for free it throws in elimination of an operation, addition. Yup, now we can do all of our transformations as matrix multiplication only.

Going back to our last example if we add another coordinate we have points that looks like P = (x,y,z,w). Now we're going to set w to 1, so terms don't disappear on us as we move our points around. This makes our original points A=(1,1,1,1) and B=(0,0,0,1).

First, in 4x4 space we have to notice that the identity matrix is


   [1 0 0 0]

I= [0 1 0 0]

   [0 0 1 0]

   [0 0 0 1]

The 1 in the bottom row is important to keep things consistant just like having w = 1. As I'll show in a couple of steps.

This makes scaling matrices look like

  [Sx 0  0  0]

S=[0  Sy 0  0]

  [0  0  Sz 0]

  [0  0  0 Sw]

For the most part we'll never scale w because it is just there as a place holder.

Moving our S from 3x3 to 4x4 we get

  [1 0 0 0]

S=[0 2 0 0]

  [0 0 1 0]

  [0 0 0 1]

Now let's put our T in 4x4 as a matrix this time

  [1 0 0 Tx]

T=[0 1 0 Ty]

  [0 0 1 Tz]

  [0 0 0 Tw]

Why are we doing it like this? Well we need to notice that if we multiply a matrix and a point (x1,y1,z1,w1) in 4d we get

[1(x1) + Tx(w1)]   [1 0 0 Tx][x1]

[1(y1) + Ty(w1)] = [0 1 0 Ty][y1]

[1(z1) + Tz(w1)]   [0 0 1 Tz][z1]

[Tw(w1)]           [0 0 0 Tw][w1]

This is almost what we want. Except that w1 is in the way.  Ah, that's why we set w=1. If we do that everything works out right.

Now we can do our formulas again, but this time we need to combine matrices before apply it to the point

New A = (T+S)A and

New B = (T+S)B

I thought you said we could eliminate addition I hear you crying. We can! IF you set Sw = 1 and Tw = 1

[1 0 0 Tx]   [Sx 0  0  0]   [1 0 0 Tx]   [Sx 0  0  0]

[0 1 0 Ty] * [0  Sy 0  0] = [0 1 0 Ty] + [0  Sy 0  0]

[0 0 1 Tz]   [0  0  Sz 0]   [0 0 1 Tz]   [0  0  Sz 0]

[0 0 0  1]   [0  0  0  1]   [0 0 0  1]   [0  0  0  1]

That gives us a single matrix that we can work with now

         [Sx 0  0  Tx]

TS = T*S=[0  Sy 0  Ty]

         [0  0  Sz Tz]

         [0  0  0   1]

Now we can take this TS matrix and apply (multiply) it to each point, rather than having to apply a formula to each point. This saves us coding and it also saves cycles (by only combining our transforms once, rather than each time we apply it to a point).

New A = (TS)A and

New B = (TS)B

Be careful with this example though, even though it doesn't matter what order we did the operation this time that's not true once you start rotating things in space, then it very much matters what order you build your transformation matrix in.

If you want to learn more about this subject let me know and I'll start posting about some more of the fundamentals.  Or you can go to check out this course on fundamental math used for graphics (http://bit.ly/hTJNA3). He keeps the linear algebra as simple as possible. For a more in-depth explination see chapter 4 of Essential Mathematics for Games and Interactive Applications, Second Edition: A Programmer's Guide (A great book, all the math you need for graphics and games, but in general WAAAY more than you need for most projects and it's pretty formal so you better remember your sophomore/junior level linear algebra. Overall, it makes a great reference though). 

Let down by the system?

I read this presentation the other day and was struck by how much it sounded like advice I've heard for computer science students.  Go do something real, anything! Go work on an open source project. Start your own. Work through OCW material, something that other people haven't done. And although it has that self-help guru slimy feeling to it, it does a decent job on delivering what it promises.

Recession-Proof Graduate

View more presentations from Charlie Hoehn.

I was treated like Charlie when I was in college. I was told over and over just get through school and you'll have an amazing job waiting for you at the end of it all.

Having my computer science degree in hand I can tell you that's not exactly true. While it is an enormously marketable degree and I've never had trouble finding a job, they weren't exactly stimulating or enriching jobs(in any sense of the word) and they actively drained my passion for technology, but I thought that was what a fresh grad was SUPPOSED to do.

Building on Charlie's thoughts I think the problem is two fold. And it isn't a problem with college per se, but more the attitude about college.

First, the education system and people's thoughts about it are stuck in the past when getting a degree wasn't something you were expected to do. It was something people did to get ahead, somewhat like getting a master's degree or MBA today (this won't be true tomorrow though; considering the rate we're cranking out MBA's and other advanced degrees). It made you stand out in the crowd of other people.  Sure maybe there were 50 applicants for a job in the 80's, but only five of them had degrees. Unfortunately this idea is still lingering and people in college the idea they are entitled to a job upon graduating.

Well, that idea is total crap. It's never been the degree they cared about. They just wanted some way of weeding through all the weak resumes down to a number that was manageable. People aren't good at making choices based on a large numbers of options. Think The Paradox of Choice. They want a handful of decent options to consider.

This leads to the second problem. The idea of doing a job search the way they teach you in high school and college (by finding job postings, sending out 1,000 resumes and praying for an interview) is completely useless, especially for new graduates! Like Charlie talks you're competing with all the people that have been in your field for more than a decade, all the people overseas that will do anything to get to the states, and all your peers. Good luck standing out in that crowd.  The other method they tell you to use is networking talk to everyone and I'm not sure about you, but I've never met anyone outside of sales that's ever actually been successful with that approach until they started developing skills and a reputation for people to talk about. "Oh, Josh? Yeah, I know him... He's that guy I went to college with. I think works for a computer company now or something." or "Hey, you should come work for my company they're awesome we make software that counts beans! (and they give me a hiring bonus for every sucker I bring in)." Most people don't get their dream jobs like that.

If you want to stand out and get your dream job then you can't follow everyone else and just try and do it better than they did. In the past I've tried to follow the culture and read Slashdot or Arstechnica and while entertaining, it hasn't let me forward. I could read twice as much Slashdot or write four times as many merge sort algorithms in the languages of the day, but that wouldn't put me ahead of the game. If you think the heart of the tech industry is facebook then let me tell you, you're way behind behind the time. Yes, facebook's a great company and they do cool shit, but they're no longer "it". And if you start with your goal of aiming to get into facebook then you're just like the 10,000 other CS grads this year that want that nice big cushy salary they offer.

What I've found has helped me most in finding jobs I'd actually want to do is to plug into the community that's on the bleeding edge of your field (not academia, of course) and follow it.   For me, right now, that's Hacker News.  If they recommend a book to each other, then read it and try to figure out why they recommended it. If they think a program is awesome, spend time with it and figure out how they made it like that (ideally read the code if it's open source). Be pick a technology or language that's brand new or no one uses and learn it just for the experience. Once you plug it you'll start feeling the ebb and flow of different topics and what's hot or not and once you learn more and more you'll be able to start picking them out yourself. Once you're on the pulse of the industry you start seeing potential jobs everywhere you look.

I'm not sure I stayed on topic here, but I think I said what I was trying to. Conventional wisdom is wrong and you need to stay at least one step ahead of everyone else if you really want to do great things. Who know, by the time you read this all this information may be out of date, but the ideas are sound no matter when it is. If tomorrow everyone has Ph.D.'s (and that may very well turn out true the way the academic system is churning them out in the US) then just having a Ph.D. won't mean anything to anyone. And all the smart people will have found twelve new ways of standing out.