An enhanced sweep and prune algorithm for multi-body continuous collision detection

Multi-body collision detection is a key and important technology in societies of computer graphics, system simulation, virtual reality, etc. and has been widely used in various graphics applications. To deal with the collision detection problem in large-scale multi-body scenes, we in this paper proposed a robust and efficient algorithm based on the kinetic "sweep and prune" technique and the event-driven mechanism. Our algorithm first culls redundant detection calculations in finding object pairs that do not collide in the scene with very large number of moving objects and then automatically generates events to predict the object collisions, which probably take place in near future. All the events are pushed into an optimized priority queue to drive the proposed algorithm. By introducing a hybrid bounding box hierarchy in the event processing process, the algorithm can detect the positions where the object pairs collide. Based on our finding that event blocking is an important factor affecting the robustness of the algorithm, we further propose several techniques to alarm blockings to be occurred or relieve the system from blocking state. Experimental results show that our algorithm has good stability and robustness, and it can improve the operating efficiency of multi-body continuous collision detections in an efficient way.