Interested Article - 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», какое было дано ему Дэвидом Бэрэффом ( англ. David Baraff Ph. D) в своей работе в 1992 году . Последующие работы, такие как «I-COLLIDE» Коуэна и других именуют алгоритм как «Sweep And Prune».

Примечания

Ericson, Christer (2005), , Morgan Kaufmann series in interactive 3D technology, Amsterdam: Elsevier, pp. 329—338, ISBN 978-1558607323 (неопр.) . Дата обращения: 8 июля 2009. Архивировано 27 июня 2009 года.
Baraff, D. (1992), , Computer Science Department, Cornell University, pp. 52—56 (неопр.) . Дата обращения: 8 июля 2009. Архивировано 5 июня 2010 года.
Cohen, Jonathan D.; Lin, Ming C.; Manocha; Ponamgi, Madhav K. (April 9–12, 1995), (PDF) , Proceedings of the 1995 Symposium on Interactive 3D Graphics (Monterey, CA), pp. 189—196 {{ citation }} : Википедия:Обслуживание CS1 (формат даты) ( ссылка ) (неопр.) . Дата обращения: 8 июля 2009. Архивировано 21 августа 2008 года.