Sweep and prune
Алгоритм широкой фазы: сортирует ограничивающие параллелепипеды объектов по каждой оси и проверяет только пары, чьи интервалы пересекаются по всем осям.
Проверять каждый объект против каждого — это O(n²), и при тысячах тел такой подход безнадёжен. Sweep and prune (он же «sort and sweep») проецирует начало и конец каждого ограничивающего параллелепипеда на оси x, y и z, сортирует списки и пробегает по ним; два параллелепипеда могут столкнуться, только если их интервалы пересекаются по всем осям. Остальное отсеивается сразу.
Секрет — в временной когерентности: между кадрами объекты сдвигаются слегка, так что отсортированные списки почти отсортированы, и сортировка вставками работает почти за линейное время. Метод вышел из библиотеки I-COLLIDE Мин Лин и Динеша Маноча начала 1990-х и сегодня сидит практически в каждом физическом движке как дешёвое грубое сито перед дорогой точной фазой.