Обнаружение столкновений

Обнаружение столкновений — это вычислительная задача определения пересечения или наложения двух и более объектов в виртуальном пространстве. Точнее, задача сводится к выяснению, происходит ли, когда и где пересекаются объекты. Обнаружение столкновений — классическая задача вычислительной геометрии с приложениями в компьютерной графике, физических симуляциях, видеоиграх, робототехнике (включая автономное вождение) и вычислительной физике. Алгоритмы обнаружения столкновений подразделяются на обрабатывающие 2D- и 3D-объекты.

Обзор

Шары для бильярда, сталкивающиеся друг с другом в виртуальном пространстве, — классический пример применения обнаружения столкновений

Обнаружение столкновений тесно связано с вычислением расстояния между объектами: несколько объектов пересекаются, когда расстояние между ними становится нулевым или даже отрицательным. Отрицательное расстояние указывает на то, что один объект проник внутрь другого. Для корректного обнаружения столкновений требуется учитывать не только расстояние между объектами, но и их контекст.

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

Обнаружение столкновений обычно включает динамические объекты, что добавляет временное измерение к расчетам расстояния. Вместо простого измерения расстояния между статическими объектами часто требуется предсказать, приведёт ли движение объектов в будущем к моменту их соприкосновения — что значительно увеличивает вычислительные ресурсы.

В многокомпонентных системах наивный подход заключался бы в проверке всех парных сочетаний n объектов, что требовало бы ${n(n-1)}/{2}$ операций, то есть сложность росла квадратично по числу объектов.

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

Распространённый способ повышения производительности — разделение процесса на две фазы: грубая фаза и точная фаза. Грубая фаза определяет, могут ли объекты потенциально столкнуться, при этом эффективно отсеивая пары, которые явно не пересекаются.

Объекты, которые нельзя полностью разделить на грубой фазе, передаются в точную фазу. Здесь с помощью более трудоёмких алгоритмов проверяется факт пересечения и, в случае его обнаружения, могут вычисляться точные время и место столкновения.

Грубая фаза

На этом этапе задача — быстро выявить такие объекты или их части, для которых очевидно не потребуется дальнейшей проверки столкновений. Такая стратегия называется чувствительной к выходным данным: вычислительная сложность зависит от числа реально близко расположенных объектов. Пример: в системе I-COLLIDE число точных проверок было $O(n+m)$, где $n$ — общее число объектов, $m$ — число находящихся в тесной близости. Это существенно лучше квадратичной сложности наивного подхода.

Пространственное разбиение

Различные методы пространственного разбиения включают октодеревья (для 3D), квадродеревья (для 2D), деревья бинарного разбиения пространства (BSP-деревья) и другие. Если пространство разделить на простые ячейки, и два объекта не могут находиться в одной ячейке, их проверять не требуется. При динамических сценах и деформируемых объектах разбиение пространства требует обновления, что увеличивает накладные расходы.

Иерархия ограничивающих объёмов (Bounding volume hierarchy)

Иерархия ограничивающих объёмов (ИОО, англ. Bounding Volume Hierarchy, BVH) — это дерево, построенное по множеству ограничивающих объёмов. Столкновения ищутся обходом дерева от корня: если ограничивающий объём корня не пересекается с интересующим объектом, дальнейшие проверки не нужны; если же пересечение есть, анализируются дочерние ветви. Несколько объектов могут быть сразу отброшены от дальнейших проверок. ИОО может применяться и для деформируемых объектов, однако требует корректировки структуры по мере деформаций. К числу задач относится и самостолкновение (self-collision). Для двух объектов пересечение проверяется сначала между их корневыми ограничивающими объёмами, а далее — между поддеревьями, где пересечения возможны. Точные проверки требуются только для листьев. Этот подход подходит как для парных, так и для самостолкновений.

Использование временной когерентности

При перемещении или деформации объектов структуры для отсечения столкновений надо обновлять. Когда изменения между кадрами малы, а объекты можно аппроксимировать выравненными по осям ограничивающими прямоугольниками, эффективным становится алгоритм sweep and prune.

Эффективность обеспечивают следующие особенности: две ограничивающие коробки пересекаются тогда и только тогда, когда их интервалы перекрываются по всем осям; можно сортировать интервалы отдельно по каждой оси; между кадрами перестановки обычно минимальны, что позволяет эффективно применять алгоритмы сортировки для почти-отсортированных массивов. Алгоритм отслеживает текущее множество пересекающихся коробок, и при движении объектов пересортировка обновляет их статус.

