170 random spheres in a confined region
Implementation
Collision detectionThe more complete rigid body simulator from homework 3 was simplified to accomplish the tasks in this assignment. More specifically, all forces acting on the bodies were removed, and the collision response was reduced to a more simple scheme:
- Sphere-sphere collision: The velocity is reflected on the plane that is tangential to both sphere surfaces (see figure 1).
- Sphere-cube collision: The sphere's velocity is reflected on the cube's surface plane.
In this algorithm, I use SWIFT for collision detection. I have also implemented routines that call other collision detection packages, such as SWIFT++, DEEP and PQP, but I have found that for this assignment, SWIFT was the right choice. That is because of the assumptions we make for this task:
- Convex objects only (SWIFT++ can deal with non-convex)
- Simple collision response. DEEP also gives penetration depth information, but we are only flipping velocities here. DEEP could be useful for a penalty-based contact response approach or in a clever time of intersection searching scheme.
SWIFT's interface is very convenient because it is an N-BODY processor. You just hand it a bunch of object's geometries, and it will do the necessary pair-checking for you. Moreover, the SWIFT algorithm has more powerful features. More specifically, it has a broad phase: SWIFT can automatically choose bounding boxes for the objects, and prune pair testing based on the overlaps between bounding boxes. It will also take advantage of time coherence (local sorting is provided). PQP's advantage is that it will return all intersecting triangles of the intersecting pairs (SWIFT only reports one contact point per pair of objects), but that doesn't weigh up against SWIFT's advantages, especially because you have to do the pair managment yourself.
These simplifications were made to be able to make a better analysis on the performance of the collision detection algorithms used in this assignment. For a more complete physically based rigid body simulator, using a full impulse-based algorithm by Guendelmann, Bridson and Fedkiw, please have a look at homework 3.
I have implemented Euler, RK4 and Midpoint methods for numerical integration. Scenes can be loaded with a simple scene description language file. There's also the possibility to specify in the file that you want a random distribution of a certain number of spheres in a confined cube of specified size. The sphere radius and initial velocity vectors are randomly chosen in that case. This is what is done in the test program that I used to do the analysis.
Analysis
All the tests were performed on an Acer Travelmate 803LCi laptop. It's a 1.6Ghz Centrino processor with ATI9000 video card.
Number of objects
The cube's size is 10x10x10. The spheres have random size and velocity, but we make sure that they don't intersect in their initial state. The timestep used in the RK4 method is 0.05s.
Here are some graphs and tables with average timings that show the influence of the number of objects in the scene. Here, I am using fairly coarsely tesselated spheres, with 144 triangles each.
# of time for transfo intersection
spheres fps simulation update test
====================================================
10 135 171 9.12 23.00
20 114 236 17.70 46.59
30 98 433 25.50 65.35
40 86 867 38.81 110.89
50 76 1196 53.35 169.25
60 68 1470 62.16 223.88
70 62 1727 76.00 255.19
80 57 1971 92.19 316.15
90 53 2295 103.83 423.75
100 49 3178 124.41 514.40
110 45 3716 129.10 647.95
120 42 4156 141.18 784.50
130 40 4038 154.42 768.75
140 38 4262 168 847.62
150 35 4848 186.36 1109.07
160 32 5956 192.09 1262.55
170 31 6262 204.80 1445.53
180 29 7072 216.37 1671.07
times are in microseconds
The first graph shows the average time for an intersection test by SWIFT. The time grows only slightly faster than linearily with the number of spheres in the scene, even though there are potentially order n^2 collisions between n objects. Mind, we have not used the early exit option here, because we wanted to know all the intersecting pairs in order to do collision response. The slightly superlinear behaviour is probably due to the higher number of collisions.
It is also interesting to observe the dip when we go from 120 to 130 spheres. I had to make the sphere radius smaller at that point in order to make all the spheres fit into the confined cube. Therefore, the cube was less filled up and there were less collisions. Moreover, SWIFT was probably able to do stronger bounding box pruning because of the larger ratio of free space at that instance.
Average SWIFT intersection query time
The second graph shows the time needed by SWIFT to update the transformations: it grows linearily. That follows from the fact that it has to perform a different transformation for each object (as they are all independent).
Average SWIFT transform update time per iteration
As a joint effect of the 2 previous observations, we can conclude that the total simulation time grows almost quadratically, if we include the integration time and collision response computation. Those clearly grow linearily with the number of collisions, which in its turn also grows linearily as the scene becomes more crowded. Hence the almost quadratic dependence on the number of spheres. The next figure shows this effect. Observe that the dip between 120 and 130 spheres is still there.
Average overall simulation time (without rendering) per iteration
Model complexity
In the next table and graphs, the effect of number of triangles per object are compared. I have run tests for sphere-like objects with 4 different numbers of triangular faces: 36, 144, 576, 2304 and 9216. They were obtained by recursively subdividing a dodecahedron and reprojecting the new vertices on the unit circle. The results for the last set (9216 faces) are shown in the table but not included in the graphs because of the extraordinary data. Probably, the computer ran into memory problems when loading the objects
#triangles total # SWIFT
per spheres faces update query fps
=======================================================
36 1800.00 35.79 121.45 90.98
144 7200.00 52.25 170.95 75.58
576 28800.00 71.69 305.07 28.48
2304 115200.00 96.66 969.11 8.11
9216 460800.00 9809.13 702511.58 0.73
times are in microseconds
For all these tests, the number of spheres in the scene was 50, and they all had the same radius (thus the space coverage was the same on average for all the tests in this case). Despite the growth of triangles, the transformation time does not grow linearily. That is probably a result of bounding box pruning and front tracking (use of temporal coherence. Because the number of spheres remains constant, the number of vertices that have to be transformed to world space does not grow linearily. Indeed, alot of them can be pruned away if the bounding boxes of the objects that these vertices belong to do not overlap or if they are not in each other's neighbourhood. That's why the time for the transformation update grows less than linearily with the number of triangles in the scene.
Average SWIFT transform update time: less than linear growth.
However, this behaviour is not present in the timings for the actual intersection tests. I can only suspect that the reason for this fact is that the scene was rather tightly filled for these tests, therefore yielding many intersections. Remember, there is a fixed cost for each intersection, because we do not use the early exit option.
Average intersection test time
The decrease in frames per second is stronger than in the previous test, but that is mainly due to the higher demand on rendering due coming from the larger tesselation.
Average number of frames per second
Object size
In this test, I used 50 spheres, 576 triangles each. The sizes are proportional to the width of the confined cube, from 1/4 to 1/80. The first graph clearly shows that...
RATIO UPDATE QUERY
=======================
0.25 75.884 775.15
0.13 69.586 190.516
0.06 67.417 120.109
0.03 66.511 99.769
0.01 66.884 95.728
times are in microseconds
The intersection query time grows almost exponentially as the size of the spheres goes up. This is most likely due to the increasing number of collisions, as the confined region is more tightly packed. Again, this strong increase is due to the joint effect of the following two phenomena:
- Less aggressive bounding box pruning can be performed because of the crowded confinement.
- The joint effect of the increase of the fixed cost per collision (again, no early exit was used, and collision response has to be handled).
Average intersection query time
It is also interesting to see that, as the spheres grow, the intersection query time only grows linearily here. That is, the number of pairs to be tested is not going to change alot, and the number of triangles/faces is constant. The increase is only due to the fact that the spheres are closer together when they grow.
Ratio of intersection query time versus total simulation time
Varying parameters
A straight-forward technique that can be used for known, fixed object sizes is the use of a uniform 3 dimenisional grid subdivision of the space that the spheres travel in. We manually activate/deactivate pairs that lie in the same or adjacent gridcells, before running the intersection query with SWIFT. The size of the grid cells is chosen depending on the size of the objects. A good choice is atleast the same size as the size of the bounding box of the objects, such that an object is likely to be contained inside one gridcell.
I have made an implementation of a Grid3D class, after modification of Miguel Otaduy's original code. Fixed objects are not placed in the cells, but are activated for pair checking with all the moving objects. This is not optimal, but we trust that SWIFT's broad phase and local sorting abilities handle that for us anyway, and that the additional gain wouldn't be worth the effort.
Mind that this is a fixed binning technique. This is fine when the parameters (size of objects, confined cube size, etc). We also assume that the objects are sphere-like, therefore it makes sense to have a cube-sized subdivision of the space.
With SWIFT's broad phase bounding-box pruning turned off, using a uniform grid, gave me a speedup of upto 3 times faster than without the uniform grid subdivision (for about 50 objects), and increasing almost quadratically in the number of objects. This seems plausible, given the fact that the number of pair-pair checks increase, aswell as the number of collisions.
I also tested the use of this uniform space grid together with SWIFT's broad phase turned on. The results for this approach are dissappointing to say the least. SWIFT apparently uses a very efficient pruning and culling technique in its broad phase to limit the number of actual pairwise collision detections. I tried to make my 3D grid code as fast as possible, but the first timings showed that my approach of manually providing SWIFT the information on which pairs to test yield timings that are up to 2 times slower. Then I thought it was the overhead of doing the the actual set-up of the pairs, but after carefully timing as close as possible around the call to the SWIFT Intersection Query, I can only suspect that SWIFT was not designed for this kind of operation and that the algorithm suffers greatly if you don't let it do its own pruning. Maybe deactivating some pairs even comes into the way of the proper functioning of the SWIFT algorithm.
Another algorithm that is that I have tested is the KD-Tree. I have used the KD-Tree implementation in G3D to test the additional gain. It works fine, but the additional gain is not superb. Again, these techniques might only be useful in the case of a non-N-body optimized collision detection algorithm, that focuses on efficient pairwise collision detection only, and in the case of a large number of primitives (> 100).
Code and Acknowledgements
Here's the link to the collision detection code again.
Thanks to Miguel Otaduy for his help and useful discussions, and to Morgan McGuire at Brown University for useful tips and for making me look at the impulse-based approach. Also, I did my rendering using the G3D library (it also includes nice linear algebra, geometry and utility routines).