Широкая и узкая фазы столкновений: кандидаты и контакты

Зачем разделять обнаружение столкновений?

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

Контракт кандидатов

Широкая фаза использует консервативные границы, чтобы не проверять каждую пару форм. Динамическое дерево Box2D организует границы, параллельные осям, в двоичную иерархию. [1] Узкая фаза работает с самими формами и может создавать контактные многообразия с точками контакта и нормалью. Фильтрация столкновений и последующий решатель ограничений имеют отдельные обязанности. [2]

Разобранный пример

Представьте 100 движущихся ящиков. Проверка каждой неупорядоченной пары потребовала бы 100 × 99 / 2 = 4950 тестов. Пусть условный пространственный запрос после фильтрации по слоям выдаёт 180 кандидатов, а геометрические тесты находят 24 соприкасающиеся пары. Эти придуманные числа объясняют этапы конвейера и не являются результатом измерения производительности.

Длинный ящик, повёрнутый по диагонали, может иметь большой ограничивающий объём, параллельный осям, с пустыми углами. Другой ящик в таком углу должен пройти широкую фазу, но не пройти тест форм. Если считать столкновением каждого из 180 кандидатов, возникнут ложные события урона. И наоборот: граница, не содержащая свою форму целиком, способна отбросить настоящий контакт до узкой фазы.

Практический процесс

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

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

Компромиссы и ограничения

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

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

Источники

[1] Динамическое дерево — Erin Catto и участники Box2D.

[2] Столкновения — Erin Catto и участники Box2D.