Assignment 3: Rigid bodies

Due: XXXXX

Starter code: Download

Overview

The purpose of this assignment is to become comfortable with simulating impulse-based rigid body systems, including broadphase and narrowphase collision detection, collision and contact resolution, and friction. You will be given partial code for a small, open-ended physics-based game in which the player loads towers of blocks from files, then fires balls at them in order to destroy them. The code is incomplete in many ways. The following parts are missing:

For all but the last of these parts (as well as other parts), unit tests have been provided. Initially many of these unit tests will fail; it is your job to implement the missing functionality so that they pass. It's strongly suggested that you implement the parts in order, as later unit tests may depend on the functionality provided by earlier unit tests. Note that passing the unit tests is necessary but not sufficient for full credit: It's possible to have the unit tests working but things still look wrong. You may want to consider adding unit tests of your own.

You get to choose a strategy for broadphase collision detection. Any broadphase collision detection system that normally does better than O(n2) is acceptable. Because of this, I can't write unit tests for you to verify behavior (again, you should consider doing that yourself). Instead, I'll be racing your collision detection system against those of your classmates. Broad and narrowphase collision will be timed for several plausible scenarios. Because narrowphase collision is being timed as well as broadphase, your broadphase should strike a careful balance between speed and accuracy. The fastest five colliders will receive 20 points of extra credit, as well as eternal bragging rights.

Practicalities

The starter code has been designed to compile and run on a Windows system running Visual Studio 2005 (like the Moore-100 Windows computers), without any external dependencies. Talk to me before beginning if you plan to develop in a different environment. The code is mostly cross-platform, but there are two caveats.

You can modify any of the starter code you wish. It's suggested that you not modify the unit tests in any way; if you find yourself needing to do so, it's a good indication that you're working against the grain and should consider a different approach.

Areas of code that you definitely need to fill in will be indicated with the text "TODO", but you may want to mess with other functions or variables as well. Make sure to search the text of the project to find all of these locations. Other areas of the code that you may be interested in reading are indicated with "LOOK". Of course, those are just suggestions; you'll need to be concerned with more of the code than just those locations.

Using the code

The code automatically runs unit tests on startup. The results of the unit tests are printed in the console window.

You can load levels by pressing the "L" button in the upper left-hand corner. To navigate around the world, drag with the left mouse button to move and drag with the right mouse button to rotate. To fire a ball, press the space bar.

Questions for you to answer

  1. TBD

Submission

Prepare a README.txt file with your responses to the above questions, as well as discussing the project and your solution to it, in the project directory. Discuss different things you tried with the rigid body simulation, and design decisions you made. If you ran into problems and were unable to complete the assignment, describe what works, what doesn't, and how I should explore your project in order to get the best idea of what you've accomplished. If I gave you special dispensation to change or add files, mention that as well. Also list all resources, whether books, webpages, or fellow students, that you used when doing the assignment.

Before submission, you MUST clean the solution and additionally delete the NCB file in the project directory. If you do not do this, you WILL lose points.

Make sure that your submission can be downloaded to a Moore 100 computer, built, and executed without any problems or other setup required.

Submit the completed assignment, zipped up, to the Courseweb site through the assignment submission link. If you encounter problems or aren't sure if your submission went through, additionally email the file to me (bsunshin at seas dot upenn dot edu).

Once you have submitted the assignment, please do NOT click "retake assessment" unless you wish your previous submission, and the time at which it was made, to be deleted and disregarded.

Note

I've written this code from scratch, and I think you'll find it a considerably nicer codebase than project 1. In large part, the design of this system parallels the design of most commercial-quality physics engines being used in games today, such as Havok and Ageia. At the same time, I've made certain sacrifices to performance in the name of readability, such as not caching inertial tensors or separating rigid bodies from their collidable geometries. I've also done nearly everything in world-space rather than object-space, which makes the math nicer but slower.

The paper on which this system is based uses mesh-based signed distance functions for collisions. That works well for high-polycount objects, and badly for cubes. Rather than do that, I've implemented per-primitive collisions which are, on the whole, more stable and well-behaved. The important thing to remember is that the contact point is not necessarily "the deepest point of interpenetration", as in the paper, but is, rather, a "good" point of intersection. For instance, when there is a collision between an edge of a cube and the ground, the collision point should be the midpoint of the edge, not one of the vertices arbitrarily chosen.

Sections 8.1, 8.2, and 9 from the paper are not implemented. You can if you like. If you plan to implement 8.1 and 8.2, contact me and we'll see about extra credit.

Start early!