CS 348C Assignment #1
Robust Collision Processing
(a.k.a. "The Spaghetti Factory")

Doug James
Due date:
Thu Oct 12, 2017 (before midnight).

In this assignment you will gain experience with robust collision detection and contact resolution for thin objects by implementing a simulator similar to the cloth system in [Bridson et al. 2002].  However, since you (and any partner) only have a couple weeks to complete your system, you will implement only a 2D version. In addition to creative artifacts, we challenge you to see "how high you can stack it" at the Spaghetti Factory before edge-edge interpenetrations occur.

Work on your own, or in a group of at most two people. 

Starter Code (cs348c.particles): This project starter code is available via Canvas (do not distribute) and provides basic functionality of a particle system.

You will modify the Symplectic Euler (SymEuler) integrator in ParticleSystem.advanceTime() to produce feasible particle velocities that resolve collisions and guarantee penetration-free position update. As documented in that function and discussed in class, the structure of the integrator step is:

  1. SymEuler velocity update using forces (gravity, springs, penalty, etc.)

  2. Velocity-level collision resolution (Gauss-Seidel-like iterative solver, ...)

  3. SymEuler position update (guaranteed interpenetration free)

Assignments Steps: You will extend the starter code to address the following steps:
1. Continuous point-edge collision detection: Robust interval-based collision detection of particle-edge intersections during the time interval (0, dt] is the core component of your system for resolving particle-edge collisions.  Here each edge is represented by a SpringForce2Particle object.  As discussed in class, you will detect the time of any first particle-edge collision event on the time interval (0, dt]. You will do this by

    (a) first determining any times of collinearity on (0,dt] by solving an appropriate quadratic equation, then

    (b) determining any contact location on the line segment, e.g., alpha on [0,1].

You will do this for all particle-edge pairs.  Be careful when implementing your interpretation of any root times, and the tests used to evaluate edge-intersection locations, e.g., the first root may lie on (0,dt] may not be on the line, etc. Be sure to implement these methods robustly, since the robustness of your overall simulator depends on them.

2. Velocity-level point-edge contact resolution: Given any point-edge collision event at time t* on (0,dt], you will apply a suitable impulse to resolve this collision.  As discussed in class, you will

    (a) evaluate the suitable collision unit normal (at collision time t*), then

    (b) estimate a suitable impulse amplitude (gamma) using the restitution hypothesis for a small near-inelastic restitution coefficient, e.g., epsilon = 0.01.
    (c) Use
inverse-mass filtering in your impulse formula to support particle pin constraints as necessary.

3. Iterative solver for resolving multiple collision interactions: Since more than one collision event may apply impulses to a single particle, the impulses may interfere with each other.  Using multiple passes through all particle-edge pairs (ignoring particles belonging the edge), apply collision impulses until all particle-edge pairs are collision free on the
(0,dt] interval. As discussed in class, note that this approach may be slow to converge for hard problems, or may even fail to converge. Also, the method assumes that no interpenetration currently exists, therefore you must strive to resolve all collisions, always.

4. Apply penalty forces:  Penalty forces will help separate objects thereby reducing the number of difficult velocity-level collision resolution problems that occur. Penalty forces will also allow you to model edge curves of a finite thickness, 2H;  
in your implementation, a typical offset value is H=0.01.  If the particle is within distance H of the line, you can apply a simple (damped) spring force with stiffness identical to the stretch springs (SpringForce2Particle). As discussed in class, velocity filters can be used to better model inelastic contact, and avoid applying penalty forces to separating particle-edge pairs.  See [Bridson et al. 2002] for related details. 

5. Verifying nonoverlapping edge-edge pairs is done for you:  prior to drawing each frame we test all edge-edge pairs for overlap. If overlap is detected, the simulation is halted (since future steps can not be expected to resolve collisions), and the background color is changed to red. "Game over."

6. Grand Challenge ("The Spaghetti Factory"): Clicking on the "Start Spaghetti Factory" button will reset the simulator, and initialize the SpaghettiFactory simulation object. See how many pieces of spaghetti you can simulate while avoiding interpenetration. Your resulting animations must be plausible---so no velocity filters that produce Peano curves of spaghetti, or incredibly bouncy spaghetti!  Feel free to modify simulation parameters (stiffness, timestep size, thickness) or add additional functionality to  achieve your best result. If you are a real simulation chef and you need even more spaghetti, you can try making the computational cell larger.

Submit the maximum number of spaghetti strands simulated, and a video documenting this simulation run.

Spaghetti Factory Contest (best results from Spring 2009 and 2010):
(Email png image of nonoverlapping simulation to antequ@cs.stanford.edu
for inclusion)
Still Image

8. Other Things To Try:  In order to simulate a very large pile of spaghetti, or make your killer animation, you may find that you need a little more sophistication or other functionality.  Here are some things to try:
Tips for robust simulation: 
Hand-in using CMS:  Please submit a
brief written report (in txt or PDF format) describing your approach and any findings, in addition to your Java implementation, images, videos, etc.   Provide videos to document any results you want us to see, any creative artifacts, and your best Spaghetti Factory run.  If you are working with a partner, be sure to form and submit your zip file as a group. 
Submit videos in a portable format such as QuickTime, mpg, but not native formats, e.g., not the FRAPS codec for your machine. 

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. Do not contact previous spaghetti contest chefs for their secret recipes!  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, September 2017