Computation and the Transformation of Practically Everything: Travel and Entertainment

DURAND: Welcome to the first afternoon session on travel and entertainment. Before we get started, I remind you to please turn off your cell phone, except maybe for the first speaker, who is waiting for a call about his acquisition. That might be important.

So this session has two great speakers. We are first going to hear about travel with Jeremy Wertheimer and then about entertainment and animation from Tony DeRose. Without any further introduction, Jeremy Wertheimer, who's the president, co-founder, and CEO of ITA software.

[APPLAUSE]

WERTHEIMER: Good afternoon. So my assignments-- and it really feels like an assignment, I just met-- had the pleasure of meeting a number of my professors that I haven't seen in many years-- but my assignment was to talk about the impact of computation on travel. I've got 20 minutes, and I figure I got 150 years to cover. So I'll get started.

And just to set the stage, when MIT was founded 150 years ago, if you wanted to travel, you had a couple means of travel. One is a stage coach service-- was actually launched in 1861-- that could take you from St. Louis to San Francisco or back. The main purpose of the stagecoach was to carry the mail. But they took passengers also. And for the sum of $200, you could ride on the stagecoach.

It took 25 days. And a reporter described it as absolute hell. And the warning, if you think the warnings we get on airplanes are bad now, the warning that you got as a stagecoach passenger included things like, should the stagecoach stop, please stay inside. If you leave, you might be left behind and be eaten by coyotes.

Also around this time, 1860s, the railroad started coming to town. And this offered a tremendous set of advances over the stagecoach. And one of the most interesting one is that you started to actually build a transportation network, in that you could actually ride the stagecoach over a limited period. And you probably were going to go to that lovely little shop in San Francisco outside the saloon and get on the stagecoach.

You would probably arrange for that travel in San Francisco at your point of origin. But for the railroad, you might actually be at another point than your point of origin and want to arrange for passage on rail. And so even though initially the practice was to go to the station to buy your ticket, as you would for a stagecoach, gradually there was evolving a practice of buying your ticket perhaps not at your point of origin.

So now moving a little more quickly, about 100 years ago-- and just to frame it, in 1908, the Wright brothers gave their first public demonstration of their flying machine. And by 1913, you had commercial air travel. Proving, I guess, the risk-pro nature of our species, people were actually getting on planes, such as this one-- this was route between St. Petersburg and Tampa, and there was another route between San Francisco and Oakland-- and you could actually fly, assuming that you made it all the way.

It wasn't the safest travel. But you could actually by carriage. And this company in St. Petersburg was actually really successful, which means it lasted a few months, which is successful for an airline.

And now, the real progress starts to happen but in the interwar years. And in the 1930s-- and just to fill in, so in the 1920s, you go from having a few thousand, hardy, air travel passengers in the United States to maybe 100,000, a little over 100,000. Over the '30s, that number increases to over a million. And part of it is brought about by the development of wonderful airplanes.

And this is one of the most famous of all, the DC-3. I don't have time today to sing all its praises, but it really was magnificent. And if you wonder why it's a color picture-- this is an aircraft from the 1930s-- well, it started flying in the 1930s. This isn't a Wizard of Oz kind of trick. This airplane was, of course, still flying 75 years later.

So what was the technology for reservations at this time, because you have two main computational-- or let's say, information processing tasks involved in commercial travel, like in many commercial activities. You have to find out if there's inventory, if the provider has the service or good that you want. And you have to negotiate a price.

So this is the technology-- a little hard to see-- but computer scientists should recognize this as the first of the typical device we might use-- a rotary storage device. You have a large Lazy Susan in the middle. There are individual slots. And in those slots, there would be a little card that would hold the inventory for a particular flight on a particular day with little pen marks as to which seats were sold.

You have eight rewrite heads arranged around the table on comfortable chairs. And this is-- and they have telephones-- and this is basically how reservations were handled. This is a great improvement over the previous linear storage device, file cabinets, where someone had to get up, walk across the room, take the card out, walk back to their desk, get on the phone, locking that record for much longer, before they could return it to the file cabinet. This provided for quicker access.

And then-- and this is one of my favorite historical finds-- there's this lovely company called The Teller Register Company. And they start in 1929, wonderful timing, and they build technology that can allow you to repeat the information that's contained on the stock tote boards in New York out to branch offices. And they have these boards, because the previous technology-- brokers, similar to airlines and a lot of things-- you would have a big tote board, somebody would be marking the prices in chalk for the stocks.

