All Topics  
Sweep and prune

 

 
   Email Print
   Bookmark   Link
 

 

Sweep and prune
 
 
  Topics Sweep and prune Topic Home

In physical simulations, sweep and prune is a broad phase algorithm used during collision detection
Collision detection

In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids....
 to limit the number of pairs of solids that need to be checked for collision
Collision

A collision is an isolated event in which two or more bodies exert relatively strong forces on each other for a relatively short time....
, 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....
 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
Collision detection

In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids....
 as it is likely that solids do not move significantly between two simulation steps.






Discussion
Ask a question about 'Sweep and prune'
Start a new discussion about 'Sweep and prune'
Answer questions from other users
Full Discussion Forum



Encyclopedia


In physical simulations, sweep and prune is a broad phase algorithm used during collision detection
Collision detection

In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids....
 to limit the number of pairs of solids that need to be checked for collision
Collision

A collision is an isolated event in which two or more bodies exert relatively strong forces on each other for a relatively short time....
, 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....
 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
Collision detection

In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids....
 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.

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....
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.

See also

  • Collision detection
    Collision detection

    In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids....
  • 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....
  • Physics engine
    Physics engine

    A physics engine is a computer program that simulates Newtonian physics models, using variables such as mass, velocity, friction and wind resistance....
  • Game physics
    Game physics

    Computer animation physics or game physics involves the introduction of the laws of physics into a simulation or game engine, particularly in 3D computer graphics, for the purpose of making the effects appear more real to the observer....


External links