Sweep and prune (original) (raw)
In physical simulations, sweep and prune is a 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.
| Property | Value |
|---|---|
| dbo:abstract | In physical simulations, sweep and prune is a 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 spheres 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. (en) Sweep And Prune (рус. найти и обрезать) — название алгоритма в физических симуляциях, который применяется в задачах обнаружения столкновений для уменьшения количества пар сплошных тел (англ. solid), которые нужно проверить на столкновение, то есть на пересечение. Таким образом, Sweep And Prune является оптимизационным алгоритмом. Алгоритм Sweep And Prune сортирует начала (верхнюю границу) и концы (нижнюю границу) (англ. Bounding volume) для каждого тела вдоль многих произвольных осей. Когда два тела двигаются, то их начала и концы могут накладываться. Если ограничивающие объёмы двух тел накладываются по всем осям, то данные тела помечаются для проверки на пересечение более точными и трудоёмкими алгоритмами. Алгоритм Sweep And Prune эксплуатирует временную когерентность, так как с высокой вероятностью тела не переместятся на значительное расстояние во время одного шага симуляции. Из-за этого на каждом шаге симуляции сортированный список начал и концов ограничивающих объёмов может быть обновлен с относительно немногими вычислительными операциями. В соответствии с типом используемого ограничивающего объёма является необходимым обновить размерности ограничивающего объёма каждый раз, когда тело переориентировано. Для обхода этого может использоваться временная когерентность для вычисления изменений в геометрии вычислительного объёма, что нуждается в меньшем количестве операций. Другим подходом является использование ограничивающих сфер (англ. Bounding sphere) в качестве ограничивающих объёмов. Алгоритм «Sweep And Prune» также известен под названием «sort and sweep», какое было дано ему Дэвидом Бэрэффом (англ. David Baraff Ph. D) в своей работе в 1992 году. Последующие работы, такие как «I-COLLIDE» Коуэна и других именуют алгоритм как «Sweep And Prune». (ru) |
| dbo:wikiPageExternalLink | https://github.com/bulletphysics/bullet3/blob/master/docs/Bullet_User_Manual.pdf |
| dbo:wikiPageID | 8485760 (xsd:integer) |
| dbo:wikiPageLength | 2980 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1109926649 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bounding_volume dbr:Insertion_sort dbr:Bounding_sphere dbr:Collision dbr:Collision_detection dbr:Game_physics dbc:Computational_physics dbc:Computer_physics_engines dbr:Physics_engine dbr:Physical_simulation dbr:Broad_phase |
| dbp:wikiPageUsesTemplate | dbt:Short_description dbt:Compu-physics-stub |
| dct:subject | dbc:Computational_physics dbc:Computer_physics_engines |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software |
| rdfs:comment | In physical simulations, sweep and prune is a 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. (en) Sweep And Prune (рус. найти и обрезать) — название алгоритма в физических симуляциях, который применяется в задачах обнаружения столкновений для уменьшения количества пар сплошных тел (англ. solid), которые нужно проверить на столкновение, то есть на пересечение. Таким образом, Sweep And Prune является оптимизационным алгоритмом. Алгоритм Sweep And Prune сортирует начала (верхнюю границу) и концы (нижнюю границу) (англ. Bounding volume) для каждого тела вдоль многих произвольных осей. Когда два тела двигаются, то их начала и концы могут накладываться. Если ограничивающие объёмы двух тел накладываются по всем осям, то данные тела помечаются для проверки на пересечение более точными и трудоёмкими алгоритмами. (ru) |
| rdfs:label | Sweep and prune (en) Sweep and prune (ru) |
| owl:sameAs | freebase:Sweep and prune wikidata:Sweep and prune dbpedia-ru:Sweep and prune https://global.dbpedia.org/id/3k6as |
| prov:wasDerivedFrom | wikipedia-en:Sweep_and_prune?oldid=1109926649&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Sweep_and_prune |
| is dbo:wikiPageRedirects of | dbr:Sort_and_sweep |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Box2D dbr:Bounding_volume_hierarchy dbr:Collision_detection dbr:Soft-body_dynamics dbr:Sort_and_sweep |
| is foaf:primaryTopic of | wikipedia-en:Sweep_and_prune |