Category Archives: Math

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!

Matrix Multiplication, A Novella: Chapter 3

There’s too many kids in the world!

See, you set up a great system going on for tracking a kid’s actions and determining how much coal or candy they get. It’s easy, and it’s foolproof. Why, it’s so good that Santa cut the budget for North Pole Behavior Psychology Lab, because he thinks you’re capable enough to do it without money.

Now, this is a problem. More and more kids are believing in Santa every day. And the computers you’ve got running the matrix multiplications to determine each kid’s presents? They’re slow. Relics from the 80s.

In fact, you just crossed a scary threshold — given the number of children Santa needs to deliver to next Christmas, you don’t have enough computing power and time to determine presents for every kid by Christmas Eve. Christmas can’t happen.

There’s three ways you can fix this problem:

  • Reduce the number of kids to compute presents for
  • Increase the number of computers to run math
  • Decrease the amount of time it takes a computer to compute presents

Unfortunately, thanks to budget cuts and your lack of desire to kill children, you can’t implement the first two solutions. Sounds like you have to make optimizations if you want to save Christmas again.

So let’s re-examine our pipeline. Identify anything we can simplify.


Alright! So we go from knowing the actions per child (matrix A), to knowing the points per child (A*B), to knowing the presents per child (A*B*C).

Huh. So, when we look at our system this way… why do we even bother with matrix B, the points per action matrix? I mean, we cancel out both terms belonging to B when we multiply A*B*C — we don’t ultimately care about points or actions. Can we fold B into C? Create one presents per action matrix, and discard the idea of “points” entirely?


Ooooooh. That’s a good idea.

Yes! That is totally possible! In fact, this is one of the most awesome and convenient things about matrix multiplication. All you need to do to combine B and C into a presents per action matrix is… multiply them.


And if we multiply our actions per child matrix with this new presents per action matrix…


It’s the same result as we got before! That’s our exact presents-per-child matrix from previous chapter, but we only did one matrix multiplication to get it!

This is called the associative property of multiplication — previously, we did (A*B)*C, and now we’re doing A*(B*C), and we get the same results. That is, matrix B can associate with A or C. If B and C are both constant matrices, we can just multiply them together into a new matrix D=B*C and use it everywhere.

So with one quick calculation of D=B*C, you just halved the amount of processing time your computers need to calculate presents per kid! You are really good at saving Christmas, dude.

Matrix Multiplication, A Novella: Chapter 2

Well, your days as an event planner are over. There was a lot of blood at Bacchanal S, and the police are looking for you. So you ditch town, fly to the North Pole, and find a job in Santa’s Behavior Psychology lab.

“Naughty” and “Nice” aren’t simple concepts, and Santa needs experts to determine which child is which. The lab tracks each child’s actions, and each action is associated with a naughtiness and niceness “score”… hey, does this look familiar to you?


Good lord, this is just like the spreadsheets you used as an event planner!


Okay, you just crushed some naughty/nice scores — but there’s more. There’s another spreadsheet that determines what Christmas presents a child gets for a given amount of naughtiness or niceness:


You can handle this! You have to take that naughtiness/niceness-score-per-child matrix you just generated, and multiply it by this matrix…


Wait. That can’t be right. Your math is correct, but those numbers are way too huge. There must be a logic error somewhere. Shoot, how does this matrix multiplication thing work, again?

  • Your first matrix is a spreadsheet representing amount of Y per X, for some set of items X and Y. For instance:
    • “Number of [tables/chairs/balloons] I need to rent per event, for [my 5 upcoming events]” (Y = items to rent, X = events to rent items for)
    • “Number of [punches/hugs/kisses] performed per child, for [every child Santa tracks]” (Y = actions children perform, X = children whose actions Santa tracks)
  • Your second matrix is a spreadsheet representing the amount of Z per Y. For instance:
    • “Price charged by [Vendor1/Vendor2/Vendor3], for each [table/chair/balloon]” (Z = vendor prices, Y = items to rent)
    • “How many [naughtiness/niceness points] you get, for each [punch/hug/kiss]” (Z = personality points, Y = actions children perform)
  • By multiplying the two matrices, you go from amount of Y per X to amount of Z per X
    • “I know how many [tables/chairs/balloons] each event requires, and I know how much [Vendor 1/Vendor 2/Vendor 3] charges to rent an individual [table/chair/balloon], so how much would it cost to use [Vendor 1/Vendor 2/Vendor 3] for each event?”
    • “I know how many [punches/hugs/kisses] each child performed, and I know how [naughty/nice] it is to perform an individual [punch/hug/kiss], so how [naughty/nice] has each child been?”

Now, let’s see what went wrong when you tried going from naughtiness/niceness-score-per-child to presents-per-child:


