Аналогия с Плоской страной
«Плоская страна» Эдвина Эббота (1884): обитатели двумерной плоскости. Они воспринимают длину и ширину. Глубина — третье измерение над ними — невидима. Они не могут её воспринимать, не могут её использовать, не могут с ней работать. Геометрия их мира содержит измерение, которое они структурно отбрасывают.
MOAD-0007 работает точно так же. Объекты в 3D-пространстве несут позицию, поворот и ограничивающий объём — богатую геометрическую структуру. Линейное сканирование обрабатывает их как плоский список. Пространственная структура присутствует, но не используется и отбрасывается. Каждая проверка пересечения сканирует весь список, как будто у объектов нет ни геометрии, ни позиции.
Пример Three.js
Three.js Raycaster.intersectObjects(): по заданному лучу (позиция и направление в 3D-пространстве) находит все объекты, с которыми луч пересекается. Реализация: перебирает все N объектов сцены и проверяет каждый на пересечение с лучом. O(N) за вызов.
Обработчик события hover вызывает intersectObjects() один раз за кадр при 60 кадрах в секунду. При N=100 объектов: 6 000 тестов пересечения в секунду. При N=10 000 объектов: 600 000 тестов в секунду. Стоимость: пропорциональна N, а не количеству объектов, с которыми луч действительно пересекается.
При N=100: незаметно. Бюджет кадра (16,7 мс при 60 fps) поглощает затраты без проблем.
При N=10 000: доминирует. 600 000 тестов пересечения в секунду насыщают основной поток. Частота кадров падает. Сцена, работавшая при N=100, тихо разрушается, когда N пересекает порог.
Структура, которую отбрасывает линейное сканирование
Объекты занимают позиции в пространстве. Объект в позиции (1000, 0, 0) не может пересекаться с лучом, направленным в сторону (-1, 0, 0) из позиции (0, 0, 0): объект находится в противоположном направлении. Линейное сканирование проверяет его всё равно.
У объектов есть ограничивающие объёмы: сфера или коробка, охватывающая весь объект. Луч, не пересекающий ограничивающий объём объекта, не может пересекаться с самим объектом. Линейное сканирование всё равно выполняет полный тест пересечения.
Геометрия кодирует, какие объекты можно пропустить. Линейное сканирование игнорирует геометрию. Это и есть отбрасывание.
Что означает «Отбрасывание структуры»
Аналогия с Flatland: жители Абботта не могли воспринимать глубину. Дефект Flatland отбрасывает геометрическую структуру, которая существует в данных, но никогда не попадает в алгоритм.
Почему хеш-множество не может исправить MOAD-0007
MOAD-0001 исправление: замените последовательную проверку членства на хеш-множество. list.contains(x): O(N). set.has(x): O(1). Вопрос о членстве: «присутствует ли x в этой коллекции?» Пространственная геометрия не задействована.
MOAD-0007 исправление: замените линейное пространственное сканирование на пространственный индекс (BVH, октодерево, k-d дерево, R-дерево). Пространственный вопрос: «какие объекты в этой коллекции пересекаются с этим лучом/сферой/фрустумом?» Требуется пространственная близость.
Хеш-множество отвечает на вопрос о членстве: «присутствует ли этот точный объект?» O(1). Оно не может ответить на вопрос о близости: «какие объекты находятся рядом с этим лучом?» У хеш-множества нет понятия расстояния или пространственного протяжения. Хеширование отбрасывает геометрию так же полностью, как и линейное сканирование.
BVH отвечает на вопрос о близости: «какие объекты попадают в этот пространственный запрос?» O(log N + k). Он организует объекты по положению, поэтому запросы близости пропускают геометрически удалённые объекты.
| Вопрос | Правильная структура | Неправильная структура |
|---|---|---|
| Находится ли объект X в этом наборе? | HashSet (O(1)) | Линейный список (O(N)) |
| Какие объекты пересекаются с этим лучом? | BVH/октодерево/k-d дерево (O(log N)) | Линейное сканирование ИЛИ HashSet (O(N) или O(N)) |
MOAD-0001 & MOAD-0007: обе операции O(N) заменены на что-то более быстрое. Требуются разные структуры, потому что вопросы различаются.
Когда строить, когда пропускать
Построение BVH стоит O(N log N). Запросы стоят O(log N + k). Точка безубыточности: когда количество запросов превышает количество построений настолько, что экономия на запросах перекрывает стоимость построения.
При N=100: линейный проход занимает микросекунды. Построение BVH добавляет накладные расходы. Пропустите BVH.
При N=10 000 и 60 Гц: линейный проход съедает бюджет кадра. Запросы BVH стоят 1/1000 от времени линейного прохода. Постройте BVH один раз; запрашивайте 60 раз в секунду. Точка безубыточности достигается ещё до первого кадра.
Правило: стройте, когда N * Q > N log N, где Q = количество запросов за цикл перестроения. Для интерактивных 3D-сцен: Q = 60 в секунду, порог N = несколько сотен объектов.
Диагностика и исправление 3D-сцены
Приложение 3D-визуализации рендерит 5000 геометрических объектов. Обработчик hover срабатывает 60 раз в секунду. При каждом событии hover обработчик вызывает scene.intersectObjects(ray, objects), который перебирает все 5000 объектов и проверяет каждый на пересечение с лучом. Частота кадров упала с 60 fps до 8 fps.
Участник команды предлагает: «Поместите все объекты в Set для O(1) поиска».