Robotics and Mechanisms Laboratory

Pruning Strategies for Distance Queries

The simulation of multi-body dynamical systems often requires the determination of the distance between two moving objects. Such distance queries perform at a very high frequency.

To decrease the computational time needed to perform each distance query, most distance determination algorithms use pre-processing (pruning) algorithms to select among the closest features. By determining the exact separation distance only between the closest features, the computational time required to process those relatively far from each other can be eliminated.

In the present work, four two-stage distance determination algorithms have been developed to allow fast and exact distance calculations between two complex objects. In the first stage, one of the pruning algorithms proposed herein is used to determine the closest features between two given objects. In the second stage, the features selected are used to determine exact distance.

Numerical results for different complex objects show that the proposed algorithms are robust and computationally efficient.