DATE

TOPICS

SUPPLEMENTAL
MATERIALS

ThJan23 
Introduction

Readings:
 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, 191209.

TuJan28 
Particle Systems

Material:

ThJan30

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 halfexplicit) DAE
integration schemes)
 Poststep projection schemes
 Position vs velocitybased corrections
 Applications: Mechanical linkages, inextensibility
constraints, incompressible flow, contact constraints
References:
 David Baraff and Andrew Witkin, Physically
Based
Modeling, Online
SIGGRAPH
2001 Course Notes, 2001.
 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:149: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:165:9.
[Advanced] References for DifferentialAlgebraic
Equations (DAEs):

TuFeb04

Particlebased Fluids

Material:
 Smoothed Particle Hydrodynamics (SPH)
 Liu, G. GuiRong, and M. B. Liu. Smoothed
particle hydrodynamics: a meshfree particle
method. World Scientific,
2003.
 Matthias Müller, David Charypar,
Markus Gross, Particlebased
fluid simulation for interactive applications,
2003
ACM SIGGRAPH / Eurographics Symposium on Computer
Animation (SCA 2003), August
2003, pp. 154159. [Video]
 Wikipedia
 Takahiro Harada, Seiichi Koshizuka, Yoichiro
Kawaguchi, Smoothed Particle
Hydrodynamics on GPUs, Computer Graphics
International, pp. 6370, 2007.
 B. Solenthaler, R. Pajarola, PredictiveCorrective
Incompressible
SPH, ACM Transactions on Graphics,
28(3), July 2009,
pp. 40:140:6. [PDF]
[YouTube
Video]
 Miles
