COMP259: Homework 2

Collision Detection Between Rigid Bodies

Problem A: Implementation

Write a program to detect collisions among many sphere-like objects of different sizes flying inside 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

Implementation

To implement the collision system I used the collision package PQP written at UNC. PQP uses swept sphere volumes (SSVs) for tolerance and distance computations, and oriented bounding boxes (OBBs) for collision tests. At each frame of the simulation every moving object is tested against every other moving object, and the walls of the scene. If a collision is detected the object's state is modified to produce a collision response. The collision response is computed as if the objects were all spheres. Thus I could simply reflect the objects velocity to produce a collision response.
source: PBMSimScene.h, PBMSimScene.cpp

The objects themselves are modified projectiles, that travel with no acceleration, and a random angular velocity. For efficiency, collision and rendering geometry can be shared between the objects.
source: PBMProjectile.h, PBMProjectile.cpp, PBMProjectileLaunchParams.h

To facilitate the handling of rotational velocity and the matrices needed to guide the collision system, I implemented a configuration class, that stores a position and rotation (as a quaternion) for the object.
source: PBMConfiguration.h, PBMConfiguration.cpp

In addition to the moving objects in the scene, I defined a new class for static walls. This class encapsulated the collision and rendering geometry for each of the 6 walls that defined the boundary of the scene.
source: PBMWall.h, PBMWall.cpp

Finally, the main program, initializes the scene and provides user interaction.
source: main1A.cpp

Numerous tests of the implementation showed that it correctly detects all object/object and object/wall collisions.
 

Problem B: Analysis

Analyze performance of your algorithm (or implementation) in different situations.
Change the following parameters and measure computation time: 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.
 
 

Analysis

1) Number of Objects

I tested the characteristics of my program with a model of a pumpkin made from 1753 triangles. For each different number of objects in the scene I gathered statistics for 10 seconds of execution. At the end of this time I reported the frame rate, as well as the number of collision tests performed, and the time for all collision tests (averaged per frame), for both object/object and object /wall collisions.
 
Number of Objects. Frames per Second Number Of Object/Object Collision Tests Average Time For Object/Object Collision Tests Number Of Object/Wall Collision Tests Average Time For Object/Wall Collision Tests
5 85.1 4780 0.000031 14340 0.000193
10 84.9 33075 0.000211 44100 0.000356
15 83.5 83552 0.000478 74598 0.0005
20 82 88803 0.000674 62490 0.000542
25 81.3 102718 0.0012718 56028 0.00073
30 80.2 145530 0.001803 64680 0.000899
35 79.1 195360 0.002562 73260 0.001097
40 73.2 188404 0.003192 61104 0.00137
45 68.5 247422 0.00444 70692 0.001345
50 65 328248 0.005504 83808 0.001616


From the graphs above we can make several conclusions. The number of object/object collision tests and the average time for object/object collisions grows quadratically with the number of objects. This makes sense, since my system tests each object against each object. The time for object/wall tests grows roughly linearly with the number of objects. This is because for each new object added the time to test wall collision goes up by the time needed to test the object against each of the six walls.
 

2) Complexity of Objects

I tested my system with 3 data sets.
  The first two were generated by simplifying the third. This ensured that the objects all had the same extents and shape.
In these tests I used 45 objects, simulated over 10 seconds.
 
Object Faces Frames Per Second Number Of Object/Object Collision Tests Average Time For Object/Object Collision Tests Number Of Object/Wall Collision Tests Average Time For Object/Wall Collision Tests
1753 81.5 188404 0.003192 61104 0.00137
9868 51.5 606870 0.004221 165510 0.002422
17001 15 526922 0.007065 147048 0.001995


The Object/Object test time seems to vary quadratically with the number of faces in the objects. This makes sense because increasing both object complexity should lead to a roughly quadratic increase in the complexity of the test to determine if they intersect. The behavior would be exactly quadratic if the collision package tested every polygon on the object against every other polygon. Since it instead uses a bounding box hierarchy, the slowdown is not as bad as this worst case. The Object/Wall test time should grow linearly with the number of polygons in the object, since the walls do not increase in complexity. Again the fact that bounding boxes are used prevents this worst case increase from being evident in practice.
 

3) Object Size

To test the effect of object size on the simulation, I used 10 of the smaller, 1753 triangle, objects and changed the size of the scene bounding box. In the first test the objects are 1/100th of the scene, i.e. a 1*1 object in a 10*10 scene. The next test has the 1*1 object in a 5*5 scene, so each object is 1/25th of the scene. The last test uses a 2*2 scene, so each object is 1/4 of the scene. Needless to say, 10 objects can't fit in a 4*4 scene without constantly colliding.
 
