Flexible exploitation of space coherence to detect collisions of convex polyhedra

The subject of this paper is a fast algorithm to compute collision translations for pairs of convex polyhedra with some interesting features. From a theoretical viewpoint, besides the novelty of the approach, the polylog asymptotic trend in the average case is as good as that of the best algorithms proposed to solve similar problems. On the other hand, the measured performances to detect possible collisions from scratch are satisfactory, and this is especially true in the cases where the bodies do not collide. But the most peculiar feature is a simple and flexible mechanism to exploit spatial coherence in a continuous range, which distinguishes this algorithm from all the other proposals we know. Furthermore, the nature of the approach is such that the self-tuning capability is attained at negligible additional costs even for unrelated collision tests. After a brief outline of the main ideas characterizing the approach, a set of numerical results are summarized. The proposed algorithm may be appropriate to plan collision-free paths, both on-line and off-line, on the basis of fine-grain descriptions of the objects in the workspace.