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 can evaluate both the performance as well as the quality of the collision response. The former is achieved by densely sampling the configuration space of a large number of highly detailed objects; the latter is achieved by a novel methodology that comprises a number of models for certain collision scenarios. With these models, we compare the force and torque signals both in direction and magnitude. It has been kept very simple so that other researchers can easily reproduce the results and compare their algorithms.
Performance Benchmark
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.
Quality Benchmark
Especially with forces, human perception is very sensitive to unexpected discontinuities both in magnitude and direction. Consequently, collision detection algorithms should provide stable and continuous forces and torques, even in extreme situations like high impact velocities or large contact areas. Moreover, they should provide these forces at interactive rates.
In order to determine the collision response quality of an algorithm, we pursue a different approach, because computing realistic forces and torques from detailed objects in complex contact scenarios is highly non-trivial. Because of that, we propose to use fairly simple scenarios and geometry tests to measure the quality of the collision response. We believe that this approach is even more warranted because different collision handling systems use different measures for the force and torque computations. For instance, penalty-based methods usually use a translational penetration depth or the penetration volume, impulse based collision response schemes often need the first time of impact.
Another advantage of simple scenarios is that we can model them, which allows us to calculate the theoretically expected forces and torques analytically for different collision response schemes. The comparison of this analytically derived ground truth data with the data gathered from the benchmarked algorithms allows us to define several measures, such as deviations and discontinuities of forces and torques, or the measurement of noise. For further details about the Quality Benchmark we used in our benchmarking suite, we refer the interested user to our VRST2010-Paper.
Publications
- A Benchmarking Suite for 6-DOF Real Time Collision Response Algorithms Proceedings of the 17th ACM Symposium on Virtual Reality Software and Technology 2010 (VRST' 2010), Hong Kong, November 2010
- A Benchmarking Suite for Static Collision Detection Algorithms International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG), Plzen, Czech Republic, January 29 - February 1, 2007
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
FreeSOLIDOPCODE
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 (low sampled version)).
Configurations were generated using
- Distances from 0%-30% of fixed object size in 30 steps
- Sphere method with PQP for distance computing
- 15° steps for spherical coordinates and 15° steps for rotations along the local coordinate axis of the moving object (collision scenario)
- Therefore, we get app. 1,991k configurations for every distance
- Intersection volume from 0%-10% of fixed object volume in 10 steps
- Sphere method with IST for intersection volume computing
- 15° steps for spherical coordinates and 30° steps for rotations along the local coordinate axis of the moving object (collision scenario)
- Therefore, we get app. 268k configurations for every intersection volume.
Apollo Capsule 16 LODs 8-170k polygons |
Download object (zip, 11MB) | Download configurations (zip, 117MB) | ||
---|---|---|---|---|
ATST-Walker 16 LODs 4-152k polygons |
Download object (zip, 6MB) | Download configurations (zip, 117MB) | ||
Castle 16 LODs 14-127k polygons |
Download object (zip, 4MB) | Download configurations (zip, 115MB) | ||
Chair 15 LODs 22-114k polygons |
Download object (zip, 4MB) | Download configurations (zip, 100MB) | ||
Cobra 16 LODs 2-256k polygons |
Download object (zip, 14MB) | Download configurations (zip, 110MB) | ||
DS9-Space-Station 45 LODs 97-584k polygons |
Download object (zip, 4MB) | Download configurations (zip, 98MB) | ||
Eagle 15 LODs 98-594k polygons |
Download object (zip, 26MB) | Download configurations (zip, 90MB) | ||
Ferrari 15 LODs 61-249k polygons |
Download object (zip, 11MB) | Download configurations (zip, 94MB) | ||
Grid5 LODs 5-414k polygons |
Download object (zip, 4MB) | Download configurations (zip, 78MB) | ||
Happy Buddha 38 LODs 10-1087k polygons |
Download object (zip, 23MB) | Download configurations (zip, 140MB) | ||
Helicopter 15 LODs 23-119k polygons |
Download object (zip, 4MB) | Download configurations (zip, 98MB) | ||
Laurel 16 LODs 13-271k polygons |
Download object (zip, 10MB) | Download configurations (zip, 115MB) | ||
Lustre 16 LODs 6-120k polygons |
Download object (zip, 4MB) | Download configurations (zip, 120MB) | ||
Pipes5 LODs 10-125k polygons |
Download object (zip, 3MB) | Download configurations (zip, 100MB) | ||
Lock15 LODs 1-207k polygons |
Download object (zip, 15MB) | Download configurations (zip, 221MB) | ||
Sponge5 LODs 12-820k polygons |
Download object (zip, 11MB) | Download configurations (zip, 80MB) | ||
Sphere5 LODs -k polygons |
OpenSG built-in | Download configurations (zip, 40MB) | ||
Torus5 LODs -k polygons |
OpenSG built-in | Download configurations (zip, 90MB) | ||
Hand 26 LODs 63-650k polygons |
Download object (zip, 26MB) | Download configurations (zip, 120MB) | ||
Dragon 35 LODs 174-871k polygons |
Download object (zip, 24MB) | |||
Chinese Dragon 55 LODs 262-1311k polygons |
Download object (zip, 41MB) | |||
Circular Box 55 LODs 280-1402k polygons |
Download object (zip, 44MB) | |||
Elephant 55 LODs 614-3074k polygons |
Download object (zip, 88MB) | |||
Female Pelvis 65 LODs 200-1000k polygons |
Download object (zip, 33MB) | |||
Filigree 75 LODs 205-1028k polygons |
Download object (zip, 23MB) | |||
Gargoyle 65 LODs 345-1726k polygons |
Download object (zip, 44MB) | |||
Knot 55 LODs 191-957k polygons |
Download object (zip, 41MB) | |||
Raptor 75 LODs 400-2000k polygons |
Download object (zip, 50MB) | |||
Armchair 65 LODs 142-712k polygons |
Download object (zip, 20MB) | |||
Vase 55 LODs 358-1792k polygons |
Download object (zip, 40MB) |
Object Resources
2. The Stanford 3D Scanning Repository
3. Large Geometric Models Archive
5.Model is provided courtesy of INRIA by the AIM@SHAPE Shape Repository
6.Model is provided courtesy of VCG-ISTI by the AIM@SHAPE Shape Repository
7.Model is provided courtesy of SensAble technologies by the AIM@SHAPE Shape Repository
License
This original work is copyright by University of Bremen.
Any software of this work is covered by the European Union Public Licence v1.2.
To view a copy of this license, visit
eur-lex.europa.eu.
The Thesis provided above (as PDF file) is licensed under Attribution-NonCommercial-NoDerivatives 4.0 International.
Any other assets (3D models, movies, documents, etc.) are covered by the
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
To view a copy of this license, visit
creativecommons.org.
If you use any of the assets or software to produce a publication,
then you must give credit and put a reference in your publication.
If you would like to use our software in proprietary software,
you can obtain an exception from the above license (aka. dual licensing).
Please contact zach at cs.uni-bremen dot de.