Look at that! These units are all wrong. So what are the right units?

Well, we know that matrix multiplication means “amount of Y per X * amount of Z per Y = Amount of Z per X“. We have the matrix [naughtiness/niceness score] per [each child Santa tracks], and we want to end up with the matrix [amount of coal/candy] per [each child Santa tracks]. So…

  • X = [each child Santa tracks]
  • Y = [naughtiness/niceness score]
  • Z = [amount of coal/candy]

Therefore, we want our second matrix, amount of Z per Y, to be [amount of coal/candy] per [naughtiness/niceness score]! Then,


So we want the amount of coal per naughtiness point, not the amount of naughtiness points per coal — we inverted the units, is all. In order to invert our matrix back to the correct position, we have to flip the rows and columns (this is called a transpose) and invert the numbers to match. And now we get:


Nice! You just solved what presents each kid is getting! You LITERALLY saved Christmas.

Matrix Multiplication, A Novella: Chapter 1

So you got hired as an event planner. Congratulations on your new job!

You’re a clever event planner, and therefore you know that your events need tables for people to eat at. You rent tables per-event from your favorite party supply place, Vendor 1. Here’s the spreadsheet you use to track costs:

(I hope you didn’t just ignore that spreadsheet. If your eyes glazed over, go back and read it. It’s simple.)

Everything looks great! However, two nights before Gala A, you wake up in a cold sweat: you forgot chairs. You figure out how many chairs each event needs, call Vendor 1 to get a price, and re-tool your spreadsheet. Nice save! Now your spreadsheet looks like this (click for bigger, and don’t ignore this one either):

It’s one night before Gala A, and your phone is ringing at 2AM. What could it be? It’s Vendor 1’s archrival, Vendor 2! She wants to scoop her old boss, and she has a deal for you: chairs cost $7 each, but tables are only $8 each. You can’t mix and match tables from Vendor 1 with chairs from Vendor 2 — ever since Vendor 2 keyed Vendor 1’s car, they won’t work together. (Click for bigger)

Looks like Vendor 2 is cheaper for Gala A, Soiree B, and Reception C. You should keep Vendor 1 for Banquet D, though!

Man, you’re good at this event planning stuff. Two months pass, and you’re an old pro. This is what your spreadsheet looks like now:

More events! vendors! More items to rent! This is intense. Frankly, now that you’re a big-shot, these labels are looking like overhead. So you clean it up:

These are the same spreadsheets, just with all the non-math information chopped out. You decide to call these math-only spreadsheets matrices. To keep things from getting confusing, you implement some rules:

  • Matrix A holds item-to-rent details per event. A row represents a single event, and a column represents the number of a single item-type to rent for each event.
  • Matrix B holds vendor prices per item-to-rent. A row represents a single item-type, and a column represents a vendor’s prices for each item.
  • If we want to add a new item-type (for instance, lamps) then we need to know how much each vendor charges per-lamp. This means that the number of columns in A (representing item-types) must match the number of rows in B (since they also represent item-types).

Now, you’ve removed everything but the sweet, sweet math. And once you do that, something surprisingly simple shows up:

That is… (click for bigger)

And you just invented matrix multiplication. Congratulations!

Let’s Talk About Cameras: Perspective and Field of View

[Note: This is technically part of the series on DirectX, but is readable on its own, and does not require programming experience to be understood.]

At the end of my previous post on rendering 3D scenes with DirectX, you were able to render an object, but you would only see a specific narrow area (-1 to +1 in X and Y, 0 to 1 in Z). Well, that’s because we didn’t set up a camera into the scene. We can do that! But first, we need to know how cameras work.

Renderers like DirectX only really care about three properties of your camera. The first two properties are its position and its orientation (where it’s looking at); it’s pretty easy to visualize how changing those parameters will change the final rendered scene. The third camera property that DirectX cares about is the camera’s field of view, and that’s actually pretty tricky for people to visualize. So that’s what this article is about!

Let’s get started! Here’s an overhead view of a living room scene:
Living Room Top Down View

And here’s that same scene viewed from a camera at the front of the living room:
70 Degree FOV Camera Front

And here’s a fun fact!

In the top-down view of this scene, the sofa at the back appears five times wider than the black chair at the front (it’s 302 pixels long, the black chair is 54 pixels long). However, in the above image, the sofa appears only twice as wide (355 pixels long, while the black chair is 180 pixels long). So, the black chair has grown to be 2.5x larger than the sofa!

Of course, that’s not true. Your mind instinctively understands that it’s the same scene, and the same furniture — the chair didn’t really grow bigger. The sofa only appears to be smaller because it’s further away from the camera.

That decrease in size with distance is called perspective, and it can be controlled. You can change how quickly things get smaller, and it creates different images. Check out this picture of the same scene, and hover your mouse over it to compare it with the previous image:

