A Benchmarking Suite for Static Collision Detection Algorithms

There are a number of algorithms for collision detection between rigid objects. Unfortunately, it is extremely difficult to evaluate and compare collision detection algorithms, because in general they are very sensitive to specific scenarios. We propose a benchmarking suite which eliminates this effect. It has been kept very simple so that other researchers can easily reproduce the results and compare their algorithms.
Almost all collision detection libraries for static collision detection between rigid objects are based on bounding volume hierarchies (BVHs). If the bounding volume (BV) of an object does not intersect a volume higher in the tree, then it cannot intersect any object below that node. So, they are all rejected very quickly. If two objects overlap, the recursive traversal during the collision check should quickly converge towards the colliding polygon pair. So, it is most time consuming if the BVHs overlap, but the objects do not. Summarizing, the testing time of pairwise collision detection algorithms depends mainly on the configuration of the two objects and their shapes, i.e. the positions, orientations, and the distance.
Therefore, it seems to be reasonable for a well-balanced benchmarking procedure to test as many configurations for a given distance as possible. Based on this observation, our benchmarking suite automatically generates a large set of configurations for a user defined pair of objects and a list of distances.

The picture above shows a set of configurations that our benchmarking suite has generated. Every red dot marks the closest point of the moving object to the fixed object for one special transformation and distance. Click on the picture to see a short video of the configuration generation. For further details about the configuration generation algorithms we used in our benchmarking suite, we refer the interested user to our WSCG-Paper.

Features

Automatic and exhaustive generation of configurations
Playback of precomputed configuration files
Wrappers for several freely available collision detection libraries
Scripts for benchmarking these libraries with the predefined objects
Scripts for automatic diagram generation
Platform independent accuracy of 1 msec
Measurement of average, minimum and maximum testing times
Two different methods for sampling the search space
Two methods for distance computing (Offset-Surfaces and optionally PQP that must be downloaded separately)
Supports loading objects in the following formats: 3ds, dxf, iv, obj, off, ply, vrml and many more. For details see OpenSGs supported file format list

Prerequisites

OpenSG version 1.6 or higher
gcc 3.5 or higher or Visual Studio 2003 or higher
Optional: gnuplot for automatical generation of diagrams

Sample Plots

Examples of automatically generated diagrams. Click here to see all results.

Download

Here, you can download the source code of our benchmarking suite for free. It is licensed under the GPL.

Supported Collision Detection Libraries so far

FreeSOLID
OPCODE
V-Collide
PQP
Dop-Tree and BoxTree
If you use our benchmarking suite for testing your own collision detection library, it would be quite nice, if you could send us your wrapper code, so that we can integrate it to our download for other researchers.

Set of Objects and Configurations

Together with our benchmarking suite, we offer a set of objects and a set of precomputed configurations for these objects. Each object is available in several resolutions. We recommend to use the precomputed configurations for your benchmarks because configuration generation is very time consuming (e.g. 2 weeks of computation on 8 3GHz-Pentium 4`s for the Eagle).

Configurations were generated using

- Distances from 0%-40% of object size in 40 steps
- Sphere method with PQP for distance computing
- 15° steps for spherical coordinates and 60° steps for rotations along the local coordinate axis of the moving object
- Therefore, we get app. 32k configurations for every distance
Most of the objects are free for non commercial use. For some models, the owners have defined specific licenses.

Apollo Capsule¹ 6 LODs 8-170k polygons	Download object (zip, 11MB)	Download configurations (zip, 117MB)
ATST-Walker¹ 6 LODs 4-152k polygons	Download object (zip, 6MB)	Download configurations (zip, 117MB)
Castle¹ 6 LODs 14-127k polygons	Download object (zip, 4MB)	Download configurations (zip, 115MB)
Chair¹ 5 LODs 22-114k polygons	Download object (zip, 4MB)	Download configurations (zip, 100MB)
Cobra¹ 6 LODs 2-256k polygons	Download object (zip, 14MB)	Download configurations (zip, 110MB)
DS9-Space-Station⁴ 5 LODs 97-584k polygons	Download object (zip, 4MB)	Download configurations (zip, 98MB)
Eagle¹ 5 LODs 98-594k polygons	Download object (zip, 26MB)	Download configurations (zip, 90MB)
Ferrari¹ 5 LODs 61-249k polygons	Download object (zip, 11MB)	Download configurations (zip, 94MB)
Grid 5 LODs 5-414k polygons	Download object (zip, 4MB)	Download configurations (zip, 78MB)
Happy Buddha³ 8 LODs 10-1087k polygons	Download object (zip, 23MB)	Download configurations (zip, 140MB)
Helicopter¹ 5 LODs 23-119k polygons	Download object (zip, 4MB)	Download configurations (zip, 98MB)
Laurel¹ 6 LODs 13-271k polygons	Download object (zip, 10MB)	Download configurations (zip, 115MB)
Lustre¹ 6 LODs 6-120k polygons	Download object (zip, 4MB)	Download configurations (zip, 120MB)
Pipes 5 LODs 10-125k polygons	Download object (zip, 3MB)	Download configurations (zip, 100MB)
Lock 15 LODs 1-207k polygons	Download object (zip, 15MB)	Download configurations (zip, 221MB)
Sponge 5 LODs 12-820k polygons	Download object (zip, 11MB)	Download configurations (zip, 80MB)
Sphere 5 LODs -k polygons	OpenSG built-in	Download configurations (zip, 40MB)
Torus 5 LODs -k polygons	OpenSG built-in	Download configurations (zip, 90MB)
Hand² 6 LODs 63-650k polygons	Download object (zip, 26MB)	Download configurations (zip, 120MB)
Dragon³ 5 LODs 174-871k polygons	Download object (zip, 24MB)	Comming Soon
Chinese Dragon⁵ 5 LODs 262-1311k polygons	Download object (zip, 41MB)	Comming Soon
Circular Box⁵ 5 LODs 280-1402k polygons	Download object (zip, 44MB)	Comming Soon
Elephant⁵ 5 LODs 614-3074k polygons	Download object (zip, 88MB)	Comming Soon
Female Pelvis⁶ 5 LODs 200-1000k polygons	Download object (zip, 33MB)	Comming Soon
Filigree⁷ 5 LODs 205-1028k polygons	Download object (zip, 23MB)	Comming Soon
Gargoyle⁶ 5 LODs 345-1726k polygons	Download object (zip, 44MB)	Comming Soon
Knot⁵ 5 LODs 191-957k polygons	Download object (zip, 41MB)	Comming Soon
Raptor⁷ 5 LODs 400-2000k polygons	Download object (zip, 50MB)	Comming Soon
Armchair⁶ 5 LODs 142-712k polygons	Download object (zip, 20MB)	Comming Soon
Vase⁵ 5 LODs 358-1792k polygons	Download object (zip, 40MB)	Comming Soon