COMP 599 - Winter 2010 - Assignment 2
Robust Collision Processing

Due 23:39 pm Tuesday February 16

Getting Started

In this assignment you will implemnet robust collision processing, similar to the cloth system in [Bridson et al. 2002]. For simplicity, your implementation will be in 2D, and will in many respects extend the code you worked on in assignment 1 (see the notes on provided code below). In addition to creating a video of something interesting, you are invited to take part in the "alphabet soup challenge" to see how many letters you can simulate before edge-edge interpenetrations occur.

Sample Code

Download the provided code from WebCT (do not distribute). The code has two main packages, similar to the previous assignment. Note that the tools package has minor updates, so you will want to make sure you use this one. The a2 package contains code which is very similar to the first assignment except for a few notable differences
  • now implements a symplectic Euler step in update particles, and does not make use of the Integrator interface from the previous assignment.
  • implements a variety of test systems that will help you debug and stress-test your code. Feel free to add your own test systems too, though note you can also do this on the fly using mouse clicks.
  • implements a joint spring between three particles, which is useful for creating long 2D strings which hold their shape (for instnace, letters).
  • is used by TestSystem to generate mass spring systems from fonts.
  • is used by the application to test for edge-edge collisions, that is, a discrete collision detection test. If collisions are found, the background turns red and the simulation is stopped (i.e., game over).

You do not need to change anything except and optionally if you want to hard code additional test cases or special scenarios. Be sure to leave a comment in your readme.txt on any additional test cases you add, or other modifications outside of the code.

The setup for jars and libraries is the same from the previous assignment. Consult the A1 page for more information. Likewise, you may also want to visit the previous assignment specification for instructions on making videos.

Steps and Objectives (5/5) * 95%

This assignment contains two main parts. First is the continuous collision detection for points and line segments. Second is the response to collisions. You will need to modify the symplectice Euler step in the updateParticles() method, which advances the system by the given time step h. As discussed in class and documented in the method, this method does the following:

  1. Symplectic Euler velocity update using forces from springs, gravity, etc.
  2. Velocity-level collision response (iterative solve)
  3. Symplectic Euler position update (guaranteed intersection free)

Both main parts of the assignment are concerned with step two listed above (i.e., the velocity-level collision resolution).

  1. Continuous Collision Detection

    Perform robust interval-based collision detection of all particle-edge pairs during the time interval (0,h] for the given step size h. The edges defined by Spring objects connecting particles. As discussed in class, you will do this by doing the following

    • Given the particles are moving on linear trajectories specified by their position at the current time and their velocity, find all times of co-linearity on (0,h] by solving the appropriate quadratic equation.
    • determine the contact location on the line segment, for instance, as a parameter alpha in [0,1].

    Note that some roots will give you a situation where the particle is not on the line segment. You should go through the roots in the interval (0,h] in ascending order, and then process only the earliest collision you find.

    Note also that your root finding needs to be robust! You may need to add epsilon checks for the alpha parameter you compute, and it may also be beneficial to check roots that happen just after h (i.e., h plus some small time based epsilon).

    A quick way of testing this part is to pin the three particles involved in a collision each time you find a collision in the interval (0,h]. You should make a very short movie to demonstrate this objective and to show your progress.

  2. Collision Impulses

    When you find a collision on (0,t], you must apply an appropriate impulse to the particles involved to resolve the collision. As discussed in class, this involves the following.

    • Computing a suitable unit normal for the collision (at the time of collision),
    • Computing a suitable impulse using a small near-inelastic restitution coefficient (e.g., the default value which is set for you in the interface).
    • Updating the velocities of the particles given the impulse, and using the assumption that pinned particles have infinite mass (i.e., in computing the impulse and distributing the impulse to the 3 particles).

    You may find it useful to temporarily setting the restitution value to 1 (or other values using the slider) to help debug your velocity impulses.

  3. Iterative Solve

    Many particles and edges may be colliding in a given time interval. You will want to sequentially check all particle-edge pairs, and immediately after each check you should apply the collision impulses you compute in the previous step. You should continue through all the pairs in this manner, but note that there may still be collisions on the interval (0,t] after processing all pairs as some particles may be involved in multiple collisions. As such you'll need to iterate over all pairs until you have resolved all collisions on (0,t]. As discussed in class, this may be slow to converge. It is a good idea to give up after a some maximum number of iterations, and return false to report the problem and halt the simulation.

  4. Penalty Forces

    Penalty forces can help keep objects separate and reduce the number of difficult velocity-level impulses that need to be applied. The penalty forces will let you model edges as if they had a thickness of 2H. A default thickness of 2 pixels is set for you in the user interface controls. So, as discussed in class, if a particle is within a distance of H of a line segment, then apply a simple spring force impulse with stiffness identical to the stretch springs. see also [Bridson et al. 2002] for more details.

    For your simulation to run smoothly, you'll likely need to address particle-particle penalty forces, i.e., forces when alpha falls just outside of [0,1].

  5. Interesting Video

    Record a sequence of something interesting or amusing. Note that you can create particles by clicking with the mouse, and you can also pin and unpin particles by clicking them. So experiment, have fun, and make a movie of something creative and interesting.

  6. Optional: Alphabet Soup Challenge

    How many letters can you simulate before the soup goes bad? Post your successes to WebCT, and the final results will be also added to this page for posterity. Note that simulation parameters must be reasonable (no extra bouncy collisions).

  7. Optional: Extensions

    You might optionally like to think about the following issues.
    • Frictional contact is generally a hard problem, but there exist many good models for friction during impact. For impacts, you may want to read about what Bridson suggests as a straightforward way to apply impulses opposing tangential motion.
    • The iterative solver can fail to converge, even after adding penalty forces. You can improve robustness and find solutions in these difficult cases by using rigid impact zones as described in [Bridson 2002]. This effectively acts like a velocity filter and provides a "fail safe" to avoid interpenetration when the iterative solver fails. There are drawbacks, however, as rigid zones can be large and will eliminate interesting deformable dynamics.
    • As particle numbers increase, the all particle-edge pair collision test becomes quite expensive. Space time bounds can be used to cull many root finding tests, but you could also consider a "broad-phase" collision detection scheme, such as a uniform grid subdivision of space.
    • You may like to think about the complexities of moving this simulation to 3D. For instance, the modifications would include: both particle triangle tests and edge-edge tests, robust solution of cubic polynomials, robustly testing point in triangle. A nice aspect of [Bridson et al. 2002] is also the subdivision surface refinement of the 3D cloth, which gives very smooth results for coarse cloth simulations.
Some tips for robust simulation. Watch out for all special cases as they will happen once you are running large simulations. If you are dividing, you can probably be sure that the denominator will be zero in some cases (and you should deal with these cases differently). Use double precision floating point. Use epsilon checks to make your code robust to floating point error. Finally, strive for correctness instead of speed.


Written Questions (1/1) * 5%

The written question is available as a PDF download.

Prepare a pdf file with your answer to this written question (scanned hand written document, or generated with latex, openoffice, or otherwise) and submit it along with your assignment via webCT.


Great! Submit your source code and two xvid encoded videos as a zip file via webCT. Include a readme.txt file with any specific comments. Also be sure to include a pdf with your written answer (i.e., scans of handwritten work, or typeset). Your readme should provide a list of people with which you discussed the assignment, or state that you did discuss the assignment with anyone.