Поиск ближайших объектов.

Автор: IvanVR1

При разработке приложений, работающих с 3D графикой, часто приходится решать три задачи:
1) Поиск объектов из множества S, находящихся в радиусе R от точки C.
2) Определение, какие объекты из множества рисуемых объектов попадают во "фрустум" (пирамиду, задающую область видимости) камеры.
3) Проверка пересечения геометрического примитива (обычно сферы, AABB или направленного отрезка) с множеством объектов S.

В решениях этих трех задач присутствует один общий этап - выделение тех объектов, которые находятся в непосредственной близости от интересующей нас точки пространства. Объединим задачи в один класс и присвоим им общее название - поиск ближайших объектов. Сделаем следующее допущение: представим каждый объект описывающей сферой. Для задач данного класса такой способ аппроксимации корректен, поскольку всегда можно провести уточнение результата. Например, при помощи функции поиска ближайших объектов можно выделить из множества S подмножество S_r , состоящее из объектов, находящихся в непосредственной близости от направленного отрезка R₀R₁. Для дальнейшего уточнения результата можно использовать функцию, проверяющую пересечение направленного отрезка с объектом.

Рисунок 1

Рассмотрим решение задачи проверки пересечения отрезка с множеством сфер. На рисунке 1 изображены отрезок и проекция множества сфер на плоскость. В начале выделяются сферы, лежащие на расстоянии меньшем или равном d от середины отрезка, где d равно половине длины отрезка. Эта область обозначена красным цветом. Затем выполняется проверка пересечения отрезка с объектами, попадающими в эту область. Безусловно, задачу можно решить и прямым перебором, но, в случае большого количества сфер, время вычисления может не устроить. Для оптимального, с точки зрения быстродействия, поиска ближайших объектов применяют специальные структуры данных. Например, для мира, описываемого "боксом" размером (dx,dy,dz), где dz<<dx, dz<<dy, а объекты, которого, описываются сферами примерно равного радиуса, и распределение объектов в пространстве равномерно, можно применить 2D сетку на плоскости XY. Для этого спроецируем все множество сфер на плоскость XY, и в каждую ячейку, в которую попадает сфера, запишем ссылку. Затем достаточно спроецировать интересующую нас область на плоскость XY, выделить ячейки, покрываемые этой областью, и осуществить перебор тех объектов, на которые ссылаются ячейки. Как видно из рисунка 2, сфера может оказаться в нескольких ячейках, поэтому, для избежания повторных проверок с одной и той же сферой, проверенную сферу маркируют специальным образом (например, записывают номер текущего кадра). Несмотря на свою примитивность, данный подход не имеет конкурентов по быстродействию в случае выполнения условия dz<<dx, dz<<dy и равномерного распределения объектов, и при этом расходует достаточно мало памяти.

 
Рисунок 2

Если распределение объектов неравномерно, а условия dz<<dx, dz<<dy выполняются, для экономии памяти используют деревья на плоскости, например quad tree или модификации k-D tree и BSP tree для плоскости. Поскольку речь зашла о k-D tree и BSP tree, правильнее перейти к пространственным k-D и BSP деревьям, которые в 3D пространстве мало проигрывают своему 2D аналогу по быстродействию и расходуют практически столько же памяти. Также можно использовать 3D сетку (малоэффективна из-за большого расхода памяти) или octant tree. При использовании пространственных деревьев, условия dz<<dx, dz<<dy и равномерное распределение объектов в пространстве становятся необязательными. Эти структуры данных расходуют мало памяти и достаточно эффективны по быстродействию, при этом решают задачу в общем случае. Ниже будет предложен вариант k-D деревьев с расширенной функциональностью, позволяющий избежать множественной проверки одного и того же объекта (в случае попадания на границу подпространств), и эффективно работающий с динамическими объектами. На рисунке 3 показана типичная картина разбиения пространства с помощью k-D деревьев.

Рисунок 3

