Verfahren und Vorrichtung zur Kollisionserkennung von Objekten

Die vorliegende Erfindung betrifft eine Vorrichtung sowie ein Verfahren zur Kollisionserkennung von Objekten durch Traversierung hierarchischer binaerer Bounding-Box-Baeume, bei denen jedes Bounding-Box-Paar einer hierarchisch tieferen Stufe aus einer Bounding-Box der hierarchisch unmittelbar darueberliegenden Stufe durch Abschneiden zweier Teilvolumina mittels zweier achsenparalleler Schnittebenen hervorgegangen ist. Fuer die Kollisionserkennung eines ersten und eines zweiten Objektes wird fuer jede auf Ueberlappung mit einer ersten Bounding-Box des ersten Objektes zu pruefende zweite Bounding-Box des zweiten Objektes eine Hilfs-Bounding-Box berechnet, die achsenparallel im Objektkoordinatensystem des ersten Objektes ausgerichtet ist, wobei die Ueberlappungspruefung mit der Hilfs-Bounding-Box anstelle der zweiten Bounding-Box durchgefuehrt wird und bei der Berechnung der Hilfs-Bounding-Box tieferer Stufen die Berechnungsergebnisse der unmittelbar darueberliegenden Stufe verwendet werden. Das Verfahren ermoeglicht eine schnelle Kollisionserkennung bei geringem Speicherbedarf.

DE 10106023 A UPAB: 20021108 NOVELTY - The collision detection involves first forming hierarchical binary bounding box trees with axially parallel bounding boxes and data in the respective object coordination system. From the tree structures the relative positions of the objects can be determined by carrying out a transformation on one of the objects. Then a simultaneous traversing of the tree structures is carried out. By testing for overlapping of the bounding boxes and polygons contained in them, it can be determined whether the objects will collide. In the bounding box tree structures, each bounding box pair has a lower hierarchical position. DETAILED DESCRIPTION - For collision detection, where bounding boxes of the objects overlap an auxiliary bounding box is calculated which is aligned with the coordinate system of the first object and surrounds the second object as closely as possible. INDEPENDENT CLAIMS also cover an apparatus for carrying out the method. USE - Especially for use in robot control, computer animation systems and virtual reality systems. ADVANTAGE - The system allows very fast collision detection whilst requiring very little memory space.