Object / Box Ratio Frames Per Second Number Of Object/Object Collision Tests Average Time For Object/Object Collision Tests Number Of Object/Wall Collision Tests Average Time For Object/Wall Collision Tests
1/100 84.9 33075 0.000211 44100 0.000356
1/25 84 40950 0.000663 54600 0.00373
1/4 51.5 40950 0.013747 54600 0.002909

You can see that for the three data sets, the Object/Object intersection time rises very quickly with the crowdedness of the scene. This makes sense , because the more crowded the objects, the deeper the collision package needs to traverse the hierarchy to ensure that they intersect. As well, there are so many collisions per frame that collision response calculations become a performance issue. The wall calculations, again provide a muddier picture. The reason that the do not effect the performance so dramatically is because there are fewer walls in the scene.
 
 

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

Proposed Improvement

Because of the hierarchical nature of the bounding box tests, and their ability to quickly reject inter object collisions if the objects are clearly disjoint, it does not make much sense to attempt to speed up a single collision query by using the object size as a rejection criterion. Instead it would be much better to find a scheme to remove the necessity of testing each object against each other object, and the quadratic growth curve that results. There are two possible methods to do this:
 
  1. A Spatial Subdivision, configured to the size of the objects.

    2. By tracking the objects through this subdivision, we can test each object only against the objects in the cells that in intersects. By making the cells big enough to fit one object, one could ensure that each object only intersects at most 4 cells. If the objects are distributed in a realistic way (i.e., not all overlapping) then this will achieve a constant number of collision tests per object. The downside of this approach is that there is an overhead associated with the spatial subdivision, since each object must be tracked through the data structure. So even though the algorithm is linear in the number of objects, the constant can get very high.
  2. Predictive Collision Scheduling

    3. Since the objects all travel at a constant velocity unless they collide with something, it is possible to quickly predict the set of objects that they can next collide with. For walls, this amounts to looking at the velocity of the object and position relative to the wall, and computing the time it will take before the object hits the wall. If we assume that the objects are all enclosed in a fixed radius, then we can easily solve this analytically. Multiple candidate walls need to be considered in the case where the object is headed into a corner, so even if the radius approximation a single contact wall, the actual geometry of the object may collide with nearby wall as well. For objects, this prediction amounts to solving the equation:

    || (P1 + V1*t) - (P2 + V2*t) || = 2*objectRadius

    By squaring both sides (since the objectRadius is positive) and writing deltaP = P1-P2 and deltaV = V1 - V2 we get:

    = (deltaP + deltaV*t) (deltaP + deltaV*t) = 4*objectRadius^2

    where the parentheses indicate vector dot product. Finally this gives:

    (deltaP)(deltaP) + 2(deltaP)(deltaV)t + (deltaV)(deltaV)*t^2 =  4*objectRadius^2

    which can be solved for t using the quadratic formula. Often there are no solutions, since to paths in 3D need not necessarily intersect. But if a solution exists, the smallest non negative solution, indicates the next time the objects will be close enough together to collide. Comparing collision times for all objects we can track the earliest collision time for each object, and only check for collisions when the time arrives. As in the case of walls, multiple candidates must be considered if their times are close enough together, that the radius approximation may incorrectly predict the outcome of the actual collision test on the geometry.

Implementation

I implemented the second proposed scheme, predictive collision scheduling. For each object I kept a record of the set of next possible collision objects, the nearest object collision time, the set of next possible collision walls, and the nearest wall collision time. These predictions had to updated every time there was a collision. If an object collides, it must again search for the next wall and object that it will impact. Also, the predictions for any objects that had they collided object as their nearest collision candidate, had to be updated.
 

Performance

At this moment the implementation is not quite working with enough stability to generate any performance results. But, it is easy to see that this algorithm has several advantages over the spatial subdivision approach, especially in the case we are considering, where objects move at constant velocities when not in collision. The predictive scheme allows very large time steps  to be taken and requires no collision computations,  between predicted collision times. At a predicted collision time, we already have a set of candidate objects which we can test to determine which object is in collision. This gives a constant time collision test per object, when the objects are well distributed and the candidate lists do not contain large number so of objects in the scene. Also, at a collision, we have to perform a linear time computation to get the next predicted collisions. But, since this happens only at collision time, rather than every frame like in the spatial subdivision method, we get a considerable time savings.  Thus it is my expectation that the predictive collision scheme will outperform the standard brute force collision method, and the spatial subdivision method in most reasonable scenes, where the size of objects is known, and the velocity of objects is constant between collisions.