The brokers at the desks would use binoculars to see the same technology that was used in the early airline, where people at big tote boards would mark inventory. And the reservationists at their desks would use binoculars to see it. But here, The Teller Register Company invented electronic means, whereby actually putting that peg in the hole, they complete a circuit, which can be interrogated by a little terminal, which I'll show you in a moment.

And here's the next improvement. That system, if you think about it, only provided remote read access. It didn't provide remote write access. And for that, we had to go away from the mechanical tote board, electric mechanical tote board, and go to a drum device. And here, you see a picture of the drum device.

Here, you see the pretty marketing picture of the brochure of the drum device with its rewrite heads. And this drum device could store information about up to 1,000 flights per day for a 12-day period. And this was pretty good.

And here was that remote device. It's hard to see, but just to point out, here you have a slot in which you would insert a card with certain tabs that we complete certain circuits. And that would select the market that you're looking at-- perhaps Boston to New York. Here is buttons zero to three and buttons zero to nine, you would enter the date. Here are buttons one to four. You enter the number of seats that you're looking for.

And then there are little switches here. And I think on this switch, you basically would toggle it-- a snap action switch-- to check availability, which will light up one of these three lights, either green if you get the seats, red if you couldn't, or yellow if they couldn't tell-- a little history, says then you should call. And here's a little button, importantly, that could actually let you sell or cancel that. So now, we basically have the beginnings of an electronic reservation system, at least an electrical reservation system, not much computation. But the scary part is a lot of this structure is still there with us now in the airline industry.

And then I should tell the path to getting here. This is, of course, a computer we're familiar with. This is from 1961. So now, we're at 50 years ago. And this machine, this is an IBM 7090 that was used to deploy SABER, which I'll talk about in a second. For the computer scientists, again, this machine, remember, had main storage 32K, 36-bit words, enough to handle all of the country's air travel at the time. And it had a cycle time of about 2 microseconds.

And the way this came about is sort of an interesting story, just for those of you interested in business. It came about from probably the most famous chance encounter on an airplane in my industry, which is that in 1953, there was a salesman for IBM, whose name was Blair Smith, working in Los Angeles, who was told to go back to New York to get training on the IBM 701, the first transistorized computer that IBM sold.

And he happened to get on the last seat of the airplane, because being well aware from earlier stints he had done at airlines of safety, he knew the last row was the safest. And then next to him sat down another gentleman, who was also named Smith. His name was CR Smith, who was the head of American Airlines. And they struck up a conversation that seven years later led to SABRE.

And here's a display from the SABRE system. And I have to apologize, this is a screen capture that I took some time over the last 20 years. I don't know when. But it doesn't really matter, because it would be about the same. And here are the essential features of air travel.

You've asked to go from Boston to Dallas, DFW, Dallas Fort Worth. And here, you see eight possibilities on eight different flights. Here, you see a little bit about Boston, Dallas, and the time of departure, time of arrival, the equipment, and a made-up number that's supposed to be on-time percentages.

And here, this interesting matrix-- I once sat across from someone from an airline, and I asked, I said, these numbers that you publish, I know you have more accurate numbers in operations. They said, oh, yes, we know them exactly. I said, I understand these numbers are not very accurate. For example, in Minneapolis you're allowed to use the July number all year. They said, yes. I said, do you think it would be an opportunity to use the more accurate information, and they just looked at me, like I was crazy.

But this is the interesting part. In here, you see the inventory. And it basically says, in F, in first class, we have seven seats. And in A, which is discounted first class, we also offer those seven seats. In Y, which is the full fare of the coach cabin, we have seven seats. And in all of these different imagery buckets, we have seven seats, though in some places, you can see that number goes down.

And let me just explain for a moment what this is. Basically, if you take an airline, you have the cabins-- first and coach, or maybe first, business, and coach. When British Airways started offering economy-- a sort of premier economy that had more leg room, it was wonderful. But that was a fourth cabin. And since three cabins was wired in, in 1960, there's no way you can get that on a reservation system. You had to call.

