Math and Movies (Animation at Pixar) – Numberphile

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.

Only registered users can comment.

  1. @Numberphile  Thanks for this. I work in 3D Animation and have been wondering about the math behind Subdivision and limit surfaces for quite some time.

    On a side note, you asked Tony if everything comes out blobized, but in this vid, it doesnt seem like he answered the question the way you were expecting. The answer is no. In the 2d example, if we wanted one corner to be sharper than the others we add 1 or more vertices near the corner vert. The result is the averaging and splitting is tighter where we've added more vertex density resulting in a sharper smoothed corner

  2. I wonder if this links to how large rubiks cubes are smoothed? Anyone else see a similarity to the cube when it is smoothed?

  3. Interesting observations:
    Each row of pascals triangle is generated by the convolution of the row above it by 1 1.

    Each progressive row becomes closer and closer to approximating a perfect gaussian curve [or e^(-x^2) ]

  4. I really enjoyed this one, but I do have a background in math, programming AND graphic design (since the 60s), so it made my skin … twitch.

  5. Fun fact about Toy Story- the character of Andy was allegedly named after Andy Van Dam, a Brown University professor who mentored many people on the animation team. In one scene, you can find Andy Van Dam's book about computer animation on a bookshelf.

  6. Can someone tell me, what is the application used in the video, where the guy introduced as the Pascal's Triangle. Where the buttons Split, Average, and the Subdivide.

  7. Quality material as usual. But please, check your microphone levels. This is not the first time that the sound is clipping a whole lot. You did show us that you are checking your sound by asking what your interviewees had for breakfast. So maybe it’s a post processing issue?

    Anyway great job, but please do something about the sound issues.

  8. So when they say 1,2,1 weights it means that B's x and y coordinates are weighed 4 times as much than both A's and C's coordinates, and the average of all those coordinates is the new value? In that case, how can you use something like 1,3,3,1 when operating on 3 points?

  9. Great video and use of STEM in film…also a great example of how to use Calculus and Geometry in animation!

  10. I have been researching into catcall-clark subdivision surface and it's very difficult to find the connection between Pascal's triangle weight to how the dots move. My brain is burnt 0____0

  11. going to hopefully be doing Computer Visualisation and Animation at Bournemouth Uni, the artistic side of computer animation is awesome but the Maths side is so damn interesting, really glad that were going to be looking at the Maths, not sure whether this'll be covered but hope so, seems really interesting:3

  12. Watched this like 3 times for some reason. Learned something useful about all rendering. Weird this is unknown by many who use this. tried to explain this to friends in AutoCAD/Image Design and ended up just showing this video.

  13. I've always been intrigued by this material. I have a double major in Sec. Math. Ed. and Mathematics with a minor in physics. I love/know my math and I know html, python, and C++. I'm currently looking for employment and I would love some experience in programming. Does anyone know what I would be qualified for?

  14. Does anyone know what software he uses?
    Also, I'm interested in constructing time graphs. I don't know any programming, but I've been working on some maths i'd like to model. Could any one recommend languages/techniques/programs to use?
    I've got a mac, so xCode's obviously an option. But I want something with a graphical interface like his one so that I can generate active graphs. Would I just have to get that going from zero?

    Would appreciate any help anyone can give!

  15. The first three minutes of this video is extremely informative. I've always wondered about how to convert a square to a circle, and it seems like this might be the way to do it.

    I also wonder if they explain this in "Pixar in a Box".

  16. Huh. I had no prior education to 3D modelling when I got started – I taught myself everything up to what I know today. It's interesting to know that what I do after making my low-poly representation to turn it into a higher detail model is a trick used by this guy as well.

  17. Thank the lords I found this video. I had to pick a job that uses science and mathematics for an essay and I chose animating. I only found small things in other videos, but I got so many notes in this video. THANK THE LORDS.

  18. We watched this in my Geometry class. Students bet me that I could not give them any examples of using geometry in real life and this was PERFECT! Thanks for helping me win my bet! 🙂

  19. Why the irritating and distracting background sound sequence? I don't think I hard it before on Numberphile. Once I noticed it, the 8 eternally repeating notes it almost drove me insane.

  20. seems like you could just have a playbook of curves… no reason to model them with this splitting-subdivision technique. This whole thing could be instantly streamlined to relatively simple geometry functions

Leave a Reply

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