Постановка задачи: из множества сфер S необходимо выделить подмножество S1, которое пересекается со сферой s0. При этом считаем, что часть сфер выполняет некоторое (небольшое) перемещение в пространстве в дискретные моменты времени. Также введем три необязательных дополнительных условия, позволяющих уменьшить время работы функции проверки пересечения и сэкономить память:
1) Предположим, что нам известен "бокс", описывающий множество S.
2) Предположим, что нам известен радиус наибольшей сферы из множества S.
3) Предположим, что мы можем сделать оценку плотности распределения сфер внутри описывающего "бокса".
Выполнить эти три условия на практике достаточно легко, но, как уже было сказано выше, четкое следование им необязательно.

Основной идеей, расширяющей функциональность k-D деревьев, является введение пересекающихся подпространств: вместо делящих плоскостей, применяющихся в классическом варианте для рекурсивного разбиения пространства, используются пары параллельных плоскостей, при этом зона между парой параллельных плоскостей является общей для двух подпространств. На рисунке 4 показано такое деление, к негативному подпространству относятся зоны, показанные красным и фиолетовым цветами, к позитивному подпространству - зоны, показанные фиолетовым и синим цветами. Ширина, общей фиолетовой зоны, больше диаметра наибольшей сферы. Как видно из рисунка, ни одна из сфер не попадает сразу и в красную, и в синюю зону. Таким образом, множество сфер можно разделить на два подмножества относительно середины фиолетовой зоны. Полученные подмножества сфер не пересекаются, несмотря на то, что подпространства, которые применяются для выделения подмножеств, пересекаются.

 
Рисунок 4

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

Введем следующие операции необходимые для работы с деревом:
1)  Добавление новой сферы.
2)  Перемещение сферы в пространстве, с изменением структуры дерева
3)  Удаление сферы
4)  Поиск сфер пересекающихся с заданной сферой.
В отличие от поиска, все остальные операции требуют изменения структуры дерева.

Алгоритм добавление новой сферы во множество сфер, представленное деревом:
1)  Для подпространства определенного "боксом", лежащим вдоль осей координат, вычисляем максимальное измерение.
2)  Если в дереве нет узла, представляющего это подпространство, создаем новый узел и запоминаем в нем "бокс" и индекс максимального измерения.
3)  Вычисляем ширину общей области для двух дочерних подпространств, BorderHalfWidth=min(MaxR,MaxBoxDimension*Density*0.25f), где MaxR - радиус наибольшей сферы, Density - безразмерная величина, определяющая плотность распределения сфер.
4)  Если радиус сферы превышает половину ширины общей области, прикрепляем сферу к узлу дерева и выходим из рекурсии.
5)  Определяем дочернее подпространство, в которое попадает сфера, и продолжаем для него рекурсию, начиная с пункта 1.

Алгоритм удаления сферы из множества:
1)  Удаляем элемент из списка прикрепленного к узлу дерева
2)  Если список прикрепленных к узлу элементов пуст, и у узла нет детей, удаляем узел, иначе выходим из цикла.
3)  Поднимаемся по дереву к родительскому узлу и переходим к пункту 2.

Алгоритм перемещения сферы в пространстве с изменением структуры дерева:
1)  Если перемещение сферы оказалось незначительным, т.е. сфера осталась внутри подпространства, определяемого "боксом" узла дерева, просто запоминаем новое положение и выходим.
2)  Удаляем элемент из списка, прикрепленного к узлу дерева
3)  Пока сфера не полностью попадает в подпространство, представленное "боксом" узла, поднимаемся по дереву с проверкой: если у узла нет детей и список элементов пуст, удаляем узел.
4)  Для найденного узла (он представляет содержащее сферу подпространство),  выполняем алгоритм добавления сферы.

Алгоритм проверки пересечения сферы с множеством сфер:
1)  Проверяем пересечение со всеми элементами списка прикрепленного к узлу дерева.
2)  Простым сравнением определяем, попадает ли сфера в позитивное подпространство, и, если попадает, продолжаем рекурсию с пункта 1 для узла, представляющего позитивное подпространство.
3)  Простым сравнением определяем, попадает ли сфера в негативное подпространство, и, если попадает, продолжаем рекурсию с пункта 1 для узла, представляющего негативное подпространство.

Важное замечание по реализации: для оптимальной скорости работы алгоритмов добавления, удаления и перемещения сферы операторы new и delete необходимо перегрузить и использовать управление памятью для блоков равного размера.