Efficient collision culling by a succinct bi-dimensional sweep and Prune algorithm

We present an improved variant of the broad phase collision-detection algorithm called Sweep and Prune (SaP) for large datasets in three-dimensional environments. Unlike previous solutions, our algorithm performs a stepwise sweep over a primary and a secondary axis, which makes it inherently bi-dimensional. As a result, it gracefully handles even challenging high-density scenarios, and it is much less sensitive to the interval clustering problem, where the number of false positives grows superlinearly along the axes, which is a characterizing problem for traditional SaP methods that by dimensional reduction essentially are one-dimensional approaches. Furthermore, our algorithm gains additional performance by the use of a succinct data structure, which allows the objects to be represented and accessed in a cache-friendly way. Experimental results confirm that our algorithm maintains attractive query times in simulations with hundreds of thousands of bodies, even in stress-test scenarios.