Monthly Archives: November 2013

Matrix Multiplication, A Novella: Chapter 4

So now you work at a video game company. That happened in between chapters.

That means you’re big league rolling! All those Khan Academy videos and Intro To Linear Algebra courses keep saying video games use matrices, and you’re gonna find out how.

Nathan Drake WireframeSo, most big-budget video games use 3D models (there’s 2D big-budget games, too, but fuck ’em). You’re probably familiar with the idea that all 3D models are composed of a bunch of tiny triangles (or squares, which are just two triangles touching bellies). Although each triangle alone is just a geometric shape, you can pile on enough of them (and have pretty enough textures sitting on top of them) that it all starts looking like a human face.

Anyhow I can’t make a human face so I’m gonna use those triangles to form Simple-O, the Simple Robot.

You keep doing your thing, Simple-O.

You keep doing your thing, Simple-O.

Now, all those triangles that make up Simple-O? You can think of all the triangles combined as being a set of 3D positions (called vertices), and a list of mappings:

vertex0 = [1.5, 2.3, 0.5] //a 3-dimensional position in [x,y,z]
vertex1 = [1.7, 2.3, 0.5]
vertex2 = [1.7, 3.0, 0.5]
vertex3 = [1.5, 3.0, 0.1]

triangle0 = [vertex0, vertex1, vertex2] //a triangle with endpoints at vertex0, vertex1, and vertex2
triangle1 = [vertex0, vertex2, vertex3] //triangle1 touches bellies with triangle0

Those mappings — the idea that triangle1 is made by connecting vertex0, vertex2, and vertex3 — never really change. The triangles that form Simple-O’s left arm will forever form his left arm.

That said, although vertex0, vertex2, and vertex3 will forever be a triangle, their individual positions can and will change — for instance, their y value will increase if Simple-O becomes twice as tall.

Okay, Simple-O, thats kinda weird.

Okay, Simple-O, that’s kinda weird.

If Simple-O is going to be twice as tall, although we don’t need to touch our mappings, we need to touch every vertex. Since 3D characters for 360/PS3 games can have 15,000+ vertices, we’re talking lots of vertices becoming twice as tall.

At this point, there’s some parallels to your job at the North Pole calculating presents for kids based on their actions:

  • We’ve got a super-long list of items
    • Kids in the North Pole
    • Vertices in Simple-O’s 3D model
  • Each item has multiple values associated with it
    • Number of punches/hugs/kisses per kid in the North Pole
    • Positions in x, y and z per vertex in Simple-O’s 3D Model
  • Given these values, we want to compute different-but-related values per item
    • Convert number of punches/hugs/kisses into amount of candy/coal per kid in the North Pole
    • Convert positions in x, y and z into new positions in x, y and z after growing twice as tall in Simple-O’s 3D model

Now, when we dealt with kids in the North Pole, it was easy to understand the conversion from punches/hugs/kisses to presents. We’re getting a lot subtler when we talk about vertex positions in video games. There’s two important differences to recognize here.

First, while punches, hugs, and kisses are clearly separate actions, positions in x/y/z are not so separate at first glance. After all, you move between x, y, and z every day without thinking of which dimension you’re moving along, right?

The key here is to think not in terms of one location in 3D space, but to think in terms of 3 locations in 3 separate 1D spaces. It’s hard to do, because we’ve been trained to think in terms of 3D space since we were babies trying to reach for the food in front of us. Just remember — when a point moves up or down (its y value changes), it does nothing to the x or z values. x, y, and z really are separate. An object moving diagonally is doing two separate things at once — like a child punching while kissing. The fact that punching-while-kissing is harder than moving diagonally doesn’t matter. You are not looking at one value (position), you are looking at three completely different values (distance-along-x-axis, distance-along-y-axis, distance-along-z-axis).

Second, when we converted actions-per-child into presents-per-child, we went from one set of information (actions a child performs) to a completely different set of information (presents the child deserves). Our matrix to make Simple-O grow twice as tall isn’t really giving us a new set of information — we’re converting from x/y/z values on the vertices that define his model to slightly different x/y/z values. We don’t ever stop talking about x/y/z values-per-vertex, not like we stopped talking about actions-per-child when we moved to presents-per-child.


This is a weird logical leap, and it has a lot of implications worth thinking about. For instance:


Let these differences sink in — re-read the past few paragraphs if you need to. They are super-important to feeling comfortable with 3D vertex positions.

Once you’re done letting them sink in, we can move to the next task: what the heck does B, the position-after-2x-taller per position matrix, look like? Or, how do we represent the idea of “grow twice as tall” as a matrix?

Actually, it’s pretty simple: let’s think of it in terms of outputX, outputY, and outputZ per inputX, inputY, and inputZ. It’s a spreadsheet just like we’ve been doing.


In our old presents-per-action spreadsheet, each row defined an action and told us how performing that action affects what presents you’ll get. Each column defined a present and told us what actions would contribute to getting that present.

We can apply that reading here. Each row defines a distance in either the x, y, or z dimension and tells us how that distance affects our distance along x, y, or z when we’re twice as tall. Each column tells us what our x, y, and z values for a theoretical twice-as-tall Simple-O rely on.

Let’s fill this in slowly.

First, we know that when you get taller, your distance along one of the x, y, or z dimensions doesn’t affect your distance along either of the other two dimensions. That is, getting taller doesn’t make you wider or fatter. So, our input x value can only affect our output x value, and same for y and z. Our outputs for a dimension only depend on our inputs in that dimension, and everything else can be set to 0.


Next, as we just said, we’re only getting taller — not wider or fatter. So our ‘inputX->outputX’ and ‘inputZ->outputZ’ values are both just ‘1’ — our taller Simple-O is 1x as thick and 1x as wide.


At this point, it should be obvious: since we’re getting twice as tall, our ‘inputY->outputY’ value is 2. That is, our outputY is double the distance along our y-axis than our inputY.


And that’s a 3D scaling matrix! As you can imagine, setting any of your x, y and z values to a non-1 value will make Simple-O that much wider, taller, and fatter. let’s see what our vertical scale looks like applied to Simple-O:


Nicely done!