Sweep and prune is a fast, incremental algorithm for determining the spatial proximity between a number of moving bodies. It is often used as the broad phase of collision detection algorithms.

Originally developed by David Baraff in his 1992 thesis, it has become very popular in modern physics engines. Here I am making available some of the research work on sweep and prune that we have done (Daniel J. Tracy, Samuel R. Buss, Bryan W. Woods). This work, published in IEEE-VR 2009, gives some more detailed analysis than has been done before, and discusses some of the new methods. The code provided consists of one of the configurations, optimized for large virtual environments.

This software is actively used in the Scalable City Project to manage all spatial relationships (collision detection, plus proximity detection for various special-purpose behaviors). The software published here focuses upon a specific configuration that is a subset of work being done. This configuration utilizes segmented interval lists for fast dynamics, grid-based subdivision to limit axial density, and a standard all-overlaps output interface for ease of use. The version used in Scalable City uses the event-based output interface to accelerate many operations.