15-863 Physically Based Modeling and Interactive Simulation

�

�
	15-863 Physically Based Modeling and Interactive Simulation Spring 2005 Computer Science Department Carnegie Mellon University

INSTRUCTOR:�
OFFICE HOURS: �
UNIVERSITY UNITS:
COURSE ROOM:
COURSE TIME:�

FIRST CLASS:

Doug James�
TBA (drop by any time, or e-mail for appt.)
12
WeH 5409
Mon & Wed, 12:00--1:20

Monday January 10, 2005

DESCRIPTION:
This course introduces students to physically based modeling for computer graphics and related fields, and summarizes current research issues. Efficient numerical methods for simulating a host of visually interesting physical phenomena will be covered, and discussed in the context of both interactive and offline simulation. The course should be appropriate for graduate students in all areas and for advanced undergraduates.

PREREQUISITES:
The prerequisite will be 15-462 Computer Graphics I (or equivalent undergraduate course) or permission of the instructor. Students should have prior exposure to numerical computation.

TEXT:
There will be no single text. Selected articles, book chapters, and course notes will be made available online.

METHOD OF EVALUATION:
Grading will be based on five programming assignments, participation in paper discussions and presentations, and a final class project and a presentation (see chart below). Collaboration and group final� projects are encouraged but must be coordinated through the instructor.

Assignments	50%
Project	30%
Paper seminar participation	20%

ASSIGNMENT LATE POLICY:
You have 5 late days that you may use for any of the assignments during the quarter but further extensions require an excellent excuse.

ASSIGNMENT HAND-IN:
Assignments are submitted electronically in your usernamed directory off /afs/cs.cmu.edu/academic/class/15863-s03. After logging in to your andrew account, you will need to run the command "cklog cs.cmu.edu" to access your directory.

TOPICS TO BE COVERED:
Depending on time and class interest we will cover topics from:

Overview of physical simulation in graphics and interactive applications
Dynamical system modeling
Numerical integration of ODEs
Rigid body dynamics
Structured deformable objects
Constraints and nonsmooth contact
Unstructured transport phenomena
Collision detection
Multiresolution geometric and physical modeling
Rendering issues: graphics, haptics and acoustics
Simulation on programmable graphics hardware
Data-driven approaches to simulation
Reality based measurement & inverse problems
Nondynamical applications of physically based modeling in graphics�

SOFTWARE
Feel free to code assignments in your preferred programming language.� Below are some suggested software libraries.

Basic numerical libraries

GSL - The GNU Scientific Library (C)
MTL - Matrix Template Library (C++ with sparse matrix support)
ATLAS - A portable self-optimising BLAS library with CBLAS interface

(Note: The following table looks better if your browser window borders are taken to infinity.)

CLASS DATE	TOPICS	MATERIAL �(supplements whiteboard)
MonJan10	Introduction	Readings from Baraff & Witkin's "Physically Based Modeling" course notes, SIGGRAPH2001 Differential Equation Basics Particle� Dynamics



