CS 348C
Assignment #1 Robust Collision Processing (a.k.a. "The Spaghetti Factory") Professor: 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. Groups: 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)

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."

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:

(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. |

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.

- "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.

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.

References:

- Robert Bridson, Ronald P. Fedkiw, John Anderson, Robust Treatment of Collisions, Contact, and Friction for Cloth Animation, ACM Transactions on Graphics, 21(3), July 2002, pp. 594-603.
- Witkin, A., and Baraff, D., Eds. 2001. Physically
Based
Modeling: Principles and Practice. Course Notes. ACM
SIGGRAPH '01.

Copyright Doug James, September 2017