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)

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) Rank #Spaghetti Submitter(s) Date #submissions 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:

• Efficient broad-phase collision processing: All-pairs collision testing will quickly become bottleneck for simulations with several hundred (or more!) edges.  You can use space-time bounds to quickly cull many of these brute-force tests. If you are lucky enough to robustly simulate very large spaghetti results, you may want to implement a broad phase collision detection scheme, such as a simple uniform subdivision scheme. Even if you don't you a fancy broad phase test, building space-time bounds on the edges and particles can lead to a fast rejection test that avoids testing all particle-edge pairs. (PS: Don't forget to update the code that verifies the nonoverlapping edge pairs (in part #5 above) so that your code still runs fast).   
  
• Handling particle-particle interactions: So far you have implemented particle-edge collisions, but not addressed individual particles. Implementing an impulse-based continuous (interval-based) collision detection for particles with some nonzero radius, H, can support particle-particle interactions.  A side benefit is that it can also help keep particles from slipping between edges due to floating point error if you find that happening. Watch out that it does not make your spaghetti too bumpy.
• Rigid impact zones: If your Gauss-Seidel-like iterations fail to converge even after adding penalty forces, and tuning your algorithm and parameters, you may need to be more agressive.  You can improve robustness by implementing rigid impact zones as in [Bridson et al. 2002].  These rigid velocity filters can provide a "fail safe" to avoid interpenetration when the iterative collision solver fails to converge after a large number of iterations.  Use sparingly, however, since rigid regions can grow to become large, will eliminate interesting deformable dynamics, and your system may get stuck in a semi-rigid state which---like eating a mouthful of uncooked spaghetti---can be unpleasant :(
• Friction can be approximated using the impulse-based approach described in [Bridson et al. 2002], wherein the magnitude of a tangential motion-opposing impulse is determined using a simple formula based on the friction coefficient mu and the current normal impulse value.
• Inextensibility constraints: Unlike the default mass-spring fibers, real spaghetti does not stretch very much (before it breaks). You can try to limit strain using a velocity filter, e.g., limiting strain after 10% stretching. When and where you use the filter requires some thought to avoid interpenetration artifacts.

Tips for robust simulation: 

• "What ever can go wrong will go wrong" may seem like it applies here.  Make sure that your quadratic root solver and point-edge collision detector is "bullet proof."  Make sure you plan for divide-by-zero errors, special cases of zero-length edges, particles at edge vertices, numerical degeneracies, etc.  These "rare" one-in-a-million problems have a way of being not being so rare when you're resolving millions of collisions.  Keep in mind that these problems may also be symptoms of problems in the calling function, or the implementation's approach.
• Throw an Exception when you encounter numerical problems. Locating numerical artifacts and understanding when/where they occur can be difficult.  Throwing exceptions can help you debug your simulation code, and make it more robust.
• Watch out for infinite loops that can result from poor iterative solver convergence, contact states resulting from rigidification, etc. 
  
• Don't forget post-deformation updates during collision processing when using a broad-phase collision detection acceleration structure. Each impulse you apply can change the space-time bound of the contacting edges, and the bound may now overlap with other bounds it did not previously. Make sure your collision detection data structures are updated conservatively during the iterative collision process or interpenetrations may occur.  
  
• Use double precision floating point computations everywhere.  Be wary of rounding errors that may produce seemingly inconsistent results, e.g., code A says the particle never crosses the line, but code B says the particle path intersects the line.
  
• Think about what is happening, and try to make good engineering decisions.  For example, "why is it that the particle pops through the edge-edge vertex when I pull very hard on it."  Some problems may be more difficult to debug, e.g., why if I have resolved all the collisions do they overlap at the next time step? Try to avoid problems before they occur.
• Strive for correctness instead of speed.  In this assignment you will receive grades for correctness, and not the speed of your simulator.  You can always make your code faster after it works.  While you do need to have some nominal performance to simulate a really large pile of spaghetti or to make an interesting and complex animation, it is far more important to resolve collisions robustly and correctly.  Simple optimizations may be helpful but are not required, e.g., ignore particle-edge collision tests for when all three particles are fixed.  Also, use the JVM's -server option.