Math and Movies (Animation at Pixar) – Numberphile
Articles,  Blog

Math and Movies (Animation at Pixar) – Numberphile


This is Pixar Studios. I’m sure almost everyone’s heard of them, and watch their movies. They’ve, they’ve won a few awards along the way, too. But less people realize just how much mathematics and science goes into animating these films. Even the boss here is a computer scientist. This is Tony DeRose, and he leads the research group at Pixar. And today he’s talking to us here at numberphile. Well my particular area of interest is in, in geometric modelling. Creating shapes of things. And that problem comes up a lot around here because we’ve got characters with, you know, pretty complicated shapes. You know, some of the characters on the board behind me. This is a, this is a sculpture of the hand of Geri, from Geri’s Game, a character in a short film that we did quite a few years ago now, and it, you know, just, it’s a complicated shape, and we needed to develop some way of representing these kinds of shapes in a way that artists could deal with, but computers could, could render and display quickly, as well. So Jan Pinkava, the director of Geri’s Game, was also a sculptor. So he created this sculpture of Geri’s hand, and then we later digitized it and made the final surface that appeared on the screen. Let’s simplify first, and we’ll get back to surfaces in three dimensions in a minute. But let’s start, say, with curves in two dimensions, to explain the basics of the process. So, what I’ve got here is a little four point polygon, and it’s gonna be my job to make a smooth curve out of it. I’m gonna make a smooth curve out of it by just repeating a few simple steps. So, the first step I’m gonna call split, and what that does is it adds midpoints to the edges. So now I’ve got eight points, but it’s not really any smoother. The next thing I’m gonna do is I’m gonna make it a little bit smoother by repositioning all eight of these points. So this guy, for instance, is gonna move from where he is now to the midpoint of his right neighbor. Similarly, this guy is going to move to his right neighbor. And let me animate that for you. I’ll call that the averaging step. So now we’ve got eight points, a little bit smoother. And again, my goal is to make a smooth curve, and so I’m just gonna repeat. I’m gonna split and average, so now I’ve got 16 points. Again, a little bit smoother. I’ll put those two steps into a combined step I’ll call subdivide. And you see that as I continue to subdivide the, a smooth curve starts to emerge. And that’s the basis of how we create all of our surfaces. This splitting and averaging idea also works for surfaces. So here’s an example where I start with a cube. So if I split, it’s a little more complicated for surfaces to split. I have to insert edge midpoints, like this one here. Like I did for curves. And I also have to introduce the middles of faces. But again, that’s just done by averaging. So this point here is just the average of the four points around it. And then I average. In this case, I need to use a carefully constructed weighted average, for reasons we may talk about in a minute. But if I pick my averaging weights carefully enough, I can continue this split and average process and generate smooth surfaces in the limit. And that’s exactly how Geri’s hand, and, in fact, Geri himself, was built. Well, here, for instance, are the points that we digitized off this, this sculpture, before subdivision, we run this splitting and averaging process a lot of times, and that smoothes the surface out, and creates the smooth shape that you ultimately see on the screen. Brady: “To the untrained person, which I very much am, this seems sort of, it doesn’t “seem very subtle. It seems like anything you feed into this process will just kind of get blob-ized in “the same way, everything will get turned into this kind of generic blob. “Is there, is there more nuance to this, than what it, than what it looks like? Or does everything turn into a big bleh?” Well, there is some nuance. There’s some magic numbers involved. So let’s get a sense of what those numbers are. One pair of magic numbers are 1, 1 here. Those are the weights that I used in this averaging step, when I moved things to midpoints. And those are magic because you can show that a nice thing happens in the limit of this subdivision. So this 1, 1 means it’s gonna go to a spot that is one part of where he is now, and one part of where his right neighbor is now. Okay, so let’s do that. Let’s, let’s, each stage is split followed by average. So there’s the split. So when he moves according to the 1, 1 rule, he’s gonna move from where he is now to here. And this guy’s gonna move from where he is now to here, and so on. So we’ll see that. And we just keep repeating that process, and a beautiful thing happens. In the limit, you can show that this curve is a, there’s a parabolic arc that sits in here, and there’s another parabolic arc that sits in here, and those two parabolic arcs meet with a smooth derivative, a smooth tangent line, at this point. And that’s all just an emergent property of this subdivision process. There are some other magic numbers I can use. For instance, if I use 1, 2, 1, so I split as before. Now if we use the 1, 2, 1 rule, this guy is gonna move from where he is now to two parts of where he is now, one part of his left neighbor, and one part of his right neighbor. So it’s 1, 2, 1. Brady: “So he, so he’s carrying more of his weight” Yeah, exactly. And so if I average it with that set of weights, I get a shape like this. If I continue to split and average, again something really nice happens. When we used the 1, 1 rule, we got piecewise parabolas, which are degree two curves. Here, we’re gonna get degree three curves, in the limit. And if I pick weights 1, 3, 3, 1, and do this process, it turns out you get degree four curves. And this pattern is, I think, probably familiar to many of your viewers. 1 1, 1 2 1, 1 3 3 1. Those are all rows of something called Pascal’s triangle. So what we’re learning here is that if you pick your weights carefully, that is, from rows of Pascal’s triangle, the curves that you get in the limit are nice and smooth, and they’re polynomials, and the degree of the polynomial is given by how deep into Pascal’s triangle you pick your weights. But you don’t have to pick them carefully, you don’t have to pick your weights carefully. I can, in fact, I don’t even have to make the weights positive. So suppose I pick rates 1, minus 2 and 3. So I split as before, and now this guy is gonna go to a point which is minus one times himself, one times his left neighbor, and three times his right neighbor. Brady: “I have no idea what’s going to happen.” Yeah. Let’s see what happens. Okay. Something interesting. Let’s continue. We’ll keep doing that. So what we’re seeing here is, in the limit, if you don’t pick your weights carefully, you get something that isn’t smooth anywhere. In fact, it’s a fractal. Brady: “So, when I watch one of your films, which one is the right one? Which one creates “the surfaces that make you happy?” Well, it turns out that for surfaces, this Pascal’s triangle pattern doesn’t work any more. You have to use a, a different set of mathematical tools to figure out weights that are gonna generate smooth objects in the limit, and those are very carefully chosen weights. They were first discovered by Ed Catmull forty years ago. Ed’s the president of Pixar. Brady: “Do we know, are those like, are they like, like fractions? Are they, what numbers are they? “Are they like one, one point seven, and three point nine two? Or…” I don’t remember them off the top of my head, but there’s a simple formula that is now well known. You can find it on our website. Brady: “So when you’ve got your 3D object, “they’re the, they’re the ones you plug in and then, bang.” Yeah, exactly. So what I was doing the subdivision with the cube, we were using those very carefully constructed weights that Ed discovered. We do this subdivision process a few times, and it, that gets us points that are kind of close to where they would go if we did in an infinite number of times. But, on top of that there’s a few tricks that we use to figure out exactly where they’re gonna go. Mathematically, we, we think about what would happen if we did it an infinite number of times, and it turns out that we can write down exactly what happens if we did do it an infinite number of times. Brady: “Let’s crack out the paper.” Yeah, so let’s see how that works. And, let’s start with an observation here. So I’m gonna go back to the simple 1, 1 rule, that we had earlier. And watch what happens on, say, this leg of the polygon. So I’m gonna split and average, and notice that what happened here is that I still have two points on this polygon leg, they’re just a little bit closer. If I split and average again, again, I get two points on this leg, they’re just a little closer together. If I do it again, again they’re closer. So, what’s gonna happen if I do this an infinite number of times? Well, these two points are gonna get closer and closer together, in the limit, they’ll be on top of each other, and the location where they converge is the midpoint of the original leg. So without doing any computation at all, I can determine very quickly that these four blue points are on that limit object. And the nice thing about that observation is that it holds at every stage of subdivision. Watch what happens on this leg of the polygon. So this leg wasn’t in my original arrangement, but it got introduced after the first stage. And, as I split and average, we’re gonna again see two points on this same line. They just get closer and closer together, as I subdivide. And again, they’re gonna converge to the midpoint of the leg when it was first introduced, so let’s go back to that arrangement, here. So I know that the midpoint of this leg is also on the limit object. So, after one stage of subdivision, I already know eight points exactly. Brady: “You refer to this thing called the limit object. “That’s the finished product.” That’s the finished product. Right. So, it’s the mathematically perfect version. And now I’ve got eight points that are on the mathematically perfect curve. Computing what happens in the limit becomes a little bit more delicate when we look at one of these other rules, like the 1, 2, 1 rule. So let’s see if we can track where this point goes as I subdivide. Brady: “So we’re using a 1, 2, 1 now.” This is a 1, 2, 1 rule, so if I split and average, Okay, so he moved some distance. Let me split and average again. He’s moved a little bit more. It’s not exactly clear where he’s gonna stop. Brady: “He’s not on the limit object yet.” He’s not on the limit object yet, so. But, yet, we can compute exactly where he’s gonna go, with some other magic numbers. Let’s take a look at how that works. I’m gonna draw a little piece of my curve, my original polygon, and since this is my original polygon, I’m gonna use superscript zeroes. So A super zero, B super zero, and C super zero. So that’s before subdivision. If I subdivide once, I get some points that are gonna sit in here, and I’m gonna call this guy A super 1, B super 1, and C super 1. And if I subdivide it again, I get some more points in here. And what we want to know is, okay, here’s B zero, here’s B 1, B 2’s gonna be some place. The question is, where is B infinity? We’d like to figure out where that is. Turns out we can answer that question. And to do that, I’m gonna write down a few things I know. Well, one thing I know is that A super 1 is just on this midpoint, so I could write that as A plus B over 2, and these are super zero guys, my original things. If you work out the algebra of the splitting and averaging, using the 1, 2, 1 rule, you can see that B super 1 is A super zero plus six B super zero plus C super zero divided by eight. So that’s just unwinding the split and average process. And then C super 1 again is just the midpoint on this leg. So that’s B super zero plus C super zero over 2. Ok, well, that isn’t obviously helping us answer the question of where B infinity is. To do that, I’m gonna do something a little bit sneaky. Take A super zero and B super zero and C super zero and combine them with weights 1, 4 and 1. And we’ll have to divide by 6. Put a 1 there. Because I have, kind of, six things in the numerator. Brady: “Where did the 1, 4, 1 come from?” My back pocket. And, you’ll see why I picked 1, 4, 1 in just a second. The real answer is it came from a tool called Eigenanalysis. But, we don’t need Eigenanalysis to see what’s gonna happen here. And we take that same combination and apply it to A super 1, B super 1, and C super 1, So I get 4 B super 1, one copy of A super 1, one copy of C super 1, and divide by 6. So now I have two expressions, and if you take these equations over here and just substitute them in here, and simplify, what you’ll see is this expression is actually equal to this expression. And it’s only true for these weights 1, 4, 1. And the cool thing is that I can use that same reasoning to figure out that going from the 1, the super 1 condition to the twice subdivided condition, again, applying 1, 4, 1 to the twice subdivided points, over six, I could, I’ll find that these two expressions are also equal. So I can repeat this process any number of times I like. Say, all the way to infinity. So I can compute A infinity, 4 B infinity, plus C infinity, over six and that’s still gonna be equal to the expression that I had to start with. And now the beautiful thing happens. If you think about what happens to this little arrangement of three points, as you continue to subdivide, those three points, on the, on the second stage get closer together, on the third stage even closer, as I do it an infinite number of times, all three of those points converge to this place, B infinity. So, these are all B infinities, actually. So, this turns into B infinity. A infinity and B infinity are the same, in the limit. C infinity and B infinity are the same. So I can rewrite this as B infinity plus 4B infinity plus B infinity divided by 6. Well, averaging together a bunch of B infinities just gives me B infinity. And, so, what I’ve learned is that B infinity is right there. I start with my original points, take them with weight 1, 4, 1, and that gives me B infinity straight away. Exactly, and no approximation. Brady: “Before you even started, you knew where B was going to end up.” Exactly. So if I take some other polygon, now, I know that B infinity is gonna be four parts of this guy, one part of this guy and one part of this guy, which is gonna be a point about right there. And again, that can be computed without approximation. If I had, say, the 1, 3, 3, 1 rule, I’d get a slightly different set of expressions here, I’d get a different collection of magic numbers, again, solved for with a systematic tool called Eigenanalysis, and it would have this same property. And the whole thing works for 3D as well. For surfaces, right. And so that lets us compute exact points on our, the surfaces of our characters, and we can even compute exact derivatives, which we need for computing that nice, smooth gradation in illumination, or shading, in the graphics. We’ll have more from this interview with Tony coming very soon, and that will be uploaded to our sister channel, computerphile. So go over there and keep an eye out for that one. Well, films that I’ve worked closely on, it’s hard to watch and not see all the flaws.

100 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *