CPSC 533B Animation Physics

January-April 2004, T and TH 9:30am-11am, in MacMillan 256

Instructor: Robert Bridson

Prerequisites: programming experience, differential equations, physics (continuum mechanics is a big plus, but not necessary), basic numerical analysis, basic computer graphics (but simple rendering code will be supplied)

This course gives a practical introduction to the use of numerical simulation for animating natural phenomena, such as the motion and interaction of rigid bodies, cloth, smoke, water, etc. The emphasis is on passive, uncontrolled motion (as opposed to human locomotion for example) but artistic control will be mentioned.

Contacting Me

You can always email me at rbridson @ cs.ubc.ca, or phone my office 604-822-1993. My office is in CICSR 189; either drop by (I'm in most of the time 9:30-5:30) or email me to set up an appointment to be sure of seeing me.

I'm happy to help out with stuff, and also appreciate feedback on the course---if the pace is right, if you want to see some particular topic covered, etc.

Assignments

Here are a few of the final projects

• Assignment #1 (minor update to fix inconsistent axis labeling)
• A simple particle renderer for assignment 1 that doesn't use OpenGL (and generates much higher quality output, much more slowly). Use this if you don't have easy access to machine with OpenGL, or you want to produce a higher quality movie. Note that while the assignment suggests a particle radius of 0.001, unless you use a lot of particles, you probably will want to increase that to 0.01 or more.
• Assignment #2 (update to fix an inconsistency in the supplied parameters file, and add a README to the software renderer, and restoring hw2_viewer to functionality!)
• Assignment #3 (with example code including a viewer, but no high-quality off-line renderer yet. Note bug fixes: code should use argv[2] instead of argv[3] for the optional output directory, frame 0 of the rigid bodies needs to be output before the main loop, normalize_q() was wrong.)
• Assignment #4 (Note: the example code lists a bending element with the common edge in the middle (vertices 1 and 2 out of 0,1,2,3) - the class slides use the common edge at the end (3 and 4 out of 1,2,3,4)).
• Assignment #5 and heightfield viewer (Note: no example code this time -- if you use something like Matlab you shouldn't need it, but let me know if you're struggling).
• Assignment #6 (Note: there may be a mistake in the derivation of the limited cubic Hermite interpolation in the paper by Fedkiw et al.; it's always safer to rederive it yourself as I started in class)
• Slice viewer, a 2D cross-section viewer for assignment 6 (which should run faster than the 3D viewer included with the example code, and doesn't have any alpha-blending issues).

There will be six programming assignments, essentially implementing some of the algorithms discussed in class. They will also have a small written component.

The first assignment counts for 10% of your final grade, and the other five assignments each count for 15%.

To hand in the programming part of an assignment, email me the source code and instructions for compiling/running it. Please don't email very large data files (instead put them on the CS file system or the web somewhere I can get them). To hand in the written component, either email it to me (preferably in plain text or PDF), give it to me in person, or slide it under my office door.

I'll try to provide some C code as a starting point for the assignments, but you may use any language within reason. I'll need to be able to compile/run your stuff; at least ensure that the language and libraries you are using are installed on the CS department servers---as I write this, languages I can deal with include C, C++, Objective C, Java, Fortran 77 and 90, Common Lisp, Scheme, Standard ML, OCAML, Python, Perl, Prolog, Matlab, Octave, ... Remember that speed is important here, and I will penalize ridiculously slow programs, so be reasonable.

It is fine to use code from other sources as long as (1) you properly attribute it and (2) it doesn't defeat the point of the assignment. For example, if I teach something in class you should not use someone else's code for that, but other support code (e.g. solving dense linear systems, FFT, generic data structures) is fair game. This can be delicate particularly for languages like Matlab, which include a whole bunch of built-in functions for numerical computing---if in doubt about something, ask me before the assignment is due!

I understand it is sometimes difficult to turn in assignments on time due to unforeseen emergencies. If you have a good reason you can't turn something in on time, please contact me as soon as possible about it and we can work something out. Otherwise, there will be a 20% penalty per day late, starting when I come to my office in the morning after the due date.

Final Project

There will also be a final project worth another 15%. I expect this will be an extension of one of the assignments apart from the first; each of these assignments will include suggestions for extensions that you could do to make it your final project. If you want to do something else, either an extension I haven't listed or maybe something completely different not related to the assignments, that's great! but you need to talk to me and get it approved.

You will need to submit the source code and a short write-up explaining what you did and how. There will also be an informal demo screening at the end of the course where you will show it to the class. This will just be a couple of minutes, briefly explaining what you did and showing the results (you can send me a movie to run on my laptop, or make other arrangements ahead of time).

Note that the late penalty for the final project will start immediately if you do not have it ready for presentation in class.

Resources

There is no assigned text, but I will provide references to useful books, papers, etc. I will assume for basic numerical analysis you can pick your own favourite text.

Note: I generally will not provide the papers in class or as links on this page; instead it is up to you to find them. The web is now a wonderful resource for finding papers. Preprints of many papers can be found on the authors' websites---use a search engine like Google to find these. Papers that appear in places like SIGGRAPH, ACM Transactions on Graphics (TOG) and Symposium on Computer Animation (SCA) can be found in the ACM Digital Library (http://www.acm.org/dl) but you will need to be logged into a UBC machine or go though the proxy server. Other journals to which UBC subscribes can be found by their search page; often you will find that recent articles were published electronically and UBC has a subscription that lets you read them online (like the ACM Digital Library). Finally there is the last resort of actually going to the library to look at a paper copy, or ordering through InterLibrary Loan if UBC doesn't have it at all.

Please find the following articles and read them:

• W. T. Reeves, "Particle systems---a technique for modeling a class of fuzzy objects", SIGGRAPH '83, pp. 359--375.
• K. Sims, "Particle animation and rendering using data parallel computation", SIGGRAPH '90, pp. 405--413. (But you can ignore the parallel computing bits---nobody uses Connection Machines anymore.)
• J. Stam and E. Fiume, "Turbulent wind fields for gaseous phenomena", SIGGRAPH '93, pp. 369--376.
• J. K. Hahn, "Realistic animation of rigid bodies", SIGGRAPH '88, pp. 299--308.
• E. Guendelman, R. Bridson, and R. Fedkiw, "Nonconvex rigid bodies with stacking", SIGGRAPH '03, pp. 871--878.
• D. Baraff, "Linear-time dynamics using Lagrange multipliers", SIGGRAPH '96, pp. 137--146.
• K. Cho and H.-S. Ko, "Stable but responsive cloth", SIGGRAPH '02, pp. 604--611.
• E. Grinspun et al., "Discrete Shells", SCA '03.
• A. Pentland and J. Williams, "Good vibrations: model dynamics for graphics and animation", SIGGRAPH '89, pp. 207--214.
• J. F. O'Brien and J. K. Hodgins, "Graphical modeling and animation of brittle fracture", SIGGRAPH '99, pp. 137--146.
• J. F. O'Brien, A. W. Bargteil and J. K. Hodgins, "Graphical modeling and animation of ductile fracture", SIGGRAPH '02, pp. 291--294.
• M. Kass and G. Miller, "Rapid, stable fluid dynamics for computer graphics", SIGGRAPH '90, pp. 49--57.
• R. Fedkiw, J. Stam, and H. W. Jensen, "Visual Simulation of Smoke", SIGGRAPH '01, pp. 15--22.
• N. Foster and D. Metaxas, "Realistic animation of liquids", Graphics Interface '96, pp. 204--212.

For an alternative look at rigid body dynamics, check out Physically Based Modeling course notes from SIGGRAPH 2001, by Andrew Witkin and David Baraff. I have tried to use the same notation as them for consistency. Their notes also cover other topics addressed in this course in a different way, and a few topics that are not.

More advanced optional reading. The abbreviation "JCP" means Journal of Computational Physics, "Numer. Math." means Numerische Mathematik, and "jgt" is the Journal of Graphics Tools.

• C. W. Shu and S. Osher, "Efficient Implementation of Essentially Non-Oscillatory Shock Capturing Schemes", JCP 77 (1988), pp. 439--471. (This is where TVD Runge-Kutta was introduced)
• J. P. Wright, "Numerical instability due to varying time steps in explicit wave propagation and mechanics calculations", JCP 140 (1998), pp. 421--431. (Another reason not to trust methods near their standard stability limit)
• R. Rannacher, "Finite element solution of diffusion problems", Numer. Math. 43 (1984), pp. 309--327. (Deals with Trapezoidal Rule's monotonicity problems for diffusion or strongly damped problems)
• K. Perlin, "Improving noise", SIGGRAPH '02, pp. 681--682, and D. Ebert et al. "Texturing and modeling: a procedural approach", 1998, 2nd edition, AP Professional: Cambridge. (The book by Ebert and company details the use of randomness in faking difficult effects efficiently, and the newer article introduces the new standard "noise" function.)
• S. Osher and R. Fedkiw, "Level set methods and dynamic implicit surfaces", 2003, Springer-Verlag New York. (A whole book on level sets - how to make them, evolve them, and use them for graphics, physics and vision)
• M. Lin and S. Gottschalk, "Collision detection between geometric models: a survey", Proc. of IMA Conference on Mathematics of Surfaces, 1998. (A reasonable starting place for learning more about collision detection)
• B. Mirtich, "Fast and accurate computation of polyhedral mass properties", jgt 1(2), 1996, pp. 31--50. (how to accurately compute inertia tensors for constant density polyhedra)
• S. R. Buss, "Accurate and efficient simulation of rigid body rotations", JCP 164 (2000), pp. 377--406.
• D. E. Stewart, "Rigid-body dynamics with friction and impact", SIAM Review 42(1), 2000, pp. 3--39. (A good theoretical review of numerical techniques for accurate rigid body simulation).
• J. B. Keller, "Impact with friction", Journal of Applied Mechanics, March 1986, 53, pp. 1--4. (A short discussion of how friction forces change during impact)
• A. Van Gelder, "Approximate simulation of elastic membranes by triangulated spring meshes", jgt 3(2), 1998, pp. 21--42. (A discussion of using mass-spring networks for elasticity)
• Y.-M. Kang and H.-G. Cho, "Bilayered approximate integration for rapid and plausible animation of virtual cloth with realistic wrinkles", Computer Animation 2002, pp. 203--214.
• P. Volino and N. Magnenat-Thalmann, "Efficient self-collision detection on smoothly discretized surface animations using geometric shape regularity", Eurographics '94, vol. 13, no. 3, pp. 155--166. (Shows how to use curvature to speed up collision-detection).
• D. Terzopoulos and K. Fleischer, "Modeling inelastic deformation: viscoelasticity, plasticity, fracture", SIGGRAPH'88, pp. 269--278. (Also has a short appendix on how to treat the rigid body modes of motion separately from deformation, summarizing another paper by Terzopoulos and Witkin in Graphics Interface '88)

For making MPEG animations of your movies from a sequence of still images, try "ppmtompeg", which is installed on (at least some of) the CS grad machines. You may need to use "convert" to change formats to PPM or JPEG, which is what ppmtompeg likes. Jason Harrison put together a script mkmpeg (download it, don't read it directly) as an easier front-end to this program; it generates a parameter file etc. for you. If you have access to a machine with Quicktime Pro, such as via a guest account on any of the Mac's in FSC 2330, you can generate higher quality .MOV files (e.g. with the MPEG-4 codec, which is usually the best) from a sequence of images. Note that Quicktime doesn't read PPM natively, but it does read SGI, JPEG, and several others.

Note: you can end up using a lot of disk space for temporary data files and images while you're creating animations. Rather than using precious NFS file server space (and your quota) for these temporary files, stick them on the local /tmp directory (inside a directory you create), make your animation, and then save just the compressed animation file in your home directory (or wherever you want). Note that files in /tmp may be deleted at any time, though it would be courteous to remove your temporary files after you've made an animation.

Miscellaneous other resources:

• For efficient dense linear algebra routines, BLAS has a home at netlib, as does LAPACK. Optimized versions are built in to Mac OS X (look out for vecLib, or in 10.3, Accelerate framework). The ATLAS project provides optimized versions for a variety of platforms. Kazushige Goto has written a possibly even better set of optimized routines for some platforms, the GOTO BLAS. Vendors such as Intel, Sun, SGI, IBM, etc. provide optimized versions for their platforms too.
• FFTW is an optimized implementation of the Fast Fourier Transform. Apple also provides a good one in the vecLib (or Accelerate) framework, and other vendors probably do too.
• Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods is a great free book about solving large and sparse linear systems (which we will encounter later in the course).
• Mersenne Twister is a great random number generator
• Numerical Recipes is a popular book with some free web versions and code. It isn't exactly up-to-date, and has its own bias, but there's useful stuff in there.
• Eric Weisstein's World of Science at Wolfram is sometimes helpful for looking up facts, tables (e.g. inertia tensors), etc...

Schedule

This is approximate and will become firmer as the course progresses. I've put links to the lecture slides as they become available. Please note that while all the fonts are embedded as needed in these PDF files, the printing system on the CS machines uses "acroread -toPostScript" to convert PDF to postscript for printing and in doing so strips out the fonts. Thus mathematical symbols are botched up by the printer, while looking fine on screen. To get around this, use "pdf2ps" to convert to postscript first, then print the postscript file.