[SCS dragon logo] 15-863 Physically Based Modeling and Interactive Simulation
Spring 2005

Computer Science Department
Carnegie Mellon University

15-863 Course Poster



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

Monday January 10, 2005

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.

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.

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

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

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

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.


Depending on time and class interest we will cover topics from:

Feel free to code assignments in your preferred programming language.  Below are some suggested software libraries.
(Note: The following table looks better if your browser window borders are taken to infinity.)
MATERIAL  (supplements whiteboard)

Tu-Jan 14
PBMIS overview
Th-Jan 16
1. Basic dynamics
2. Numerical integration
Tu-Jan 21
No class. Read SIGGRAPH course notes.

1. Constraints & stabilization
2. Collision detection

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
  • 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

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)
Th-Feb 6
1. Elastostatic Green's functions
2. Capacitance Matrix Algorithm

Tu-Feb 11
Deformable models in graphics

Deformable models in graphics (cont'd)

  • References:
    • See previous class slides & references.
    • 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.
    • 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)
Tu-Feb 25
Deformable multibody systems

Th-Feb 27
Sound modeling

Tu-Mar 4 Cloth modeling  (by Chris Twigg)

Th-Mar 6
No class (mid-term break)

Tu-Mar 11
Hair and strand-like deformable models

Th-Mar 13
Attend lecture by Szymon Rusinkiewicz
Tu-Mar 18  Multiresolution deformable modeling:
Adaptive simulation

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

Th-Apr 3
Fracture and cutting

Tu-Apr 8
1. Finite Element Method (FEM) details
2. Implicit-Explicit (IMEX) schemes

Th-Apr 10
Conservation laws

Tu-Apr 15
Conservation laws (cont'd)

Th-Apr 17
1. Semi-Lagrangian integration schemes
2. Smoke simulation
Visual Simulation of Smoke, 2001
Tu-Apr 22
1. Level sets
2. Fluids and fire simulation

Tu-Apr 24 Project presentations
Tu-Apr 29
No class (ACM I3D)
Tu-May 6
Project presentations
Fri-May 9
Projects Due

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)