 |
| From https://github.com/genekogan/FlockingBoids |
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 |
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 |
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
- The Phi phenomenon
- Flip-book animation
- Discretizing space and time: pixels and frames
- Animation vs. simulation vs. display rates
- The coordinate system
- Immediate mode vs. retained mode graphics APIs
- Polling vs. event-driven user input
- Spritesheets
- Thinking with vectors
- Distance between points
- Point in polygon intersection detection
- Rectangle-rectangle intersection (collision) detection
Sample project and resources:
- Make a simple animated, moving character
- codeheart.js Knight demo
- Nice Javascript sprite tutorial
Ballistic Motion
- Newton's laws of motion
- State space
- Derivatives and integrals review
- [Simulation as an ordinary differential equation]
- Numerical integration
- Taylor expansion review
- Order of error
- Euler (Forward, backward)
- Runga-Kutta (2nd + 4th order)
- Verlet
- Point-disk intersection
- Disk-disk intersection
- Penalty forces
- Impulses
- Particles
- Structure of arrays vs. array of structures
- SIMD vs. Arrays
Sample projects and resources:
- Make a character that moves in the presence of gravity (platformer)
- Make a particle system
- CG:PP chapter 35, first half
- codeheart.js "Physics" demo
- codeheart.js Warrior Princess demo
- Reeve's Particle Systems paper
- Witkin & Baraff's SIGGRAPH course notes, sections A-C [HTML version]
- Jarrod Overson's article
- Javascript RK4
- Derivation of Verlet integrator
- Leapfrog integration
- [Verlet, L. "Computer experiments on classical fluids. I. Thermodynamical properties of Lennard-Jones molecules", Phys. Rev., 159, 98-103 (1967).]
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
- Cloth simulation
 |
| The now-defunct Sodaplay app |
Sample projects and resources:
- Build a top-down animal simulation with predators and prey
- Build a modern version of Decarlo's xspringies and Sodaplay
- Craig Reynold's "Boids" SIGGRAPH paper
- Verlet cloth
- Karl Sims' Evolving virtual creatures
- Interpolation and splines GDC notes
- All you need is force: a constraint-based approach for rigid body dynamics in computer animation, Kees van Overveld and Bart Barenbrug, Computer Animation and Simulation 1995
- Meshless Deformations Based on Shape Matching, Matthias Muller, Bruno Heidelberger, Matthias Teschner, and Markus Gross, SIGGRAPH 2005
- Smooth Rotation Enhanced As-Rigid-As-Possible Mesh Animation, Zohar Levi and Craig Gotsman, IEEE TVCG 2003
Rigid Bodies
 |
| Angry Birds built a game brand empire from rigid body simulation |
- Conservation of momentum
- Disk-rectangle collisions
- Polygon-polygon collisions
- Minkowski sums
- Torque
- Moment of inertia
- Friction
- Elasticity
- Working with rigid body APIs
- Revolute and "world" joints
- codeheart.js Box2D demo
- CG:PP chapter 35
- MIT moments of inertia
- Nonconvex Rigid Bodies with Stacking, Eran Guendelman, Robert Bridson, Ronald Fedkiw, SIGGRAPH 2003
Articulated Sprite Animation
- Articulated rigid body, relative reference frames
- Joint forces and constraints
- "Ragdoll"
- Splines
- Bones
- Inverse kinematics
- Spriter
- Inverse kinematics
- Real-time motion retargeting to highly varied user-created morphologies ("the Spore paper"), Hecker et al., SIGGRAPH 2008
Cellular Automata ("Voxels")
 |
| A falling sand game |
- Conway's Game of Life
- Falling sand
- Minecraft
Sample projects and resources:
- Implement a falling sand game
- Cellular Automata for Physical Modelling, Tom Forsyth, Game Programming Gems 3, 2001 (page 200)
- Jos Stam's stable fluids
- The Making Of Dwarf Fortress (page 9), John Harris, Gamasutra, 2008 (focus on the hard case of volume-preserving water; check out recent results in Voxel Quest and speculate about how that system might work)
Fluid Dynamics
- Drag forces
- Cellular automata fluids
- Smoke
- Compressibility
- Pressure
- Pressure systems for cellular automata
- Viscosity
- Adhesion
- Wave dynamics
- Particle system fluids
- Smoothed particle hydrodynamics
Sample projects and resources:
- Make a shallow-water top-down simulation, with boats and islands
- Make a cellular automata side-view simulation with incompressible fluids
- Jos Stam's Stable Fluids
- Navier-stokes
- Navier-stokes demo
- SPH for games
- Multiresolution particle-based fluids, Richard Keiser, Bart Adams, Philip Dutre, and Leonidas Guibas, Technical Report, ETH Zurich, 2007
- Adaptive particles
- Real-time Eulerian water simulation using a restricted tall cell grid, Nuttapong Chentanez and Matthias Muller, SIGGRAPH 2011
- Highly Adaptive Liquid Simulations on Tetrahedral Meshes, Ryoichi Ando, Nils Thurey, Chris Wojtan, SIGGRAPH 2013
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.
