I'm Morgan McGuire (@CasualEffects). I've been working on computer graphics and games for 20 years at great places including NVIDIA, University of Waterloo, Williams College, Brown University, Roblox, Unity, and Activision.

See my home page for a full index of my blog posts, books, research, and projects.

Friday, February 5, 2016

The Joy of Animation: An Undergraduate 2D Computer Animation Syllabus

From https://github.com/genekogan/FlockingBoids
I'm exploring the idea of teaching a new, mid-level course on animation in the Williams College Computer Science department. I was pleasantly surprised by just how excited my students were about animation topics in other computational graphics courses, and think it could stand alone.



There's an opportunity to introduce the field of animation earlier in the curriculum and with more depth than permitted by a few weeks in a high-level course. This class would require only multivariable calculus plus two semesters of programming courses. It would thus be available to sophomores and non-CS majors. That allows a close encounter with simulation algorithms for, say, a future chemist, biologist, economist, or social scientist. It also would allow a potential CS major to experience elective material before committing to the program.

In some contexts, "animation" means 2D cel movies, Pixar-style CGI movies, animated GIF, or sprite frames. In this course, I'm instead referring to "computational dynamics" or "classical physics simulation": numerical simulation of the classical mechanics methods of Newton, Boyle, Hooke, Venturi, Pascal, Stokes, etc. that are employed in scientific simulations, movies, and video games.

At a high level, this course combines the "Motion" chapter of Computer Graphics: Principles and Practice 3rd Edition with the Optimal Animation, Synthetic Creatures, and Unconventional Animation units from CS372: Visual Media Revolution...in 2D. This is all material that has worked well in previous courses for me when covered quickly, and now would have an opportunity to expand to its natural scope.


2D

Why 2D? It seems anachronistic when the high-impact animation work in research and industry is 3D. However, the computational demands of 3D are high and the mathematics of 3D rotation are fairly complex. By simplifying to 2D these can be avoided, focusing on the concepts unique to simulation instead of optimization or 3D math. Fortunately, most of the key numerical concepts are the same from 2D to 3D dynamics, but with fewer cases to handle. This includes collision detection and integrators.

The rendering and user interface are also much simpler in 2D, and I want this course to benefit from that simplicity...we have plenty of other courses on those topics.

Finally, many people find 3D rotation dynamics counter-intuitive. This makes debugging really hard. Now, there's beautiful and important math behind that--for an upper-level course. Mid-level students excited about arcade games and web animations aren't ready for quaternions and inertia tensors, and I want to use their excitement to increase their skills to the point where they'll be ready for 3D in another course.

Even physics majors can graduate without ever learning how to compute 3D rotation dynamics for classical mechanics, so I don't see that as a requirement for sophomores in a non-major CS course!

Y = Up

As any graphics programmer knows, there's one seemingly trivial choice in 2D that comes back to cause problems throughout development. Does the y-axis (vertical) increase downward, as in windowing systems, image editing programs, and text coordinates, or upward as is conventional in graphs and 3D systems?

For 2D game programming I've usually chosen downward to reduce opportunities for bugs when working with mouse and touch events and so that pixel coordinates picked out in Photoshop match what the renderer is outputting. This also makes the axes textures (image sprites) being read match the output being written. However, this creates opportunities for error in direction of rotation, trigonometry (cos, sin) and vector cross products.

I think that for simulation it is more important to avoid the latter confusion, so y = up is my choice for this course and I'll have to adapt the underlying 2D platform's coordinate system.

Mathematics

Computational dynamics applies mathematics in a way that builds intuition for abstract concepts, such as vector bases and differential equations. It also introduces fundamental numerical algorithms that underly all applications in scientific and economic simulation. A simulation course is a good way to solidify and expand existing mathematics knowledge and tie it to discrete computation.

What is the right level of math to require for incoming students? It would be possible to learn/teach dynamics without calculus. However, the equations would be more complicated and obscure their fundamental structure...and you'd end up reinventing calculus along the way, regardless.

It would be really easy to teach dynamics to students who have already mastered of linear algebra, differential equations, and Newtonian mechanics. However, the only undergraduates with such knowledge are junior and senior mathematics majors.

Typical equations encountered in dynamics algorithms. While the compact notation may be intimidating at first, the key mathematical tools are just integrals and derivatives in 2D spaces.

Multivariable calculus seems like the right prerequisite for an animation course. 60% of all students at Williams College take multivariable (Math 150/151), and almost all science majors. Limiting the math prerequisite keeps the course accessible to many students while ensuring that everyone who enrolls is already comfortable with 2D spaces and time varying quantities. The linear algebra required for 2D animation (essentially, vector operations and working with matrices up to rank 4, for splines) can be learned piecemeal as the course progresses, and differential equations can be alluded to without explicit discussion. I assume that many students exited their calculus courses without perfect recall and understanding, so I'd review (or introduce) some topics early in the course at their first application:
  • Taylor polynomials
  • Derivation of the derivative
  • Derivation of the Riemann integral
  • Definite vs. indefinite integrals
  • Independent and dependent variables; the chain rule
  • First fundamental theorem of calculus
  • Area vs. line integrals
  • Partial derivatives
  • L'Hopital's rule
  • Gradient and divergence

Development Platform

I want assignments to produce attractive, real-time, interactive results that can be easily shared. This makes them enjoyable and intuitive to develop and makes the course self-advocating to future students.

