CS 5643 Assignment #1
Particle Systems

Doug James

Due date: Tuesday Feb 23 (by midnight).

In this first assignment you will experiment with particle systems, modifying a skeleton interactive program to add new behavior, and produce a creative artifact.

Work on your own, or in a group of at most two people. 
Plants modeled using a particle system [Reeves 1983]

Starter Code (cs567.particles): This project has starter code (zip), primarily to support OpenGL rendering and a simple Swing GUI. Online Javadoc documentation here. In this assignment, you will modify this package as needed.  The starter code uses 2D primitives and drawing calls for simplicity, however you can trivially convert it to 3D for more fun and to enable your creative artifact.

Software Dependencies:  The starter code will compile and run using JDK 1.5 or later. In addition to Java, the starter code also uses two other libraries that you need to install/get:
Assignments Steps [with suggested grade%]: The starter code allows you to build mass-spring particle systems, but is missing a number of features that you need to address:
1.  Implement Spring Forces [5%] Three spring forces currently do nothing:
and need to have their  apply_force()  function implemented.  The first two should use a damped Hookean spring (as in the Witkin course notes), whereas the second can use the bending force derived in class (here is a simple derivation of that bending force).  Following these implementations, your "Create Spring" and "Create Hair" tasks should have more meaningful results. 

2.  Implement Gravity and Viscous Damping Forces [5%]: Currently gravity and viscous damping are "hacked" into ParticleSystem.advanceTime(), and conflate integration and physical modeling. Implement some global Force objects,
and add these to the ParticleSystem (immediately after its construction) to properly apply these forces to all particles.

3.  Implement Numerical Integrators using Witkin's Interface [10%]: The current forward Euler implementation is flakey, and hard coded---it doesn't support proper abstractions to enable easy swapping in/out of different integrators. Implement an Integrator interface to provide support for the following integrators:
As discussed in Witkin's course notes, the ParticleSystem could implement an interface (perhaps called DynamicalSystem) consisting of the get/setState(), derivEval(), getStateN(), getTime()... functions.  However, you may want to modify your interface to accommodate the symplectic Euler/Verlet methods which treat position and velocity components differently.  The Integrator interface might abstract timestepping the system using a method such as Integrator.advanceTime(double, DynamicalSystem). Also, constraints and velocity/position filters (discussed below) may affect your design.  Document your choices.

Question: Given the same time-step size, which integrators are the least and most stable for very stiff hair?  Provide experimental evidence (data, videos, etc) to support your analysis.

Add GUI controls (e.g, radio buttons, or a list, etc.) to easily change the active Integrator implementation.  The time-step size is currently adjusted using the +/- keys, but you can optionally add that to the GUI too. 

3.  Pin constraints [10%] were implemented using a post-step velocity and position projection in the hacky integrator. Implement a Filter class to implement constraints using a velocity/state filter.  You will have to think about how to make your pin constraint filter play nicely with your various integrators. For example, using Symplectic Euler it is easy to apply a Pin constraint using a velocity filter before the position update, but not so for Forward Euler.

4.  Wall-particle collision detection and response (or "staying inside the box") [10%]: The particles are currently not constrained to stay inside the unit computational cell. Implement a simple scheme to detect collisions with the four walls, and (as in Witkin's course notes) filter the state to provide simple collision response, using a restitution coefficient to attenuate normal velocity (defined in Constants.RESTITUTION_COEFF). Similar to the Pin constraint filter, be careful how you update the particle velocity/position or you might find your particles sinking into the wall.
Generate a video demonstrating collisions.

5.  Particle-Particle Interaction Forces (or fluids, smoke, goop and glop) [30%]: Particles are very versatile, but many effects require more complex inter-particle forces.  In this step you will create a Force object that implements either
    (a) the Globular dynamics interaction forces of [Miller and Pearce 1989] or
    (b) Smoothed-Particle Hydrodynamics (SPH) fluid forces (see [Mueller et al. 2003]), or
    (c) a compelling particle-particle interaction model that is specific to your creative-artifact phemonenon. 
These short-range interaction forces avoid all-pairs O(N^2) computational costs, but require you to find particle neighbors within a short distance.  Implement a simple uniform subdivision scheme to enable efficient neighbor finding inside the applyForce() function.

6.  Creative Artifact [30%]:  Probably the coolest part of physically based animation is imagining and building creative artifacts that produce compelling and exciting imagery.  Use your imagination and animation system's functionality to animate something clever/interesting/beautiful/complex or somehow outstanding.  PLEASE don't be afraid to be bold and make necessary changes to enable your design. Suggestions:
  • Animate! The easy part of PBA is thinking of interesting things to animate: draping cloth, splashing water, particle-based flowers blowing in the breeze, massive explosions, kooky characters, abstract virtual worlds, or the largest bowl of Jello ever.  Be creative.  (If you are interested in a particular phenomena but don't know where to start or the background, just ask.)
  • Appearance modeling: How you draw your particles will greatly effect what you can achieve [Reeves 1983].  Consider (dynamic) particle appearance models for improved results, or build a surface mesh.
  • Go 3D!  There is nothing inherently 2D about this project. Go 3D by replacing your Point2d/Vector2d with Point3d/Vector3d, making minor changes to your OpenGL drawing code, etc.  Note you may wish to do this first... before implementing the whole assignment.
  • Design and animate procedurally: It can be tedious to manually create/draw and interact with your examples when they are complex.  Generating particles/springs/forces/etc procedurally, i.e., via functions or scripts, will allow you to create complex examples easily, e.g., recall Karl Sim's "Particle Dreams" animation, or Reeves models of plants (e.g., modeling grass with particles).
  • Build better tools: You may need special tools to create your artifact. That's a fun part of animation, too!
  • Run long jobs offline to simulate detailed examples and get the most out of your solver. It's amazing what you can do with just another million particles. Of course, you'll want to get it working on smaller examples first.
  • Create a compelling high-resolution still: An image can be worth a thousand words, or a billion particles. See if you can use your simulator to create a single captivating image that says it all.
  • Render frames using a 3rd-party renderer: Export 3D geometry (e.g., particle positions) and make a nicely rendered animation with a 3rd-party renderer, such as Yafaray or Blender.
    • For implicit blobby surfaces of particle-based fluids and goop, try using POV-Ray since it can render isosurfaces for unions of blobs directly---without you having to first extract triangle isosurface meshes.  Steven An made a simple water-like example for you here: (pov, png).
Submit your creative artifact.

Hand-in using CMS:

Start early. Ask questions. Have fun!!!

On collaboration and academic integrity: You are allowed to collaborate on the assignments to the extent of formulating ideas as a group, and derivation of physical equations. However, you must conduct your programming and write up completely on your own (or with your partner), and understand what you are writing. Please also list the names of everyone that you discussed the assignment with.  (You are expected to maintain the utmost level of academic integrity in the course. Any violation of the code of academic integrity will be penalized severely.)


Copyright Doug James, February 2010.