Bounding box collision detection
Tomasz Koziara, Nenad Bičanić · 2005
In this paper we address the problem of intersection detection between pairs of bounding boxes in three-dimensional space. Our motivation for investigating this problem comes from the need for an efficient collision detection framework applicable in the context of large scale contact analysis. Not considering underlying physics of the mechanical contact problem we focus on purely geometrical setting. Moreover we simplify the geometrical entities further by assuming that the objects we are dealing with are axis aligned bounding boxes undergoing arbitrary combination of a simultaneous rigid move, shrinking and expanding along specific directions. This simplification, as it could seem restrictive, allows us not to relay on object representation details and at the same time gain an insight into combinatorial nature of the problem. This in turn helps to realise the place of the collision detection pipeline among other computational tasks in contact mechanics. Assuming we are dealing with n boxes, with k intersecting pairs among them, we try to address the question how close can we get to an ideal algorithm having O (n+ k) running time and O (n) space demands.