Wednesday, 30 December 2015

"Computer Behind Pixar": Teaching Computational Thinking for 3D Modeling and Representation

How do you teach a group of middle- or high-schoolers about computer graphics without setting them down in a computer lab or showing them code? How do you teach them about 3D geometry without writing down a single mathematical formula on the board? And how, without doing all these things, can you nevertheless equip them with the vocabulary and intuition to be able to discuss and understand concepts in computer graphics, geometry, and representation?
Pinart toy: what better way to explain height fields?

That was our goal, and our chosen plan of attack was to flood the senses: let our students touch and explore physical models, work through group activities, watch video clips, participate in class discussions, and see demos. We filled our classroom with 3D printed models of various materials, faceted animal shapes, wooded mannequins, pin art boards, crayons and fuzzy pipe cleaners. 
What do all these objects have in common?

These physical models serve as examples and applications of different representational choices, including voxel grids, meshes, and height fields. Having physical examples to point to and explore can launch a discussion of different representational (3D modeling) choices.

Splash 2015 @ MIT

On November 22, 2015, Hijung Valentina Shin, Adriana Shulz, and I taught a 2-hour high-school class as part of MIT's yearly Splash! program - a Fall weekend during which thousands of high-schoolers flood hundreds of MIT's classrooms to be taught anything and everything. 

In our Splash! classroom, we sought to ask and answer the following questions: How is an animated character created? How can we represent different types of 3D structures? What kind of modeling decisions are made for a special effects film? What techniques do anthropological reconstruction, 3D printing, and game design have in common?

Importantly, we believed that these questions could be answered on an intuitive level, with no mathematical prerequisites. What better way to motivate the study of the mathematical and computational sciences than to give students a faint whiff of the awesome things they would be able to accomplish and think about in greater depth if armed with the right tools? 

Computational thinking to the rescue!

Here I will briefly outline the structure of our 2-hour class and the decisions made along the way, to provide possible inspiration for similar classroom activities and lessons. For the benefit of others, we have made all our slides available online.

Coding without coding

Target shape that one student described to the other using only
a set of provided primitives: colored squares, line segments, or
polygonal shapes.
Our ice-breaker activity first introduced the concepts of representational primitives and algorithmic decisions. Students split up into pairs, armed with grids and sketching utensils (colored crayons or pencils). One student was given a target shape, a set of primitives, and instructions. The goal was to supply one's partner with a sufficient and clear recipe to reproduce the target shape as accurately as possible. Some students could only specify one grid cell at a time with coordinates and a target color. Another set of instructions armed students with a ruler and the ability to specify starting and ending coordinates of line segments. A third group of students had polygonal shape rulers – e.g. triangles, squares, circles. Students could tell their partners to center a shape at specific coordinates.
Polygonal primitives
(ordered on Amazon)

Overall, we gave different student pairs different primitives:
  • pixels (colored squares)
  • line segments
  • polygonal shapes
We gave all students the same amount of time to complete this activity in pairs (15 minutes), after which students showed off their creations to their partners and other students in the class. These creations were hung around the classroom at the amusement of the students.

This gave us a great launching pad for discussion about the trade-offs between representational accuracy and algorithmic efficiency. We asked students: What did you find easy and hard? Were there parts of the shape that were well represented by your primitives? Could everything be represented by the primitives? What took you the longest? How many individual primitives did you end up using?

This kind of activity (or variants of it) is a good intro to programming activity, as students have to think about formalizing clear step-by-step instructions for their partner to carry out. The full instructions and templates for our activity are included here.

Computer behind Pixar

Inspired by the recent hype around Pixar* and particularly Boston Museum of Science's temporary Pixar exhibit, we called our class "Computer behind Pixar". The common goal of the exhibit and other educational media about Pixar is to hook in the general public with the beloved animations and characters for the purpose of introducing and motivating the underlying mathematical and scientific concepts. In fact, Mike from Monsters Inc. served as a repeating element throughout our activities, though we branched beyond Pixar, and beyond animation more generally. 

* Reference links on the topic of math behind Pixar:

