A large class of general-purpose collision detection algorithms use the strategy of successive trivial rejection. This is a divide-and-conquer approach in which entire groups of polygons are tested for potential overlap by testing their bounding volumes for overlap. If the bounding volumes are disjoint, then there is no possible contact between the polygons they contain. But if the bounding volumes do overlap, then the contact status for the polgyons is indeterminate. In this case, the bounded polygons are divided into still smaller groups, and the bounding volumes for these groups are tested for overlap, and so on. In this manner, we conduct a depth-first search through a tree of overlap tests, as depicted in theabove figure. When we encounter a leaf node in the hierarchy which can no longer be divided, we resort to testing directly the primitive therein.
There are many variations of this basic strategy, and one of the most common is to adjust the choice of bounding volume. Bounding volumes range in complexity from spheres to convex hulls. Generally speaking, the simpler shapes, such as spheres, have less expensive overlap tests than the complex ones, such as convex hulls. But the simpler shapes also adhere to the underlying geometry less tightly -- they amount to a less accurate approximation of the model -- and thus more overlap tests are required to resolve a collision query. So, as we move across the spectrum of bounding volume complexity, we go from many inexpensive overlap tests to fewer but more costly overlap tests. The optimum choice of bounding volume is very much an open problem.
The basis of the RAPID system is to embed each model in its own hierarchy (a binary tree) of oriented bounding boxes (OBBs). Each OBB is oriented and scaled along each axis so as to tightly bound the underlying polygons. Along the left margin are successive levels of an OBB hierarchy for a plane curve. Along the right margin, for comparison, we show successive levels of an axis-aligned bounding box (AABB) hierarchy for the same curve.
What sets OBBTrees apart is that using arbitrary orientations enables the rectanguloids to approximate geometry more accurately. The approximation convergence is quadratic as we descend the levels of the hierarchy. For trees of spheres, cubes, and rectanguloids with a finite fixed set of orientations (such as AABBs), the convergence is linear. The result is that for complex models containing highly polygonalized surfaces in close proximity, such as with a piston moving inside a combustion chamber, OBBTrees require asymptotically fewer overlap tests than the hierarchies mentioned above -- resulting in significantly faster collision query times.
The heart of the RAPID system is the oriented bounding box overlap test. This can be performed in less than 200 arithmetic operations. Since early exit of the routine is frequently possible, average operation count is close to 100 arithmetic operations per call.