That image above is the same living room scene, except things get even smaller as they get farther from the camera. None of the chairs have moved between these two images.

So how do we describe the degree to which things in a scene get smaller as they get further away? It’s called field of view (or focal length if you’re working with real-world cameras, but I think “field of view” is a clearer term).

Field of view is measured in degrees, and it represents how much of the scene the camera can “see”. If a camera has a 70 degree field of view, then it can “see” anything at most 35 degrees to the left or right from the direction it’s facing. Hopefully, this image will explain things:

Two Different Fields of View

On top, we can see a birds-eye view of the living room with two wedges marking what two different cameras can see. On bottom is the image each camera produces. The camera on the left has a 70 degree field of view, meaning that the triangular visibility wedge in the bird’s-eye view is 70 degrees wide. The camera on the right has a 90 degree field of view, so its wedge is 90 degrees wide.

When the camera’s field of view increases, the camera can see more stuff. However, it doesn’t see equal amounts more nearby stuff and far-away stuff — it sees way more far-away stuff than nearby stuff. Check out how the visibility wedges for the two cameras are almost the same at the nearby black chair, but the 90 degree FOV camera on the right has a massively wider view wedge at the far-away sofa. In order to fit all that far-away stuff, things that are far away have to get smaller. And that’s perspective!

One final note — you may have noticed that the 70-degree FOV camera on the left has actually been placed farther from the black chair than the 90-degree FOV camera on the right. I did this on purpose to make the black chair appear equally big in both scenes. Here’s what it looks like to have the camera increase its field of view and move closer at the same time:


It looks like the world is growing more distant around the chair!

Movies use this effect way often, because it’s a super-fun way to express an idea to the audience.

Alfred Hitchcock’s Vertigo moves the camera back and increases the field of view here to make it look like the ground is receding, emphasizing the main character’s vertigo.

Steven Spielberg does it here in Jaws to show the main character — who just spotted a shark — losing track of everything else around him. Martin Scorsese’s Goodfellas does this trick in reverse (move the camera further away and decrease the field of view) here. This causes the viewer to feel the characters’ paranoia — the world around them is closing in, and they have to watch for an assassin in every corner.

So that’s pretty cool! You just learned a ton about cameras and it came with a free lesson in film appreciation. And come DirectX part 5, we’ll learn how to write our own 3D cameras and play with this stuff ourselves!

Conditional Probability: PROBABLY Awesome

Forget computer architecture, I want to talk about statistics.

LET’S SAY that you invent a test that determines whether someone is in the Illuminati, and it’s 99.9% accurate. Now, let’s say 0.1% of the world’s population is actually in the Illuminati. Someone takes the test, and it claims they’re Illuminati. What are the odds they’re really a member of a shadow government?

Well, gee, it’s like a 99.9% chance, right? Or, 99.8% or something to account for inaccuracy? No. It’s 50%, as good as a coin flip. So, congratulations. Your 99.9%-accurate test is worthless. And if you want to know why, look to conditional probability.

See, until the 1700s, statistics wasn’t much further along than “lol coin flips”. Then, in 1763, Bayes published an essay that asked (and answered) a new question: how do statistics change if the probability of an event depends on the probability of another event? Like, the probability of a test saying you’re in the Illuminati depends on the probability of you actually being in the Illuminati.

This whole sub-branch of statistics is called conditional probability — as in, the probability something happens given the condition that something else happens. It’s great, because the math involved is simple, but some of the results throw our human intuitions for a loop.

Statistics textbooks usually start abstracting out from here and it gets easy for your eyes to glaze over, but as I said, the math is simple:

NAH BRAH (0.1%) 0.00001%
WHAT? NO (99.9%) DAMN DUDE (0.1%) 0.0999%
NAH BRAH (99.9%) 99.8001%

What are the chances you’ll be told you’re Illuminati correctly? (0.1% chance you’re Illuminati * 99.9% chance test calls it) = 0.0999% chance.

What are the chances you’ll be told you’re Illuminati incorrectly? (99.9% chance you’re boring as shit * 0.1% chance the test is wrong) = 0.0999%, or, the same damn likelihood.

IN CONCLUSION: if any of you think I’m part of the Illuminati, no matter how much evidence you have, you’re probably wrong. Hint hint.

Multiply Like A Pro

I’m going to teach you how to multiply any two numbers between 1 and 100, in your head, as quickly as it takes to input them in a calculator. And it’s dead simple.

(It does require some memorization though)

So, I figured out this technique – probably somebody else figured it out before me, but I’ve never heard of it before – that reduces the task of multiplying any two numbers together into some addition, some subtraction, and one division by two. It’s pretty simple. In fact, it all just boils down to one equation:

