CS 5643 Physically Based Animation

CS 5643: Physically Based Animation for Computer Graphics
Spring 2015

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	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., Platt, 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.
TuJan27	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 (preview of energy function usage) Videos: Particle Dreams by Karl Sims, 1988.
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 = ksin^2(theta/2) [handout] Other topics:* Numerical differentiation (less appealing in higher dimensions) Automatic and symbolic differentiation (Wiki) A local Mitsuba autodiff implementation Symbolic derivatives with optimized codegen (Maple) Slides Timothy Langlois's writeup on Automatic Differentiation of Moving Least Squares [Code example] Other examples
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: 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. [Advanced] References for Differential-Algebraic Equations (DAEs): U.M. Ascher and L.R. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, SIAM. E. Hairer and G. Wanner, Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems, 2nd edition, Springer, 1996. (See Chapter VII.(1-2) Differential-Algebraic Equations of Higher Index)
TuFeb10 ThFeb12	Particle-based Fluids	Material: 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] Miles Macklin and Matthias Müller. Position Based Fluids. ACM Trans. Graph. 32, 4, Article 104 (July 2013), 12 pages. (other videos) Liu, G. Gui-Rong, and M. B. Liu. Smoothed particle hydrodynamics: a meshfree particle method. World Scientific, 2003. 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] SIGGRAPH fluids course: [SPH pages (pp. 83-86)] 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. [Book format] Granular materials: ../2014sp/images/thumb_symplecticEuler.jpgNathan 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] Isosurface extraction Rendering
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) Velocity Verlet method Stability analysis of forward & backward Euler schemes on test problem
TuFeb24 ThFeb26	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"
ThFeb26 TuMar03 ThMar05	Position Based Dynamics, and other relaxation-based dynamics	References: M. Müller, B. Heidelberger, M. Hennix, J. Ratcliff, Position Based Dynamics, Proceedings of Virtual Reality Interactions and Physical Simulations (VRIPhys), pp 71-80, Madrid, November 6-7 2006, Best Paper Award, PDF, (video), (slides) Jos Stam, Nucleus: Towards a Unified Dynamics Solver for Computer Graphics, 2009 Conference Proceedings: IEEE International Conference on Computer-Aided Design and Computer Graphics, pp. 1-11, 2009. (related talk) T. Jakobsen, Advanced Character Physics, Game Developer Conference, 2001. Miles Macklin, Matthias Müller, Nuttapong Chentanez, and Tae-Yong Kim. 2014. Unified particle physics for real-time applications. ACM Trans. Graph. 33, 4, Article 153 (July 2014), 12 pages. [ACM link] Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective dynamics: fusing constraint projections for fast simulation. ACM Trans. Graph. 33, 4, Article 154 (July 2014), 11 pages. [ACM link]
	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: 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. T. Brochu, E. Edwards, and R. Bridson, Efficient Geometrically Exact Continuous Collision Detection, Proc. SIGGRAPH 2012. (open-source code, project) (method to avoid the nonrobustness of "cubic solver approach" for 3D cloth) 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 Untangling cloth interpenetrations: David Baraff, Andrew Witkin, and Michael Kass. 2003. Untangling Cloth. ACM Trans. Graph. 22, 3 (July 2003), 862-870. Pascal Volino , Nadia Magnenat-Thalmann, Resolving surface collisions through intersection contour minimization, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
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. Rigid Body Simulation (slides) (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: K. van den Doel and D. K. Pai, The Sounds of Physical Shapes, Presence: Teleoperators and Virtual Environments, 7:4, The MIT Press, 1998. pp. 382--395. Kees van den Doel, Paul G. Kry, Dinesh K. Pai, FoleyAutomatic: Physically-Based Sound Effects for Interactive Simulation and Animation, Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, August 2001, pp. 537-544. [Video] Dinesh K. Pai, Kees van den Doel, Doug L. James, Jochen Lang, John E. Lloyd, Joshua L. Richmond, Som H. Yau, Scanning Physical Interaction Behavior of 3D Objects, Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, August 2001, pp. 87-96. [Video] James F. O'Brien, Perry R. Cook, Georg Essl, Synthesizing Sounds From Physically Based Motion, Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, August 2001, pp. 529-536. Perry R. Cook, Sound Production and Modeling, IEEE Computer Graphics & Applications, 22(4), July-August 2002, pp. 23-27. James F. O'Brien, Chen Shen, and Christine M. Gatchalian. Synthesizing sounds from rigid-body simulations. In The ACM SIGGRAPH 2002 Symposium on Computer Animation, pages 175–181. ACM Press, July 2002. Doug L. James, Jernej Barbić and Dinesh K. Pai, Precomputed Acoustic Transfer: Output-sensitive, accurate sound generation for geometrically complex vibration sources, ACM Transactions on Graphics, 25(3), pp. 987-995, July 2006, pp. 987-995. Changxi Zheng and Doug L. James, Rigid-Body Fracture Sound with Precomputed Soundbanks, ACM Transactions on Graphics (SIGGRAPH 2010), 29(3), July 2010, pp. 69:1-69:13. Changxi Zheng and Doug L. James, Precomputed Acceleration Noise for Improved Rigid-Body Sound, ACM Transactions on Graphics, August 2012. Steven S. An , Doug L. James, and Steve Marschner, Motion-driven Concatenative Synthesis of Cloth Sounds, ACM Transactions on Graphics, August 2012. Timothy R. Langlois, Steven S. An, Kelvin K. Jin, and Doug L. James. Eigenmode Compression for Modal Sound Models. ACM Transactions on Graphics (SIGGRAPH 2014). 33(4), August, 2014.
ThMar19 ...	Rigid Body Contact: Impulse- and Constraint-based Methods	Material: General discussion of contact methods, with specific discussions of typical impulse-based [Guendelman et al. 2003] and constraint-based [Erleben et al. 2007] solvers. Excellent recent review: Jan Bender, Kenny Erleben and Jeff Trinkle, Interactive Simulation of Rigid Body Dynamics in Computer Graphics, Computer Graphics Forum, Volume 33, Issue 1, pages 246–270, February 2014, DOI: 10.1111/cgf.12272. Impulse-based contact solvers: 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. [an iterative impulse-based solver] Projected Gauss-Seidel solver: 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. Projected Jacobi solver: Richard Tonge, Feodor Benevolenski, Andrey Voroshilov, Mass Splitting for Jitter-Free Parallel Rigid Body Simulation, ACM Trans. Graphics (SIGGRAPH 2012), 31(4), 2012. SIAM Review of rigid-body contact: D.E. Stewart, Rigid-body dynamics with friction and impact, SIAM Review, volume 42, 2000. "Staggered Projections" method: 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]
TuMar24	Final Project Idea Blitz!	A whirlwind discussion of ideas and paper references to inspire your final project choice. Project proposal (PDF format) [DUE: Thursday, April 10, 2015]
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] Robert Bridson, Fluid Simulation for Computer Graphics, A K Peters, 2008:
Reading	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) 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: Demetri Terzopoulos, Kurt Fleischer, Modeling Inelastic Deformation: Viscoelasticity, Plasticity, Fracture,Computer Graphics (Proceedings of SIGGRAPH 88), August 1988, pp. 269-278. James F. O'Brien, Jessica K. Hodgins, Graphical Modeling and Animation of Brittle Fracture, Proceedings of SIGGRAPH 99, Computer Graphics Proceedings, Annual Conference Series, August 1999, pp. 137-146. James F. O'Brien, Adam W. Bargteil, Jessica K. Hodgins, Graphical Modeling and Animation of Ductile Fracture, ACM Transactions on Graphics, 21(3), July 2002, pp. 291-294. Neil Molino, Zhaosheng Bao, Ron Fedkiw, A virtual node algorithm for changing mesh topology during simulation, ACM Transactions on Graphics, 23(3), August 2004, pp. 385-392. 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) Mark Pauly, Richard Keiser, Bart Adams, Philip Dutré, Markus Gross, Leonidas J. Guibas, Meshless animation of fracturing solids, ACM Transactions on Graphics, 24(3), August 2005, pp. 957-964. [ACM] (Video) [PDF] Hayley N. Iben, James F. O'Brien, Generating Surface Crack Patterns, 2006 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, September 2006, pp. 177-186. Denis Steinemann, Miguel A. Otaduy, Markus Gross, Fast Arbitrary Splitting of Deforming Objects, 2006 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, September 2006, pp. 63-72. (Video) Bao, Z., Hong, J.-M., Teran, J. and Fedkiw, R., Fracturing Rigid Materials, IEEE TVCG 13, 370-378 (2007). Eftychios Sifakis, Kevin G. Der, Ronald Fedkiw, Arbitrary Cutting of Deformable Tetrahedralized Objects,2007 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, August 2007, pp. 73-80. Eric G. Parker and James F. O'Brien, Real-Time Deformation and Fracture in a Game Environment, In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pages 156–166, August 2009. Su, J., Schroeder, C. and Fedkiw, R., Energy Stability and Fracture for Frame Rate Rigid Body Simulations,ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), edited by Eitan Grinspun and Jessica Hodgins, pp. 155-164 (2009). Changxi Zheng, Doug L. James, Rigid-Body Fracture Sound with Precomputed Soundbanks, ACM Transactions on Graphics, 29(4), July 2010, pp. 69:1-69:13. M Müller, N Chentanez, TY Kim, Real time dynamic fracture with volumetric approximate convex decompositions, ACM Transactions on Graphics (TOG), 2013. [Video] Oleksiy Busaryev, Tamal K. Dey, and Huamin Wang. 2013. Adaptive fracture simulation of multi-layered thin plates. ACM Trans. Graph. 32, 4, Article 52 (July 2013). [Video] Zhili Chen, Miaojun Yao, Renguo Feng, and Huamin Wang. 2014. Physics-inspired adaptive fracture refinement. ACM Trans. Graph. 33, 4, Article 113 (July 2014). [ACM] A recent review of fracture in graphics: L Muguercia, C Bosch, G Patow, Fracture modeling in computer graphics, Computers & Graphics, 2014.
TuApr21	Controlling Smoke, Water, & Fire	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 Related programming assignment from previous class. 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: Ken Perlin and Eric Hoffert, Hypertexture, 1989 Computer Graphics (proceedings of ACM SIGGRAPH Conference), Vol. 22, No. 3. (Ken's write-up) Jos Stam and Eugene Fiume. 1993. Turbulent wind fields for gaseous phenomena. In Proceedings of the 20th annual conference on Computer graphics and interactive techniques (SIGGRAPH '93). ACM, New York, NY, USA, 369-376. 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) Jerry Tessendorf, Simulating Ocean Water, SIGGRAPH course notes, 2002. [Slides 2004] Frequency-domain methods commonly used for water wave simulation, e.g., NVIDIA WaveWorks. F. Neyret, Advected textures, In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim. (2003), pp. 147–153. Andrew Selle, Nick Rasmussen, Ronald Fedkiw, A vortex particle method for smoke, water and explosions, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005. Robert L. Cook and Tony DeRose. 2005. Wavelet noise. ACM Trans. Graph. 24, 3 (July 2005), 803-811. [ACM] Alexander Goldberg, Matthias Zwicker, Frédo Durand, Anisotropic noise, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008. Robert Bridson, Jim Houriham, Marcus Nordenstam, Curl-noise for procedural fluid flow, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007. (movie and public domain example code available.) Theodore Kim, Nils Thürey, Doug James, Markus Gross, Wavelet turbulence for fluid simulation, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008. [ACM] (code available) H. Schechter, R. Bridson, Evolving sub-grid turbulence for smoke animation, Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, July 07-09, 2008, Dublin, Ireland. [Movie] Rahul Narain, Jason Sewall, Mark Carlson, Ming C. Lin, Fast animation of turbulence using energy transport and procedural synthesis, ACM Transactions on Graphics (TOG), v.27 n.5, December 2008. Tobias Pfaff, Nils Thürey, Andrew Selle, and Markus Gross, Synthetic Turbulence using Artificial Boundary Layers, ACM SIGGRAPH Asia 2009 Papers, ACM Press, 2009.
TuApr28	Animation Sound	Material: K. van den Doel and D. K. Pai, The Sounds of Physical Shapes, Presence: Teleoperators and Virtual Environments, 7:4, The MIT Press, 1998. pp. 382--395. Kees van den Doel, Paul G. Kry, Dinesh K. Pai, FoleyAutomatic: Physically-Based Sound Effects for Interactive Simulation and Animation, Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, August 2001, pp. 537-544. [Video] Dinesh K. Pai, Kees van den Doel, Doug L. James, Jochen Lang, John E. Lloyd, Joshua L. Richmond, Som H. Yau, Scanning Physical Interaction Behavior of 3D Objects, Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, August 2001, pp. 87-96. [Video] James F. O'Brien, Perry R. Cook, Georg Essl, Synthesizing Sounds From Physically Based Motion, Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, August 2001, pp. 529-536. Perry R. Cook, Sound Production and Modeling, IEEE Computer Graphics & Applications, 22(4), July-August 2002, pp. 23-27. James F. O'Brien, Chen Shen, and Christine M. Gatchalian. Synthesizing sounds from rigid-body simulations. In The ACM SIGGRAPH 2002 Symposium on Computer Animation, pages 175–181. ACM Press, July 2002. Yoshinori Dobashi, Tsuyoshi Yamamoto, Tomoyuki Nishita, Real-Time Rendering of Aerodynamic Sound Using Sound Textures Based on Computational Fluid Dynamics, ACM Transactions on Graphics, 22(3), July 2003, pp. 732-740. [project page] Doug L. James, Jernej Barbić and Dinesh K. Pai, Precomputed Acoustic Transfer: Output-sensitive, accurate sound generation for geometrically complex vibration sources, ACM Transactions on Graphics, 25(3), pp. 987-995, July 2006, pp. 987-995. Changxi Zheng and Doug L. James, Harmonic Fluids, ACM Transaction on Graphics (SIGGRAPH 2009), 28(3), August 2009, pp. 37:1-37:12. Jeffrey Chadwick, Steven An, and Doug L. James, Harmonic Shells: A Practical Nonlinear Sound Model for Near-Rigid Thin Shells, ACM Transactions on Graphics (SIGGRAPH ASIA Conference Proceedings), 28(5), December 2009, pp. 119:1-119:10. Changxi Zheng and Doug L. James, Rigid-Body Fracture Sound with Precomputed Soundbanks, ACM Transactions on Graphics (SIGGRAPH 2010), 29(3), July 2010, pp. 69:1-69:13. Jeffrey Chadwick and Doug L. James, Animating Fire with Sound, ACM Transactions on Graphics, 30(4), August 2011. Jeffrey N. Chadwick, Changxi Zheng and Doug L. James, Precomputed Acceleration Noise for Improved Rigid-Body Sound, ACM Transactions on Graphics, August 2012. Steven S. An , Doug L. James, and Steve Marschner, Motion-driven Concatenative Synthesis of Cloth Sounds, ACM Transactions on Graphics, August 2012. Timothy R. Langlois and Doug L. James, Inverse-Foley Animation: Synchronizing rigid-body motions to sound, ACM Transactions on Graphics (SIGGRAPH 2014), 33(4), August 2014.
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: Benton, Brandon Wu, Rundong Zhang, Zechen Rogers, Machenzie Jiang, Mingde Zhao, Zeqiang Wang, Ning Gross, Joel & Cytryn, Jeremy Hakobyan, Gagik Wu, Scott Westura, Travis Tuesday, May 5 Speakers: Bern, Noah Wang, Jui-hsien Veizaga, Einar & Henderson, Kylar Adegunloye, Olufemi Peele, Bryan Qian, Yuhao Collin Evans, Bryce & Paris, Youenn Sperling, Daniel Duffany, Brandon 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, "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]

	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: Assignment Webpage 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.