physical simulation A simulation is an imitative representation of a process or system that could exist in the real world. In this broad sense, simulation can often be used interchangeably with model. Sometimes a clear distinction between the two terms is made, in ...

s, sweep and prune is a broad phase algorithm used during

collision detection Collision detection is the computational problem of detecting an intersection of two or more objects in virtual space. More precisely, it deals with the questions of ''if'', ''when'' and ''where'' two or more objects intersect. Collision detect ...

to limit the number of pairs of solids that need to be checked for

collision In physics, a collision is any event in which two or more bodies exert forces on each other in a relatively short time. Although the most common use of the word ''collision'' refers to incidents in which two or more objects collide with great for ...

, i.e. intersection. This is achieved by sorting the starts (lower bound) and ends (upper bound) of the

bounding volume In computer graphics and computational geometry, a bounding volume (or bounding region) for a set of objects is a closed region that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency ...

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 Coherence expresses the potential for two waves to Wave interference, interfere. Two Monochromatic radiation, monochromatic beams from a single source always interfere. Wave sources are not strictly monochromatic: they may be ''partly coherent''. ...

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 is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Howev ...

, 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 In mathematics, given a non-empty set of objects of finite extension in d-dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is a d-dimensional solid sphere containing all of these ...

s or other orientation independent bounding volumes. Sweep and prune is also known as ''sort and sweep'', referred to this way in David Baraff's Ph.D. thesis in 1992. Later works like the 1995 paper about I-COLLIDE by Jonathan D. Cohen ''et al.'' refer to the algorithm as ''sweep and prune''.

References

External links

Bullet user manual
Computational physics Computer physics engines {{compu-physics-stub

See also

References

External links