Stanford CS448Z Physically Based Animation and Sound

Stanford University, Fall 2015
CS 448Z: Physically Based Animation and Sound

Instructor: Prof. Doug James

Description: Intermediate level, emphasizing physically based simulation techniques for computer animation and synchronized sound synthesis. Topics vary from year to year, but include integrated approaches to visual and auditory simulation of rigid bodies, deformable solids, collision detection and contact resolution, fracture, fluids and gases, and virtual characters. Written assignments and programming projects.

Location	Gates B12, TuTh 3:00PM - 4:20PM
Prerequisites	None. However, prior exposure to computer graphics (CS 148 and CS 248), and/or scientific computing (CS 205), is recommended. Exposure to computer music and/or sound synthesis is helpful.
Textbook	None; lecture notes and research papers assigned as readings will be posted here.
Communication	Piazza: https://piazza.com/stanford/fall2015/cs448z/home
Requirements	Students are expected to attend the lectures and participate in class discussions, and read the supplemental materials.
Assignments	There will be programming assignments, and a final project based on a student-selected topic.
Exams	None.

SYLLABUS

Sound waves and radiation modeling

Sound pressure; acoustic wave equation; Helmholtz equation; boundary conditions for one-way coupling.

Rigid-body dynamics & contact modeling

Animation background; equations of motion; discrete-time integration; collision detection; contact resolution strategies; friction.

Acceleration noise for rigid-body impacts

Rigid-body acceleration; Hertz contact and impact time scale; acceleration noise pulses; precomputation; rendering details.

Modal vibration analysis & synthesis

Simple harmonic oscillator, mass-spring systems; modal vibration of 3D solids; mass and stiffness matrices; meshing and discretization; generalized eigenvalue problem; eigenfrequencies and eigenmodes; eigensolvers for large systems; damping models; time-stepping modal vibrations; integration with rigid-body dynamics engines.

Acoustic transfer for modal vibrations

Transfer function definition; multipole expansions; solvers and precomputation; fast evaluation; rendering details.

Sound propagation modeling and auralization
Implementing a rigid-body sound pipeline

Programming assignments

Fracture

Animation background; rigid-body sound approximation; fracture impulses; ellipsoidal sound proxies; simplified implementation using pre-scored fracture.

Reduced-order dynamics modeling; Application to thin shells

Animation background; nonlinearly coupled modes; subspace integration; implementation details.

Liquids

Animation background; acoustic bubble models; particle-based bubble simulation; acoustic transfer; speed-accuracy trade-offs; simplified implementation.

Turbulence & aeroacoustics

Modeling background; turbulence; Curle's model; precomputation techniques.

Fire

Animation background; combustion noise; low-frequency approximation; sound texture synthesis.

Cloth

Animation background; integration techniques; sound modeling of frictional contact and crumpling events.

Open problems in animation sound
Selected topics (based on student interest)

PROGRAMMING PROJECTS

Warm-up!: Audiovisual code warm-up using using openFrameworks
Real-time rigid-body dynamics with acceleration noise (3 weeks; due Oct 22)
Real-time rigid-body dynamics with modal sound (3 weeks; due Nov 12)
Final project (student choice; final presentation Dec 3; due Dec 11)

SCHEDULE