But if you look at these numbers, what's interesting is that they represent different virtual buckets of inventory. And the idea is, just to summarize it in a sentence, the economics of air travel are such that there's price elasticity, which means there are more people who will travel if it's $200 than will travel if it's $500. And yet, unfortunately, there is no price that will actually fill an airplane and make a profit.

And so what the airline has to do is it has to decide how to sell tickets to people who will pay more for more and how to fill the empty seats to people who will pay less, not cannibalize between those two, which would be unfortunate, and sort of play that game versus the customers. And that's sort of the sum of what is done. And you can see in the AeroAstro department here, a lot of work is done on revenue management. But we'll get back to this in a moment.

The basic standard of how airline travel was sold persisted certainly from the 1930s, as we've talked about-- and again, to understand, the airline initially was regulated in this country and in most of the world, which meant that there were government regulators-- who I'm great fans of-- who set the schedules, the prices, and pretty much everything about the airline was something that was arranged with a regulator. And deregulation only came in 1978. And that was the first time that the airlines were allowed without government regulation to decide where to fly, when to fly, and how much to charge.

And among the interesting forces that emerged, you had, for example, Sir Freddie Laker in the UK and People Express here in the early '80s that were offering very low prices. And the response to that from folks like American Airlines was to say, fine, we will sell a couple of seats down here at a price that will undercut you. But we can sell more expensive seats up here, because we have fancy computer systems. And People Express responded by going out of business.

But now, here, this is what air travel looks like now with some code that we've written up the block at ITA Software. And just to give you an idea, if you basically say that you'd like to go from Boston to San Diego, maybe you have to go tomorrow, while there is a nonstop still available-- at least there was this morning on JetBlue, I mean, it's relatively expensive-- if you basically say, well that's all right, I know that's 6 and 1/2 hours, and it will cost me almost $900, but I'm willing to look at stops, then you can make that trip in about a little over 8 hours and save almost half the money.

And if you wanted to go instead-- let's assume that you had a different trip you had to take-- and here, if I'm going to San Francisco, there are in fact more non stops. But the connections are still a little cheaper. And if I'm planning far enough in advance-- let's say I'm going to Los Angeles-- then I've got many different connections, all of which are relatively inexpensive.

Why are they inexpensive? Well, again, remember, that segregation, that market segmentation the airline has to do, they have to make sure that the business traveler who will pay a lot of money pays a lot of money. And they have to make sure to fill the seat with a leisure traveler, who won't pay a lot of money. And one of the standard types of senses that you would use to separate those two, properly segregate those two, are rules that you would catch to those different fares.

And so here's an example of a fare that was part of initially we saw. It's an AA QA14SQY1, which means it's from that Q inventory class between Boston and LA. And I've just taken out for you three of the fare rules-- there are more than 50.

But one of them says, it's only good on Tuesday and Wednesday, because those are the lowest travel days. The other one says that you have to book this 14 days in advance. And the last rule, which I've given you just a piece of, says, if you'd like, you could combine this fare with other fares to pay for your trip, but there are certain rules that will apply.

And here, just to give you an idea of the brilliance of airline pricing, on this graph, I've just put down the number of fares published in these different markets by American Airlines Friday afternoon. And so literally, that means there are 300 different fares between Dallas and Boston, and 400, more than 400, between Boston and Chicago, and more than 500 between either Chicago and SFA or between Dallas and San Francisco, and about 400 for that full trip, which means, when we were computing that display, a little while back, we actually had to go and compute over a very large combinatorics explosion of possibilities.

And there are many articles you can read if you want to get the exact numbers. But just to give you a rough intuition, there are many different places, besides the places on my little map, that you could transit to if you want to go from Boston to SFO. Boston, you can get to about 80 different airports. And for most of them, you can get on to SFO.

So there are many different routes. On a particular route, American or someone like that might have five or six flights a day. And even once you've chosen all of your flights, they're all nailed down, you still have this amazing combinatoric explosion of the number of different fares you could pay for those flights, because of that segregation and that-- it's called revenue management. And so there's a vast amount of possibilities that have to be looked at relatively quickly.

And here's where we found some computation to be helpful. And just to give you sort of rough numbers, these are pretty close, over at ITA Software, our product called QPX, we do about a billion searches a month, a little more. And at any given time, there's about 100,000 scheduled flights. That's on each day, so over the next year, you've got about 30 million different scheduled flights.

