| CS 5643
Rigid Body Contact
Professor: Doug James
Due date: Sun, Apr 16, 2013 (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.
Letters with fixed ground plane.
structure. Use friction to keep him steady or he'll do the mambo.
& Hardy" seesaw example. Watch out for interpenetration.
||A 10 brick
||A 25 brick
||A 50 brick
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.
stacked wall with reducible A matrix.
||Sparsely stacked wall with reducible A matrix.||no
||Sparsely stacked wall with reducible A matrix.||no
stacked wall with reducible A matrix. The largest example.
stacked wall with irreducible A matrix.
stacked wall with irreducible A matrix. The largest example.
||168||A more complicated scene involving solid images.||no
||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
||Nasty case for
broad and narrow phase collision detection due to one huge object
containing many other objects.
||It snows in Ithaca occasionally.||no
|Please submit student images for
|5. Challenge #2:
"The Jelly Bean
Once your simulator is working and ready for a bigger
challenge try running the Jelly Bean Factory images:
images/jellyBeanFactory.tga [contest image]
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.
|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 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 restitution model. Note that this only involves modifying the right-hand 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.
Mass-Splitting Jacobi: Swap out the Gauss-Seidel solver, and try the new modified Mass-Splitting Jacobi iteration of [Tonge et al. 2013]. It may produce better results in some scenarios, especially if you do not use shock propagation.
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).
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.
Copyright Doug James, March 2013.