Implementation
Collision Detection Between Rigid Bodies
I have implemented a simple scene modeling collisions. Several spheres are added to a cube with random positions, velocities, and rotations. The spheres then move about and collide with the walls and each other. I used the PQP library to handle the collision detection. Since the simulation does not model proper force interaction, a simple euler integrater was used to update the sphere's status. It is assumed that only spheres and planes will be used in the collisions.
Upon collision, the sphere's velocity is reflected about the plane orthagonal to the intersection normal. The sphere's rotation is simply reversed upon impact. It is also worth noting that the engine used to render the scene is a raytracer. All spheres are rendered as raytracing primitives, and thus no polygons are rendered on screen. Each sphere does have a tessellation structure that is used in the collision routines.
The code and binaries for OS X are available here.
Analysis
Number of objects
For this analysis, only the number of objects is changed; all other parameters are held constant. The number of objects increases by 5 from 0 to 150.
Initial state:
Boundary size: 10 x 10 x 10
Number of objects: 0 -> 150
Tesselation degree: 10 (180 polygons)
Size: 0.5 - 1.0
Results:
As expected, as objects are added, the time cost to perform a simulation step increases. Since each object must be collided against every other object, the number of possible collisions increases quadradically. Without knowledge of the spatial orginization of the scene, the collision library is thus bound to quadradic performance. As shown above, PQP performs with a quadratic bound, with some constant coefficient.
For this analysis, only the tessellation of the objects was altered. The tessellation decreases by 1 degree from a degree of 69 to 4. The number of polygons ranges from 9384 to 24.
Initial state:
Boundary size: 10 x 10 x 10
Number of objects: 20
Tesselation degree: 69 (9384 polygons) ->4 (24 polygons)
Size: 0.5 - 1.0
Results:
While one may expect the time needed for each step to greatly increase as the tessellation of the objects increases, this is not the case. While the time cost does increase, it does not do so consistantly or with a substantial degree. It is likely that the PQP library performs optimization to reduce the collision cost, even for complex models. It is worth noting that the data is extremely noisy and this may be influencing the analysis
In this analysis, the difference between the minimum and maximum possible radius was decreased. This is to reduce the possibililty that two scenes with the same number of objects behave differently. The radius begins at 0.0 and 0.5 and increases by 0.05 up to 1.2 and 1.7. The graph shows the ratio of the average radius to the width of the containing cube.
Initial state:
Boundary size: 10 x 10 x 10
Number of objects: 10
Tesselation degree: 10 (180 polygons)
Size: 0.0 - 0.5 -> 1.2 - 1.7
Results:
As the radius increases, the number of collisions increases, since the objects are in a confined space. The result of increasing the object size seems to cause the computation time to grow quadratically, however, the noise in the data may be influencing the appearance of the graph.
Varying the Parameters
Spatial subdivision
If the size of the objects is known and constant, a subdivision grid may be built to accellerate collision query performance. By only colliding objects in the same subdivision section, the computation time may be reduced significantly. I used a simple octree structure and only intersected objects at the same octree level.
To test the performance of the structure, it was compared against the normal method with regard to a varying number of objects. Each method was tested beginning with 5 objects and increasing by 5 more up to a total of 180 objects.
Initial state:
Boundary size: 10 x 10 x 10
Subdivision size: 5 x 5 x 5
Number of objects: 10 -> 170
Tesselation degree: 10 (180 polygons)
Size: 0.2 - 0.4
Results:
Using a simple one level octree structure provides an impressive performance gain. In the worst case, an object would be in several subdivisions, and require testing with all objects in those subdivisions. This only happens as an object passes between the subdivisions. Since the divisions are large relative to the maximum radius, most collisions happen between objects in the same subdivision. In the above picture, colored objects on in only one octant, while grey objects are in at least two octants.