At any given time, there's about 150 million published fares. But again, the combinatorics comes in, because we're using those in combinations. And in our system, just as a sort of arbitrary number that worked out, we'll usually pick a surge that says, for the outbound, I'll compute 400 itineraries, that is, possible flight times and routes.

And that's pretty easy, because since all flights have more than zero time, I know that if I just start with any algorithm that you would know, perhaps A star, to grow a set of leading edges of that search space, I will provably get all the possible paths that are less than a certain amount of time. And so if we find the 400 out and 400 back for this kind of trip, it's pretty good. And that will, on the whole then, require us to check the seat availability of about 1,000 flights. And if there's time, I'll get into that for a little minute as to why that's hard.

This takes about 2 million lines of code in languages like LISP, that used to be taught here many years ago, and Perl and Python and C++ and Java and runs on roughly about 5,000 x86 processing cores. And by doing that, we're able to service a lot of the air travel. I can't say a dominant amount, because the judge hasn't signed our decree yet, but a lot of air travel.

So this is basically a problem that was there, which is that post regulation, post deregulation, there was a challenge in how you find the best airfare. And this is a program that we wrote to address that. And it's been modestly successful. Again, a judge hasn't yet signed the decree.

And now, I just want to spend a moment putting this in context. So this is the piece of software at an airline that will tell you how much the trip costs. And remember back in the days of SABRE, that system that was in use 50 years ago-- and here, I'll just take a minute to tell a story.

When I was a student at MIT, must have been in the '80s, maybe early '90s, Professor Fredkin once gave a talk. He had come back from Moscow and it must have been before '89. And he had the mission among others of trying to get the first Russian computer to be exhibited in the Computer Science Museum-- the computer museum that was in Boston at the time.

And his Russian host kept saying it would be a wonderful idea. They were proud to show Russian technology. They kept saying yes, but they were never given the machine. And finally, he had insight. And he said, I see, it's still in use, isn't it? And they said, yes.

And SABRE, I have to say, was a wonderful invention. It was deployed 50 years ago. And it's still in use. And in fact, at the moment, every time you buy a ticket on an airline, you're using a piece of software that's either 50 years ago or there's a newer version that runs on HP 3000-- that's only 35 years old-- for smaller airlines. But that's basically what you're using.

And we at ITA had the foolhardy idea that maybe we should build a new reservation system. My joke was when I started, every 30 years, you should replace your computational infrastructure, whether it needs it or not. 10 years ago, I modified that, and I said, every 40 years, you should replace. Now, I say every 50 years. And in 10 years, we'll see what I'm saying then.

But this is a picture of the main modules in our reservation system. Again, I don't have time to go through it in detail. But there are modules that do things like maintain the inventory.

And also, remember those early inventory systems, they didn't centralize just writing down who you were. They just wanted to know that they weren't selling a seat twice. That was still locally stored. And so after a while they added information about who you were to the central store.

And then later when they invented frequent fliers, they had to add information about that to the central store. And then when they created websites, they had to add that to the central store. But these are all layered databases. They don't really talk to each other. So when you're talking to an airline and you say, I need to change my address and I'd also like to change on my frequent flyer program, and they say, oh, you have to call a complete different company, now you understand, it's a different organization running a different system.

But anyway, this is a relatively complicated system that we've built. It's one of those million-hour man-hour-plus systems, that when I look in the literature for that size system, it says, we would tell you how likely you are to finish, but we have no successes yet to count. But to put it in context, this system, which is about 5 million lines of code-- again in LISP and Java and C++ and Perl and Python-- it sits at the middle.

And this is a relatively simple context diagram from the midsize airline that we've worked with. And there are 45 systems that are arrayed around this one. And for one of the larger airlines that we work with, there are over 450 systems arrayed around this.

So one of the lessons that I've learned is that, as computer scientists, we figured out how to install interesting mission critical systems. We haven't figured out how to uninstall them yet. And we haven't really figured out to evolve them yet. And some of our earlier design commitments, like the fact that first reservation system you saw didn't store the month, because that was implicit, SABRE didn't store the year, because that was implicit.

And if you think that maybe we've gotten beyond that, I challenge you to try to make a reservation 331 days from now and see what happens, because in fact, the year is not stored. And implicitly, the dates go back 30 days and forward 330 days.

