Software Library for Interference Detection
May the source be with you...
SOLID was originally written by Gino van den Bergen. The original homepage of SOLID version 2.0 is still available here.
- May 18, 2002. SOLID version 2.1.0 is available for download.
- October 18, 2000. SOLID version 2.0.2 is available for download.
- October 16, 2000. SOLID is now hosted at sourceforge.
March 25, 2000. A GLUT version of the GJK demo is now
avalable in the GJK-engine. Thanks Christophe Barbé for the
May 22, 1999. A fast and robust implementation of the Gilbert-Johnson-Keerthi
algorithm, which is the 'heart' of SOLID, is released as a separate library,
called GJK-engine. SOLID uses the GJK algorithm for testing intersections,
determining common points, and computing pairs of closest points of convex
objects. An archive file containing the sources for building the library
and an OpenGL demo application can be downloaded here.
See the papers section for an explanation of this
SOLID is a library for collision detection of three-dimensional
objects undergoing rigid motion and deformation. SOLID is designed to be
used in interactive 3D graphics applications, and is especially suited
for collision detection of objects and worlds described in VRML.
Some of its features are:
Object shapes are represented by primitive shapes (box, cone,
cylinder, sphere), and complexes of polytopes (line segments, convex polygons,
convex polyhedra). A single shape can be used to instantiate multiple objects.
Motion is specified by translations, rotations, and nonuniform
scalings of the local coordinate system of each moving object. These
changes can be given absolute or relative to the previous frame. The local
coordinate system can also be set according to an
array of sixteen floats or doubles representing a 4x4 column-major matrix
of an affine transformation, as used in OpenGL.
Deformations of complex shapes can be specified using client-defined
Collision response is defined by the client by means of call-back
functions. Response may be defined per object pair, for all pairs containing
a specific object, and as default for all pairs of objects.
Response call-backs can use collision data describing the
configuration of a pair of colliding objects. As collision data can be
used a point common to both objects, and the closest point pair of the
objects from the previous frame. The latter response type can be used for
approximating the collision plane in physics-based simulations.
Frame coherence is exploited by maintaining a set of pairs
of proximate objects (incremental sweep and prune of axis-aligned bounding
boxes), and caching separating axes for these pairs. This feature
is optional and may be turned on/off at any time during a simulation.
The following papers discuss the algorithms used in SOLID:
G. van den Bergen. "Efficient Collision Detection of Complex
Deformable Models using AABB Trees." Journal
of Graphics Tools, 2(4):1-13 (1997), PDF (164Kb).
G. van den Bergen. "A Fast and Robust GJK Implementation
for Collision Detection of Convex Objects." Journal
of Graphics Tools, 4(2):7-25 (1999), PDF (79Kb).
The library is written in standard
C++ and relies heavily on STL.
Currently it compiles under GNU g++
version 2.8.1 and Visual C++ 5.0. The library has a standard C API and
can be linked to both C and C++ applications. Note that for the use in
C applications, you need to explicitly include the libstdc++ library in
For fast intersection tests and distance computations
between convex polyhedra, SOLID relies on the Qhull
for convex hull computations. Qhull is a free software library and
is available for most platforms. Note that a properly operating SOLID library
can be compiled without using Qhull. However, it is recommended to incorporate
Qhull for a better performance when polyhedra are used.
SOLID library and accompanying C++ classes for 3D transformations are released
under the terms of the GNU Library General Public License (see documentation).
Current SOLID is available for download in the
sourceforge files section (
If this link broken, go to there to find it).
The README file has instructions on how to build and install
SOLID for your platform. In case you have a recent GNU developers environment
installed simply typing make in the root of the distribution directory
Check out the following links related to collision detection:
a collision detection package for convex polyhedra.
idem, uses a separating axis test to determine intersections.
based on the OBB tree (SIGGRAPH '96).
combines I-COLLIDE's sweep 'n' prune with RAPID.
Palmer uses sphere trees in REALISM and ACE.
has written a thesis on collision detection.
So has Gabriel Zachmann.
GJK by Stephen Cameron is a package for incrementally computing the
distance between convex polyhedra.
an improved implementation of the Lin-Canny closest feature tracking algorithm,
as used in I-COLLIDE.
is a collision detection package by Klosowski, e.a., that uses discrete-orientation
polytopes (DOPs) as bounding volumes.
Last updated on June 13th, 2002 by Olivier Michel Olivier.Michel@cyberbotics.com