Homework #2: Collision Detection Between Rigid Bodies

Due on Monday, March 27, 2000

(10 pt) Problem A: Implementation

Write a program to detect collisions between many objects flying inside a cube. Each object is given an initial random velocity and angular velocity. The velocity stays the same unless an object hits a wall of the cube, in which case a component of the velocity should be flipped so that the object stays in the cube. You may also approximate the collision detection between an object and a wall by checking whether the center of the object is inside the wall, since correct collision response is not the focus of this assignment

Try two different algorithms.

Hierachical OBB overlap test for O(N²) pairs

Use RAPID version 2.01 http://www.cs.unc.edu/~geom/OBB/version201.html

Sweep & prune and hierachical OBB

V-COLLIDE http://www.cs.unc.edu/~geom/V_COLLIDE/

V-COLLIDE distribution tar file includes RAPID as well, so you do not have to download RAPID separately.
The tar file also includes a demo program similar to this assignment (VCOLLIDE/demos/bunny).

You can choose PQP instead of RAPID and V-COLLIDE:

PQP: http://www.cs.unc.edu/~geom/SSV

(15pt) Problem B: Analysis

Analyze performance of two algorithms in different situations.
Change the following parameters and measure computation time:

Number of objects (1~50)
Complexity of objects (The number of polygons for each object. Try 3 different data files in VOLLIDE/demos/bunny/input)
Sizes of objects (The relative size of each object w.r.t. the extension of the bounding cube.)

Two algorithms should exhibit different characteristics to the variation of these parameters.
Present data in tables and graphs, and explain the differences in performance.