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


Copyright Doug James, March 2007.