CS 5643: Physically Based Animation for Computer Graphics
Spring 2015

PROFESSOR:  Doug James

TA: Timothy Langlois (Office hours: Mon, 6-7pm, Gates G11)

HELP SESSIONS AND OFFICE HOURS:  After class, and by appointment. Please also ask questions on the Piazza forum.

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:  Gates G01

SCHEDULE (previous years: Spring 2013, Spring 2014)
DATE
TOPICS
SUPPLEMENTAL MATERIALS
ThJan22 Introduction

• An interesting historical perspective:
• Terzopoulos, D., Platt, J., Barr, A., Zeltzer, D., Witkin, A., and Blinn, J. 1989. In ACM SIGGRAPH 89 Panel Proceedings (Boston, Massachusetts, United States, July 31 - August 04, 1989). SIGGRAPH '89. ACM Press, New York, NY, 191-209.
TuJan27 Particle Systems
Material:
ThJan29
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
• functions of distance, W(||p_j-p_k||)
• 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]
Other topics:
TuFeb03
ThFeb05
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)
• Post-step projection schemes
• Position- vs velocity-based corrections
• Applications: Mechanical linkages, inextensibility constraints, incompressible flow, contact constraints
Written Homework (Due Thurs Feb 12)
References:
[Advanced] References for Differential-Algebraic Equations (DAEs):
TuFeb10
ThFeb12
Particle-based Fluids

Material:
ThFeb12 Assignment #1:
Position Based Fluids

Project webpage. Starter code is on CMS.
TuFeb17
Winter Break
No class
ThFeb19
Basic Integrators

Material:
• Forward Euler
• Backward Euler
• Symplectic Euler (a.k.a. semi-implicit Euler); symplectic Euler adjoint
• E. Hairer, C. Lubich, and G. Wanner. Geometric Numerical Integration. Structure-Preserving Algorithms for Ordinary Differential Equations., Springer Series in Comput. Mathematics, Springer-Verlag, volume 31, 2002.
• Midpoint method
• Verlet method (a.k.a. Störmer's method)
• Stability analysis of forward & backward Euler schemes on test problem
TuFeb24
ThFeb26
Implicit Integration;
IMEX and other schemes

Material:
ThFeb26
TuMar03
ThMar05
Position Based Dynamics,
and other relaxation-based dynamics

References:

Assignment #2:
Position Based Dynamics

Project webpage. Starter code on CMS.
ThMar05
TuMar10
Robust Collision Processing
Material:
• Motivation: cloth and hair animation
• Continuous collision detection
• 2D/3D sphere-sphere, 2D (point-edge), and 3D (point-face, edge-edge) tests
• Velocity-level collision resolution; collision impulses
• Supporting pin/trajectory constraints
• Inverse-mass-matrix filtering
• Penalty forces
• Rigid cloth zones
• Untangling cloth
References:
TuMar10
ThMar19
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 damping"
• Frictionless contacts:
• Nonpenetration constraints
• Velocity-level constraints (see Baraff course notes for acceleration-level constraints)
• Linear Complementarity Problem (LCP)
References:
• David Baraff and Andrew Witkin, Physically Based Modeling, Online SIGGRAPH 2001 Course Notes, 2001.
• (see cloth references for rigid cloth zones)
ThMar12
TuMar17
Rigid Body Sound
Guest Lecturer: Tim Langlois

Material:
• Modal sound synthesis
• Precomputed acoustic transfer
• Precomputed acceleration noise
• Compression techniques
References:

ThMar19
...
Rigid Body Contact:
Impulse- and Constraint-based Methods

Material:
TuMar24 Final Project Idea Blitz!
A whirlwind discussion of ideas and paper references to inspire your final project choice.
ThMar26
Project working class

Working meeting to discuss A2-Part II (due FriMar27) and final project ideas with Tim Langlois (TA).
• No lecture.
• Prof James away--chairing SIGGRAPH 2015 Technical Papers committee meeting in Chicago.

TuApr07
ThApr09
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]
Material:
• Jonathan Richard Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, August 1994.  PDF (516k, 58 pages)
• G.H. Golub and C.F. Van Loan, Matrix Computations, 4th Edition, Johns Hopkins University Press, 2013.
TuApr14
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. [ACM] [PDF] [MOVIE]
ThApr16
Fracture Animation

Material:

TuApr21
Controlling Smoke, Water, & Fire
Materials:
• Adrien Treuille, Antoine McNamara, Zoran Popović, Jos Stam, ACM Transactions on Graphics, 22(3), July 2003, pp. 716-723. [paper] [project] [videoGraphbib page
• Antoine McNamara, Adrien Treuille, Zoran Popović, Jos Stam, ACM Transactions on Graphics, 23(3), August 2004, pp. 449-456. [paper] [projectGraphbib page
• Raanan Fattal, Dani Lischinski, ACM Transactions on Graphics, 23(3), August 2004, pp. 441-448. [paper] [projectGraphbib page
• N. Rasmussen, D. Enright, D. Nguyen, S. Marino, N. Sumner, W. Geiger, S. Hoon, and R. Fedkiw. 2004. Directable photorealistic liquids. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation (SCA '04). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 193-202.
• Lin Shi and Yizhou Yu. 2005. Taming liquids for rapidly changing targets. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation (SCA '05). ACM, New York, NY, USA, 229-236.
• N Thürey, R Keiser, M Pauly, U Rüde, Detail-preserving fluid control, Graphical Models, 2009. [Video]
• Christopher Horvath and Willi Geiger. 2009. Directable, high-resolution simulation of fire on the GPU. In ACM SIGGRAPH 2009 papers (SIGGRAPH '09), Hugues Hoppe (Ed.). ACM, New York, NY, USA, , Article 41 , 8 pages.
ThApr23 Noise & Turbulence Modeling

Materials:
TuApr28 Animation Sound

Material:
ThApr30
TuMay05
Project Presentations

Two-day extended in-class slide presentation period.
• Give overview of animation problem
• Demo preliminary results
• Final project submitted on CMS by May 18

Presentation schedule (5 minute talks, randomized order):

Thursday, April 30 Speakers:

1. Benton, Brandon
2. Wu, Rundong
3. Zhang, Zechen
4. Rogers, Machenzie
5. Jiang, Mingde
6. Zhao, Zeqiang
7. Wang, Ning
8. Gross, Joel & Cytryn, Jeremy
9. Hakobyan, Gagik
10. Wu, Scott
11. Westura, Travis

Tuesday, May 5 Speakers:

1. Bern, Noah
2. Wang, Jui-hsien
3. Veizaga, Einar & Henderson, Kylar
5. Peele, Bryan
6. Qian, Yuhao Collin
7. Evans, Bryce & Paris, Youenn
8. Sperling, Daniel
9. Duffany, Brandon
10. Dupre, Guillaume

SUPPLEMENTAL MATERIAL

 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, "" 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]

 Assignment #1 Particle Systems Assignment #1 Homepage Assignment #2 Robust Collision Processing (a.k.a. "The Spaghetti Factory") Assignment #2 Homepage Video highlights (from previous years): divx (10MB) mov (20MB) 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. Assignment #3 Rigid Body Contact (a.k.a. "The Jelly Bean Factory") Material: Starter code available from CMS 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] Passive Rigid Motion Control Material: Simulation accuracy vs plausibility Exploiting errors for control Random sampling methods Optimization based methods Interactive artist-driven methods References: 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.