В физическом моделировании , развертка и чернослив является широкой фазой алгоритм , используемым в процессе обнаружения столкновения , чтобы ограничить число пар твердых веществ , которые должны быть проверены для столкновения , то есть пересечения. Это достигается путем сортировки начала (нижняя граница) и концов (верхняя граница) ограничивающего объема каждого твердого тела по ряду произвольных осей. По мере движения твердых тел их начало и конец могут перекрываться. Когда ограничивающие объемы двух твердых тел перекрываются по всем осям, они помечаются для проверки более точными и трудоемкими алгоритмами.
Функция Sweep and Prune использует временную когерентность, поскольку вполне вероятно, что твердые тела существенно не перемещаются между двумя этапами моделирования. Из-за этого на каждом шаге отсортированные списки начала и конца ограничивающего объема могут обновляться с относительно небольшим количеством вычислительных операций. Алгоритмы сортировки, которые быстро сортируют почти отсортированные списки, такие как сортировка вставкой , особенно хороши для этой цели.
В зависимости от типа используемого ограничивающего объема необходимо обновлять размеры ограничивающего объема каждый раз, когда твердое тело переориентируется. Чтобы обойти это, можно использовать временную когерентность для вычисления изменений в геометрии ограничивающего объема с меньшим количеством операций. Другой подход - использовать ограничивающие сферы или другие ограничивающие объемы, не зависящие от ориентации.
Развертки и чернослив также известен как своего рода и размах , [1] называют таким образом в Ph Дэвида Барафф в. D диссертации в 1992 году [2] Позже работает как в 1995 году статьи о I-Collide Джонатан Д. Коэном и др. [3] называют алгоритм поиском и сокращением .
См. Также [ править ]
Ссылки [ править ]
- ↑ Ericson, Christer (2005), Обнаружение столкновений в реальном времени , серия Morgan Kaufmann в интерактивных 3D-технологиях, Амстердам: Elsevier, стр. 329–338, ISBN 978-1-55860-732-3
- ^ Барафф, Д. (1992), Динамическое моделирование непроникающих твердых тел, (докторская диссертация) , факультет компьютерных наук, Корнельский университет, стр. 52–56.
- ^ Коэн, Джонатан Д .; Lin, Ming C .; Маноча; Понамги, Мадхав К. (9–12 апреля 1995 г.), I – COLLIDE: интерактивная и точная система обнаружения столкновений для крупномасштабных сред) (PDF) , Труды симпозиума 1995 г. по интерактивной трехмерной графике (Монтерей, Калифорния), стр. 189–196
Внешние ссылки [ править ]
 | Эта статья о компьютерах - незавершенная . Вы можете помочь Википедии, расширив ее . |
