Лучшее решение для удаления 2D окклюзии

В моей 2D-игре у меня есть статические и динамические объекты. Камер может быть несколько. Моя проблема: Определить объекты, которые пересекаются с прямоугольником обзора текущей камеры.

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

Я изучил несколько структур данных, которые могли бы решить мою проблему:

• Quadtree

Это было первое, что я задумал, однако проблема в том, что это заставит мои сцены иметь фиксированный размер. (Приемлемо для статических, но не для динамических объектов)

• Динамическое дерево AABB

Выглядит хорошо, но накладные расходы на перебалансировку кажутся слишком большими для многих динамических объектов.

• Пространственный хэш

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

В общем, мои критерии для хорошего решения этой проблемы: :

• Динамический размер: Решение не должно приводить к ограничению размера сцены или требовать тяжелого пересчета для изменения размера

• Хорошая производительность запросов (для камеры)

• Хорошая поддержка очень динамических объектов: Вычисления, необходимые для обрабатывать объекты с постоянно меняющейся позицией должно быть хорошо:

Максимальное разумное количество динамических объектов в моей игре за один раз, вероятно, составляет 5000. Учтите, что все они меняют свое положение каждый кадр. Существует ли вообще структура данных, которая может быть быстрее, учитывая частые вставки и удаления, чем сравнение AABB объектов с камерой каждый кадр?