CS 5643 Assignment #2
 
Robust Collision Processing
(a.k.a. "The Spaghetti Factory")

Professor:
Doug James
Due date: Wed, Mar 27, 2013 (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 <3 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.


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


Starter Code (cs5643.particles): This project starter code (which extends the functionality of the first assignment) is available via CMS (do not distribute). Please see the first assignment webpage for basic information on
software dependencies and video generation.


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. Creative Artifact (20%): Given a robust collision processing implementation, you will be able to animate many more interesting systems than in assignment #1. 
Use your imagination to make something clever/interesting that also shows off your system's functionality.  Try animating a physical contraption, build an interactive game, add forces to model a phenomenon, or try adding controllers to your objects to make them behave like virtual characters, etc. Continuous collision detection is also great for animating high-speed objects such as projectiles, explosions, ballistic sports, and racing effects. By breaking springs, you can approximate fracture effects, e.g., to shoot a bullet through a 2D balloon or smash some uncooked spaghetti. If you are very ambitious (and slightly crazy) you might be consider implementing cloth in 3D, however robust collision processing will be much harder and given the time constraints it might be better suited for a final project.


7. 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  djames@cs.cornell.xxx 
for inclusion)
Rank
#Spaghetti
Submitter(s)
Date
#submissions
Still Image
1 1019 Jacob Roberts/Sam Park Mar 31, 2013 2 2013JacobRobertsSamPark_1019.png
2 835 Michael Flashman/Tianhe Zhang Mar 29, 2013 1 2013_mtf53_tz249_835.png
3 776 Jacob Roberts/Sam Park Mar 28, 2013 1 2013JacobRobertsSamPark_776.png
4 733 Pramook Khungurn Mar 27, 2013 1 PramookKhungurn_733_Mar27-2013.png
5 727 Chun-Po Wang Mar 17, 2010 1 cw522.png
6 644 Wenzel Jakob Mar 6,2009 2 Wenzel_Jakob-2.png
7 518 Qin Chen/Manolis Savva Mar 6,2009 2 qc32_mss86-2.png
8 430 Spencer Perreault/Kyle Johnson Mar 11,2009 1 SK-1.png
9 409 Donald Holden Mar 8,2009 2 Donald_Holden-2.png
10 311 Caleb Johnston/Terry Haruguchi Mar 19, 2010 1 cs5643p2_contest_cjj37-th435.png
11 293 Qin Chen/Manolis Savva Mar 6,2009 1 qc32_mss86-1.png
12 234 Wenzel Jakob Mar 4,2009 1 Wenzel_Jakob-1.png
13 201 Alexander Yuan Mar 8,2009 3 aey4-3.png
14 158 Alexander Yuan Mar 7,2009 2 aey4-2.png
15 140 Donald Holden Mar 7,2009 1 Donald_Holden-1.png
16 106 Ben Humberston Mar 3,2009 1 Ben_Humberston-1.png
17 79 Prof. James Feb 18,2009 1 00079_djames_export0-05217.png
18 64 Dr. Hypercube Feb 18,2009 1 00064_hypercube.png
19 52 Joann Luu/Fei Han Mar 9,2009 2 BettyCrocker-1.png
20 19 Joann Luu/Fei Han Mar 6,2009 1 BettyCrocker.png
21 12 Alexander Yuan Mar 3,2009 1 Alexander_Yuan-1.png


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, and creative simulation artifacts, 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, or divx, 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.  


References:


Copyright Doug James, March 2013.