CS 5643 Physically Based Animation (Spring 2009)

CS 5643: Physically Based Animation for Computer Graphics
Spring 2009

PROFESSOR: Doug James

TA: Changxi Zheng

HELP SESSIONS AND OFFICE HOURS: TBA (+after class, and by appointment)

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: MW 2:55-4:10pm

LOCATION: Phillips Hall (PHL) 219

GRADE OPTION: letter or S/U

NUMBER OF CREDITS: 4

PREREQUISITES: Permission of the instructor, or COM 322 (Intro to Scientific Computing), or COM S 465 (Computer Graphics I). Students from CIS 300 (Intro to Computer Game Design) are strongly encouraged. Java applet programming in assignments.

EXAMS: None (Grade based on assignments and project)

ACADEMIC POLICIES

APPROACH:

Just do it!
Hands-on, fun approach
Build confidence and understanding using simpler 2D physics
Focus on algorithms and implementation---equations are a given
Biweekly Java applet projects
Lectures: ½ background & ½ survey
Final project of your choosing (20% grade)

PROGRAMMING ASSIGNMENTS:

Mass-Spring Particle Systems (20%)
Robust Collision Processing (a.k.a. "The Spaghetti Factory") (20%)
Rigid Body Dynamics and Contact (20%)
Fluid Control (20%)
Final Project of Your Choosing (20%)

PREVIOUS COURSE OFFERING:

Spring 2007: COM S 567: Physically Based Animation for Computer Graphics

SCHEDULE

DATE	TOPICS	SUPPLEMENTAL MATERIALS
Jan21	Introduction	Readings: David Baraff and Andrew Witkin, Physically Based Modeling, Online SIGGRAPH 2001 Course Notes, 2001. Differential Equation Basics Particle System Dynamics 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.
Jan26	Review: Tensor Calculus	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]
Jan28	Particle Systems	Material: Discussed Assignment #1 Particle Systems Symplectic Euler integrator (a.k.a. semi-implicit Euler) 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. 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
Due Sun Feb 15	Assignment #1 Mass-Spring Particle Systems	Link to assignment webpage
Feb02	Symbolic Code Generation and Differentiation	Material: Slides (PDF) Foreshadowing: deformation mapping deformation gradient Polar decomposition Newton-Schulz iteration
Feb04	Implicit Integration; IMEX and other schemes	Material: David Baraff and Andrew Witkin, Physically Based Modeling, Online SIGGRAPH 2001 Course Notes, 2001. Implicit Methods (Baraff) Slides Lecture Notes 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"
Feb09	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.
Feb11 Feb16 Feb18	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: 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. 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. 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) 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)
Due Sun Mar 8	Assignment #2 Robust Collision Processing (a.k.a. "The Spaghetti Factory")	Material: Assignment Webpage See Spaghetti Factory contest results Starter code available from CMS
Feb23	Rigid Body Simulation	Material: Rigid body concepts (position, orientation, linear/angular velocity, momentum, inertia, etc.) 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)
Feb25 Mar02	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) 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]
Mar02 Mar04	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)
Mar09	Rigid Body Contact; Projected Gauss-Seidel Solver	Material: 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 Mar09 lecture)
Mar11	Assignment #3 Rigid Body Contact (a.k.a. "The Jelly Bean Factory")	Material: Assignment Webpage See "Jelly Bean Factory" contest results Starter code available from CMS (soon)
Mar16 Mar18	March Break
Mar23	Corotational Finite Elements	Material: 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]
Mar25	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]
Mar30 Apr06	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.
Apr1	Assignment Q&A Session	Material: Assignment Webpage
	Final Project	Webpage
Apr08 Apr13	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:
Apr15	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
Apr20	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]
Apr22 Apr27	"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]
Apr29	Project Presentations