Patent ID: 6862026

Claim:
A process for collision detection of objects comprising providing the objects with first hierarchical binary bounding BoxTrees with axis-aligned bounding boxes in a respective object coordinate system; providing data from which a position of the objects in relation to each other is derivable by conducting a planned transformation step of at least one object; and conducting a simultaneous traversal of said bounding BoxTrees during which, by means of an overlap check of said bounding boxes and of possible polygons contained therein, collision or non-collision of the objects is determined; wherein bounding BoxTrees are provided in which each bounding box pair of a hierarchically lower level is derived from a bounding box from an immediately higher level by cutting off two sub-volumes by means of two parallel cut-planes; and wherein for said collision detection of a first object and a second object, checking each second bounding box of the bounding BoxTree of said second object for overlap with a first bounding box of the bounding BoxTree of said first object, computing an auxiliary bounding box which is axis-aligned in the object coordinate system of said first object and encloses said second bounding box with minimal volume, and conducting therewith said overlap check as opposed to with said second bounding box and utilizing computation results from the immediately higher level for computation of auxiliary bounding boxes of lower levels.