The problem of collision detection is fundamental to interactive
applications such as computer animation and virtual environments. In
these fields, prompt recognition of possible impacts and the pair of
closest points between two polytopes in collision are important for
computing real-time response.
We present a simple exact collision detection algorithm for convex polytopes.
The algorithm finds quickly a separating plane between two polytopes if they are non-colliding,
or else reports collision and the pair of closest points between them if it cannot possibly find a separating plane. In the case of non-collision, the separating plane found for one
time frame is cached as a witness for the next time frame; this use
of time coherence further speeds up the algorithm in dynamic applications.
Both temporal and geometric coherences are exploited to make this
algorithm run in expected constant time empirically. In practice,
our algorithm is significantly faster than existing methods.
Q_COLLIDE is an implementation of our algorithms. It is
modified and improved from the previous
I_COLLIDE
collision detection packages. It is a quick and exact collision
detection library for large scale virtual environments composed of convex polyhedra. For
non-convex polyhedra they can be decomposed into set of convex
polyhedral before using this library. Q_COLLIDE exploits geometric and
temporal coherence so that simulation of many complex objects can be
done in real time and interactively.
When there is a collision, a modified Gibert algorithms (originally
run in expected linear time, now run in expected constant time) is
used to determinate the closest point between the polytopes the
moment before there is a collision. In other words,
we save the transformation matrix of previous time frame
and use it to determine the closest point when there is a collision.
There is also another procedure which call the modified Gibert algorithm
directly in case the closest point is of interest even though there is
no collision.
Difference between Q_COLLIDE and
I_COLLIDE
Q_COLLIDE uses separating vector algorithm whereas I_COLLIDE
uses the closest features tracking algorithm as the main collision
detection algorithm when bounding boxes overlap.
I_COLLIDE computes the closest features pair at every time frame
whereas Q_COLLIDE computes the closest features/points pair only at
the time frame immediately before a collision occurs.
Q_COLLIDE computes only the closest pair of closest features whereas
I_COLLIDE computes both the closest pair of points and the closest pair of
features.
Q_COLLIDE uses less memory and is more efficient then I_COLLIDE.
Only the lower layer of I_COLLIDE for exact collision detection is replaced.
Comparision of Q_COLLIDE and I_COLLIDE
Experiments
Experiments have been carried out to investigate the performance of
Q_COLLIDE compared with I_COLLIDE with different number of vertices
when translational/rotational velocity or density of the environment change.
The simulation uses 500 polytopes of the same number of vertices moving in a closed
environment. The time is recorded for a simulation of 1000 frames
using SGI/Indy (R4600) machine.
Polytopes of three different shapes are used: ellipsoid, a thin rod,
and flat plate, obtained by randomly sampling points on
the surface of an ellipsoid, a thin rod, and a flat plate, respectively.
They provide a variety of different shapes for testing.
Each object has the same translational velocity and
rotational velocity.
When there is a collision between two polytopes,
their rotational and translational velocities are reversed.
Different Translational Velocity
Different Rotational Velocity
Different Density
In is shown that in all cases Q_COLLIDE is significantly faster and
more efficient then I_COLLIDE. As an example, for velocity that is
20% of object radius per time frame and the number of vertices of each
polytope is 500, nearly 28 times speedup by Q_COLLIDe is achieved.
Why Q_COLLIDE is faster ?
I_COLLIDE uses closest feature tracking algorithm (CF) and
a linear programming algorithm whereas Q_COLLIDE uses
separating vector algorithm (SV) and the improved Gilbert's
algorithm.
When the translational/rotational velocity increases or the
complexity increases, the CF algorithm needs more time
to walk around on the boundary of polytopes in order to find the
closest features, since each step may walk from vertex to
edge, edge to
face, face to vertex etc. However, in the SV algorithm
and the improved Gilbert's algorithm a walk is always from vertex
to vertex so they proceed "faster".
The condition for a walk to take place in the SV algorithm or
the improved Gilbert's algorithm
is simply a comparison between dot product of vectors. But in CF it
requires an involved
checking about whether
one feature lies inside the Voronoi regions of other features.
CF transforms every feature along the walking path
to the world coordinate system for comparison. However,
in SV and the improved Gilbert's algorithm, the comparison is done
in the local coordinate system of polytopes only.
Only two coordinate
transformation are required for a searching for a supporting vertex and there is no
need to transform every vertex along the walking path to the world
coordinate system during the search.
The I_COLLIDE library needs to call another linear
programming algorithm for exact collision detection every time
when there is a recycling of features (e.g. a collision occurs).
Thus it runs in O(n) time in the case of collision and cases where the
closest features algorithm cannot resolve conflicts. However,
Q_COLLIDE uses a nearly constant time algorithm even when
there is a collision.
Papers
For a description of the algorithms used in Q_COLLIDE, see:
Papers
Thesis
For a complete description of the algorithms, see:
Thesis
Code
Due to legal issues, the authors of I_COLLIDE prevent us to
freely distribute the source code of the library publicly.