The Box2D Example in codeheart.js
For programming lightweight animation assignments, I lean towards Javascript, with a rendering and user input framework based on either three.js or codeheart.js. The ideal framework might be a WebGL back end for codeheart.js to combine performance and an easy-to-use 2D API.

Javascript is a good graphics prototyping tool. It is accessible, since every student computing platform has a JS and WebGL-enabled browser, from Windows/Mac desktop to mobile to Linux. So, everyone can access it and can easily show results on like.

Javascript is interpreted, avoiding the development overhead of compilation and linking. Browsers provide an inspection console, debuggers, and profilers. It has a fairly sparse syntax and lots of useful libraries, including a nice Box2D implementation. Javascript's weaknesses on data (no file system, no easy way to embed files) and systems programming (no operator overloading, static typing, or language-level import) are less limiting for small, procedural animations than for other assignments.

Most of our students are currently facile in Java and can learn Python quickly. Unfortunately, Java's an awkward language for lightweight animation because it is buried in boilerplate syntax, binds awkwardly to graphics APIs, and is increasingly unsupported on the web.

Python has a relatively beautiful syntax and even offers operator overloading. Unfortunately, its graphics and physics API libraries are even more limited than Java's, and the web is largely unavailable to it. In the long run, I hope to see a stable and well-supported Python to asm.js compilation path emerge, and nice WebGL and Box2D bindings for it. For those interested in using Python for an animation course, I suspect that using the PyGame framework for handling graphics and UI. Some simple physics examples are available using it.

C++ and OpenGL or Vulkan is probably not a viable combination for a 200-level course at my institution, given the students' lack of experience working at such a low level or with such powerful (and thus "dangerous") tools.

I could imagine using Processing. However, my hunches are that the cross-language compilation step would confuse students when writing more complex simulations (it has in the past when I used it for game programming) and that I'm going to want direct access to GPU pixel shaders for fluid simulation.

P_malin's Shader Rally
It is worth noting that for experienced hackers, it is possible to prototype many animation algorithms in Shadertoy. For example, shallow water simulation, Navier-Stokes fluid, SPH fluid, 2D rigid bodies, and 3D rigid bodies. Although I'm a big fan and these are great motivating examples, Shadertoy isn't a natural or friendly programming environment for new programmers (let alone those who don't understand real-time ray tracing), so I haven't seriously considered it as a course platform.


Topics

Below I list some topics in a cumulative order, where the later ones build on ideas developed earlier. The list contains about twice as much content as I'd be able to cover with projects in a 12-week semester. So, I'd likely describe articulated sprite topics in lecture or readings but avoid assigning a programming project on them. At a school with a longer semester or for a slightly higher-level course those would be great topics to invite students to explore through implementation.

Sprite Animation

  1. The Phi phenomenon
  2. Flip-book animation
  3. Discretizing space and time: pixels and frames
  4. Animation vs. simulation vs. display rates
  5. The coordinate system
  6. Immediate mode vs. retained mode graphics APIs
  7. Polling vs. event-driven user input
  8. Spritesheets
  9. Thinking with vectors
  10. Distance between points
  11. Point in polygon intersection detection
  12. Rectangle-rectangle intersection (collision) detection

Sample project and resources:

Ballistic Motion

  1. Newton's laws of motion
  2. State space
  3. Derivatives and integrals review
  4. [Simulation as an ordinary differential equation]
  5. Numerical integration
    1. Taylor expansion review
    2. Order of error
    3. Euler (Forward, backward)
    4. Runga-Kutta (2nd + 4th order)
    5. Verlet
  6. Point-disk intersection
  7. Disk-disk intersection
  8. Penalty forces
  9. Impulses
  10. Particles
  11. Structure of arrays vs. array of structures
  12. SIMD vs. Arrays

Sample projects and resources:

Intelligent and Emergent Behavior

  • Interpolation and extrapolation
  • Splines
  • Flocking, herding, and schooling
  • Constraint systems
  • Mass-spring systems
  • Hooke's law
  • Damping and oscillation
  • Spring "motors" and prismatic joints
  • Meshes
    • The now-defunct Sodaplay app
  • Cloth simulation

Sample projects and resources:

Rigid Bodies

Angry Birds built a game brand empire from rigid body simulation
  1. Conservation of momentum
  2. Disk-rectangle collisions
  3. Polygon-polygon collisions
  4. Minkowski sums
  5. Torque
  6. Moment of inertia
  7. Friction
  8. Elasticity
  9. Working with rigid body APIs
  10. Revolute and "world" joints
Sample projects and resources:

Articulated Sprite Animation

  1. Articulated rigid body, relative reference frames
  2. Joint forces and constraints
  3. "Ragdoll"
  4. Splines
  5. Bones
  6. Inverse kinematics
Sample projects and resources:

Cellular Automata ("Voxels") 

A falling sand game
  1. Conway's Game of Life
  2. Falling sand
  3. Minecraft

Sample projects and resources:


Fluid Dynamics


  1. Drag forces
  2. Cellular automata fluids
  3. Smoke
  4. Compressibility
  5. Pressure
  6. Pressure systems for cellular automata
  7. Viscosity
  8. Adhesion
  9. Wave dynamics
  10. Particle system fluids
  11. Smoothed particle hydrodynamics

Sample projects and resources:







Morgan McGuire (@morgan3d) is a professor at Williams College, a researcher at NVIDIA, and a professional game developer. His most recent games are Project Rocket Golfing for iOS and Skylanders: Superchargers for consoles. He is the author of the Graphics Codex, an essential reference for computer graphics now available in iOS and Web Editions.
Posted by at