CS 5643: Physically Based Animation for Computer Graphics
Spring 2013

PROFESSOR:  Doug James

TA: TBA

HELP SESSIONS AND OFFICE HOURS:  Mon 4-5pm, Wed 1-2pm, Fri 4-5pm

DESCRIPTION:  Modern computer animation and interactive digital entertainment are making increasingly sophisticated use of tools from scientific and engineering computing. This course introduces students to common physically based modeling techniques for animation of virtual characters, fluids and gases, rigid and deformable solids, and other systems. Aspects of interactive simulation and multi-sensory feedback will also be discussed.  A hands-on programming approach will be taken, with an emphasis on small interactive computer programs.

TIME:  TR 2:55-4:10pm 

LOCATION:  Hollister Hall 306

DATE	TOPICS	SUPPLEMENTAL MATERIALS
Jan22	Introduction	Readings: David Baraff and Andrew Witkin, Physically Based Modeling, Online SIGGRAPH 2001 Course Notes, 2001. Differential Equation Basics Particle System Dynamics Cloth and Fur Energy Functions An interesting historical perspective: Terzopoulos, D., Pltt, J., Barr, A., Zeltzer, D., Witkin, A., and Blinn, J. 1989. Physically based modeling: past, present, and future. In ACM SIGGRAPH 89 Panel Proceedings (Boston, Massachusetts, United States, July 31 - August 04, 1989). SIGGRAPH '89. ACM Press, New York, NY, 191-209.
Jan24	Review: Tensor Calculus	Discuss Particle System Dynamics Discussed differentiating the following quantities with respect to particle position vectors, p_i: constant, c position, p_j vectors, (p_j-p_k) distances, ||p_j-p_k|| distance powers, ||p_j-p_k||^n dot products, (p_1-p_0)^T (p_3-p_2) cross products Example: hair bending energy derivative, E = k*sin^2(theta/2)  [handout]
Jan29	Particle Systems	Material: David Baraff and Andrew Witkin, Physically Based Modeling, Online SIGGRAPH 2001 Course Notes, 2001. Differential Equation Basics Particle System Dynamics Cloth and Fur Energy Functions Videos: Particle Dreams by Karl Sims, 1988. Other classic videos: Evolved Virtual Creatures by Karl Sims, 1994. Panspermia by Karl Sims, 1990. Pipe Dream, 2001.
Jan31	Basic Integrators	Material: Forward Euler Backward Euler Symplectic Euler (a.k.a. semi-implicit Euler) Midpoint method Verlet method (a.k.a. Störmer's method) Velocity Verlet method
Feb5	Assignment #1 Particle Systems	Assignment #1 Homepage
Feb7 Feb12		No classes (Professor James is away)
Feb5 Feb14	Particle-Based Fluids	Material: Particle interaction force models Gavin Miller, Andrew Pearce, Globular dynamics: A connected particle system for animating viscous fluids, Computers & Graphics, 13(3), 1989, pp. 305-309. (Note there are some obvious equation typos) Smoothed Particle Hydrodynamics (SPH) Matthias Müller, David Charypar, Markus Gross, Particle-based fluid simulation for interactive applications, 2003 ACM SIGGRAPH / Eurographics Symposium on Computer Animation (SCA 2003), August 2003, pp. 154-159.  [Video] Wikipedia Takahiro Harada, Seiichi Koshizuka, Yoichiro Kawaguchi, Smoothed Particle Hydrodynamics on GPUs, Computer Graphics International, pp. 63-70, 2007. B. Solenthaler, R. Pajarola, Predictive-Corrective Incompressible SPH, ACM Transactions on Graphics, 28(3), July 2009, pp. 40:1-40:6. [PDF] [YouTube Video] Granular materials: Nathan Bell, Yizhou Yu, and Peter J. Mucha, Particle-Based Simulation of Granular Materials, ACM SIGGRAPH/ Eurographics Symposium on Computer Animation 2005, [PDF] [Video] Coupling SPH and rigid-body simulations (advanced): N. Akinci, M. Ihmsen, G. Akinci, B. Solenthaler, M. Teschner, Versatile Rigid-Fluid Coupling for Incompressible SPH, ACM Trans. Graph. (SIGGRAPH Proc.), 2012. [PDF] [AVI] Particle advection Isosurface extraction Rendering
Feb19	Implicit Integration; IMEX and other schemes	Material: Blackboard David Baraff and Andrew Witkin, Physically Based Modeling, Online SIGGRAPH 2001 Course Notes, 2001. Implicit Methods (Baraff) Slides Lecture Notes David Baraff, Andrew P. Witkin, Large Steps in Cloth Simulation, Proceedings of SIGGRAPH 98, Computer Graphics Proceedings, Annual Conference Series, July 1998, pp. 43-54. Implicit-Explicit (IMEX) integration schemes: Ascher, Ruuth, Wetton, Implicit-Explicit Methods for Time-Dependent Partial Differential Equations, SIAM J. Num. Anal. 32, pp. 797-823, 1995. Bernhard Eberhardt, Olaf Etzmuß, Michael Hauth, Implicit-Explicit Schemes for Fast Animation with Particle Systems, Computer Animation and Simulation 2000, Proceedings of the EG Workshop in Interlaken, 21-22 August, 2000.  Example: "Going implicit on damping"
Feb21 Feb26 Feb28	Robust Collision Processing	Material: Velocity-level collision resolution Continuous collision detection 2D (point-edge, sphere-sphere), and 3D (point-face, edge-edge) tests Impulse resolution Supporting pin/trajectory constraints Inverse-mass-matrix filtering Penalty forces Rigid cloth zones References: Cloth related: Robert Bridson, Ronald P. Fedkiw, John Anderson, Robust Treatment of Collisions, Contact, and Friction for Cloth Animation, ACM Transactions on Graphics, 21(3), July 2002, pp. 594-603 A. Selle, J. Su, G. Irving, and R. Fedkiw, Robust High-Resolution Cloth Using Parallelism, History-Based Collisions and Accurate Friction, IEEE Transactions on Visualization and Graphics (TVCG), 15(2), 339-350. Robust Treatment of Simultaneous Collisions, David Harmon, Etienne Vouga, Rasmus Tamstorf, Eitan Grinspun, ACM Transactions on Graphics, 27(3), August 2008, pp. 23:1-23:4. (equality-constraint alternative to rigid cloth zones) X. Provot, Collision and self-collision handling in cloth model dedicated to design garment. Graphics Interface, 177–89, 1997. (first introduction of rigid cloth zones) General collision detection: M. Lin and S. Gottschalk, Collision detection between geometric models: A survey, Proc. of IMA Conference on Mathematics of Surfaces, volume 1, pp. 602-608, 1998. P. Jimenez, F. Thomas, and C. Torras, 3D collision detection: A survey, Computers & Graphics, Elsevier, 25(2), pp. 269-285, 2001. Gino Van Den Bergen, Efficient collision detection of complex deformable models using AABB trees, Journal of Graphics Tools, 1998
	Assignment #2 Robust Collision Processing (a.k.a. "The Spaghetti Factory")	Assignment #2 Homepage Video highlights (from previous years): divx (10MB) mov (20MB)
Mar5	Rigid Body Simulation	Material: Rigid body dynamics Position, orientation, linear/angular velocity, momentum, inertia, equations of motion, etc. Euler's equations of angular rigid-body dynamics (in body coordinates) Contact impulses Example: rigid zones for cloth Frictionless contacts: Nonpenetration constraints Velocity-level constraints (see Baraff course notes for accleration-level constraints) Linear Complementarity Problem (LCP) References: David Baraff and Andrew Witkin, Physically Based Modeling, Online SIGGRAPH 2001 Course Notes, 2001. Rigid Body Simulation (slides) (see cloth references for rigid cloth zones)
Mar7 Mar12	Constrained Dynamics	Material: Holonomic constraints, C(p)=0. Example: Bead on a wire Differentiating constraints w.r.t. time. Constraint Jacobian, J Lagrange multipliers, lambda, and constraint forces, J^T lambda Solving for Lagrange multipliers Implicit constraint (and half-explicit) DAE integration schemes References: David Baraff and Andrew Witkin, Physically Based Modeling, Online SIGGRAPH 2001 Course Notes, 2001. Constrained Dynamics (slides) Examples from Cloth Simulation: Rony Goldenthal, David Harmon, Raanan Fattal, Michel Bercovier, Eitan Grinspun, Efficient Simulation of Inextensible Cloth, ACM Transactions on Graphics, 26(3), July 2007, pp. 49:1-49:7.  [ACM Digital Library link] Jonathan M. Kaldor, Doug L. James, Steve Marschner, Simulating Knitted Cloth at the Yarn Level, ACM Transactions on Graphics, 27(3), August 2008, pp. 65:1-65:9.
Mar12 Mar14	Solving Sparse Linear Systems	Material: Poisson's equation model problem Overview of space/time complexity results for Poisson's equation Iterative methods for sparse linear systems Matrix splitting & iterative solution Basic Methods: Jacobi Gauss-Seidel Successive overrelaxation (SOR) Krylov Subspace Methods Basic idea Conjugate Gradient Method Preconditioning Reference: James W. Demmel, Applied Numerical Linear Algebra, SIAM Press, Philadelphia, 1997. (errata) Barrett et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd edition, 1994.
Mar19 Mar21	March Break	No classes
Mar26 Mar28	Rigid Body Contact; Projected Gauss-Seidel Solver	Material: SIAM Review of rigid-body contact: D.E. Stewart, Rigid-body dynamics with friction and impact, SIAM Review, volume 42, 2000. Projected Gauss-Seidel solver (material for assignment): K. Erleben, Stable, robust, and versatile multibody dynamics animation. Ph.D. thesis, Department of Computer Science, University of Copenhagen, Denmark, 2005. [avi movie] K. Erleben, Velocity-based shock propagation for multibody dynamics animation, ACM Trans. Graph. 26, 2, Jun. 2007.  (most similar to Mar17 lecture) Other impulse-based simulation papers: Brian Mirtich, John Canny, Impulse-based Simulation of Rigid Bodies, 1995 Symposium on Interactive 3D Graphics, April 1995, pp. 181-188. Eran Guendelman, Robert Bridson, Ronald P. Fedkiw, Nonconvex Rigid Bodies With Stacking, ACM Transactions on Graphics, 22(3), July 2003, pp. 871-878. [another iterative impulse-based solver]
	Assignment #3 Rigid Body Contact (a.k.a. "The Jelly Bean Factory")	Material: Assignment Webpage Starter code available from CMS
Apr2 Apr4	Fluid Animation	Materials: Jos Stam, Stable Fluids, Proceedings of SIGGRAPH 99, Computer Graphics Proceedings, Annual Conference Series, August 1999, pp. 121-128.  [Slides and notes] Ronald Fedkiw, Jos Stam, Henrik Wann Jensen, Visual Simulation of Smoke, Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, August 2001, pp. 15-22.  (introduces vorticity confinement forces) Bridson, R., Fedkiw, R., and Muller-Fischer, M. 2006. Fluid simulation: SIGGRAPH 2006 course notes, In ACM SIGGRAPH 2006 Courses (Boston, Massachusetts, July 30 - August 03, 2006). SIGGRAPH '06. ACM Press, New York, NY, 1-87.  [Slides, Notes] Robert Bridson, Fluid Simulation for Computer Graphics, A K Peters, 2008:
Apr4	Final Project	Webpage Project proposal (PDF format) [DUE: Thursday April 4]
Apr16	Smoke Control	Materials: Adrien Treuille, Antoine McNamara, Zoran Popović, Jos Stam, Keyframe Control of Smoke Simulations, ACM Transactions on Graphics, 22(3), July 2003, pp. 716-723. [paper] [project] [video]  Graphbib page Antoine McNamara, Adrien Treuille, Zoran Popović, Jos Stam, Fluid control using the adjoint method, ACM Transactions on Graphics, 23(3), August 2004, pp. 449-456. [paper] [project]  Graphbib page Raanan Fattal, Dani Lischinski, Target-driven smoke animation, ACM Transactions on Graphics, 23(3), August 2004, pp. 441-448. [paper] [project]  Graphbib page
Apr25	Fluid-Solid Coupling	Materials: Mark Carlson, Peter J. Mucha, Greg Turk, Rigid Fluid: Animating the Interplay Between Rigid Bodies and Fluid, ACM Transactions on Graphics, 23(3), August 2004, pp. 377-384. [paper] [project] [graphbib] [ACM Digital Library]  (a really simple way to add rigid bodies to a fluid simulation) William V. Baxter III, Ming C. Lin, Haptic Interaction with Fluid Media, Graphics Interface 2004, May 2004, pp. 81-88.  Eran Guendelman, Andrew Selle, Frank Losasso, Ronald Fedkiw, Coupling water and smoke to thin deformable and rigid shells, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California. [project] Nuttapong Chentanez, Tolga G. Goktekin, Bryan E. Feldman, James F. O'Brien, Simultaneous coupling of fluids and deformable bodies, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria. [project] Jeroen Molemaker, Jonathan M. Cohen, Sanjit Patel, Jun-yong Noh, Low Viscosity Flow Simulations for Animation,  Symposium on Computer Animation 2008. [paper] [video (mpeg4)] [youtube] CUDA Car Demo / NVIDIA APEX Turbulence Sneak Peak. Interactive fluid simulation and volume rendering demo written by Jonathan M. Cohen, Sarah Tariq, and Simon Green. [youtube] [CUDA Zone] Robinson-Mosher, A., Shinar, T., Gretarsson, J., Su, J. and Fedkiw, R., Two-way Coupling of Fluids to Rigid and Deformable Solids and Shells, SIGGRAPH 2008, ACM TOG 27, 46.1-46.9 (2008). [Videos: 1, 2, 3]
Apr23	Shape Matching Methods	Material: Matthias Müller, Bruno Heidelberger, Matthias Teschner, Markus Gross, Meshless deformations based on shape matching, ACM Transactions on Graphics, 24(3), August 2005, pp. 471-478. [ACM] [PDF] [AVI] Alec R. Rivers, Doug L. James, FastLSM: Fast Lattice Shape Matching for Robust Real-Time Deformation, ACM Transactions on Graphics, 26(3), July 2007, pp. 82:1-82:6. [ACM] [PDF] Denis Steinemann, Miguel A. Otaduy, Markus Gross, Fast Adaptive Shape Matching Deformations, ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Dublin, July 7-9, 2008. [PDF] [AVI] Matthias Müller and Nuttapong Chentanez. Solid simulation with oriented particles. ACM Trans. Graph. 30, 4, Article 92 (July 2011), 10 pages, 2011. [PDF] [MOVIE]
Apr30	Position Based Fluids + Project Discussion	Material: Miles Macklin and Matthias Müller, Position Based Fluids, SIGGRAPH 2013 (to appear).
Thurs May2	Project Presentations

TOPICS	SUPPLEMENTAL MATERIALS
Deformable Models; and Corotational Finite Elements	Material: Blackboard Basic continuum mechanics Deformation (material and deformed coordinates, deformation gradient) Polar decomposition (rotation, stretch) Strain (Green, linearized Cauchy) Strain Energy Stress and forces Tetrahedral finite elements Corotational finite elements References: Bonet and Wood, "Nonlinear continuum mechanics for finite element mechanics," Cambridge University Press, 1997. M. Müller, M. Gross, Interactive Virtual Materials, in Proceedings of Graphics Interface (GI 2004), pp 239-246, London, Ontario, Canada, May 17-19, 2004. [Video] J. Georgii and R. Westermann, Corotated Finite Elements Made Fast and Stable, VRIPHYS Workshop in Virtual Reality Interactions and Physical Simulations, 2008.  [PDF] [Video]
The Conjugate Gradient Method	Material: Jonathan Richard Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, August 1994.  PDF (516k, 58 pages)
Passive Rigid Motion Control	Material: Ronen Barzel , John F. Hughes , Daniel N. Wood, Plausible motion simulation for computer graphics animation, Proceedings of the Eurographics workshop on Computer animation and simulation '96, p.183-197, December 1996, Poitiers, France . Jovan Popovic, Steven M. Seitz, Michael Erdmann, Zoran Popovic, Andrew P. Witkin, Interactive Manipulation of Rigid Body Simulations, Proceedings of ACM SIGGRAPH 2000, Computer Graphics Proceedings, Annual Conference Series, July 2000, pp. 209-218. Stephen Chenney, D. A. Forsyth, Sampling Plausible Solutions to Multi-Body Constraint Problems, Proceedings of ACM SIGGRAPH 2000, Computer Graphics Proceedings, Annual Conference Series, July 2000, pp. 219-228. Christopher D. Twigg, Doug L. James, Many-Worlds Browsing for Control of Multibody Dynamics, ACM Transactions on Graphics, 26(3), July 2007, pp. 14:1-14:8.  [ACM] [PDF] [Software Demo] Christopher D. Twigg, Doug L. James, Backward Steps in Rigid Body Simulation, ACM Transactions on Graphics, 27(3), August 2008, pp. 25:1-25:10.  [ACM] [PDF] C. O'Sullivan and J. Dingliana, Collisions and Perception, ACM Trans. Graph. 20, 3 (Jul. 2001), 151-168.
"Staggered Projections"	Material: Danny M. Kaufman, Shinjiro Sueda, Doug L. James, Dinesh K. Pai, Staggered Projections for Frictional Contact in Multibody Systems, ACM Transactions on Graphics, 27(5), December 2008, pp. 164:1-164:11. A good reference on convex optimization: Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004. Stanford lecture notes/book [PDF]