CS 5643
Assignment #3 Rigid Body Contact Professor: Doug James Due date: Sun, Apr 16, 2013 (before midnight). In this assignment you will implement a 2D rigidbody system with broad and narrow phase collision detection and velocitylevel contact resolution based on a projected GaussSeidel complementarity constraint solver. The starter code provides you with a simple frictionless penaltyforce simulator, and allows you to draw simulation scenarios and input them into your simulator as images. You will test the scalability of your simulator on various imagebased simulation scenarios, such as towers of stacked rigid blocks. Groups: Work on your own, or in a group of two people. 
Image
Name 
#Bodies 
Image 
Description 
Include
Video? (YES/no) 
lcp.tga 
4 
Default test
image. Letters with fixed ground plane. 
no 

balancingBlocks.tga 
12 
Classical
cantilevered beams. 
no 

delicate.tga 
37 
A delicate
structure. Use friction to keep him steady or he'll do the mambo. 
YES 

seesaw.tga 
5 
A "Laurel
& Hardy" seesaw example. Watch out for interpenetration. 
no 

tower10.tga 
11 
A 10 brick
tower 
no 

tower25.tga 
26 
A 25 brick
tower 
YES 

tower50.tga 
51 
A 50 brick
tower 
no 

tower100.tga 
101 
The largest
tower100 bricks. Keep it steady, and watch out for
interpenetration. You will need a lot of iterations for this
example. Shock propagation is helpful. Try knocking it down
once it's stable to make sure it's not just glued in place. 
YES 

wallSmallSparseLow.tga 
36 
Sparsely
stacked wall with reducible A matrix. 
no 

wallSmallSparseHigh.tga 
141 
Sparsely stacked wall with reducible A matrix.  no 

wallWideSparseLow.tga 
36 
Sparsely stacked wall with reducible A matrix.  no 

wallWideSparseHigh.tga 
141 
Sparsely
stacked wall with reducible A matrix. The largest example. 
YES 

wallWideDenseLow.tga 
33 
Densely
stacked wall with irreducible A matrix. 
no 

wallWideDenseHigh.tga 
131 
Densely
stacked wall with irreducible A matrix. The largest example. 
YES 

mario.tga 
168  A more complicated scene involving solid images.  no 

clutter.tga 
1554 
A highly cluttered scene from a New York Times op/ed on Stanley Kunitz. See if you can simulate this one without objects interpenetrating! Where is your bottleneck???  YES 

crossStitch.tga 
280 
Nasty case for
broad and narrow phase collision detection due to one huge object
containing many other objects. 
no 

snowflakes.tga 
16 
It snows in Ithaca occasionally.  no 

Please submit student images for
inclusion here... 
Jelly Bean Factory Contest
(Best results from Spring 2009, 2013): (Email png image of simulation to stevenan.cornell.xxx for inclusion)
Highlighted Video Submissions:
6. Other Things To Try: In order to simulate a very large pile of jelly beans, or make your castle destruction animation, you may find that you need a little more sophistication or other functionality. Here are some things to try: Broad phase collision
detection:
Once you have an efficient narrow phase processing and the
velocitylevel constraint solver working, you can collide
detailed objects together efficiently and your bottleneck will shift to
the
allpairs broad phase test for certain scenarios. You can implement any
broad phase collision
detection scheme provided it yields decent performance on the large
examples. Schemes you might consider are uniform spatial subdivision
and related hashing schemes, hierarchical grids (better performance on
variable object sizes), octrees, kdtrees, as well as sweep and prune.
Feel free to use your own code from the second (Spaghetti Factory)
assignment.
Adaptive Time Stepping: Given that contacts are detected using discrete collision tests, you may want to monitor the maximum Block speed to reduce the timestep size to avoid missing collisions. Continuous Collision Detection: High speed motion can lead to missed collisions or deep interpenetration when using the discrete collision checks. Implementing a continuous spheresphere check (using a quadraticroot finder and range check) can help you find those highspeed collisions and obtain better contact normals. Of course you still want to be able to handle interpenetration robustly. Exploiting temporal coherence: In addition to adaptive timestepping, you can exploit temporal coherence by reusing previous values from your PGS solve to "warm start" solutions at the next time step. This is particularly useful for quasistatic examples, such as stacks, but it can also be useful for less contrived examples. One challenge is establishing contactcontact correspondence between time steps. Restitution coefficient: The contact conditions derived in class impose a nonnegative normal velocity at contacts, however for new impacting contacts you may wish to impose an impact condition on the normal velocity based on a restitution model. Note that this only involves modifying the righthand side "b" of the linear system used for the contact conditions (see equation 22 of [Erleben 2007]). "Shock Propagation":
Stacking examples are particularly challenging for PGS, and shock
propagation techniques are commonly used to accelerate convergence or
provide more plausible approximate solutions [Erleben 2007]. Try
building a contact graph and using shock propagation to improve the
stability of your stacks, and achieve that extra special OCD
distinction.
Other
optimizations:
Erleben mentions various enhancements to improve the performance of the
PGS solver. Feel free to incorporate these into your submission.
Other forces: Feel free to add springs, joint constraints or other rigid body system elements to allow you to model more interesting mechanisms. MassSplitting Jacobi: Swap out the GaussSeidel solver, and try the new modified MassSplitting Jacobi iteration of [Tonge et al. 2013]. It may produce better results in some scenarios, especially if you do not use shock propagation. Handin 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. Provide videos to document any results you want us to see, any creative artifacts, and your best Jelly Bean Factory run, and your best stacking example runs. 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. Please submit videos with a fixed resolution of 720by720 (the default resolution). 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. You may not use code from the web. Please also list the names of everyone that you discussed the assignment with. 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. 