CS 567 Assignment #3: Rigidbody Collision Processing
Professor: Doug James

Due date: Sun, April 1 (before midnight).

In this third assignment you will implement broad and narrow phase collision detection for a 2D rigidbody system, modifying a skeleton interactive program as needed. Your goal is to simulate large 2D rigidbody systems input from

Starter Code (cs567.rigidbody): This project has significant starter code, primarily to support rigidbody dynamics, image-based scene construction, OpenGL rendering and a skeleton all-pairs support for collision processing to get you started. It is available here, with online Javadoc documentation here. In this assignment, you will modify this package as needed and however you like. Things you might want to tinker with are simulation parameters, color schemes, mouse/keyboard controls, exception handling for neural input device, etc.

• RigidImageSimulation is the main() access point which accepts two arguments specifying the image to simulate (in uncompressed TGA format), and true/false to enable collision processing. You'll also find all keyboard and mouse controls in this object; a summary of default key assignments is as follows:
  
• SPACE : toggles simulation.
• 'r' : Resets simulations, and pauses it.
• 'w' : Toggles wireframe rendering.
• 'b' : Toggles Disk bounds rendering.
• 'l' : Toggles between single and multiple Euler steps per frame.
• 'j' : Jiggle--applies random accelerations to objects.
• 'e' : Export frames toggle.
  

• Software Dependencies:  As before, the starter code will compile and run using JDK 1.5 or later. I recommend you get Sun's latest JDK here. In addition to Java the starter code also uses JOGL/OpenGL and Vecmath familiar from previous assignments.  Although you're welcome to modify the OpenGL portion of the assignment, it is not necessary to complete it.

• Performance Profiling: In addition to timing your broad and narrow phase collision times, you can use the  "java -Xprof ..."  option to help identify and remove program bottlenecks (currently used in r.bat).

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. Penalty contact between two Block objects is currently implemented for you using a simple undamped spring. Familiarize yourself with how contact is done, and perhaps clean up the code to suit your taste--you might want to pull the contact model out of the narrow phase code.  Add damping to the spring so you can have an inelastic collisions. Add your contact parameters to the Constants class.
   
• Setting the spring stiffness can be a pain with penalty methods, since they may not be stiff enough to handle all cases, and making them too stiff complicates the numerics. Note that the current spring stiffness incorporates the effective mass of the object-object interaction, so that it's actually more like an acceleration parameter: light objects will use softer springs, whereas heavier objects will use harder springs. This helps a little to avoid too much stiffness  when you don't need it, say in ballistic simulations. However, big stacks of objects can require stiffer springs, especially when you have an elephant on a pile of tiny blocks.  You'll need to adjust your contact model to make it work in all examples. Taking tiny time steps is fine.
  
• Other contact models (optional): If you're daring, feel free to not use penalty contact. For example, you might try a impulse formulation that filters velocities to satisfy contact constraints. You might also try to detect collision times more accurately using continuous collision detection.
  
2. Rigidbody dynamics are mostly implemented, but some things are missing. Familiarize yourself with that code. You'll need to add a 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.
3. Narrow phase collision detection: Even with only a couple letters, e.g., web.tga,  contact processing is slow due to naive all-pairs collision processing---each Block on object "i" is tested against every Block on object "j".  Fix this by building a bounding volume hierarchy of your choosing on the Block/Disk primitives, e.g., you might build a tree of bounding Disk objects. Alternately you could build a body-frame spatial subdivision--reusing code from part 4.
• Only boundary blocks needed: As an additional speedup, you might only use blocks that are on the boundary of the rigid object, so that you don't waste time culling internal Blocks that will not be in contact. This will save you a lot of work if you have large images or solid regions in your scene, e.g., mario.tga.
  
4. Improve mouse picking and dragging: Use your narrow phase test to improve the mouse picking to select a (nearby) point on the object rather than just its center of mass.
5. Broad phase collision detection: Once you have an efficient narrow phase processing, you can collide objects together efficiently and your bottleneck will shift to the all-pairs broad phase test. 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 hash ing schemes, hierarchical grids (better performance on variable object sizes), octrees, kd-trees, as well as sweep and prune. If you've already implemented one of these before, try a different one for something new.
   
6. Pin constraint and rigid boundary: (a) Implement a pin constraint by implement RigidBody.setPin(boolean enable), and having RigidBody.advanceTime(double dt) ignore forces, and not change the position/velocity state. (b) add a rigid boundary to the unit computational cell using a pin constraint: create a set of Block objects that tile the cell boundary, and use them to create a RigidBody, and then call setPin(true) on it. Voila!
   
• Aside: Another way (although not the best way) you can impose a pin constraint is to effectively set the mass/inertia of the object to a very large number--don't forget the old values though.
  
• Aside: Similar to a pin constraint, you might want to weld rigid objects together so that they behave as one, allowing you to build things.
• Aside: One problem may be that the input image is sized too close to the unit computational cell. You may need to resize things slightly.
  
7. Gravity: Implement a simple Force object for gravity so that objects can fall down onto the boundary, etc. Again, you may need to adjust your penalty stiffness to make it work with large stacks of objects.
   
8. Test Images: I've included a number of helpful test images (see zip for image credits), with the first two working with collisions "out of the box." These are uncompressed TGA images, with empty space specified by white (255,255,255) colors.
   
• web.tga (3 rigid bodies): Simple test image #1 (default image in RigidImageSimualtion)
  
• snowflakes.tga (15 rigid bodies--more like 3): Simple test image #2
  
• mario.tga (167 rigid bodies): A more complicated scene involving solid images that stress out the narrow phase test.
  
• crossStitch.tga (272 rigid bodies): An interesting scenario for narrow and especially broad phase collision detection.
  
• clutter.tga (1554 rigid bodies): A highly cluttered scene from a New York Times op/ed on Stanley Kunitz. See if you can simulate this one!  Where is your bottleneck???
  
• How much more complicated/interesting an example you can simulate?!?  Try posting particularly interesting or challenging images to the course group.  
9. One Creative Artifact!: One of the best parts of computer animation is creative use of mathematics and computer programming. Create! Use your imagination to create something really interesting. Modify the starter code in any way you want. Image editing should make it easier to build scenes. Try making a game by adding interactive keyboard/mouse controls. Try to build an interesting contraption, pinning objects in space, adding thrusters, or other special controls.  Add scrolling to fly along a long corridor. Try connecting rigid bodies using springs, or joints. Go bananas. Submit a video showing your creative artifact, either shot using FRAPS, or other utilities.
   
• Dumping frames: For slower animations (the big ones) you should export frames using 'e' (frames are written to the "frames" subdirectory). 
  
10. Include videos of your work, and also please include one still image that represents your most interesting scenario.

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, and understand what you are writing. 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.)

Hand-in using CMS: Please submit a short write-up (detailing what you did, your findings, and who you discussed the assignment with, etc.), as well as your Java implementation, a creative simulation artifact(s), and videos of anything you want me to see, etc.

Enjoy!!!

Copyright Doug James, March 2007.