Abstract
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 multi-threaded 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.
Keywords
Bounding volume hierarchy, Sweep-and-prune, Self-collision detection, Cable simulation
Acknowledgement
The author is greatly indebted to the suggestions and comments provided by a number of anonymous referees. This work was supported by the Swedish Governmental Agency for Innovation Systems, VINNOVA through the FFI Sustainable Production Technology Program, the Wingquist Laboratory VINN Excellence Center and is part of the Sustainable Production Initiative and the Production Area of Advance at Chalmers University of Technology. The author is also greatly indebted to Tomas Hermansson for his many valuable discussions, the help with programming, for providing the code for the sphere BVH and also for helping teach the author how to use the IPS software.
Authors and Affiliations
- E. Shellshear, Fraunhofer Chalmers Centre