We described and showed a video about the rendering pipeline*, and drew attention to the importance of modeling at the core of this pipeline, as the initial step that all future steps crucially depend on. We defined modeling as a mathematical representation composed of primitives
The rest of our discussion centered around different representational choices and their properties.

* More rendering resources:
Video about rendering in Pixar
Article about rendering in "Inside Out"
Character rendering (dark knight)
Rendering pipeline summary

Tangible examples of 3D representations

3D printed models are a tangible
demonstration of discretization and
the resolution issue.

Voxel grids

We introduced the concept of discretization, necessary for the representation of shapes in digital computers: 2D shapes as pixels and 3D shapes as voxels. We reminded students of the ice-breaker activity where grid cells were used as primitives.   
We then discussed voxel grids as one form of representation for 3D objects, commonly used for 3D printing. We talked about the resolution issue: the trade-off between accuracy and efficiency. We passed around physical 3D printed models at various resolutions, similar to the models pictures on the right.

Physical models to demonstrate the
differences between volumetric and
boundary representations. One is much
lighter! Why? It requires less material
to represent (and store).

Triangular meshes

In talking about efficiency, we introduced the notion of boundary representations, specifically meshes, for representing 3D objects without having to represent and explicitly store all the internal voxels (the volume). 
We connected the boundary representation to the ice-breaker activity, where in 2D, line segments were used to represent the target shape's boundary. We then showed students a demo of MeshLab, and passed around physical examples of volumetric and boundary representations.


We moved on to discuss how simple shapes can be combined with different operations to create more complex shapes, in 3D via constructive solid geometry (CSG). We reminded students that the ice-breaker activity also contained polygonal primitives in 2D. For 3D, we showed students a demo of OpenScad and discussed primitive operations (union, intersection, difference, ...) that can be performed on shapes. Applications in manufacturing were discussed. 

Height Fields

Heigh fields were introduced with the help of pin art boards, as pictured at the beginning of this article. Students played with the pin boards and considered again the concepts of discretization and the representation issue. We asked students: which kind of shapes or surfaces can be represented this way and which can not?

Procedural Modeling

The grass in Pixar's Brave was created with procedural modeling,
using parametric curves and randomness.
A great hands-on demo of this kind of modeling can be found on:
 Khan Academy's Pixar-in-a-Box.
We discussed how shapes could be created by specifying procedures on primitives (aside from the primitive operations in CSG). We showed demos of solids of revolution (what better way to motivate the concept that for most students appears for the first time only in college calculus?).   We discussed how procedures like revolution and extrusion can be performed along different paths to create all sorts of complex shapes. We discussed how these paths can be further parametrized so that the revolution or extrusion procedure changes along the path. We introduced randomness as another concept that can be used to add variability to the representation.
We discussed applications to modeling trees, forests, grassy fields, crowds, and cities.

3D Representation        Primitives                Operations (recipe)                   
Voxel grids                   Voxels                     Material specification for each voxel
Triangle mesh               Triangles                 List of triangles with locations
CSG                              Basic shapes            CSG operations (union, intersection, etc.)
Height field                  Points with height    Assignment of heights to points
Procedural model         Basic shapes            Procedure (e.g. extrusion along path)

A new way to look at things

With our class, we hoped to give students a look at the modeling decisions that underly all the animated films, video games, and special effects they see on a daily basis. We wrapped up our class with a thought exercise, putting students in the position of making decisions about how to model different objects. We told them to think about the different representations we discussed: the primitives and operations required. We told them to consider the trade-off between accuracy and efficiency. Given a representation, we also told them to think about its usability - what kind of use cases are being considered, e.g. whether the modeled object needs to be animated and how. Students were asked to brainstorm how they would model the following objects: buildings, cities, fabric, hair, grass, water. Along the way, we showed them image and video demos (all these links can be found in the slides). We passed around more physical models. Together, we watched a video "behind special effects" that showcased the kinds of 3D models used in movies, a great visual review of the many representations covered in our class. We told students to look around and realize that 3D modeling decisions underlie many other applications: special effects in films, video games, simulations, anthropological reconstructions, product design, urban planning, robotics, and 3D printing. To be reminded that they have been armed with a new way to look at things, students took home polygonal stickers.