The Physics Project

The goal of this project is to give you a chance to explore the issues in doing simulation for animation. The idea is to make you simulate something very simple, but to simulate it using various methods to see the tradeoff between them.

The basic requirement is for you to build a 2D particle simulation (each particle is a point mass that can have forces pushing it). You can do 3D, but then the user interface is harder. For this assignment, trying different simulation methods is more important than making fancy images.

The project does have various stages, that you should progress through. However, you should look ahead to make sure that your design decisions in an early phase don't preclude what you will need to do later.

The early phase of the project will have you build a particle simulator where you use various forces on the particles to move them around. You should try to make your system interactive and fast so you can try lots of things.

The later phase of the project will have you experiment with making a piece of string. A piece of string is basically a 1D piece of cloth. You will be able to make a springy string using the early part of the project. But if you want to make those springs connecting the particles of the string together stiff, you will need to explore different solution methods: explicit integrators (such as predictor-corrector), implicit integration (ala. Baraff&Witkin's cloth paper), and semi-implicit integration (Bridson Fedkiw).

Ground Rules

You must work with a partner. You may not work with a partner that you have worked with for any of the previous assignments.

You may use any development tools and language that you like. I can offer little help to you if you choose something that I don't know, but the graphics for this project are simple and 2D, so languages like Java might be a reasonable alternative to C++.

You will almost certainly want to use some numerical library. If nothing else, you will want to use a library to solve linear systems (you will need it for implicit integration, if nothing else). There's a lot of numerics code out there on the internet. Be careful and use stuff from a reliable source.

If you want to use code other than a numerics library, please check with me. You are welcome to use my "basics" library.

Phase 1

For phase 1, you must build an interactive 2D particle simulator.

You must be able to simulate a number of particles - each particle should be able to have its mass set to a different value. You should be able to add particles interactively.

You must be able to watch the simulation as it progresses. Trust me, this is important and useful for debugging. The simulation does not need to run at a constant frame rate (this will become more difficult in the later steps).

You must be able to read in a file that describes the initial configuration of the particules, as well as any forces to be applied to them.

You must be able to save the results of a simulation and replay it. While your simulation does not have to be real time, your playback should be able to play at the correct frame rate for your simulation. Note: you may want to have an adaptive step-size integrator at some point, so make sure your playback understands the simulator timing.

You should implement (at least) the following forces:

• a constant force (constant in a particular direction, like gravity)
• a damping (or velocity dependent) force
• a spring (of a setable distance) between two particles
• a spring between a particle and a specific location (or, allow some particles to be un-movable nails and then you just need springs between particles)
• a spring that pushes particles upward from the floor (penalty collistions with the floor), or outward from the walls.
• damping between particles (e.g. a force proportional to the relative velocity of particles)
• repulsion between particles (if the distance between particles is ever less than X, they push each other away)

This is more fun if you have a user interface for creating the particles, However, all that is required is the ability to read in a description.

You should also implement some way for the user to interact with the particles. I recommend both being able to grab a particle directly, as well as being able to connect a spring between the mouse and a particle, as well as having the mouse be able to repel any nearby partlces.

I recommend being able to draw all of the connections/forces. Especially the spring connections.

You will probably get this to work first with an Euler Integrator. You should design things to try out other integrators, such as Runge-Kutta 4, adaptive Euler, or a predictor/corrector method.

Here are some things you should be able to do:

1. make a "soft" object by taking some particles and connecting them with a lattice of springs. the simplest is a triangle. throw the object around and watch it bounce off the walls and jiggle.
2. make a fountain of particles - use repulsion to make a "fluid". the stream of the fountain should wind up in a puddle of particles at the bottom. (use damping to make sure that things don't explode)
3. make a swinging rope or chain. connect a line of particles to their neighbors, and nail the top on in place. (use a little damping to prevent explosions)

At this point, everything should be either very springy or very damped, since you are still using simple integration methods.

Phase 2: stiff systems

In this phase of the project, we'll improve on what you did in phase 1 by implementing better integrators.

Make a chain of 10-20 partcles, connected with springs and a little bit of damping. Nail the top one in place, and let this "rope" swing. Make a graph of the total length of the chain. Notice how it stretches and compresses. The ability to measure this stretching will be useful as we explore different integrators.

Try to raise the stiffness of the springs to prevent stretchiness. At some point, the equations will become too stiff and the string will explode.

Experiment with the tradeoff between stiffness and timestep.

Implement at least 3 explicit integrators (for example, Euler, RK4, and Predictor Corrector).

Implement an implicit euler's method (as in Baraff and Witkin). Because the system is so small (its only 10-20 particles), you need not worry about their efficiency tricks for large sparse linear systems. Once you have an implicit solver, a semi-implicit solver should be easy (use explicit solution of the springs and gravity, and implicit solution of damping - as in Bridson&Fedkiw).

You now have the ability to experiment with the various tradeoffs in creating a stiff piece of string. It should be the case that with better integrators (like implicit), you can take larger time steps, but each time step takes longer to compute. An implicit solver might allow you to take timesteps that at 100 times bigger than an explicit solver, but it might take 200 times longer to compute (in which case, its probably better to do 100 explicit steps).

For this part of the assignment, you need to report on what you find. What are the tradeoffs? How much better are different solvers? Is implicit necessarily better than explicit? Is one RK4 step better than 4 euler steps (which should be approximately the same amount of computation).

What you will turn in

You will prepare a web page describing you assignment, complete with pictures of what your program looks like and a description of its features and user interface. Be sure to detail all of the integrators that work, and all the types of forces that the user can create. You should also document your file format for describing simulation initial conditions.

You must also write a report (either in html or a pdf) that is linked to this page describing your experiments and results for phase 2. Describe how to maximize stiffness, minimize damping, and maximize performance. What are the tradeoffs? Be as detailed as possible.

Wherever possible, provide quantitative details. And, be sure to discuss how what you find compares with what you would expect to find.

Also, consider the computational costs. At what point would it be useful to switch to a sparse linear solver? how would the size of the system that you were simulating effect the choices in integrator?