CS 5643 Physically Based Animation (Spring 2010)

CS 5643: Physically Based Animation for Computer Graphics
Spring 2010

PROFESSOR: Doug James

TA: Steven An

HELP SESSIONS AND OFFICE HOURS: 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 (first class is Mon Jan 25)

LOCATION: Hollister Hall 368 Thurston Hall 203

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

PROGRAMMING ASSIGNMENTS (Tentative):

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

PREVIOUS COURSE OFFERING:

SCHEDULE (Spring 2010)

DATE	TOPICS	SUPPLEMENTAL MATERIALS
Jan25	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.
Jan27	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]
	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.
Feb1	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
Feb3	Assignment #1 Particle Systems	Assignment #1 Homepage Video highlights:
Feb8	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. 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] Particle advection Isosurface extraction Rendering
Feb10	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"
Feb15 Feb17	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]

Feb22 Feb24 Mar01	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. 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: divx (10MB) mov (20MB)
Mar03	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.
Mar08 Mar15	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.
Mar15 Mar17	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)
Mar17 Mar29 Mar31	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
Mar22 Mar24	March Break
Apr5 Apr7	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:
Apr7	Final Project	Webpage Project proposal (PDF format) [DUE: Wednesday April 7]
Apr12	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
Apr14	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]
Apr19	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]
Apr21 Apr26	No Classes
Apr28	Fracture	Material:
May3 May5	Project Presentations

SUPPLEMENTAL MATERIAL (from Spring 2009)

TOPICS	SUPPLEMENTAL MATERIALS
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]