It is extremely difficult to evaluate and compare collision detection algorithms, because in general they are very sensitive to specific scenarios, i.e., the relative size of the two objects, the relative position to each other, the distance, etc.

My test scenario involves two identical objects which are positioned at a certain distance from each other. The distance is computed between the centers of the bounding boxes of the two objects. Then one of them performs a full revolution about the z- and x-axis (z is pointing towards the viewer in the figure below) in a fixed, large number of small steps (usually, I use 2000). With each step a collision query is done, and the average collision detection time for that distance is computed. This procedure is done for different distances, which yields graphs as shown in the figures below.

Here is the
source code
of the "main loop" of my benchmark program
`bench.c`, which I use for my benchmarks.
And you might want to get this
include file, also (vector math macros).

I'm afraid I can't make the collision detection code public domain (yet),
but don't hesitate to contact
me if you would like to consider some sort of cooperation.

sphere | torus | cubes | tetraflake |
---|---|---|---|

And here are some real-world CAD objects:

door (BMW) | lock (BMW) | Sharan (VW) | pipes |
---|---|---|---|

3391 polygons | 20898 polygons | 60755 polygons | 124544 polygons |

Please contact me, if you would like to obtain them in Inventor format.

All plots have been derived from the same set of data.

The program for generating the data is the same as described above, except that only the "interesting" range of distances has been considered. The interesting range is the one around the "contact" distance. Here, I have considered the last two distance steps

The three postscript files contain the same plots with different "zoom" levels.

1.0 | 0.9 | 0.8 |

It seems that performance of OBB-trees and DOP-trees is about similar, while QuickCD and Boxtree have poorer performance.

The following postscript files show the results in more detail. The second section in each postscript file (entitled "time-vs-kompl") shows the performance of each algorithm depending on object type and complexity.

Each plot shows the same data, except with different zoom levels.

All timings have been done on a 194 MHz R10000 Onyx (IP25).

1.0 | 0.9 | 0.8 |

All timings have been done on a 195 MHz R10000 Onyx2 (IP27).

1.0 | 0.9 | 0.8 |

Note that the cylinder ("zy") contains 2 very large polygons
(compared to all the others, which have the same size); these are the
bottom and top "lids", which consist of *n* vertices
(*n* being the "sampling").
This might explain why the collision detection time increases so steeply
with complexity.

It is funny that this algorithm exposes a behavior similar to the
hierarchical algorithms with respect to
complexity for the "SCHLOSS" object.

Description | Movie | Annot. |
---|---|---|

My separating planes algorithm in action | MPEG (1.5 MB) | |

Making an object slide along the surface of other objects. Here with a simple scene. | MPEG (3.5 MB) | |

A small excerpt from the previous sliding movie. | MPEG (300 kB) | |

The sliding (gliding) simulation of some real-world objects.
The simulation used my DOP tree algorithm for collision detection. |
MPEG (4.8 MB) | |

A small excerpt from the previous sliding movie. | MPEG (470 kB) | |

Another excerpt from the previous sliding movie. | MPEG (100 kB) | |

Yet another excerpt from the previous sliding movie. | MPEG (100 kB) | |

Of course, I've got a torus chain simulation, too. | MPEG (350 kB) | |

This shows how a hierarchical collision detection algorithm works. Actually, it is a pretty old algorithm of mine (a very early version of the BoxTree), but the principle is the same. | MPEG (1.3 MB) | |

Another little demo with various objects. I call it the "Zoo" :-) | MPEG (500 kB) |

All movies (except if otherwise noted) have first been filmed off the screen in real-time and then converted to MPEG, so that the full frame-rate was achieved. If your movie player plays them at 24 frames/sec, then you'll see exactly what I have seen on the screen.

(+)
These movies were recorded using SGI's
`mediarecorder`, which causes a decrease of frame-frate by a factor.

Gabriel Zachmann

Last modified: Fri Feb 23 15:50:13 MET 2007