Подметать и подрезать

В физическом моделировании « развертка и обрезка» — это широкофазовый алгоритм, используемый при обнаружении столкновений для ограничения количества пар твердых тел, которые необходимо проверить на предмет столкновения , то есть пересечения. Это достигается путем сортировки начал (нижняя граница) и концов (верхняя граница) ограничивающего объема каждого твердого тела по ряду произвольных осей. По мере движения тел их начала и концы могут перекрываться. Когда ограничивающие объемы двух твердых тел перекрываются по всем осям, они помечаются для проверки с помощью более точных и трудоемких алгоритмов.

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

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

Очистка и обрезка также известна как сортировка и очистка . ^[1] об этом говорится в докторской диссертации Дэвида Барафа. диссертацию в 1992 году. ^[2] Более поздние работы, такие как статья Джонатана Д. Коэна и др. об I-COLLIDE 1995 года. ^[3] ссылайтесь на алгоритм как развертку и обрезку .

См. также

Ссылки

^ Эриксон, Кристер (2005), Обнаружение столкновений в реальном времени , серия Моргана Кауфмана по интерактивным 3D-технологиям, Амстердам: Elsevier, стр. 329–338, ISBN 978-1-55860-732-3
^ Барафф, Д. (1992), Динамическое моделирование непроникающих твердых тел (докторская диссертация) , Факультет компьютерных наук, Корнельский университет, стр. 52–56.
^ Коэн, Джонатан Д.; Линь, Мин К .; Маноча; Понамги, Мадхав К. (9–12 апреля 1995 г.), I-COLLIDE: интерактивная и точная система обнаружения столкновений для крупномасштабных сред) (PDF) , Материалы симпозиума 1995 г. по интерактивной 3D-графике (Монтерей, Калифорния), стр. 189–196

Внешние ссылки

Руководство пользователя пули

Эта вычислительной физике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[1] Эриксон, Кристер (2005), Обнаружение столкновений в реальном времени , серия Моргана Кауфмана по интерактивным 3D-технологиям, Амстердам: Elsevier, стр. 329–338, ISBN 978-1-55860-732-3

[2] Барафф, Д. (1992), Динамическое моделирование непроникающих твердых тел (докторская диссертация) , Факультет компьютерных наук, Корнельский университет, стр. 52–56.

[3] Коэн, Джонатан Д.; Линь, Мин К .; Маноча; Понамги, Мадхав К. (9–12 апреля 1995 г.), I-COLLIDE: интерактивная и точная система обнаружения столкновений для крупномасштабных сред) (PDF) , Материалы симпозиума 1995 г. по интерактивной 3D-графике (Монтерей, Калифорния), стр. 189–196

[1]

[2]

[3]