And just because I'm supposed to say something about the future as the second segue, here's some of the stuff that we've deployed-- a little app on mobile, which is a big area. And this is on an iPhone. And we also have it running on Android.

And here is the shopping you've seen. Here is something where you say, if I want to go for a week to Aruba but I don't care exactly when, I can get various displays about when might be a good time to go. We can do various things involving maps.

And then the last two little bits of air travel, as you might have noticed over the last year and a half, the airlines have realized that there's a really good way to try to improve their profits, which is try to sell you something that doesn't cost them a lot of money. And right now, airplanes and pilots and other labor and fuel costs a lot of money. But letting you use the Wi-Fi or lending you a blanket or lending you a video recorder or feeding you some food don't cost that much money, but there's a great prophet potential.

So one of the really big areas is the airlines have decided that, of course, air travel right now is too simple in terms of figuring out where you're going to pay. So let's provide additional bits of things that we can add or take away. So if you want to use the lounge, for another $20 you can do that. If you want to change your return time on the day that you're returning, maybe for another $20, I'll let you do that.

One of our partners, Air Canada, had the idea of the opposite, which is if you basically can say I promise I won't bring a bag, we'll give you back $20. But if you bring a bag, we're going to charge you $50. And they would also say things like, if you promise you don't care what seat you're sitting in, then we'll give you back $20, which I thought was really very nice, because Delta does the same thing. It doesn't give you back any money.

And finally, just sort of an obligatory thing that we've been doing a little experimentation recently with some social technology. And this is a little app that we'll probably release soon, that when you turn it on, it loads your friends from Facebook. And if you shake the thing, it will spin this little wheel and pick one of your friends and tell you how much it will cost to go visit them at some point over the next couple of weekends.

So one of the lessons, one lesson is that it really is the tools that you learn when learn how to program are very powerful. And if you hit it just right, you can write a program that can have a lot of impact. Of course, the Chinese curse does apply, which is, if you are too successful, then people in high places will take an interest in your work. The other lesson is that any architectural sins that you commit will haunt you and your children forever. Thank you very much.

[APPLAUSE]

DURAND: We have time for one or two questions for Jeremy.

AUDIENCE: What's the app--

DURAND: What's the app?

AUDIENCE: The app, the name of the app.

WERTHEIMER: OnTheFly.

AUDIENCE: The concern seems-- one concern seems to be that virtually Google that what you will do is tell the users to Google search, and it'll say, how can apply blah, blah, blah, blah and use this software. What is the fear of that led to objections to the merger that has now gone through [INAUDIBLE]?

WERTHEIMER: So I'm happy to say that the Department of Justice put a lot of work into it. And you can read a very long set of papers they've written. And they're open for public comment for the next 60 days.

[LAUGHTER]

AUDIENCE: Quick question, one of the things is optimizing for cost. In this brave new world of very busy flights, computationally, how difficult would it be to optimize for seat selection? I want to get an aisle seat, going between a and b. Or for that matter, you know how you build different connections, does it really become that computationally complex when you're going off within alliances but still trying to get from a to b?

WERTHEIMER: So luckily, these aren't computational problems. They're just problems of getting the data. So in fact, the algorithm that we have, we can sort on anything.

And this was good, when I started doing this work, I would do-- being sort of just out of cognitive science land-- I would do little studies of people to see what their preferences were. And some people would basically say, well, I'll take a connection, but I hate long flights, so try to break it up for me. Others would say, I'll take a connection, but I hate short flights, so try to get me longer flights.

So luckily, we can optimize for anything, that doesn't matter. The data hasn't been available. But now it is, because the airlines have realised that one of the main things they can now sell is choice seating.

And that's one of the biggest areas in airline merchandising right now, to basically figure out where the choice seats represent them and basically say, would you pay $50 more for some leg room? Somebody else might say, I'm happy to pay $50 less and have less leg room, I don't care. I would always take the $50 more for more leg room myself. And luckily, that data is now becoming available.

The problem is those reservation systems can't store it. They can't display it. They can't process it. Luckily, we can. And as this data is becoming available, we've got a number of projects where this will be coming out over the coming months, that you will be able to basically auction off essentially at the end any seat on the plane.

AUDIENCE: Thank you.

