Homework #2: Collision Detection Between Rigid Bodies

Due on Thursday, March 23, 2006

(6 pt) Problem A: Implementation

Write a program to detect collisions among many sphere-like objects of different sizes flying insid a confined region (e.g. a cube, a table with boundary, etc); Each object is given an initial random velocity and angular velocity. The velocity stays the same unless an object hits an obstacle (e.g. a wall or another object), in which case a component of the velocity should be flipped so that the object stays within the confinement. State your assumptions about the objects! You may wish to reuse and modify the source code available at: http://www.cs.unc.edu/~geom/collide/packages.shtml

(9pt) Problem B: Analysis

Analyze performance of your algorithm (or implementation) in different situations.
Change the following parameters and measure computation time:
  1. Number of objects (1~50)
  2. Complexity of objects (The number of polygons for each object.  Try at least 3 different data sets)
  3. Sizes of objects (The relative size of each object w.r.t. the extension of the bounding cube.)
Your algorithm (implementation) should exhibit different characteristics to the variation of these parameters.
Present data in tables and graphs, and explain the differences in performance.

(10pt) Problem C: Varying Parameters

Same as Problem A, except the objects have the same size. What would you do differently? Show a simple prototype implementation to compare and contrast the performance of two different algorithms (implementation).

This assignment will be graded based upon:

  • Correctness of the implementations (40%)
  • Comparison and Analysis (60%)