Sweep and prune

From Wikipedia, the free encyclopedia

In physical simulations, sweep and prune is a broad phase algorithm used at collision detection to limit the number of pairs of solids 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 axis. As the solids move their starts and ends may overlap. When the bounding volume of two solids overlap in all axis they are flagged to be test by more precise and time consuming algorithms.

Sweep and prune exploits temporal coherence as is likely that solids do not move too much between two simulation steps. Because of that, at each step the sorted lists of starts and ends of bounding volumes can be updated with few computational operations.

According with the type of bounding volume used, 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 less operations. Another approach is to use bounding spheres or other orientation independent bounding volume.

Sweep and prune is also know as sort and sweep[1] being called that way at David Baraff Ph. D thesis in 1992[2]. Later works like the 1995 paper about I-COLLIDE by Cohen et al [3] refer to the algorithm as sweep and prune.


[edit] References

  1. ^ Ericson, Christer (2005), Real-time collision detection, Morgan Kaufmann series in interactive 3D technology, Amsterdam: Elsevier, pp. 329-338, ISBN 978-1558607323, <http://realtimecollisiondetection.net/books/rtcd/> 
  2. ^ Baraff, D. (1992), Dynamic Simulation of Non-Penetrating Rigid Bodies, (Ph. D thesis), Computer Science Department, Cornell University, pp. 52-56, <http://www.cs.cmu.edu/~baraff/papers/index.html> 
  3. ^ Cohen, Jonathan D.; Lin, Ming C.; Manocha & Ponamgi, Madhav K. (April 9-12, 1995), I–COLLIDE: an Interactive and Exact Collision Detection System for Large Scale Environments), Proceedings of the 1995 Symposium on Interactive 3D Graphics (Monterey, CA), pp. 189-196, <http://www.cs.jhu.edu/~cohen/Publications/icollide.pdf> 

[edit] See also

[edit] External links

 This computer-related article is a stub. You can help Wikipedia by expanding it.