Широкая фаза (broad phase)
Первый этап поиска столкновений в физическом движке: дёшево отсеивает пары объектов, которые заведомо не могут соприкоснуться.
Если в сцене n объектов, возможных пар около n²/2, и точная проверка каждой из них становится безнадёжной уже на паре сотен объектов. Поэтому широкая фаза сравнивает приблизительные ограничивающие объёмы — обычно параллелепипеды, выровненные по осям, — и возвращает короткий список пар-кандидатов, которые действительно перекрываются. Точную проверку оставляют узкой фазе.
Классические методы: sweep and prune (интервалы объектов сортируются вдоль оси и просматриваются «заметающей» прямой; описан Коэном и соавторами в I-COLLIDE, 1995), равномерные сетки, пространственное хеширование и иерархии ограничивающих объёмов. Выбор зависит от распределения объектов: редкое протяжённое поле подходит для sweep and prune, плотная куча — для сетки.