CS 5643 Assignment #3
 
Rigid Body Contact
Professor: Doug James
TA: Steven An

Due date: Sun, Apr 11, 2010 (before midnight).

In this assignment you will implement a 2D rigid-body system with broad and narrow phase collision detection and velocity-level contact resolution based on a projected Gauss-Seidel complementarity constraint solver.  The starter code provides you with a simple frictionless penalty-force 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 image-based simulation scenarios, such as towers of stacked rigid blocks.

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


Starter Code (cs5643.rigidbody): This project has significant starter code, primarily to support rigid-body dynamics, all-pairs penalty-based contact, image-based scene construction, and OpenGL rendering. It is available via CMS. In this assignment, you will modify this package as needed. Feel free to borrow code from your previous assignments, but all code used should be your own.
 Assignments Steps: Here are the steps you need to address, most of which involve modifying the CollisionProcessor object to support narrow and broad phase tests:
1. Rigidbody dynamics are mostly implemented, but some minor things are missing such as rotational dynamics. As a first step in familiarizing yourself with the code,  add torque in RigidBody.applyContactForceW(Point2d contactPointW, Vector2d contactForceW) to make the objects spin; you can do this by taking the z-component of the cross product of the xy-plane force and relative position, i.e., the triple scalar product, zHat-dot-(x-p)-cross-force. Also, finish implementing the Symplectic Euler integrator so that it works. (You can find both parts by searching for "TODO")

2. Narrow phase collision detection: Even with only a couple letters, e.g., web.tga, collision processing is slow due to both the small time-steps used and the naive all-pairs collision processing, i.e., each boundary Block on object "i" is tested against every boundary Block on object "j" for overlap of their bounding disks.  Your first step is to acclerate object-object collision detection of overlapping Block/Disk primitives, and thus speed up the penalty-based simulator. You could do this in various ways.  First, you could build a bounding volume hierarchy on each RigidBody's Block primitives, with the most natural hierarchy for Block primitives being one with axis-aligned bounding boxes (an AABB tree).  Be careful that the bounds contain the support of any disk-like penalty forces, etc.  Build the narrow phase data structure in each object's RigidBody constructor.
3. Velocity-level contact solver:  The main part of this assignment is the implementation of the velocity-level complementarity constraint solver.  You will implement the project Gauss-Seidel solver for the nonlinear complementarity problem discussed in class [Erleben 2007].  The steps you need to pursue are as follows:

4. Challenge #1: "Stacks and other structures"   Large stacks of objects and other statically stable structures can be a challenge for the PGS solver, and therefore make interesting test cases.  I have made a number of these test cases for you. Good friction forces are particularly important given that contact geometry is modeled using disk-disk contact.

Include videos of your most realistic stacking scenarios as indicated by "YES" in the "Include Video" column.

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
 no
tower50.tga
 51
 A 50 brick tower
 no
tower100.tga
 101
 The largest tower---100 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...




5. Challenge #2:  "The Jelly Bean Factory"   Once your simulator is working and ready for a bigger challenge try running the Jelly Bean Factory images:

images/jellyBeanFactory.tga         [contest image]
images/jellyBeanFactory_half.tga    [easier]
images/jellyBeanFactory_quarter.tga [easiest]

The "Jelly Bean Factory" will start automatically.  Use the low resolution images (quarter or half) for practice before tackling the full-resolution contest image (jellyBeanFactory.tga).

The goal of the contest is to fill up the jelly bean as much as you can, which means using friction to help you heap the beans into a big cone-shaped pile.  Don't worry if some slide off the sides.  Keep the beans from interpenetrating too much, or it won't look realistic---not to mention that the disk-disk contact model will start to break down and generate bad normals.

"Room for resting beans only, please.": To make it extra challenging, your friction forces need to keep as many of your beans from moving as possible. That means no implausibly sliding, jittering, or chattering beans---these aren't coffee beans!  The simulator will track how many beans are resting at any time (nResting), and the historical maximum (nRestingMax).  It will also estimate a not-so-robust height of your resting jelly bean pile (Pile Height) and its historical maximum (Best Height).  Good luck!

No cheating:  Do not modify the Jelly Bean Factory code, or your contest submission will be void.  Also, you are not allowed to simply set the velocity of beans to zero (which will void your submission).  You must rely on the same general-purpose projected Gauss-Seidel (or better) complementarity-based velocity-level contact solver used in all examples.

OCD Distinction!  One more thing... if you can achieve a plausibly impressive >256 resting jelly beans using your frictional contact solver, then you will attain the impressive OCD Distinction. This will be hard. Very hard. No one has even done it before. Heck, they won't even fit in the jar. Come to think of it, it's probably not even possible. You might as well not even try...

Jelly Bean Factory Contest (Best results from Spring 2009):
(Email png image of simulation to  stevenan.cornell.xxx  for inclusion)
Rank
 #RestingMax
 #Beans
 Best Height
 Submitter(s)
 Date
 #submissions
 Still Image
1 332 407 0.61 Perreault & Johnson Apr 6, 2009 2 sdp63_krj32_3.png
2 331 427 0.64 Chen & Savva Apr 5, 2009 1 mss86_qc32_2.png
3 331 407 0.61 Perreault & Johnson Apr 6, 2009 1 sdp63_krj32_2.png
4 281 373 0.57 Wenzel Jakob Apr 5, 2009 1 waj23_2.png
5 270 346 0.51 Chen & Savva Apr 5, 2009 1 mss86_qc32_rest270.png
6 260 360 0.52 Wenzel Jakob Apr 5, 2009 1 waj23_1.png
7 230 330 0.45 Chen & Savva Apr 2, 2009 1 mss86_qc32_0.png
8 153 241 0.39 Mora & Chen Apr 6, 2009 1 mc462_awm25_1.png
9 130 202 0.49 Luu & Han Apr 5, 2009 1 jl2394_vh64_1.png
10 126 290 0.54 Dr. Penal T. Bounce Mar 12, 2009 1 PenalTBounce.png
11 99 299 0.68 Perreault & Johnson Apr 1, 2009 1 sdp63_krj32_1.png
350 (penalty-based solver) 654 0.73 Bryant Williams Apr 5,2009 1 bryant_1.jpg

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 velocity-level constraint solver working, you can collide detailed objects together efficiently and your bottleneck will shift to the all-pairs 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, kd-trees, 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 time-step 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 sphere-sphere check (using a quadratic-root finder and range check) can help you find those high-speed 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 time-stepping, 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 quasi-static examples, such as stacks, but it can also be useful for less contrived examples. One challenge is establishing contact-contact 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 resitution model.

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

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.   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 720-by-720 (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 2010.