If your eyes glazed over at the above equation, be strong! Do the FOIL method and check it out for yourself. This is about as hard as the math gets.

Cool! What does that equation mean, though? Well, any two numbers (we’ll call them ‘a’ and ‘b’) can be rewritten in terms of ‘x’ and ‘n’ —

That is, we say that n is half of the difference between our numbers a and b, and that x is the number halfway between a and b. Now, b = x – n and a = x+n! Therefore, for any a and b,

We’re going to run through these formulas using some example numbers, to keep you following along, before we talk about how to solve x2 – n2. Let’s take the following two sets of numbers:

23 x 41
49 x 74

These numbers are big enough that most people wouldn’t even bother try to multiply them in their heads. Is it easier with this new method? (Yes.)

First, find n, half of the difference between the two numbers…

23 x 41:
41 – 23 = 18
n = (18 / 2) = 9

74 x 49:
74 – 49 = 25
n = (25 / 2) = 12.5

So the halfway point between 23 and 41 is

23+9 = 32

And the halfway point between 49 and 74 is

49 + 12.5 = 61.5

This means that…

23 x 41 = 322 – 92
49 x 74 = 61.52 – 12.52

But what are 61.52 , 12.52 , 322 and 92?

This is the hard part of the method. I don’t expect you to be able to solve 61.52 in your head. Instead, you’re going to have to memorize 100 squares – the square of every integer from 0 to 100. Yeah.

It’s a lot of work, but it’s entirely doable. There’s only 100 numbers, and you probably already know the squares of, like, 30 of them. If you’re thinking of giving up now, just think of all the sexy mathematician ladies (or dudes) you’ll be picking up at parties once you’ve memorized these and can multiply in a second!

If sexy mathematician ladies (or dudes) aren’t enough to make you memorize all 100 squares, though, there are tricks you can use to calculate squares very quickly in your head. I’m not going to talk about them here. I’m not supporting your laziness. But if you’re interested, you should read up on Vedic Mathematics, it’s got some pretty cool stuff about mental algebra.

But seriously, go the hardcore route, memorize this table. If you do so, you’ll already know the squares of all those integers-plus-one-half like 61.52 (but more on that later):

x x2 x x2 x x2 x x2
0 0 25 625 50 2500 75 5625
1 1 26 676 51 2601 76 5776
2 4 27 729 52 2704 77 5929
3 9 28 784 53 2809 78 6084
4 16 29 841 54 2916 79 6241
5 25 30 900 55 3025 80 6400
6 36 31 961 56 3136 81 6561
7 49 32 1024 57 3249 82 6724
8 64 33 1089 58 3364 83 6889
9 81 34 1156 59 3481 84 7056
10 100 35 1225 60 3600 85 7225
11 121 36 1296 61 3721 86 7396
12 144 37 1369 62 3844 87 7569
13 169 38 1444 63 3969 88 7744
14 196 39 1521 64 4096 89 7921
15 225 40 1600 65 4225 90 8100
16 256 41 1681 66 4356 91 8281
17 289 42 1764 67 4489 92 8464
18 324 43 1849 68 4624 93 8649
19 361 44 1936 69 4761 94 8836
20 400 45 2025 70 4900 95 9025
21 441 46 2116 71 5041 96 9216
22 484 47 2209 72 5184 97 9409
23 529 48 2304 73 5329 98 9604
24 576 49 2401 74 5476 99 9801


Now, here’s a cool trick: even though we need to know integers-plus-one-half like 61.5 for this method, we already know them if we know the square of that number’s closest integer (rounded down). This is because:

= (x+0.5)(x+0.5)
= x2 + x + 0.25

And for bonus points, we can ignore that “+ 0.25” completely! It’s just going to be subtracted out by the second half of our equation! Forget about it! Therefore…

61.52 = 612 + 61 = 3721 + 61 = 3782
12.52 = 122 + 12 = 144 + 12 = 156

Now, it should be easy for you solve those two problems.

23 x 41 = 322 – 92 = 1024 – 81 = 943
49 x 74 = 61.52 – 12.52 = (3721 + 61) – (144 + 12) = 3782 – 156 = 3626

And there you go! To recap this method:

  • Find half of the difference between the two numbers you’re trying to multiply
  • Add that to the smaller number to get the midpoint between your two numbers
  • Midpoint squared minus half-of-difference squared equals your result!
  • If the number is an integer-plus-one-half, remember that (x+0.5)2 = x2 + x (for our purposes)

There’s no reason you can’t use this method to multiply two numbers over 100, either! You just have to memorize your squares tables up to the highest number you’re willing to multiply.

I hope you get tons of use out of this and impress all the sexy mathematician ladies (or dudes)!