DURAND: Let's thank Jeremy again.

WERTHEIMER: Thank you.

[APPLAUSE]

DURAND: Next speaker is Tony DeRose, who is a senior research scientist and leader of the Pixar research team.

[APPLAUSE]

DEROSE: Oh, what an honor. Thank you, Fredo, for the invitation and Victor for the organizing, also for the dinner last night. So this is sort of an interesting anniversary. It was almost exactly 30 years ago today that I got my rejection letter from MIT.

[LAUGHTER]

But I'm not bitter. So there have been many broad talks today. I'd like to talk about something much narrower. So this is the entertainment part of the program. And within entertainment, I'm going to talk about animation, because that's the only part I think I really understand.

And one nice thing about being here at MIT is I think I can kind of pull out all the stops and really tell you what's going on underneath. So let's start.

[LAUGHTER]

Nah, of course, I'm just kidding. I felt a lot of people's hearts coming into their throats, though, for that one. So I've only got about 80 years of animation to cover. So my job is a lot easier than most of the other speakers that have been here today.

Animation started about 80 years ago, as I said, with the Walt Disney Studio, where they really invented what later became an art form. Steamboat Willie was one of the first milestones. And in this era, the only real technology was pencil, paper, and film. So the artist would draw a complete drawing, including outlines and shading, for each of 24 frames. And those 24 frames would flash by in a second, and they would do that large number of drawings to make their films.

The technology progressed primarily at the Disney Studio. But it wasn't computational in nature. It was mostly mechanical and optical, until in 1989 when the Little Mermaid was released. And this was really a pivotal film, in that just about the entire film was made with the traditional means, but the last shot of the movie was computationally accelerated.

Let me show you that last shot.

[VIDEO PLAYBACK]

[END PLAYBACK]

Okay, happy ending, tears in your eyes. So the shot itself might not be that remarkable just looking at it. But the remarkable thing about it is, it was the first deployment of a system called CAPS, which stands for Computer Animation Painting System. And CAPS was developed by-- it was a collaborative team, some at Disney and some at this little company called Pixar at the time, leading up to 1989.

And although they were able to get this one shot done, it was pretty brutal. There were lots of bugs. The artists couldn't figure out how to use it very well. But nonetheless, they charged forward.

And the next film was Rescuers Down Under. And there was a commitment that they were going to make the entire film using CAPS. First deployment, this is an artistic culture, not a technical culture, the through put in the system was way below the throughput of the artists, especially early on.

But as the production went on, things got more and more streamlined. And by the end of the film, they were flying much faster than artists could have done by themselves. And I think they ended up coming in under budget and under time.

By the time they got to Beauty and the Beast, which is 1991, not only had CAPS been perfected and they got really tremendous throughput, but they also started introducing some three-dimensional effects by Beauty and the Beast. Roughly in parallel, in a small group that would later become Pixar, there was a team of programmers and artists working inside the digital part of Lucas Film. And one of their first animated shorts was Andre and Wally B.

So that was 1984, and let me fast forward to today and give you a little bit of a glimpse for how we're making films now. And it starts with story. So storyboard artists, like the one here, create these thumbnail sketches. And then they pitch the story to each other over and over again. We put these storyboards, these storyboard panels, up on videotape, add scratch sounds to create something called the story reel, which I'd like to show a little piece for you now from Finding Nemo.

[VIDEO PLAYBACK]

-Any of you heard of P Sherman 42 Wallaby Way, Sydney?

-Sydney? Oh, sure! Hey, Ted here's got relatives in Sydney. Don't you, Ted?

-Sure do.

-Oh, hey, they know Sydney.

-[GASP]

[END PLAYBACK]

DEROSE: Okay, so that's the first time we have a film. That's just a short little clip, but when the story is working, you very quickly forget that you're looking at those fairly crude pictures. You just get caught up in the story and the characters and the worlds that they're working in.

There's been a lot of talk about areas that computation has dramatically impacted, various disciplines. And it's certainly dramatically impacted Pixar. In fact, the first deployment, the CAP System, was kind of an acceleration of what was a manual system before that. By the time we get to three-dimensional computer graphics, that's not even possible by hand. Artists simply cannot get the kind of consistency and visual richness. You have to have computation.

