1D sweep-and-prune self-collision detection for deforming cables

摘要

Detecting self-collision for cables and similar objects is an important part of numerous models in computational biology (protein chains), robotics (electric cables), hair modeling, computer graphics, etc. In this paper the 1D sweep-and-prune algorithm for detecting self-collisions of a deforming cable comprising linear segments is investigated. The sweep-and-prune algorithm is compared with other state-of-the-art self-collision detection algorithms for deforming cables and is shown to be up to an order of magnitude faster than existing algorithms for cables with a high proportion of segments moving. We also present a multithreaded version of the algorithm and investigate its performance. In addition, we present worst-case bounds for 1D sweep-and-prune algorithms whereby the colliding objects do not exceed a certain object density, and apply these results to deforming cables.