Macklin and Matthias Müller. Position
Based Fluids. ACM Trans. Graph. 32, 4,
Article 104 (July 2013), 12 pages. (other
videos)
 SIGGRAPH fluids course: [SPH
pages (pp. 8386)]
 Bridson, R., Fedkiw, R., and MullerFischer, 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, 187. [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, ParticleBased Simulation of
Granular Materials, ACM SIGGRAPH/
Eurographics Symposium on Computer Animation 2005,
[PDF]
[Video]
 Coupling SPH and rigidbody simulations (advanced):
 N. Akinci, M. Ihmsen, G. Akinci, B. Solenthaler, M.
Teschner, Versatile
RigidFluid Coupling for Incompressible SPH,
ACM Trans. Graph. (SIGGRAPH Proc.), 2012. [PDF]
[AVI]
 Particle advection
 Isosurface extraction
 Rendering

ThFeb06

No Class

Prof. James is away at NYU.
Read: ([Müller
et al. 2003], SPH
course notes), and Position
Based Fluids.

TuFeb11

Particlebased
Fluids (cont'd)


ThFeb13 
Assignment #1:
Position Based Fluids

Project webpage.
Starter code is on CMS. 
TuFeb18

Winter Break

No class

ThFeb20

Basic Integrators

Material:
 Forward
Euler
 Backward
Euler
 Symplectic
Euler (a.k.a. semiimplicit Euler); symplectic
Euler adjoint
 E. Hairer, C. Lubich, and G. Wanner.
Geometric Numerical Integration.
StructurePreserving Algorithms for Ordinary
Differential Equations., Springer Series in Comput.
Mathematics, SpringerVerlag, volume 31, 2002.
 Midpoint
method
 Verlet
method (a.k.a. Störmer's method)
 Stability analysis of forward & backward Euler
schemes on test problem


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)
 David
Baraff, Andrew P. Witkin, Large
Steps
in
Cloth Simulation, Proceedings of SIGGRAPH
98, Computer Graphics Proceedings, Annual Conference
Series, July 1998, pp. 4354.
 ImplicitExplicit (IMEX)
integration schemes:
 Ascher,
Ruuth, Wetton, ImplicitExplicit
Methods for TimeDependent Partial
Differential Equations, SIAM J.
Num. Anal. 32, pp. 797823, 1995.
 Bernhard
Eberhardt, Olaf Etzmuß, Michael Hauth, ImplicitExplicit
Schemes for Fast Animation with Particle
Systems, Computer Animation and
Simulation 2000, Proceedings of the EG Workshop in
Interlaken, 2122 August, 2000.
 Example:
"Going implicit on damping"

TuFeb25

Review:
Tensor Calculus

Discussed differentiating
the following quantities with respect to particle position
vectors, p_i:
 constant, c
 position, p_j
 vectors, (p_jp_k)
 distances, p_jp_k
 distance powers, p_jp_k^n
 functions of distance, W(p_jp_k)
 dot products, (p_1p_0)^T (p_3p_2)
 cross products
 Example: hair bending energy derivative, E =
k*sin^2(theta/2) [handout]
Other topics:

ThFeb27
TuMar04

Position 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 7180, Madrid, November
67 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 ComputerAided Design and
Computer Graphics, pp. 111, 2009. (related talk)
 T. Jakobsen, Advanced
Character Physics, Game Developer
Conference, 2001.

ThMar06

Assignment #2:
Position Based Dynamics

Project webpage.
Starter code on CMS.

ThMar06
TuMar11
ThMar13

Robust Collision Processing

Material:
 Motivation:
cloth and hair animation
 Continuous
collision detection
 2D/3D
spheresphere, 2D (pointedge), and 3D (pointface,
edgeedge) tests
 Velocitylevel
collision resolution; collision impulses
 Supporting
pin/trajectory constraints
 Inversemassmatrix
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. 594603
 A. Selle,
J. Su, G. Irving, and R. Fedkiw, Robust
HighResolution Cloth Using Parallelism,
HistoryBased Collisions and Accurate Friction, IEEE Transactions on
Visualization and Graphics (TVCG), 15(2),
339350.
 T. Brochu,
E. Edwards, and R. Bridson, Efficient
Geometrically Exact Continuous Collision
Detection, Proc. SIGGRAPH 2012. (opensource
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:123:4. (equalityconstraint
alternative to rigid cloth zones)
 X. Provot,
Collision and selfcollision 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. 602608, 1998.
 P. Jimenez, F.
Thomas, and C. Torras, 3D collision
detection: A survey,
Computers & Graphics, Elsevier, 25(2),
pp. 269285, 2001.
 Gino Van Den
Bergen, Efficient
collision detection of complex deformable
models using AABB trees, Journal of
Graphics Tools, 1998

TuMar18

Rigid
Body Simulation

Material:
 Rigid body
dynamics
 Position,
orientation, linear/angular velocity, momentum,
inertia, equations of motion, etc.
 Euler's
equations of angular rigidbody dynamics (in
body coordinates)
 Contact
impulses
 Example:
"rigid damping"
 Frictionless
contacts:
 Nonpenetration
constraints
 Velocitylevel
constraints (see Baraff course notes for
accelerationlevel 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)

ThMar20

No class

SIGGRAPH PC Meeting

TuMar25

Proposal for Final Project 
Webpage
 Project proposal (PDF
format) [DUE: Thursday April 10]

TuMar25
ThMar27
TuApr08

Rigid
Body Contact:
Impulse and Constraintbased Methods

Material:
 General
discussion of contact methods, with specific
discussions of typical impulsebased [Guendelman et
al. 2003] and constraintbased [Erleben et al. 2007]
solvers.
 Impulsebased
contact
solvers:
 Brian Mirtich,
John Canny, Impulsebased
Simulation of Rigid Bodies, 1995
Symposium on Interactive 3D Graphics, April 1995,
pp. 181188.
 Eran Guendelman, Robert Bridson,
Ronald P. Fedkiw, Nonconvex Rigid Bodies
With Stacking, ACM Transactions on
Graphics, 22(3), July 2003, pp. 871878. [an iterative
impulsebased solver]
 Projected GaussSeidel 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, Velocitybased shock
propagation for multibody dynamics animation,
ACM Trans. Graph. 26, 2, Jun. 2007.
 Projected
Jacobi solver:
 SIAM
Review of rigidbody contact:
 "Staggered Projections" method:
 A good reference on convex
optimization:
 Stephen
Boyd and Lieven Vandenberghe, Convex Optimization,
Cambridge University Press, 2004.
 Stanford
lecture notes/book [PDF]

TuApr08
ThApr10

Passive Rigid Motion Control

Material:
 Simulation
accuracy vs plausibility
 Exploiting
errors for control
 Random
sampling methods
 Optimization
based methods
 Interactive
artistdriven 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.183197, 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.
209218.
 Stephen
Chenney, D. A. Forsyth, Sampling
Plausible
Solutions
to MultiBody Constraint Problems, Proceedings
of ACM SIGGRAPH 2000, Computer Graphics Proceedings,
Annual Conference Series, July 2000, pp. 219228.
 Christopher
D. Twigg, Doug L. James, ManyWorlds Browsing
for Control of Multibody Dynamics, ACM
Transactions on Graphics, 26(3), July 2007, pp.
14:114: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:125:10. [ACM] [PDF]
 C.
O'Sullivan and J. Dingliana, Collisions and
Perception, ACM Trans. Graph. 20, 3
(Jul. 2001), 151168.

TuApr15
ThApr17

Fluid Animation

Materials:
 Jos Stam,
Stable Fluids,
Proceedings of SIGGRAPH 99, Computer Graphics
Proceedings, Annual Conference Series, August 1999,
pp. 121128. [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. 1522. (introduces vorticity confinement
forces)
 Bridson, R.,
Fedkiw, R., and MullerFischer, 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, 187. [Slides,
Notes]

ThApr17

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.

TuApr22

Fracture Animation

Material:
 Demetri
Terzopoulos, Kurt Fleischer, Modeling
Inelastic Deformation: Viscoelasticity,
Plasticity, Fracture,Computer Graphics
(Proceedings of SIGGRAPH 88), August 1988, pp.
269278.
 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.
137146.
 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.
291294.
 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. 385392.
 M. Müller,
M. Gross, Interactive
Virtual Materials, in
Proceedings of Graphics Interface (GI 2004), pp
239246, London, Ontario, Canada, May 1719, 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. 957964. (Video)
 Hayley N.
Iben, James F. O'Brien, Generating
Surface Crack Patterns, 2006
ACM SIGGRAPH / Eurographics Symposium on Computer
Animation, September 2006, pp. 177186.
 Denis
Steinemann, Miguel A. Otaduy, Markus Gross, Fast
Arbitrary Splitting of Deforming Objects, 2006
ACM SIGGRAPH / Eurographics Symposium on Computer
Animation, September 2006, pp. 6372. (Video)
 Bao, Z.,
Hong, J.M., Teran, J. and Fedkiw, R., Fracturing
Rigid Materials, IEEE
TVCG 13, 370378 (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. 7380.
 Eric G.
Parker and James F. O'Brien, RealTime
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. 155164
(2009).
 Changxi
Zheng, Doug L. James, RigidBody
Fracture Sound with Precomputed Soundbanks, ACM
Transactions on Graphics, 29(4), July 2010, pp.
69:169:13.

ThApr24

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. 382395.
 Kees van den
Doel, Paul G. Kry, Dinesh K. Pai, FoleyAutomatic:
PhysicallyBased Sound Effects for Interactive
Simulation and Animation, Proceedings of ACM
SIGGRAPH 2001, Computer Graphics Proceedings, Annual
Conference Series, August 2001, pp. 537544. [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. 8796. [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. 529536.
 Perry R.
Cook, Sound
Production and Modeling, IEEE Computer Graphics
& Applications, 22(4), JulyAugust 2002, pp.
2327.
 James F.
O'Brien, Chen Shen, and Christine M. Gatchalian. Synthesizing
sounds from rigidbody simulations. In The ACM
SIGGRAPH 2002 Symposium on Computer Animation, pages
175–181. ACM Press, July 2002.
 Yoshinori
Dobashi, Tsuyoshi Yamamoto, Tomoyuki Nishita, RealTime
Rendering of Aerodynamic Sound Using Sound Textures
Based on Computational Fluid Dynamics, ACM
Transactions on Graphics, 22(3), July 2003, pp.
732740. [project
page]
 Doug L.
James, Jernej Barbić and Dinesh K. Pai, Precomputed
Acoustic Transfer: Outputsensitive, accurate sound
generation for geometrically complex vibration
sources, ACM Transactions on Graphics, 25(3),
pp. 987995, July 2006, pp. 987995.
 Changxi
Zheng and Doug L. James, Harmonic
Fluids, ACM Transaction on Graphics (SIGGRAPH
2009), 28(3), August 2009, pp. 37:137:12.
 Jeffrey
Chadwick, Steven An, and Doug L. James, Harmonic
Shells: A Practical Nonlinear Sound Model for
NearRigid Thin Shells, ACM Transactions on
Graphics (SIGGRAPH ASIA Conference Proceedings),
28(5), December 2009, pp. 119:1119:10.
 Changxi
Zheng and Doug L. James, RigidBody
Fracture Sound with Precomputed Soundbanks, ACM
Transactions on Graphics (SIGGRAPH 2010), 29(3), July
2010, pp. 69:169: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 RigidBody Sound, ACM Transactions on Graphics, August 2012.
 Steven
S. An , Doug
L. James, and Steve
Marschner, Motiondriven
Concatenative Synthesis of Cloth Sounds, ACM Transactions on Graphics, August 2012.

TuApr29

Yarnlevel Cloth Simulation
(Guest
lecturer: Eston Schweickart)


ThMay01

Project working session

(Prof. James at SIG CHI) 
TuMay06

Project Presentations

Tentatively organized for an extended
inclass presentation period. The CS colloquium no longer
meets after our class, and therefore we can extend the
class into the following slot and remain in Gates G01.