But of all the pieces of our pipeline, the story is a place where computation has had only very minor impacts so far-- basically in making the drawings a little bit faster using tools like Photoshop. At this point, it seems to be mind-limited. It doesn't seem to be tool-limited. Many of the other parts of the pipeline I'll talk about are computationally very intense.

Art is another area, where only moderate improvements have occurred because of computation. Here's some artwork, concept art leading to some of the character designs in Monsters, Inc. How many of you have seen one of our films? Okay, good. How many of you have seen them all? A few hands, good. Keep going, how many of you have seen all the DreamWorks films? No, I'm just kidding.

[LAUGHTER]

Lots of art gets done. Here's a sketch called a personality pose for Remy. In addition to sketches, there's a lot of sculpture that's done. Our sculptures are very, very fast.

Once the character designs start to settle, now we move into a digital world. And roughly speaking, our films take about four years from start to finish with the first two years spent in story and art and about the last two years spent in digital production. And creating the geometric models, this is for a character named Dash from The Incredibles, on the order of 5 to 10,000 points in his character mesh. So if you think about the analog of building a digital character, in the physical world, it'd be like building a physical marionette. So the creation of the static geometry is much like carving the wood or the Styrofoam that you would in the real world.

One of the next stages is rigging. And that's the analog of adding strings to the character to make the character move. So the digital analog are these animation degrees of freedom, which control the pose of the character, some of which can be fairly crude, like the degree to which an elbow is bent. But some are very fine, like the degree to which the inner part of the left eyebrow is raised. And we end up with about 300 controls in each of our faces, for instance.

And I'm told that human faces have on the order of 30 independent degrees of freedom. So our characters are on the order of 10 times better than human. Now, part of that is just over-engineering. It's a lot easier for us to add a new string than it is for evolution to add a new degree of freedom. But part of it is our characters can hit poses that no human face can hit.

So here's a little test of a facial rig. And at the time this was recorded during Ratatouille, to render these frames, it was taking a about a second or so. So these were prerecorded and then played back for the animators. Just a couple of months ago, computational power, especially on GPUs, reached a point where we can do renderings like this and considerably more complex in real time.

Another stage in the process is we call shading, which is determining how the surfaces are going to respond to light. And here's some concept art leading to the shader for Sullivan. So these days, there's lots of modeling, lots of shading, lots of placement. So as computers get faster, our worlds can get richer and hopefully more compelling.

One of the last stages of the pipeline is lighting and rendering. So here's some concept art that the art department gave to the digital lighting artist to indicate the mood that was desired in this particular shot from Monsters, Inc. And here's one of the final renders.

And so the job of the lighter is to take the positions of the virtual characters in the virtual environment and to place virtual light sources, so that when we do the simulation to describe how light is bouncing around in the scene, the virtual camera receives an image that looks like the director's intent. So that's the job of the digital lighter. We'll talk more about that in a second.

So let's put the pieces together and follow a couple of shots down the production pipeline.

[VIDEO PLAYBACK]

-Any of you heard of P Sherman 42 Wallaby Way, Sydney?

-Sydney? Oh, sure. Hey, Ted here's got relatives in Sydney. Don't you, Ted?

-Sure do.

-Oh, hey, they know Sydney.

-[GASP]

-Any of you heard of P Sherman 42 Wallaby Way, Sydney?

-Sydney? Oh, sure. Hey, Ted here's got relatives in Sydney, don't you, Ted?

-Sure do.

-Oh, hey, they know Sydney.

-[GASP]

-Any of you heard of P Sherman 42 Wallaby Way, Sydney?

-Sydney? Oh, sure. Hey, Ted here's got relatives in Sydney. Don't you, Ted?

-Sure do.

-Oh, hey, they know Sydney.

-[GASP]

-Any of you heard of P Sherman 42 Wallaby Way, Sydney?

-Sydney? Oh, sure. Hey, Ted here's got relatives in Syndey. Don't you, Ted?

-Sure do.

-Oh, hey, they know Sydney.

-[GASP]

-Any of you heard of P Sherman 42 Wallaby Way, Sydney?

-Sydney? Oh, sure. Hey, Ted here's got relatives in Sydney. Don't you, Ted?

-Sure do.

-Oh, hey, they know Sydney.

[GASP]

[END PLAYBACK]

DEROSE: And it's that easy.

