Collision Detection Library

Overview

CD is a collision detection library intended for use in games based on DIRECTX. It was written as part of my Bs. Sc. thesis, which I wrote way back in 2002. Algorithm is based on QuickCD algorithm. There are two main differences compared to QuickCD: the first is the way how two hierarchical trees are compared and  the second is the choice of primitives in tree – CD uses convex patches composed of limited number of triangles. The algorithm is described in CD algorithm section and more in detail in pdf file which is available in Downloads section, where you’ll also find source code and other stuff.

Collision detection algorithms

Collision detection algorithms are used in many different areas: virtual reality, robotics and computer graphics are just a few of them. The brute force approach to collision detection would be to check all pairs of triangles from both objects that could be colliding. This approach is obviously very slow, so here we come to different collision detection algorithms. Those algorithms need to be fast, accurate and robust.

Collision detection algorithms can be divided into two groups:

  • algorithms that can be used only for collision detection between two convex shaped objects and
  • algorithms that are not limited by object’s shape.

First group is represented by algorithms such as I-COLLIDE and Q-COLLIDE (they are not the only representatives of algorithms in this group, they are just the ones I focused on). Since those algorithms are focused on more narrow field of usage they are also significantly faster in those cases than algorithms from second group.

The second group is represented by algorithms based on sphere trees, SOLID, RAPID, QuickCD, SWIFT++ and other algorithms including CD. Those algorithms use a combination of bounding volume and hierarchy tree (the deeper we go to the tree the more accurate the approximation of object is). On next picture you can see some examples of bounding volumes: sphere, AABB (axis aligned bounding volumes) – used in SOLID algorithm and k-dop bounding volume – used in QuickCD and also in CD.

volumes-medium

CD algorithm

The algorithm is based on QuickCD. Many properties of CD algorithm are based on experiments performed by the authors of QuickCD algorithm (the most obvious is the choice of 18-dop bounding volume). There are two major differences between QuickCD and CD:

  • QuickCD is designed with assumption that one of the two objects that are tested for collision is static, CD on the other hand does not have this limitation (both objects can be dynamic).
  • The leafs of QuickCD’s hierarhical tree contain a limited number of triangles for dynamic object and a single triangle for static object. CD contains convex patches that are also limited by a maximum number of triangles on such patch.

The principle of convex patches is used on the last stage of algorithm: triangle-triangle tests. Not all possible pairs of triangles from two patches need to be tested due to their convexity.

BUILDING HIERARCHY TREE

Two steps are performed while building hierarchy tree. First we need to read all object’s data that is all object’s triangles since we are only interested in it’s geometry. All those triangles form the root of the tree. The dimensions of the bounding volume are automaticly updated when a new triangle is added. Convex patches are calculated in this step also. Maximum number of triangles on convex patch is determined by a constant in algorithm. A triangle is added to existing convex patch if it conforms to following rules when comapred to every single triangle on patch:

  • normals of both triangles are facing the same side of the patch,
  • the surface of other triangle must not be visible from the first triangle and vice versa,
  • if triangles are not touching then the triangle being added must not intersect the plane formed by second triangle.

reflex_edge-full

Example of breaching the first rule: normals of triangles A and B are not facing the same side.

triangles_seen-full

Second condition violated: Triangle B can be seen from triangle A and vice versa.

intersect_plane-full

Triangle does nor conform to third rule: If triangle A is added the plane formed by triangle B would be intersected.

convex_patch-full

An example of convex patch formed by three triangles.

A new convex patch is formed if there are no existing convex patches or triangle can’t be added to any of the existing ones.

The second step begins when all triangles are added. This stage is all about building the tree hierarchy, that is splitting the nodes until the node contains only one convex patch. This step is performed in the similar way as in QuickCD. More details about building the hierarchy tree can be found in .pdf document which is available in Downloads section.

COLLISION DETECTION

Two steps are performed during collision detection. First the two trees are compared and if necessary triangle-triangle tests are executed (if comparison of trees comes to the leafs of both trees). During comparison of the trees the following heuristics is used (this was yielding the best results):

  • If both nodes are leafs do a triangle-triangle test.
  • If one node is a leaf and the other an internal node, unfold internal node with the smaller son being visited first.
  • if both nodes are internal unfold the larger node first.

