Robust Collision Processing
(a.k.a. "The Spaghetti Factory")
TA: Steven An
Due date: Sun,
Mar 16, 2010 (before
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.
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
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
1. SymEuler velocity update using forces (gravity, springs, penalty,
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].
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
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
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
5. Verifying nonoverlapping edge-edge
pairs is done for you: prior to drawing each frame we test
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
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
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
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
Factory Contest (best results from Spring 2009 and 2010):
(Email png image of nonoverlapping simulation to firstname.lastname@example.org
||Mar 17, 2010
||Qin Chen/Manolis Savva
||Spencer Perreault/Kyle Johnson
||Caleb Johnston/Terry Haruguchi
||Mar 19, 2010
||Qin Chen/Manolis Savva
||Joann Luu/Fei Han
||Joann Luu/Fei Han
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
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
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
broad-phase collision processing: All-pairs collision testing
will quickly become bottleneck for simulations with several hundred (or
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.
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
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
- 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
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
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
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
Hand-in using CMS: Please
written report (in txt or PDF format) describing your approach and any
findings, in addition to your
implementation, and creative simulation artifacts, videos,
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.
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
- 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
Doug James, February 2010.