Tu-Jan 14	PBMIS overview	Course overview slides (ppt)
Th-Jan 16	1. Basic dynamics 2. Numerical integration	Baraff & Witkin's "Physically Based Modeling" course notes, SIGGRAPH2001 Differential Equation Basics Particle� Dynamics Implicit Methods Time-stepping & absolute stability. Uri M. Ascher and Linda R. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, SIAM, 1998. ISBN 0-89871-412-5. Ch. 3: Basic methods, basic concepts Brief slide comments (ppt) FUN: http://www.sodaplay.com
Tu-Jan 21	No class. Read SIGGRAPH course notes.	Baraff & Witkin's "Physically Based Modeling" course notes, SIGGRAPH2001 Cloth and Fur Energy Functions Rigid Body Dynamics� Constrained Dynamics Collision and Contact
Th-Jan23	1. Constraints & stabilization 2. Collision detection	Recap of Baraff & Witkin reading Constrained Dynamics Any introductory text on Lagrangian mechanics, e.g., Goldstein or Marion & Thornton. Comment on Baumgarte stabilization (whiteboard) J. Baumgarte. Stabilization of constraints and integrals of motion in dynamical systems. Comp. Methods Appl. Mech., 1:1-16, 1972. U. Ascher, Stabilization of invariants of discretized differential systems, Numerical Algorithms, 14, pp. 1-23, 1997. (See this for projection and post-stabilization methods) Ming Lin's course notes on collision detection: Collision Detection: Basics & Convex Polyhedra D. P. Dobkin and D. G. Kirkpatrick. Determining the separation of preprocessed polyhedra: a unified approach. In Proc. 17th Int. Colloq. Automata, Languages, and Programming, Lect. Notes in Comput. Sci., vol. 443, Springer-Verlag, pages 400--413, 1990. I-COLLIDE: Interactive and Exact Collision Detection for Large-Scale Environments, by Cohen, Lin, Manocha & Ponamgi, Proc. of ACM Symposium on Interactive 3D Graphics, 1995.� A Fast Procedure for Computing the Distance between Objects in Three-Dimensional Space, by E. G. Gilbert, D. W. Johnson, and S. S. Keerthi, In IEEE Transaction of Robotics and Automation, Vol. RA-4:193--203, 1988. Matthew Moore , Jane Wilhelms, Collision detection and response for computer animation, SIGGRAPH 88. Brian Mirtich, V-Clip: fast and robust polyhedral collision detection, ACM Transactions on Graphics (TOG), v.17 n.3, p.177-208, July 1998 Fast Penetration Depth Computation For Physically-based Animation,Young J. Kim, Miguel A. Otaduy, Ming C. Lin, Dinesh Manocha, ACM SIGGRAPH Symposium on Computer Animation. pp. 23-32, 2002. Collision Detection: BVHs & Spatial Partitioning Interactive Collision Detection, by P. M. Hubbard, Proc. of IEEE Symp on Research Frontiers in Virtual Reality, 1993. (aka Sphere Trees--good for deformable objects) Efficient collision detection using bounding volume hierarchies of k-dops, by J. Klosowski, M. Held, J. S. B. Mitchell, H. Sowizral, and K. Zikan, IEEE Trans. on Visualization and Computer Graphics, 4(1):21--37, 1998. Collision Detection between Geometric Models: A Survey, by M. Lin and S. Gottschalk, Proc. of IMA Conference on Mathematics of Surfaces 1998.� OBB-Tree: A Hierarchical Structure for Rapid Interference Detection, by S. Gottschalk, M. Lin and D. Manocha, Proc. of ACM Siggraph, 1996. Rapid and Accurate Contact Determination between Spline Models using ShellTrees, by S. Krishnan, M. Gopi, M. Lin, D. Manocha and A. Pattekar, Proc. of Eurographics 1998. Other references John M. Snyder , Adam R. Woodbury , Kurt Fleischer , Bena Currin , Alan H. Barr, Interval methods for multi-point collisions between time-dependent curved surfaces, Proceedings of SIGGRAPH 93, p.321-334, September 1993. (Check out the "Fruit Tracing" example... with a lobster!). John M. Snyder, An interactive tool for placing curved surfaces without interpenetration,Proceedings of ACM SIGGRAPH 95, p.209-218, September 1995. Collision detection software: Google section; UNC gamma software
	Assignment #1	Constrained Particle Systems (Due Tuesday, Feb 11, 2003) Submit your write-up, code and videos in your directory off�/afs/cs.cmu.edu/academic/class/15863-s03
