Обнаружение столкновений
Выяснить, какие из тысяч объектов действительно соприкасаются, не сравнивая каждую пару со всеми остальными.
Наивная реализация имеет сложность O(n²) и рушится на нескольких тысячах объектов, поэтому работу делят на две части. Широкая фаза быстро отсеивает лишнее по грубым приближениям — ограничивающим параллелепипедам по осям, пространственному разбиению, BVH-деревьям или sweep and prune — и передаёт короткий список пар, которые могут соприкасаться. Узкая фаза проверяет их точно, обычно алгоритмом GJK или теоремой о разделяющей оси.
Классическая ошибка — туннелирование: быстрый снаряд пролетает сквозь стену, потому что столкновение происходит между двумя кадрами и никогда не попадает в выборку. Лекарство — непрерывное обнаружение столкновений, которое протягивает объём вдоль траектории и обходится дорого, поэтому движки обычно включают его только для пуль и транспорта.