Patent attributes
The present invention relates to a process and a device for the collision detection of objects by traversal of hierarcichal binary bounding BoxTrees, in which each bounding box pair of a hierarchically lower level is derived from a bounding box from the immediately above level by means of cutting off two sub-volumes by means of two parallel cut-planes. For the collision detection of a first and a second object, for each second bounding box of the bounding BoxTree of the second object to be checked for overlapping with a first bounding box of the bounding BoxTree of the first object, an auxiliary bounding box is computed which is axis-aligned in the object coordinate system of the first object and encloses the second bounding box with minimal volume, and with which the overlap check is conducted instead of with the second bounding box, and the computation results from the level immediately above are utilized for computation of auxiliary bounding boxes of lower levels. The process makes quick collision detection possible with low memory requirements.
