Introduction

Collision Detection is an important problem in fields like motion planning, computer animation and virtual reality. We can loosely define the problem to be the search for intersecting planes of different 3D models in a scene. Worst case, the complexity of collision detection is O(N²) with N the number of faces in the scene. Luckily, there exist many approach that reduce very strongly the number of face-face pairs that have to be checked in a rapid way. A collision detection technique usually works in two levels. One part of the algorithm rapidly determines which objects are close enough to potentially collide. The second part checks all object-object pairs returned by the first step for face-level intersections. Also for this step, we use some sort of technique to reduce the number of face-face pairs.

In this paper, we will discuss a parallel implementation of a collision detection strategy. For the object level, we use a technique called Sweep and Prune. Face-Face pairs are eliminated using Axis Aligned Bounding Box trees or Oriented Bounding Box trees.