Sweep and prune
Encyclopedia
In physical simulations, sweep and prune is a broad phase algorithm used during collision detection
to limit the number of pairs of solids that need to be checked for collision
, i.e. intersection. This is achieved by sorting the starts (lower bound) and ends (upper bound) of the bounding volume
of each solid along a number of arbitrary axes. As the solids move, their starts and ends may overlap. When the bounding volumes of two solids overlap in all axes they are flagged to be tested by more precise and time consuming algorithms.
Sweep and prune exploits temporal coherence as it is likely that solids do not move significantly between two simulation steps. Because of that, at each step, the sorted lists of bounding volume starts and ends can be updated with relatively few computational operations. Sorting algorithms which are fast at sorting almost-sorted lists, such as insertion sort
, are particularly good for this purpose.
According with the type of bounding volume used, it is necessary to update the bounding volume dimensions every time a solid is reoriented. To circumvent this, temporal coherence can be used to compute the changes in bounding volume geometry with fewer operations. Another approach is to use bounding sphere
s or other orientation independent bounding volumes.
Sweep and prune is also known as sort and sweep being called that way at David Baraff Ph. D thesis in 1992. Later works like the 1995 paper about I-COLLIDE by Cohen et al. refer to the algorithm as sweep and prune.
Collision detection
Collision detection typically refers to the computational problem of detecting the intersection of two or more objects. While the topic is most often associated with its use in video games and other physical simulations, it also has applications in robotics...
to limit the number of pairs of solids that need to be checked for collision
Collision
A collision is an isolated event which two or more moving bodies exert forces on each other for a relatively short time.Although the most common colloquial use of the word "collision" refers to accidents in which two or more objects collide, the scientific use of the word "collision" implies...
, i.e. intersection. This is achieved by sorting the starts (lower bound) and ends (upper bound) of the bounding volume
Bounding volume
In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operations by using simple volumes to contain more complex...
of each solid along a number of arbitrary axes. As the solids move, their starts and ends may overlap. When the bounding volumes of two solids overlap in all axes they are flagged to be tested by more precise and time consuming algorithms.
Sweep and prune exploits temporal coherence as it is likely that solids do not move significantly between two simulation steps. Because of that, at each step, the sorted lists of bounding volume starts and ends can be updated with relatively few computational operations. Sorting algorithms which are fast at sorting almost-sorted lists, such as insertion sort
Insertion sort
Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...
, are particularly good for this purpose.
According with the type of bounding volume used, it is necessary to update the bounding volume dimensions every time a solid is reoriented. To circumvent this, temporal coherence can be used to compute the changes in bounding volume geometry with fewer operations. Another approach is to use bounding sphere
Bounding sphere
In mathematics, given a non-empty set of objects of finite extension in n-dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is an n-dimensional solid sphere containing all of these objects.In the plane the terms bounding or enclosing...
s or other orientation independent bounding volumes.
Sweep and prune is also known as sort and sweep being called that way at David Baraff Ph. D thesis in 1992. Later works like the 1995 paper about I-COLLIDE by Cohen et al. refer to the algorithm as sweep and prune.