Assignment #3: Rigidbody Collision Processing
Due date: Sun, April 1 (before
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
- RigidImageSimulation is
access point which accepts two arguments specifying the image to
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
- 'j' : Jiggle--applies random accelerations to objects.
- 'e' : Export frames toggle.
As before, the starter code will compile and run using JDK 1.5 or
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
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:
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).
- 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
spring so you can have an inelastic collisions. Add your contact
parameters to the Constants class.
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.
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.
- 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.
Improve mouse picking and
dragging: Use your
narrow phase test to improve the mouse picking to select a (nearby)
on the object rather than just its center of mass.
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.
- 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.
Pin constraint and rigid
boundary: (a) Implement a pin constraint by implement
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.
Gravity: Implement a
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.
- 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.
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
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
Artifact!: One of the best parts of computer animation is creative use of mathematics and computer programming. Create! Use your imagination to create
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.
- web.tga (3 rigid bodies): Simple test
image #1 (default image in RigidImageSimualtion)
- snowflakes.tga (15 rigid bodies--more like 3):
- mario.tga (167 rigid bodies): A more
complicated scene involving solid images that stress out the narrow
(272 rigid bodies): An interesting scenario for
narrow and especially broad phase collision detection.
(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.
Include videos of
your work, and also please
include one still image that represents your most interesting
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
- Dumping frames:
animations (the big ones) you should
export frames using 'e' (frames are written to the "frames"
Hand-in using CMS: Please
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.