So well deserved !!!
Two founders of animation powerhouse Pixar have won the 2019 ACM AM Turing Award, with a $1m prize, for their pioneering work on 3D graphics. Pat Hanrahan and Ed Catmull are largely responsible for moving computer graphics from jagged polygons trying to represent reality to the smooth, shaded, 3D images that we take for …
Very much so.
Mid-80s I remember going to a computer graphics show in London, and they showed Pixar's first short "Luxo Jr.". Absolutely stunning, had the audience in awe, and still looks good today.
Times change, though. That show also featured an animation of a flag fluttering in the breeze. Might not have looked too special to an inexperienced eye, but the maths behind it was impressive, especially since it was running on a BBC Micro! Today we get blasé about even the most clever graphics: "Oh, it's just CGI, it's not real".
Maybe you can't handle it, but I guess that I can. And that's not being boastful. Any gamer that's evaluating graphics cards and how certain games might play out on the new hardware will be totally au fait with a shit load more details in how it works under the hood than the article provides.
Expert knowledge has a way of becoming mainstream, after all. That's science, bitch!
I've been upgrading my graphics card since - (checks records) - 1992. Yes, I've read up on interpolation, yes I know what NURBS are and can tell that I want a card to do that. But know how it works ?
Sorry, bud, I'm a gamer, not a mathematician. I check the specs and choose my card because I've been told what to look for. I have a vague idea of how stuff works because I read about it. I absolutely cannot fathom the math behind it and, being a gamer, I don't have the time. Those games aren't going to play themselves, you know.
Now, if only I could get a version of Minecraft that used Toy Story graphics. That would be awesome.
NURBS (Non-Uniform Rational Basis Splines) basically allows you to select multiple TANGENT POINTS in 3D-XYZ or 2D-XY space (i.e. Tangents are a series of points placed ANYWHERE on an arbitrary line or curve) and use one or more TENSIONING BARS that move outwards from those tangent points which describe the distance and amount of curvature to apply when drawing a spline curve outwards from each given tangent point 2D-XY or 3D-XYZ coordinate.
These splines connect to the NEXT or PREVIOUS tangent points giving you a simple curve, a compound curve or a arbitrary shape that can then be FILLED with a specific colour or shaded with a user-specified texture such as leather, chrome, fur, skin, etc.
Splines and their cusps describe the drawing angle, drawing distance and the amount of flatness or curvature applied any given spline curve. These calculations are always real numbers and converted at the last second to discrete pixel coordinates which are operations USUALLY accelerated by high end GPU graphics cards which contain thousands of miniature CPU cores working in parallel to allow for FAST drawing of such curves and creating the textures which will fill those curves and shapes.
I remember when an SGI Onyx Graphics Supercomputer was STARTING AT $1.5 million US and now my $300 smartphone has more drawing horsepower than that 1990's era graphics supercomputer!
It's generally quite a bit easier to understand someone else's research, after they've already done the work, than it is to invent it on your own. That's the whole point of "standing on the shoulders of giants".
If none of us could understand ideas we didn't come up with ourselves, there'd be no communication.
And it's even possible - at least for some of us - to understand things in areas we don't work in. It does require some thinking and an open mind, which I know are insurmountable hurdles for some.
Catmull-Clark subdivision surfaces is probably the big one. It's a technique that allows a single polygon to simulate multiple smaller polygons with a smooth gradation between the joins.
This allows a model to appear to be high-polygon when it is in fact relatively simple and low-polygon.
What's more the technique is open and as such is widely used. Blender includes it as a modifier. Its user guide also includes some nice example images of subdiv in action.
"It's a technique that allows a single polygon to simulate multiple smaller polygons with a smooth gradation between the joins.
This allows a model to appear to be high-polygon when it is in fact relatively simple and low-polygon.
What's more the technique is open and as such is widely used. Blender includes it as a modifier"
Blender may use Catmull-Clark as a method to decide how to subdivide faces but it doesn't "simulate" the additional smaller polygons to make a model "appear" like it has a high polygon count as your post would suggest; Subdivide a simple cube 4 times with Subdivision Surface and you'll end up with a sphere (of sorts) with 1,536 faces. All those extra faces are there as if you manually created them. Catmull-Clark, or at least it implementation in Blender, isn't some visual trickery, like Smooth Shading, to "simulate" the "appearance" of extra detail. The editable verts/edges/faces do become something more akin to "handles" on curves in vector based image editors but you don't get the look of a high polygon model without the extra CPU/GPU overheads that brings.
What I'm more impressed with is it appears that some games are now using live Catmull-Clark subdivision (slightly edited to keep edges without adjoining faces always sharp) on their models in certain circumstances where there is less going on (like in menus or photomodes) and they can afford to significantly bump up the per-model poly count. It wouldn't surprise, on the next gen of consoles, if we start to see live Catmull-Clark subdivision in many more (playable) areas of games since, as well as making lower poly models look better, it also effectively acts as a form of "compression" in a similar way as vector based images do compared to a bitmap based image for certain types of images.
Toy Story 1 didn't use GPUs, it was rendered (with RenderMan) on a farm of SPARC systems:
"The images required 800,000 hours generation time on a RenderFarm consisting of 87 2-CPU SparcStation 20's, 30 4-CPU Sparc-Station 20's and a SparcServer 1000." (IMDB)
That was state of the art at the time, it took 7 weeks elapsed time to render the 75 minutes of film. Apparently they redid it in 2011 on then-current hardware, it was 50-60x faster.
Catmull's dissertation is available online, albeit as a PDF of screenshots of the typed pages.
Quick take: State of the art at the time was rendering forms using Garoud-shaded triangles. The big problem with GS is that the first derivative is discontinuous which produces noticeable Mach banding. Various anti-aliasing techniques were applied to blur the bands and smooth the surface appearance, but that approach isn't ideal.
Catmull's approach uses bicubic patches1, which I believe are capable of expressing any smoothly-curved surface (but it's been a long time since I did any of this stuff). So each patch can accurately represent any smooth part of whatever you're rendering. Then he showed how to quickly subdivide each patch until you get to single pixels (which depends on viewport and distance), at which point you can render that subdivision of the patch. And he showed how to map 2D images to patches, so you could do texture-mapping.
So the old technique (which remained in use for many years after, since it was easier to do quickly) was "decompose into triangles and shade from the vertices in, by linear interpolation"2. Catmull's was "decompose into bicubic surfaces, then decompose those further".
It's good stuff, as was his later work, and he and Hanrahan are well-deserving. But then Turing Award recipients usually are; the ACM does a good job of selecting them. (Which is not to say there aren't plenty of other folks who would also be appropriate choices.)
1A bicubic patch is a surface defined by a parametric system of two parameters, s and t. You vary s and t each from 0 to 1 at whatever sampling rate you want, and each value is a point on the surface. Think Bezier curve extended to 2 dimensions.
2There are other triangle-shading algorithms, such as Phong.
A good fried, Lance Williams (who died way too soon):
New York Institute of Technology (NYIT)
In 1974 Dr. Alexander Schure, a wealthy entrepreneur, began to assemble the Computer Graphics Laboratory (CGL) at the New York Institute of Technology. His vision was to create a feature length animated film, with the aid of the days most sophisticated computer graphics techniques. NYIT itself was founded by Dr. Schure, had grounds encompassing numerous estates situated in the beautiful wooded hillsides of Old Westbury New York. Some of these estates were owned by members of the Rockafeller family, who also happened to have a seat on the board of Evans & Sutherland. Because of the close association of E&S with the University of Utah, Dave Evans recommended to Alex to seek out Edwin Catmull to head the new CGL. Ed Catmull had just finished his Ph.D. at Utah and taken a job at a CAD/CAM company called Applicon. It was not a hard sell to get Ed to leave Applicon for NYIT however, so he and fellow Utah graduate Malcolm Blanchard packed their bags for New York. Alvy Ray Smith and David DiFrancesco (both fresh from Xerox PARC) joined the team a few months later in what was called the 3Gerry Mansion2. Alvy and David had heard of Dr. Schure9s plans from Martin Newell at Utah (whom Alex had just hired briefly as a consultant). Dr. Schure had recently come through Utah and literally ordered 3one of everything2 to jump start his NYIT project. Some of this equipment included a DEC PDP-11, a new E&S LDS-1 and the first random access frame buffer also from E&S. Later, the CGL group would also receive the very first commercial VAX.
[SIDEBAR] VAX ALMOST SMASHED! In fact, the VAX almost never made it inside the building, if not for Alvy Ray Smith9s quick actions. It seems that when the computer was just lowered off the back of the delivery truck, another truck parked behind and uphill had it9s brakes slip, which started it rolling towards the brand new machine. Alvy quickly jumped in the driver-less truck and stopped it just before it could smash the VAX back into the very truck it was just unloaded from.
The CGL quickly attracted other technology experts and artists, including Christy Barton(from E&S), Tom Duff, Lance Williams, Fred Parke, Garland Stern, Ralph Guggenheim, Ed Emshwiller, and many others. Throughout the 1970s, the people of the CGL thrived in a pioneering spirit, creating milestones in many areas of graphic software. Many of the 3firsts2 that happened at NYIT were based on the development of the first RGB full color (24bit) raster graphics.
A few of the more notable 3firsts2: First RGB anything (because they had the first RGB framebuffers in the world). First RGB paint program (Paint by Alvy Ray Smith). First soft-edged fill (Alvy Ray again). First computer-controlled video editing. First TV commercial with raster graphics (Lance, I think, or maybe it was Ephraim Cohen). First pixel dissolve. First networked computer system (Christy rolled our own for us). The alpha channel is invented by Ed Catmull and Alvy Ray Smith. First hidden surface algorithm within a pixel (Ed). Lance Williams invented mipmapping (texture mapping is still done this way today). Garland Stern implemented the first scan and paint system (this is how the Disney/Pixar CAPS system now makes 2D animation - different system but same idea).
The atmosphere at the CGL was also very open, with many invited tours coming through the lab all year-round. Other universities like Cornell, and companies such as Quantel were among those to visit and take notes about what was being developed. The personnel structure was virtually non- existent, with never any heavy handed management from Dr. Catmull. People did what they were best at and helped each other out whenever needed.
[Strangest Job Title ever!] Alvy Ray Smith would later accidently come across an organization chart for the lab put together by Dr. Shure. Ed Catmull was running the lab of course but there where people listed above and below him that no one had even heard of. Alvy was particularly amused to find that his official title was 3Information Quanta2. A term very much in keeping with Dr. Shure9s somewht unique, and non-standard form of communicating.
Ed Catmull9s Tween, Alvy Ray Smith9s Paint program, and the 2D animation program SoftCel, all were in keeping with the original charter of the CGL, which was 2D CG. There were also many breakthroughs in image techniques involving fractals, morphing, image compositing, and Mip-Map texture mapping and many others. Key to this pioneering effort was the seemingly unlimited financing evidenced by Alex Schure. One such example took place when Alvy Ray Smith spoke with Alex about how good it might be to have not just the one, but three frame buffers. This way, Alvy explained, the three 8bit buffers could be combined to create the first RGB color frame buffer ever! Sometime later Alex not only delivered the two additional frame buffers, but an additional 3, which gave the CGL team a grand total of 6. (3Enough for two of those RGB things2 said Alex.) At $60,000 each (plus the $80,000 for the first) what this meant in today9s dollars was that on a simple request, Alex had just delivered about $2million worth of equipment. More Utah people joined the CGL, including Garland Stern who would write the vector animation system BBOP. David DiFrancesco would also begin what would be turn out to be a long association with film recording at this time. Jim Blinn even worked at the CGL as a summer intern in 1976.
As a graphics geek, I've always been watching for those little scenes where Pixar would just plain show off their graphics capabilities. Mrs Fink gets quite peeved when I point at the screen and go "wow - that's REALLY difficult!" while the poor girl is just trying to watch the movie.
So, it's fantastic to see these guys properly rewarded for their decades of effort.
This post has been deleted by its author
Depends on the time, as some things that were fantastic at the time are ordinary now! A few off the top of my head:
- Monsters Inc: there's a scene where the blue monster (sorry kids can't remember his name ;)) is tobogganing down a hill and they've managed to animate all the hairs on his body blowing in the wind individually. For the time it must've taken forever to render.
- Cars: ray tracing! Wow look at those reflections! (Of course these days your new video card just does this out of the box.) There's also a few desert scenes where they've obviously randomly generated the landscape features (down to small rock level) and generated some kind of weathering/dusting effect on top to give the ground over the top.
- One of the Toy Stories (2???): at one point, someone scatters a box of those cheese snack things all over the floor. They've all got super-irregular surfaces done in fine detail, and they've managed both to get the surfaces right and to do the lighting correctly. At that point I thought to myself "Pixar you're just f'n showing off, aren't you?"
- In one of the shorts, they play with a container of milk. Milk is notoriously difficult to do, as the lighting, transparency and consistency are really hard to get right. Can't remember the short sorry - I have a vague idea their little lamp was jumping around in it as well...
- there's a recent short called Piper, which just blew me away. It's about a sandpiper on a beach, so lots of textures to play with :). The work on the feathers is just brilliant, and they've also done an amazing job on the surf. The water is great (again difficult), and they've got the little areas of foam that the waves leave behind just right. The sea isn't quite photo-realistic, but it's pretty damn close. Find it (in hi-def!) and have a watch.
That's all I can remember quickly - damn I'm going to have to get watching again. If only I was wfh..oh...