Tu-Jan 28	Introduction to rigid body dynamics	Recap of Baraff & Witkin reading Rigid Body Dynamics Brief slide comments (ppt) References: Goldstein, H., Classical Mechanics, Addison-Wesley, Reading, 1983. Featherstone, R., Robot Dynamics Algorithms, Kluwer, Boston, 1987. R. M. Murray, Z. Li, and S. S. Sastry, A Mathematical Introduction to Robotic Manipulation, CRC Press, first edition, 1994. (See Chapter 1 hand-outs). Software:� See Jeff Trinkle's page on multibody dynamics. Includes a nice survey of simulation packages and projects.
Th-Jan 30	Rigid body dynamics and contact	Class slides (ppt) References: (see also those from last class) David Baraff, Curved surfaces and coherence for non-penetrating rigid body simulation, Proceedings of ACM SIGGRAPH 94, Volume 24 ,� Issue 4 �(August 1990). David Baraff, Fast contact force computation for nonpenetrating rigid bodies, Proceedings of ACM SIGGRAPH 94, p.23-34, July 1994. Brian Mirtich , John Canny, Impulse-based simulation of rigid bodies, Proceedings of the 1995 symposium on Interactive 3D graphics, p.181-ff., April 09-12, 1995, Monterey, California, United States. Brian Mirtich, Timewarp rigid body simulation, SIGGRAPH 2000, pp. 193-200, ACM SIGGRAPH, 2000. Paul G. Kry and Dinesh K. Pai, Continuous Contact Simulation for Smooth Surfaces, Transactions on Graphics, Vol 22, No 1, January, 2003. References on fast multibody forward dynamics algorithms: Featherstone, R., Robot Dynamics Algorithms, Kluwer, Boston, 1987. D. Baraff. Linear-time dynamics using Lagrange multipliers. ACM SIGGRAPH 96, 137-146, 1996.� U. M. Ascher, D. K. Pai and B. Cloutier, Forward Dynamics, Elimination Methods, and Formulation Stiffness in Robot Simulation. International Journal of Robotics Research, 16:6, pp. 749--758, December 97. Fran�ois Faure, Fast Iterative Refinement of Articulated Solid Dynamics, IEEE Transactions on Visualization and Computer Graphics, 5(3), pp. 268-276, 1999.� U. Ascher and P. Lin, Sequential Regularization Methods for simulating mechanical systems with many closed loops,�SIAM J. Scient. Comput. 21, 1244-1262, 1999. Interesting applications: Karl Sims, Evolving virtual creatures, Proceedings of ACM SIGGRAPH 94, p.15-22, July 1994. Stephen Chenney, D. A. Forsyth, Sampling Plausible Solutions to Multi-Body Constraint Problems, Proceedings of ACM SIGGRAPH 2000. pp. 219-228, 2000. Jovan Popović, Steven M. Seitz, Michael Erdmann, Zoran Popović, Andrew P. Witkin, Interactive Manipulation of Rigid Body Simulations, Proceedings of ACM SIGGRAPH 2000, pp. 209-218, 2000.
Tu-Feb 4	Elasticity fundamentals	Class slides (ppt) References: Any text on (nonlinear) elasticity, e.g.,� Ogden, R.W., Non-Linear Elastic Deformations Atkin, R.J. & Fox, N., An Introduction to the Theory of Elasticity Fung, Y.C., Foundations of Solid Mechanics Timoshenko, S.P. & Goodier, J.N., Theory of Elasticity Boundary integral formulation; Boundary element method (BEM) D. James and D. K. Pai, ArtDefo, Accurate Real Time Deformable Objects, In Proceedings of ACM SIGGRAPH 99, Annual Conference Series,�pp. 65--72, August 1999.
Th-Feb 6	1. Elastostatic Green's functions 2. Capacitance Matrix Algorithm	Black-box (data-driven) introduction to linear elastostatic models. Class slides (ppt) Slide references: D. James and D. K. Pai, ArtDefo, Accurate Real Time Deformable Objects, In Proceedings of ACM SIGGRAPH 99, Annual Conference Series,�pp. 65--72, August 1999. D. James and D. K. Pai, A Unified Treatment of Elastostatic and Rigid Contact Simulation for Real Time Haptics, Haptics-e, the Electronic Journal of Haptics Research, Vol.2, No. 1, September 2001. �(Defines Capacitance Matrix Algorithm using discretization-abstracted Green's functions; same notation as in class) Other deformable references:� Morten Bro-Nielsen, Stephane Cotin, Real-time Volumetric Deformable Models for Surgery Simulation using Finite Elements and Condensation, Computer Graphics Forum, 1996. St�phane Cotin, Herv� Delingette, Nicholas Ayache, Real-time elastic deformations of soft tissues for surgery simulation, IEEE Transactions on Visualization and Computer Graphics, 5 (1), 62-73, 1999. Jeffrey Berkley et al., Banded Matrix Approach to Finite Element Modeling for Soft Tissue Simulation, Virtual Reality: Research, Development,� and Application, 4:203-212, 1999. (webpage) Low-rank updating references: William W. Hager, Updating the inverse of a matrix, SIAM Review, 31, 221--239, 1989.
Tu-Feb 11	Deformable models in graphics	Survey of selected formative works on deformation. Class slides (ppt) References: Some geometric deformation refs: Alan H. Barr, Global and Local Deformations of Solid Primitives, Computer Graphics (Proceedings of SIGGRAPH 84). 18(3), pp. 21-30, 1984. Thomas W. Sederberg, Scott R. Parry, Free-Form Deformation of Solid Geometric Models, Computer Graphics (Proceedings of SIGGRAPH 86). 20(4), pp. 151-160, 1986. Sabine Coquillart, Extended Free-Form Deformation: A Sculpturing Tool for 3D Geometric Modeling,Computer Graphics (Proceedings of SIGGRAPH 90). 24(4), pp. 187-196, 1990. William M. Hsu, John F. Hughes, Henry Kaufman, Direct manipulation of free-form deformations, Computer Graphics (Proceedings of SIGGRAPH 92). 26(2), pp. 177-184, 1992. Ron MacCracken and Kenneth I. Joy. Free-form deformations with lattices of arbitrary topology. ACM SIGGRAPH 96, pages 181–188. ACM Press, 1996. Karan Singh, Eugene L. Fiume, Wires: A Geometric Deformation Technique, Proceedings of SIGGRAPH 98. pp. 405-414, 1998. Some physically based deformation refs: Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K., Elastically Deformable Models, ACM SIGGRAPH 87, 205-214, 1987.� John C. Platt, Alan H. Barr, Constraint methods for flexible models, ACM SIGGRAPH Computer Graphics, June 1988. Demetri Terzopoulos, Andrew Witkin, Physically Based Models with Rigid and Deformable Components, IEEE Computer Graphics & Applications. 8(6), pp. 41-51, 1988. Alex Pentland, John Williams, Good Vibrations: Modal Dynamics for Graphics and Animation, Computer Graphics (Proceedings of SIGGRAPH 89). 23(3), pp. 215-222, 1989. Dimitri Metaxas, Demetri Terzopoulos, Dynamic deformation of solid primitives with constraints, ACM SIGGRAPH Computer Graphics, 26(2), p.309-312, July 1992.� David Baraff, Andrew Witkin, Dynamic simulation of non-penetrating flexible bodies, Computer Graphics (Proceedings of SIGGRAPH 92). 26(2), pp. 303-308, 1992. Marie-Paule Gascuel, An implicit formulation for precise contact modeling between flexible solids, ACM SIGGRAPH 93, p.313-320, September 1993. Demetri Terzopoulos , Hong Qin, Dynamic NURBS with geometric constraints for interactive sculpting, ACM Transactions on Graphics (TOG), v.13 n.2, p.103-136, April 1994.� Petros Faloutsos, Michiel van de Panne, Demetri Terzopoulos, Dynamic Free-Form Deformations for Animation Synthesis, IEEE Transactions on Visualization and Computer Graphics. 3(3), pp. 201-214, 1997. Marie-Paule Cani-Gascuel, Mathieu Desbrun, Animation of Deformable Models Using Implicit Surfaces, IEEE Transactions on Visualization and Computer Graphics. 3(1), pp. 39-50, 1997.� Sarah F. F. Gibson, 3D Chainmail: a Fast Algorithm for Deforming Volumetric Objects, 1997 Symposium on Interactive 3D Graphics. pp. 149-154, 1997. S. Gibson and B. Mirtich. A Survey of Deformable Modeling in Computer Graphics, Tech. Report No. TR-97-19, Mitsubishi Electric Research Lab., Cambridge, MA, November 1997.
Th-Feb13	Deformable models in graphics (cont'd)	References: See previous class slides & references. Dimitri Metaxas, Demetri Terzopoulos, Dynamic deformation of solid primitives with constraints, ACM SIGGRAPH Computer Graphics, 26(2), p.309-312, July 1992. (whiteboard)� Shabana, A., Dynamics of multibody systems, Wiley, New York, 1989. (whiteboard)
	Assignment #2	HAIL STORM! (Due Tuesday, March 11) HINT: Single barycentric point constraint Starter code is located in� /afs/cs.cmu.edu/academic/class/15863-s03/pbmisA2_HailStorm_starterCode.zip
Tu-Feb 18	Collision detection for deformable models	Class slides (ppt) References: My handout: James, "Summary of Collision Detection Algorithms for Deformable Models," unpublished, 2002. Interactive Collision Detection, by P. M. Hubbard, Proc. of IEEE Symp on Research Frontiers in Virtual Reality, 1993. (Sphere trees) G. van den Bergen. Efficient Collision Detection of Complex Deformable Models using AABB Trees. Journal of Graphics Tools, 4(2):1--13, 1997. S. Cotin, H. Delingette, and N. Ayache, Real-time elastic deformations of soft tissues for surgery simulation, IEEE Transactions on Visualization and Computer Graphics, 5 (1), 62--73, 1999. (example using uniform space partitioning) Thomas Larsson and Tomas Akenine-M�ller, Collision Detection for Continuously Deforming Bodies, Eurographics 2001. (Improved updating of AABB-Trees) J. Brown, S. Sorkin, C. Bruyns, J.C. Latombe, K. Montgomery, and M. Stephanides. Real-Time Simulation of Deformable Objects: Tools and Application. In Proceedings of Computer Animation 2001, Seoul, Korea, November 7-8 2001. (example of updating a sphere tree with fixed topology) Leonidas Guibas, An Nguyen, Daniel Russel, and Li Zhang. Collision Detection for Deforming Necklaces. In Proceedings of the Eighteenth Annual Symposium on Computational Geometry, pages 33-42. ACM Press, 2002. (updating a sphere tree w/ temporal coherence)
Th-Feb 20	NVIDIA lecture (by Cem Cebenoyan)	Class slides (ppt) Read handouts from Shabana text for next week.
Tu-Feb 25	Deformable multibody systems	Chapter 5 of Ahmed A. Shabana, Dynamics of Multibody Systems, Cambridge University Press, 2nd edition, April 1998.� Class slides (ppt)
Th-Feb 27	Sound modeling	Class slides (ppt) References: Adam Stettner, Donald P. Greenberg, Computer Graphics Visualization For Acoustic Simulation, Computer Graphics (Proceedings of SIGGRAPH 89). 23(3), pp. 195-206, 1989. Tapio Takala, James Hahn, Sound Rendering, Computer Graphics (Proceedings of SIGGRAPH 92). 26(2), pp. 211-220, 1992. 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. Thomas A. Funkhouser, Patrick Min, Ingrid Carlbom, Real-Time Acoustic Modeling for Distributed Virtual Environments, Proceedings of SIGGRAPH 99. pp. 365-374, 1999. Perry Cook, Physically Based Parametric Sound Synthesis and Control, ACM SIGGRAPH Course Notes, 2000. Nicolas Tsingos, Thomas Funkhouser, Addy Ngan, Ingrid Carlbom, Modeling Acoustics in Virtual Environments Using the Uniform Theory of Diffraction, Proceedings of ACM SIGGRAPH 2001. pp. 545-552, 2001. Kees van den Doel , Paul G. Kry , Dinesh K. Pai, FoleyAutomatic: Physically Based Sound Effects for Interactive Simulation and Animation, SIGGRAPH 2001, p.537-544, August 2001.� James F. O'Brien , Perry R. Cook , Georg Essl, Synthesizing Sounds from Physically Based Motion, SIGGRAPH 2001, p.529-536, August 2001. �(Project page) 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, ACM SIGGRAPH 2001, p.87-96, August 2001.� Perry R. Cook, Real Sound Synthesis for Interactive Applications, AK Peters, 2002. O'Brien, J. F., Shen, C., Gatchalian, C. M., Synthesizing Sounds from Rigid-Body Simulations,� ACM SIGGRAPH 2002 Symposium on Computer Animation, San Antonio, Texas, July 21-22, pp. 175-182. Thomas Funkhouser, Jean-Marc Jot, Nicolas Tsingos, “Sounds Good to Me!” Computational Sound for Graphics, Virtual Reality, and Interactive Systems, �ACM SIGGRAPH Course Notes, 2002. Software JASS (Java Audio Synthesis System). Kees van den Doel. Includes Java SDK, documentation, and applets. The Synthesis ToolKit in C++ (STK), Perry R. Cook and Gary P. Scavone. BEM for Acoustic Problems, Stephen Kirkup.
Tu-Mar 4	Cloth modeling �(by Chris Twigg)	Class slides (pdf) References: Xavier Provot, Deformation Constraints in a Mass-Spring Model to Describe Rigid Cloth Behavior, Graphics Interface '95, pp. 147-154, 1995. David Baraff and Andrew P. Witkin, Large Steps in Cloth Simulation, Proceedings of SIGGRAPH 98, pp. 43-54, 1998. D. E. Breen, D. H. House, P. H. Getto, A Physically-Based Particle Model of Woven Cloth, The Visual Computer. 8(5-6), pp. 264-277, 1992. David E. Breen, Donald H. House, Michael J. Wozny, Predicting the Drape of Woven Cloth Using Interacting Particles, Proceedings of SIGGRAPH 94. pp. 365-372, 1994.� Robert Bridson, Ron Fedkiw, and John Anderson, Robust treatment of collisions, contact and friction for cloth animation, Proceedings of SIGGRAPH 2002, pages 594--603.� Kwang-Jin Choi and Hyeong-Seok Ko.� Stable but responsive cloth, Proceedings of SIGGRAPH 2002, pages 604--611, 2002. X. Provot, Collision and Self-collision Handling in Cloth Model Dedicated to Design, Computer Animation and Simulation '97, pp. 177-190, 1997. Martin Courshesnes, Pascal Volino, Nadia Magnenat-Thalmann, Versatile and Efficient Techniques for Simulating Cloth and Other Deformable Objects, Proceedings of SIGGRAPH 95, pp. 137-144, 1995.
Th-Mar 6	No class (mid-term break)
Tu-Mar 11	Hair and strand-like deformable models	Course project discussion Class slides (ppt) References: Featherstone, R., Robot Dynamics Algorithms, Kluwer, Boston, 1987. Ken-ichi Anjyo, Yoshiaki Usami, Tsuneya Kurihara, A simple method for extracting the natural beauty of hair, Computer Graphics (Proceedings of SIGGRAPH 92). 26(2), pp. 111-120, 1992. Ronen Barzel, Faking Dynamics of Ropes and Springs, IEEE Computer Graphics & Applications. 17(3), pp. 31-39, 1997. N.Magnenat-Thalmann, S.Hadap, P.Kalra, State of the Art in Hair Simulation, International Workshop on Human Modeling and Animation, Seoul, Korea, Korea Computer Graphics Society, pp. 3-9, June, 2002. Sunil Hadap, Nadia Magnenat-Thalmann, Modeling Dynamic Hair as a Continuum, Computer Graphics Forum, Volume 20, Issue 3, Eurographics 2001 Proceedings, Manchester, United Kingdom, September 2001. Eric Plante, Marie-Paule Cani, Pierre Poulin, Capturing the Complexity of Hair Motion, GMOD num�ro 1 volume 64 , january 2002. Johnny T. Chang, Jingyi Jin, Yizhou Yu, A Practical Model for Hair Mutual Interactions, ACM SIGGRAPH Symposium on Computer Animation. pp. 73-80, 2002. Tae-Yong Kim, Ulrich Neumann, Interactive Multiresolution Hair Modeling and Editing, ACM Transactions on Graphics. 21(3), pp. 620-629, 2002. Dinesh K. Pai, STRANDS: Interactive Simulation of Thin Solids using Cosserat Models, Computer Graphics Forum. 21(3), pp. 347-352, 2002.
Th-Mar 13	Attend lecture by Szymon Rusinkiewicz	Title: Fast and Flexible 3D Scanning Wean Hall 4623, Talk 12:30pm - 2:00pm
Tu-Mar 18�	Multiresolution deformable modeling: Adaptive simulation	Class slides (ppt) References: H. Yserentant, On the multilevel splitting of finite element spaces, Numer. Math., 49 (1986), pp. 379--412. �(related pub) Yan Zhuang and John Canny, Real-time Simulation of Physically Realistic Global Deformation,� IEEE Vis'99 Late Breaking Hot Topics. San Francisco, California. October 24-29, 1999. Gilles Debunne, Mathieu Desbrun, Marie-Paule Cani, Alan H. Barr, Dynamic Real-Time Deformations Using Space & Time Adaptive Sampling, Proceedings of ACM SIGGRAPH 2001. pp. 31-36, 2001. Xunlei Wu, Michael S. Downes, Tolga Goktekin, Frank Tendick, Adaptive Nonlinear Finite Elements for Deformable Body Simulation Using Dynamic Progressive Meshes, Computer Graphics Forum. 20(3), pp. 349-358, 2001. Steve Capell, Seth Green, Brian Curless, Tom Duchamp, Zoran Popović, A Multiresolution Framework for Dynamic Deformations, ACM SIGGRAPH Symposium on Computer Animation. pp. 41-48, 2002. Eitan Grinspun, Petr Krysl, Peter Schr�der, CHARMS: A Simple Framework for Adaptive Simulation, ACM Transactions on Graphics. 21(3), pp. 281-290, 2002.
Th-Mar 20	No class (SIGGRAPH committee meeting)
Tu-Mar 25	No class (Spring break)
Th-Mar 27	No class (Spring break)
Tu-Apr 1	Multiresolution deformable modeling: Data-driven simulation	Class slides (ppt) References: Wim Sweldens, The Lifting Scheme: A Construction of Second Generation Wavelets, SIAM Journal on Mathematical Analysis, 29(2), pages� 511--546, 1998. Peter Schr�der and Wim Sweldens, Spherical Wavelets: Efficiently Representing Functions on the Sphere, SIGGRAPH, ACM Press, Pages: 161 - 172, 1995. Doug L. James, Dinesh K. Pai, Multiresolution Green's Function Methods for Interactive Simulation of Large-scale Elastostatic Objects, ACM Transactions on Graphics. 22(1), pp. 47-82, 2003. (movies)
Th-Apr 3	Fracture and cutting	References: Terzopoulos, D. and Fleischer, K., Modeling Inelastic Deformation: Viscoelasticity, Plasticity, Fracture, ACM SIGGRAPH 88, 269-278, 1988. James F. O'Brien , Jessica K. Hodgins, Graphical Modeling and Animation of Brittle Fracture, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.137-146, July 1999.� F. Ganovelli, P. Cignoni, C. Montani, R. Scopigno, Enabling Cuts on Multiresolution Representation, The Visual Computer. 17(5), pp. 274-286, 2001. Andrew Mor, Progressive Cutting with Minimal New Element Creation of Soft Tissue Models for Interactive Surgical Simulation, doctoral dissertation, tech. report CMU-RI-TR-01-29, Robotics Institute, Carnegie Mellon University, 2001. James F. O'Brien , Adam W. Bargteil , Jessica K. Hodgins, Graphical Modeling and Animation of Ductile Fracture, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002.
Tu-Apr 8	1. Finite Element Method (FEM) details 2. Implicit-Explicit (IMEX) schemes	References: Explicit linear tetrahedral FEM material: See previous FEM references, or ... James F. O'Brien , Jessica K. Hodgins, Graphical Modeling and Animation of Brittle Fracture, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.137-146, July 1999.� 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.� Mathieu Desbrun, Peter Schr�der, Al Barr, Interactive Animation of Structured Deformable Objects, Graphics Interface '99. pp. 1-8, 1999.
Th-Apr 10	Conservation laws	References: Randy LeVeque, Numerical Methods for Conservation Laws, Birkhauser Verlag, Boston, 2000.
Tu-Apr 15	Conservation laws (cont'd)	References: Randy LeVeque, Numerical Methods for Conservation Laws, Birkhauser Verlag, Boston, 2000.
Th-Apr 17	1. Semi-Lagrangian integration schemes 2. Smoke simulation	References: Staniforth, A., and J. Cote, Semi-Lagrangian integration schemes for atmospheric models - A review. Mon. Wea. Rev., 119, 2206-2223,�1991. Dale R. Durran, Numerical Methods for Wave Equations in Geophysical Fluid Dynamics, Springer-Verlag, 465 pages, 1999. (See chapter 6) Jos Stam, Stable Fluids, SIGGRAPH 99. pp. 121-128, 1999. Fedkiw, R., Stam, J. and Jensen, H.W., Visual Simulation of Smoke, SIGGRAPH 2001, pp. 23-30, 2001.
Tu-Apr 22	1. Level sets 2. Fluids and fire simulation	References: Stanley J. Osher, Ronald P. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Springer Verlag, 1st ed., 2002. Nick Foster, Ronald Fedkiw, Practical Animation of Liquids, Proceedings of ACM SIGGRAPH 2001. pp. 23-30, 2001. Douglas P. Enright, Stephen R. Marschner, Ronald P. Fedkiw, Animation and Rendering of Complex Water Surfaces, ACM Transactions on Graphics. 21(3), pp. 736-744, 2002. Duc Quang Nguyen, Ronald P. Fedkiw, Henrik Wann Jensen, Physically Based Modeling and Animation of Fire, ACM Transactions on Graphics. 21(3), pp. 721-728, 2002.
Tu-Apr 24	Project presentations
Tu-Apr 29	No class (ACM I3D)
Tu-May 6	Project presentations
Fri-May 9	Projects Due
N/A	Primer on numerical linear algebra	References: James W. Demmel, Applied Numerical Linear Algebra, SIAM, 1997. (Chapter 6: Iterative Methods for Linear Systems) William L. Briggs, Van Emden Henson, Steve F. McCormick, A Multigrid Tutorial, SIAM, 2000. (See tutorial slides)