Парное отсечение (pairwise pruning)

После выбора пары физических тел для дальнейшей проверки требуется более тщательный анализ столкновений. Обычно сложные объекты описываются множеством простых примитивов (треугольников). Пусть объекты представлены наборами треугольников $S=\{S_{1},S_{2},\dots ,S_{n}\}$ и $T=\{T_{1},T_{2},\dots ,T_{n}\}$ (для простоты считаем одинаковое число элементов).

Наивная проверка всех треугольников $S_{j}$ против всех $T_{k}$ приведёт к $n^{2}$ операциям, что неэффективно. Предпочтительно с помощью методов отсечения резко сократить количество проверяемых пар примитивов.

Самый распространённый подход — использование иерархий ограничивающих объёмов: для каждого объекта заранее строится дерево ограничивающих сфер (или иной формы объёма, например, AABB или OBB). Проверяя пересечение на уровне ограничивающих сфер и рекурсивно разбивая объекты, можно эффективно исключить множество пар из дальнейшего анализа.

Для данной структуры каждый внутренний узел дерева соответствует множеству треугольников и содержит ограничивающую сферу для этого множества. Применяя дерево для обеих фигур, многие пары треугольников отбрасываются, если соответствующие ограничивающие области не пересекаются. Аналогично работают структуры с AABB и OBB.

Точная фаза (narrow phase)

Объекты, которые не удалось однозначно разделить на грубой фазе, переходят в точную фазу. Здесь находятся объекты, потенциально близкие друг к другу. Опционально выполняется ещё «промежуточная» фаза быстрого отсечения Только после этого используются численно точные алгоритмы для проверки факта пересечения, а при необходимости — для определения времени и координат столкновения.

Ограничивающие объёмы

Быстрый способ избежать лишних дорогостоящих вычислений — проверить, пересекаются ли ограничивающие объёмы интересующих объектов. Если нет — более точная проверка не требуется. Если же ограничивающие объёмы пересекаются, необходим более подробный анализ. Важно сбалансировать два свойства: а) вычисление пересечения ограничивающих объёмов должно быть быстрым; б) ограничивающий объём должен плотно обхватывать фигуру, чтобы минимизировать число ложных срабатываний. Распространены ограничивающие прямоугольники (AABB) и кубоиды благодаря простоте.. Более сложные ограничивающие объёмы (OBB, K-DOP, выпуклые оболочки) обеспечивают большую точность, но требуют сложных расчетов.

Ограничивающие объёмы используют на этапе отсечения, чтобы детально сравнивать только те объекты, чьи объёмы перекрываются.

Точное парное обнаружение столкновений

Для объектов, где отсечение не исключило возможность пересечения, требуется точная проверка.

Столкновения между выпуклыми объектами

Согласно теореме о разделяющей плоскости, для любых двух непересекающихся выпуклых тел существует такая плоскость, по разные стороны от которой они лежат. Это позволяет строить эффективные алгоритмы обнаружения столкновений выпуклых объектов. Существуют специализированные алгоритмы для поиска минимального расстояния между поверхностями двух выпуклых многогранников и определения факта столкновения. Например, методы, использующие модифицированный симплекс-метод линейного программирования или алгоритм Гилберта–Джонсона–Кирти (ГДК-алгоритм). Эти методы работают почти за постоянное время при последовательных проверках между почти статичными объектами. Так обеспечивается реальное время для большого числа объектов.

A priori отсечение

Когда большинство объектов неподвижны (например, в видеоиграх), способы с предварительными вычислениями (a priori) позволяют существенно ускорить обработку. Здесь также актуальны различные методы отсечения, однако тип траекторий и характеристики системы оказывают значительное влияние на выбор алгоритма.

Для точной парной проверки часто требуется численное решение, чтобы вычислить точный момент соприкосновения (например, по факт движения вершин).

Сегменты центроидов треугольников

Часто в 3D-моделировании используются треугольные сетки. Проверка может строиться по пересечению самих треугольников либо ограничивающих тел. Центроид треугольника (центр масс) определяется как среднее арифметическое координат вершин. По центроидам двух объектов можно задать отрезок между ними, а его длина используется в качестве критерия столкновения (например, при аппроксимации треугольника сферой).