[LAUGHTER]

All right, so let's talk about some of the computational challenges that we face now. The computation is certainly to the point where we can make these films. Hopefully, the stories are captivating and the characters interesting, and you all go out and buy lots of DVDs.

One of the most challenging computational pieces for us is this lighting and rendering stage. And let me just explain what's going on here from the mathematical point of view. So here's a scene from Monsters, Inc. again.

And the problem we have to solve is, for every point y in the environment and for every point z in the environment-- and let's assume that there's no fog or anything like that, so y and z lie on the surfaces in the environment, they don't have to be scattered around inside the volume, that simplifies the problem-- we have to determine how much light and its color that it's travelling from y towards z. And we have to do that for all pairs of points y and z.

And mathematically, we can determine that. So let's let l be the total amount of light travelling from y to z. And that's going to be equal to the amount of light that's emitted at y towards z. So if we know where all the virtual light sources are, we know that term, e of y, z. But then to that, we have to add the contribution from every other point x.

And so from point x to point y, we need to know how much light is going to scatter towards z. And so if you let x range over all locations in the environment, that turns into an integral. And inside the integral, we have the amount of light coming from x to y-- that's this piece-- that scatters towards z. And if we know how each of the surfaces responds to light from the shading department, then that's a known term as well, r of x, y, z. And the thing that makes this equation difficult is that the unknown, this l of y, z, is both outside the integral on this side and inside the integral on that side.

So we have to solve this big complicated integral equation. We have a variety of ways of doing that. One way that you could imagine is basically using piecewise constant finite elements, which turns this into a constant, that into a sum. And you end up with a big linear system. And by big, I mean 10 million by 10 million at least.

Another way to do it is by stochastic sampling. So you can just fire arrays in here, and that corresponds to Monte Carlo estimation of that integral. So it's challenging.

How challenging? Well, let's look at some render times. And let's compare render times in the Toy Story era, which is 1995, with the farm of the day that we had then-- our average rendering time per frame was four hours, so four hours of rendering time for every 24th of a second in the film.

Now, it's this fast forward to 2010, last year for Toy Story 3. Measured in terms of original Toy Story render farms, our render farm currently is 600 times more powerful. Great. So our render times for Toy Story 3 were, oh, about five-- actually, that's a little low.

It's really, there are about eight. So even though we had a render farm 600 times more powerful, our average time for frame doubled. So we still don't have enough computing power.

In fact, we'd like to-- our goal is to make this lighting calculation fully real time. Imagine the life of a lighter right now. You move a digital light source and then you wait for hours to see the image come back. That takes it out of-- lighting should be an artistic activity. When you have to wait four hours after you move something, it's not an artistic activity at all. It's an optimization process.

And so our best lighting artists are computer scientists that are solving essentially these big optimization problems in their head. We want to make that real time. That's a factor of between five and six orders of magnitude. So computing will get us some amount of the way there, just faster hardware. But we'll get bigger speed-ups through algorithms.

So look at this shot, for instance. There's a lot of really subtle lighting going on here. And for us, it's all about the subtlety. Our artists spend a long time trying to get the highlights in just the right place, trying to keep a lot of the artifacts from accidental alignments from appearing where the director doesn't like them.

So here's a quick little hint at an algorithm-- an acceleration algorithm. So the idea is to take a simple scene-- in this case, just a box with some balls in it for illustration purposes-- and a light source located somewhere on the ceiling. And we're going to take a sequence of those frames representing an exploration of where the lights might be in that environment.

We can do a statistical analysis of these images to produce two things. The first thing is the identification of a collection of points that have high predictive power. And the idea is that, if we know the intensities at these about 200 spots out of the quarter million pixels, if you know the intensity of these 200 pixels, you can very accurately and very rapidly determine the intensity at all the other pixels.

These pixels aren't all random. There's a lot of coherence from one to the next. And so you get both of those things out of the analysis-- both where to sample to get highly predictive results and then a linear method, in fact, to compute the other pixels. So this is an acceleration technique that was developed in the research group. It's currently on the shelf waiting to be deployed into production.

Another place where, not just computational power, but also authoring effort comes to bear is this rigging process. So here's Dash that we saw a few moments ago. To rig him means describing how each of his 10,000 points is going to move under the control of the animator for each of those digital strings.