DATE	TOPIC	SUPPLEMENTAL MATERIALS
TuSep22	Introduction	Slides (PDF)
ThSep24 TuSep29	Sound waves and radiation modeling	Topics: Eqn of continuity; momentum equation; eqsn of linear acoustics; velocity potential; incompressible fluids; pulsating bubble; free-space Green's function; general solution; point sources (monopole, dipole, quadrupole); power; acoustic far-field radiation; Fraunhofer approximation; translating/vibrating sphere References: Whiteboard notes M. S. Howe. (2002). Theory of Vortex Sound. [Online]. Cambridge Texts in Applied Mathematics. (No. 33). Cambridge: Cambridge University Press. Available from: Cambridge Books Online <http://dx.doi.org/10.1017/CBO9780511755491> Chapter 1, Introduction. Additional background reading: 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] See "Appendix A Background" (of the Notes) for a good primer on vector calculus for fluids.
ThOct01	Acceleration noise for rigid-body impacts	Topics: Rigid-body acceleration; Hertz contact and impact time scale; acceleration noise pulses; precomputation; rendering details. References: Whiteboard notes Jeffrey N. Chadwick, Changxi Zheng and Doug L. James, Precomputed Acceleration Noise for Improved Rigid-Body Sound, ACM Transactions on Graphics, August 2012. (PDF - Table 1 typo fixed) Jeffrey N. Chadwick, Changxi Zheng, and Doug L. James, Faster Acceleration Noise for Multibody Animations using Precomputed Soundbanks, ACM/Eurographics Symposium on Computer Animation, July 2012.
ThOct01	Homework 1: Real-time Rigid-Body Dynamics with Acceleration Noise	PDF Due in 3 weeks.
TuOct06	Rigid-body dynamics & contact modeling	Topics: Animation background; equations of motion; discrete-time integration; collision detection; contact resolution strategies. Blackboard notes; focussed on material needed for HW#1. David Baraff and Andrew Witkin, Physically Based Modeling, Online SIGGRAPH 2001 Course Notes, 2001. Rigid Body Simulation (slides) Excellent recent RBD 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.
ThOct08	Acceleration noise for rigid-body impacts (cont'd)
TuOct13	Constraints & rigid-body contact	Topics: Constrained dynamics; post-step stabilization (quaternion example); rigid-body contact problem; equality and inequality constraints; linear complementarity problems. References: David Baraff and Andrew Witkin, Physically Based Modeling, Online SIGGRAPH 2001 Course Notes, 2001. Constrained Dynamics (slides) 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. "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.
ThOct15 TuOct20	Modal vibration analysis & sound synthesis	Topics: Simple harmonic oscillator, mass-spring systems; modal vibration of 3D solids; mass and stiffness matrices; meshing and discretization; generalized eigenvalue problem; eigenfrequencies and eigenmodes; eigensolvers for large systems; damping models; time-stepping modal vibrations; integration with rigid-body dynamics engines. References: A.A. Shabana. Theory of Vibration, Volume II: Discrete and Continuous Systems. Springer-Verlag, New York, NY, first edition, 1990. [Excellent reference on modal vibration analysis fundamentals] 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] Doug L. James and Dinesh K. Pai, DyRT: Dynamic Response Textures for Real Time Deformation Simulation with Graphics Hardware, ACM Transactions on Graphics (ACM SIGGRAPH 2002), 21(3), pp. 582-585, 2002. 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. 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 (see appendix on modal sound synthesis) Changxi Zheng and Doug L. James, Toward High-Quality Modal Contact Sound, ACM Transactions on Graphics (SIGGRAPH 2011), 30(4), August 2011. 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.
ThOct22	Homework 2: Real-time Rigid-Body Dynamics with Modal Sound	PDF Modal model data Due in 3 weeks
TuOct27 ThOct29 TuNov03	Acoustic transfer for modal vibrations	Topics: Transfer function definition; multipole expansions; solvers and precomputation; fast evaluation; rendering details. References: Handout: D. James, Course notes on "Acoustic Transfer" (unpublished) Associated Legendre polynomials in terms of angles Spherical harmonics Doug L. James, Jernej Barbic 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. (appendix on acoustic transfer computation) R.D. Ciskowski and C.A. Brebbia. Boundary element methods in acoustics. Springer, 1991. N.A. Gumerov and R. Duraiswami. Fast multipole methods for the Helmholtz equation in three dimensions. Elsevier Science, 2004. F. Ihlenburg. Finite element analysis of acoustic scattering, volume 132. Springer Verlag, 1998. M. Ochmann. The source simulation technique for acoustic radiation problems. Acta Acustica united with Acustica, 81(6):512–527, 1995. M. Ochmann. The full-field equations for acoustic radiation and scattering. The Journal of the Acoustical Society of America, 105:2574, 1999.
TuNov03 ThNov05 TuNov10	Fracture	References: 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. Also see other papers on acceleration noise for fracture sound results: Jeffrey N. Chadwick, Changxi Zheng and Doug L. James, Precomputed Acceleration Noise for Improved Rigid-Body Sound, ACM Transactions on Graphics, August 2012. (PDF - Table 1 typo fixed) Jeffrey N. Chadwick, Changxi Zheng, and Doug L. James, Faster Acceleration Noise for Multibody Animations using Precomputed Soundbanks, ACM/Eurographics Symposium on Computer Animation, July 2012. 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.
ThNov12 TuNov17	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. 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]
TuNov17	Liquid Sounds	Materials: Changxi Zheng and Doug L. James, Harmonic Fluids, ACM Transaction on Graphics, 28(3), July 2009, pp. 37:1-37:12.
ThNov19	Turbulence & Fire Sound	Materials: 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] M. S. Howe. (2002). Theory of Vortex Sound. [Online]. Cambridge Texts in Applied Mathematics. (No. 33). Cambridge: Cambridge University Press. Available from: Cambridge Books Online <http://dx.doi.org/10.1017/CBO9780511755491> Y.Dobashi, T. Yamamoto, T. Nishita, Synthesizing Sound from Turbulent Field using Sound Textures for Interactive Fluid Simulation, Computer Graphics Forum (Proc. EUROGRAPHICS 2004), Vol. 23, No. 3, pp. 539-546, 2004. [project page] ` Jeffrey Chadwick and Doug L. James, Animating Fire with Sound, ACM Transactions on Graphics, 30(4), August 2011.
TuNov24 ThNov26	Thanksgiving Recess (no class)
TuDec01	Project working session	In-class working session. Come prepared to discuss your progress and problems with Prof. James.
ThDec03	Project presentations & discussions
FriDec11	Final projects due	Last day to submit your final project (HW3) on Canvas.