Положение центра треугольника с координатами $(x_{1},y_{1},z_{1})$, $(x_{2},y_{2},z_{2})$ и $(x_{3},y_{3},z_{3})$ вычисляется как $\left({\frac {x_{1}+x_{2}+x_{3}}{3}},{\frac {y_{1}+y_{2}+y_{3}}{3}},{\frac {z_{1}+z_{2}+z_{3}}{3}}\right)$.

Расстояние между центроидами двух точек в 3D: $\mathrm {distance} ={\sqrt {(z_{2}-z_{1})^{2}+(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}}$.

Размер сегмента может задавать порог возникновения события столкновения. Сфера с центром в центроиде аппроксимирует тестируемую геометрию.

Применение

Обнаружение столкновений в компьютерных симуляциях

Физические симуляторы по-разному реагируют на столкновения. Некоторые используют мягкость материала для вычисления силы, устраняющей столкновение в последующих шагах, что требует больших вычислений для жёстких тел. В других временное наступление столкновения определяется интерполяцией, возможно с откатом симуляции и пересчётом по законам сохранения.

Некоторые используют итерации линейной интерполяции (метод Ньютона) для более точного расчёта времени столкновения. Использование временной когерентности позволяет делать шаги по времени ещё меньше без существенного увеличения нагрузки, например, в системах управления воздушным движением.

После неупругого столкновения могут появиться состояния скольжения и покоя, например, Open Dynamics Engine моделирует такие состояния через ограничения, избегающие накопления ошибок (дрейфа).

В целом симуляторы бывают двух типов: с обнаружением столкновения a posteriori (после факта столкновения) и a priori (до столкновения). Практически все современные алгоритмы используют иерархию, часто соответствующую терминам «дискретное» и «непрерывное» (continuous).

A posteriori (дискретные) и a priori (непрерывные) методы

В подходе a posteriori симуляция выполняет шаг вперёд, после чего анализируется факт пересечения. На каждом шаге формируется список столкнувшихся тел, после чего их положения и траектории корректируются, что называется «после события» — обычно фактическое мгновение контакта пропускается.

В методах a priori используются алгоритмы, позволяющие заранее предугадать траектории всех тел и получить с высокой точностью момент столкновения, в итоге тела физически не проникают друг в друга. Здесь обнаружение выполняется до факта, непосредственно по имеющимся данным.

Преимуществами a posteriori является простота — алгоритмы не обязаны моделировать сложную физику (трение, пластичность и т. п.), а справляются с простым анализом тел. Кроме того, a posteriori проще, так как не учитывает временную компоненту.

Однако есть и недостатки: требуется исправлять невозможные ситуации (проникновения), а слишком крупный шаг может привести к пропуску столкновения (объект «проскочит» сквозь другой, если достаточно быстр или мал).

A priori обеспечивает большую точность и устойчивость. Однако разделить физическую симуляцию и определение столкновений полностью сложно, если не невозможно. В большинстве случаев задача вычисления момента столкновения пары тел не имеет аналитического решения и требует численного поиска корня.

Особого внимания требует ситуация «контактного покоя», например, ваза, стоящая на столе. Обычно такие состояния реализуются через сцепление с помощью графа сцены.

Видеоигры

Видеоигры должны делить ограниченное процессорное время между многими задачами. Но даже с ограниченными ресурсами и простыми алгоритмами им удаётся реализовать приемлемые, пусть и неточные, системы столкновений.

Долгое время в играх количество объектов было мало, и парные проверки не представляли трудности. В 2D-играх аппаратное обеспечение часто позволяло находить и обрабатывать пересечения пикселей между спрайтами. В других случаях экран делится на плитки, и каждому спрайту сопоставляются затронутые плитки; для парных проверок часто используется ограничивающий прямоугольник/эллипс (hitbox).

В трёхмерных играх для грубого отсечения используют пространственное разбиение; в парных проверках чаще всего применяются сферы, редко — полные аналитические методы (только реалистичные симуляции). Точная проверка редко требуется по всем объектам.

Поскольку цель — не физическая точность, а правдоподобие, устойчивость не критична. Как правило, применяется a posteriori обнаружение, а разрешение реализуется простыми правилами: например, если персонаж застрял в стене, его перемещают на последнюю корректную позицию, либо корректируют допустимую длину перемещения до препятствия.

Часто для лично героя приближённого моделирования достаточно точки, для которой проверяется попадание в сцену (например, через BSP-деревья). При моделировании столкновений между персонажами и снарядами, как правило, применяются отдельные структуры.

Работоспособный симулятор должен разумно реагировать на любые входные. Проблемы обычно возникают при больших шагах симуляции — автомобиль на высокой скорости может, например, «перепрыгнуть» невысокую стену и вылететь в неограниченную область (так называемый «чёрный ад» или «blue/green hell»), что свидетельствует о несостоятельности алгоритмов столкновений. Известный пример неработающей системы обнаружения — Big Rigs: Over the Road Racing.

Hitbox

Хитбокс (англ. hitbox) — невидимая форма, обычно ограничивающий прямоугольник или параллелепипед, используемая в видеоиграх для обнаружения столкновений в реальном времени. В 2D-играх — это чаще прямоугольник, в 3D — кубоид. Иногда используется окружность или сфера (но по инерции может называться «box»). Анимированным объектам обычно назначают набор хитбоксов для различных подвижных частей, чтобы гарантировать корректное взаимодействие при движении.

Хитбокс применяется для «односторонних» столкновений (например, попадание удара или пули в персонажа). Для обнаружения механических контактов (толкание, скольжение) предпочитают примитивные ограничивающие объёмы (AABB), поскольку управлять кучей хитбоксов для перемещающихся частей сложно. Термин «хитбокс» иногда используется пользователями для обозначения всех типов таких взаимодействий.

Хёртбокс — разновидность хитбокса для приема урона. Часто в играх хитбоксы разных типов: атакующая зона (hitbox в узком смысле) и принимающая урон зона (hurtbox), причем по их пересечению определяется исход обмена ударами. Термины не являются полностью стандартизированными: в некоторых играх определения меняются местами, а где-то обе области называют «hitbox».

Примечания

Литература

• Тешнер, М.; Киммерле, С.; Хайдельбергер, Б.; Закманн, Г.; Рагупати, Л.; Фурманн, А.; Кани, М.-П.; Фор, Ф.; Магненат-Тальман, Н.; Штрассер, В.; Волино, П. (2005). “Collision Detection for Deformable Objects”. Computer Graphics Forum [англ.]. 24: 61—81. CiteSeerX 10.1.1.58.2505. DOI:10.1111/j.1467-8659.2005.00829.x. S2CID 1359430. Дата обращения 2024-06-10.
• 39 // Handbook of discrete and computational geometry : [англ.]. — 3-е. — Бока-Ратон, Лондон, Нью-Йорк : CRC Press, Taylor & Francis Group, 2018. — ISBN 978-1-4987-1139-5.
• Эндрюс, Шелдон. Contact and friction simulation for computer graphics // ACM SIGGRAPH 2022 Courses : [англ.] / Шелдон Эндрюс, Кенни Эрлебен, Закари Фергюсон. — ACM, 2 августа 2022. — P. 1–172. — ISBN 978-1-4503-9362-1. — doi:10.1145/3532720.3535640.
• Хадап, Сунил. Collision detection and proximity queries // ACM SIGGRAPH 2004 Course Notes : [англ.] / Сунил Хадап, Дэйв Эберле, Паскаль Волино … [et al.]. — ACM, 8 августа 2004. — P. 15. — ISBN 978-1-4503-7801-7. — doi:10.1145/1103900.1103915.
• Эриксон, Кристер. Real-time collision detection : [англ.]. — Nachdr. — Амстердам, Гейдельберг : Elsevier, 22 декабря 2004. — P. 329–338. — ISBN 978-1-55860-732-3.
• Коэн, Джонатан Д. I-COLLIDE: An interactive and exact collision detection system for large-scale environments // Proceedings of the 1995 symposium on Interactive 3D graphics - SI3D '95 : [англ.] / Джонатан Д. Коэн, Мин Ц. Лин, Динеш Маноча … [et al.]. — ACM Press, 1995. — P. 189–ff. — ISBN 978-0-89791-736-0. — doi:10.1145/199404.199437.

Ссылки

• Обнаружение столкновений в CSS-анимациях
• Страница исследовательского проекта по обнаружению столкновений университета Северной Каролины
• Сайт проф. Стивена Кэмерона (Оксфорд) по обнаружению столкновений
• Как избежать столкновения — демонстрация Джорджа Бека, проект Wolfram Demonstrations Project.
• Bounding boxes and their usage (архив)
• Теорема о разделяющей оси
• Справочник по столкновениям Unity 3D
• Коллизии в физике движка Godot