Sweep and prune

Sweep And Prune (рус. найти и обрезать) — название алгоритма в физических симуляциях, который применяется в задачах обнаружения столкновений для уменьшения количества пар сплошных тел (англ. solid), которые нужно проверить на столкновение, то есть на пересечение. Таким образом, Sweep And Prune является оптимизационным алгоритмом. Алгоритм Sweep And Prune сортирует начала (верхнюю границу) и концы (нижнюю границу) ограничивающего объёма (англ. Bounding volume) для каждого тела вдоль многих произвольных осей. Когда два тела двигаются, то их начала и концы могут накладываться. Если ограничивающие объёмы двух тел накладываются по всем осям, то данные тела помечаются для проверки на пересечение более точными и трудоёмкими алгоритмами.

Алгоритм Sweep And Prune эксплуатирует временную когерентность, так как с высокой вероятностью тела не переместятся на значительное расстояние во время одного шага симуляции. Из-за этого на каждом шаге симуляции сортированный список начал и концов ограничивающих объёмов может быть обновлен с относительно немногими вычислительными операциями.

В соответствии с типом используемого ограничивающего объёма является необходимым обновить размерности ограничивающего объёма каждый раз, когда тело переориентировано. Для обхода этого может использоваться временная когерентность для вычисления изменений в геометрии вычислительного объёма, что нуждается в меньшем количестве операций. Другим подходом является использование ограничивающих сфер (англ. Bounding sphere) в качестве ограничивающих объёмов.

Алгоритм «Sweep And Prune» также известен под названием «sort and sweep»,^[1] какое было дано ему Дэвидом Бэрэффом (англ. David Baraff Ph. D) в своей работе в 1992 году^[2]. Последующие работы, такие как «I-COLLIDE» Коуэна и других именуют алгоритм как «Sweep And Prune».^[3]

Примечания

↑ Ericson, Christer (2005), Real-time collision detection, Morgan Kaufmann series in interactive 3D technology, Amsterdam: Elsevier, pp. 329—338, ISBN 978-1558607323, Архивировано 27 июня 2009, Дата обращения: 8 июля 2009 Источник (неопр.). Дата обращения: 8 июля 2009. Архивировано 27 июня 2009 года.
↑ Baraff, D. (1992), Dynamic Simulation of Non-Penetrating Rigid Bodies, (Ph. D thesis), Computer Science Department, Cornell University, pp. 52—56, Архивировано 5 июня 2010, Дата обращения: 8 июля 2009 Источник (неопр.). Дата обращения: 8 июля 2009. Архивировано 5 июня 2010 года.
↑ 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) (PDF), Proceedings of the 1995 Symposium on Interactive 3D Graphics (Monterey, CA), pp. 189—196, Архивировано (PDF) 21 августа 2008, Дата обращения: 8 июля 2009 Источник (неопр.). Дата обращения: 8 июля 2009. Архивировано 21 августа 2008 года.