Sweep and prune

Sweep and prune

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.

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 spheres or other orientation independent bounding volumes.

Sweep and prune is also know as "sort and sweep" [Citation |last=Ericson|first=Christer|pages=329-338|title=Real-time collision detection|publisher=Elsevier|place=Amsterdam|isbn =978-1558607323|series=Morgan Kaufmann series in interactive 3D technology|date=2005|url=http://realtimecollisiondetection.net/books/rtcd/] being called that way at David Baraff Ph. D thesis in 1992 [Citation |last=Baraff|first=D.|title=Dynamic Simulation of Non-Penetrating Rigid Bodies, (Ph. D thesis)|date=1992|publisher=Computer Science Department, Cornell University |url=http://www.cs.cmu.edu/~baraff/papers/index.html|pages=52-56 ] . Later works like the 1995 paper about I-COLLIDE by Cohen "et al" [Citation| last=Cohen|first=Jonathan D.|last2=Lin|first2=Ming C.|last3=Manocha|first4=Dinesh|last4=Ponamgi|first4=Madhav K.|pages=189-196 |title=I–COLLIDE: an Interactive and Exact Collision Detection System for Large Scale Environments)|publisher=Proceedings of the 1995 Symposium on Interactive 3D Graphics (Monterey, CA)|date=April 9-12, 1995|url=http://www.cs.jhu.edu/~cohen/Publications/icollide.pdf] refer to the algorithm as "sweep and prune".


ee also

*Collision detection
*Bounding volume
*Physics engine
*Game physics

External links

* [http://bulletphysics.com/ftp/pub/test/physics/Bullet_User_Manual.pdf Bullet user manual]
* [http://www.elsevier.com/wps/find/bookdescription.cws_home/677976/description Collision Detection in Interactive 3d Environments]
* [http://www.ziggyware.com/readarticle.php?article_id=128 Broadphase Collision Detection]

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Sweep and prune — (рус. найти и обрезать) название алгоритма в физических симуляциях, который применяется в задачах обнаружения столкновений для уменьшения количества пар сплошных тел (англ. solid), которые нужно проверить на столкновение, то есть на… …   Википедия

  • Обнаружение столкновений — (англ. Collision detection)  вычислительная проблема обнаружения пересечений между собой двух или больше объектов. Тема чаще всего связана с её использованием в физических движках, компьютерной анимации и робототехнике. В дополнение к… …   Википедия

  • Collision detection — For collision detection on networks see CSMA/CD 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 …   Wikipedia

  • Box2D — Infobox Software name = Box2D caption = developer = Erin Catto latest release version = 2.0.1 latest release date = 2008 04 13 [http://sourceforge.net/projects/box2d Box2D on Sourceforge] ] latest preview version = latest preview date = operating …   Wikipedia

  • Box2D — Физический движок Разработчик Эрин Катто (англ. Erin Catto) Поддерживаемая ОС не зависит от ОС Написан на языке …   Википедия

  • Fairyfly — Fairyflies Temporal range: Early Cretaceous to present …   Wikipedia

  • History of Santa Clara County, California — Santa Clara County, California is one of California s original counties, but its history extends far back into prehistory.Early historyThe first documented inhabitants included the Ohlone, residing on Coyote Creek and Calaveras Creek, although… …   Wikipedia

  • Amputation — Removal of part or all of a body part enclosed by skin. For example, removal of part of a finger or an entire finger would be termed an amputation. Removal of an appendix, on the other hand, would not be termed amputation. A person who has… …   Medical dictionary

  • French Republican Calendar — History of France series French Revolution Causes Estates General National Assembly Storming of the Bastille National …   Wikipedia

  • Prophecies of Joseph Smith, Jr. — Joseph Smith Jr., the founder of the Latter Day Saint movement, is viewed as a prophet in the tradition of the ancient prophets recorded in the Bible by members of the Latter Day Saint movement. This article examines some of the prophecies… …   Wikipedia

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.