The algorithm which compares two convex patches is somewhat complicated so it won’t be described here (details can be found in .pdf document). The convex property of patches is used here – that is some of the triangles can be ignored since we know that they can’t intersect because of convexity.

The algorithm can be stopped when a given timeout is exceeded, by default there is no timeout. Algorithm results are of course less accurate in cases when timeout is exceeded. Algorithm always stops when a defined number of collision points was found.

Usage of collision detection algorithms

METHODS USED TO DETERMINE NECESSARY COLLISION TESTS

In general, a collision detection algorithm is used to check if there is a collision between two objects in space. But in reality we have many objects that can collide with each other. So we have to come up with a method that determines which objects really need to be tested.

Axis sort

The idea behind this method is to project bounding volumes of all objects in space onto some selected axis. If projection of two distinct bounding volumes overlap we need to use collision detection algorithm to precisely determine if there really is a collision. This method behaves very good in cases where the scene is sparse but it’s performance quickly deteriorates when the scene is dense.

Grid

This method uses more information about object’s location in space. The size of the cell in grid must be bigger than the biggest bounding volume of any object. This condition assures that the objects for which there is a possibility of collision are spaced at most one cell apart. Objects are sorted into cells based on their bounding volume’s center point. As a consequence of that at most half of a given bounding volume can be in neighbouring cell. This also means that objects spaced at least two cells apart can’t collide. There are two simple rules to create a list of necessary tests:

  • if a cell contains more than one object then all possible pairs of objects are added to necessary tests list,
  • if the cell is not empty and it’s neighbouring cell is also not empty we add all possible pairs of objects in those cells to necessary tests list.

With proper searching we avoid double checking of any cell (for a 2D grid we would start searching the grid in upper left corner and check only the cells below and right of the current cell before moving to next cell and repeating the same procedure).

If we consider the fact that a given object does not change it’s cell too often, we can improve this procedure by updating the necessary tests list only when at least one object has changed the cell to which it belongs.

Comparison of intervals on X, Y and Z axis

This procedure is similar to axis sort, but in this case we project bounding volumes on three axis. If intervals for given two objects overlap on all three axises then we have a possible collision and we need to add the pair of objects to necessary tests list. A pair of objects is removed from test list if it overlaped before but does not overlap on all three axis at this moment. This method is used in I-COLLIDE and you can find more about it there.

Use of human perception

This method uses human perception to sort necessary tests by their importance. Objects that are spotted faster than others have higher priority. That is a simple consequence of human perception of eniviroment – object that are bigger, nearer etc. are spotted faster. See more in paper that can be found on John Dingliana Research page.

OBJECT’S COLLISION RESPONSE

Usually we need objects to respond to collision. Physical model is the factor that determines how accurate the response will be. Physical model includes several parameters such as object’s mass, speed, acceleration etc. There are several other factors that have influence on object’s movement: gravity, air resistance, friction, etc.

A SIMPLE GAME

Some of the methods described in this topic are used in a simple game that I wrote to demonstate the use of CD collision detection algorithm. The game is available for download in Downloads section.

game-medium

Downloads

Note: To compile source code you will need some ancient software. The project was written in Visual Studio 6 and DirectX 8. A lot has changed since so good luck! Also a look at this code makes me realise that I have come a long way since graduating!

Description of CD algorithm (english version)
Description of CD algorithm (original, slovenian version)
Chm help file
All you need to use CD in your applications
C++ source of CD
Test case executable
Test case source code
Installation of simple game that uses CD library
Source of simple game

Links

Note: These links were current as of circa 2002. Unfortunately some of them are broken now and I am unable to find the new location of this content (if it still exists). Nevertheless, I am listing them here for completeness.

QuickCD (Quick Collision Detection)
RAPID (Robust and Accurate Polygon Interference Detection System)
SOLID (Software Library for Interference Detection)
SWIFT++ (Speedy Walking via Improved Feature Testing for Non-Convex Objects)
I-COLLIDE (An interactive and exact collision detection system for large scale enviroments)
John Dingliana Research
Home page for Qhull
Jgt: triangle-triangle intersection
Personal Page of Martin Held
DirectX Home Page