On the computation of groups of bounding boxes for fast test of objects intersection

Abstract

Several computer graphics algorithms (such as ray-tracing) heavily relate their performances to the efficiency of the tests of intersection between the rays of a light source and the objects of a synthetic scene. Some solid modeling and robotics algorithms need also to test quickly the possible interferences of the different parts of a system such as the arms of different robots. To speed-up the test, the free form objects to be tested are encapsulated into boxes and the test starts by performing a check on overlapping of the bounding boxes, thus producing a section of the space where an intersection can occur. Then, only if the boxes overlap the test continues on the original free form objects only in the portion of the 3D-space resulting from the first step. In this paper we present a simple, fast and efficient algorithm (called the Bounding Boxes Group method) to compute a tight bounding entity of a complex object modeled in the constructive solid geometry (CSG). If no upper limit is set to the number of elements of each Bounding Box Group, we demonstrate that our algorithm achieves the tightest possible solution. We present also algorithms which permit to reduce the number of bounding elements still providing a satisfactory and tight encapsulation.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>