Homework #2: Collision Detection Between Rigid Bodies
For this project I created a simple scene consisting of a cube containing a number of tetrahedra, cubes, and tesselated spheres. These objects are given random initial linear and angular velocities and are left to bounce around the scene. Simple Euler integration is sufficient to calculate the motion of the objects. I used the SWIFT package to perform collision detection. The collision response is very simple. I assume that all of the objects are spherical. When two objects collide, an impulse is generated along the vector joining the object centers. This approximation produces fairly convincing collisions. The forces generated by the impulse are applied at the end of the step-step and not at the moment of collision. If there is significant penetration, the forces may not actually separate during the next time step. When this occurs, the velocity vectors are flipped back so that the objects are heading towards each other again which causes them to remain in collision. Typically two objects stuck in this configuration spin around around each other for a moment and then finally break free. I scale the impulse slightly to give the objects a little extra "kick" to separate them. The following sections explain how varying different parameters affects
the performance of the program.
Number of ObjectsIncreasing the number of objects causes the collision detection time to increase. While there are theoretically O(n^2) interactions, Figure 1 shows that SWIFT does a good job at exploiting coherence in the scene to keep the growth almost linear initially. The increase in the slope of the graph with larger n is due to the fact that the objects are confined to a small enclosure. With many objects collisions occur much more frequently.
Object ComplexityTo measure the effect of object complexity on collision detection time I timed 1000 iterations with 20 spheres with varying degrees of tesselation to increase in the number of polygons. As seen in Figure 2, polygon count does have an effect on the average time per iteration. The computation time appears to grow linearly with polygon count.
Object SizeVarying the scale of the objects does little to affect the performance of the collision detection. Figure 3 was generated by varying the scale for 10 cubes. There is a slight increase in calculation time for larger objects which is once again due to the fact that they are enclosed in a small space. Larger objects have less room to move and collide more frequently.
"Optimization" for Uniform-Sized ObjectsFor a scene consisting of objects that are all the same size, a uniform spatial subdivision seems to be an obvious optimization. I subdivided the confinement into a grid of voxels roughly the size of the objects. I place an reference to an object in all of the voxels it overlaps. Then I test each object for collisions only with those objects contained in the voxels it overlaps.
ImplementationThis project was built on top of the code for the past projects. In addition I added the ability to pick objects and manipulate them with the mouse. This turned out to be a great debugging tool because I could manually cause collisions. There are a few bugs, particularly with the simulation timing that I never got around to fixing.Use the right mouse button to select and deselect. Left drag rotates, Shift-Left drag translates and Ctrl-Left drag scales. Objects turn red when they are in collision. |
The results
of this optimization are disappointing. Figure 4 shows that the grid optimization
is much slower than than SWIFT alone. SWIFT uses a broad phase to in its
computation to cull a significant number of collision tests. I hoped that
my gridding optimization would enhance performance if the broad phase was
not used. Even without it, SWIFT performed better. I was not sure why the
grid was so slow. I tried to make it as fast I could. I preallocated all
of the voxels so that no heap allocation is ever performed during the simulation.
I avoided having to clear the grid by using a timestamp to invalidate the
voxels of the previous time step. Then I timed the code and found that
the time to put the objects in the grid was neglible. It was only taking
a few microseconds. All of the time went to the repeated calls to SWIFT.
My guess is that the library is not optimized for this kind of use.
