Двоичное разбиение пространства было разработано в контексте 3D компьютерной графики в 1969 году. [1] [2] Структура дерева BSP полезна при рендеринге , поскольку она может эффективно предоставлять пространственную информацию об объектах в сцене, например, объекты, упорядоченные спереди назад относительно зрителя в заданном месте. Другие приложения BSP включают: выполнение геометрических операций с фигурами ( конструктивная сплошная геометрия ) в САПР , [3] обнаружение столкновений в робототехнике и 3D видеоиграх, трассировку лучей , моделирование виртуального ландшафта, [4] и другие приложения, которые включают обработку сложных пространственных сцен.
История
1969 Schumacker et al. [1] опубликовали отчет, в котором описывалось, как тщательно позиционированные плоскости в виртуальной среде могут быть использованы для ускорения упорядочивания полигонов. Методика использовала глубинную когерентность, которая гласит, что полигон на дальней стороне плоскости не может никоим образом препятствовать более близкому полигону. Это использовалось в летных симуляторах, созданных GE, а также Evans и Sutherland. Однако создание организации полигональных данных выполнялось вручную дизайнером сцены.
1980 Фукс и др. [2] расширили идею Шумакера до представления трехмерных объектов в виртуальной среде, используя плоскости, совпадающие с полигонами, для рекурсивного разделения трехмерного пространства. Это обеспечило полностью автоматизированную и алгоритмическую генерацию иерархической полигональной структуры данных, известной как двоичное дерево разбиения пространства (BSP-дерево). Процесс происходил как этап автономной предварительной обработки, который выполнялся один раз для каждой среды/объекта. Во время выполнения зависящий от вида порядок видимости генерировался путем обхода дерева.
Кандидатская диссертация Нейлора 1981 года представила полную разработку как деревьев BSP, так и подхода на основе теории графов с использованием сильно связанных компонентов для предварительного вычисления видимости, а также связь между двумя методами. Особое внимание уделялось деревьям BSP как пространственной структуре поиска, независимой от размерности, с приложениями к определению видимой поверхности. Диссертация также включала первые эмпирические данные, демонстрирующие, что размер дерева и количество новых полигонов были разумными (с использованием модели космического челнока).
1983 Фукс и др. описали реализацию алгоритма BSP-дерева на основе микрокода в системе буфера кадров Ikonas. Это была первая демонстрация определения видимой поверхности в реальном времени с использованием BSP-деревьев.
1987 Тибо и Нейлор [3] описали, как произвольные многогранники могут быть представлены с помощью дерева BSP в отличие от традиционного b-rep (граничного представления). Это обеспечило твердотельное представление вместо поверхностного. Операции над множествами многогранников были описаны с помощью инструмента, позволяющего выполнять конструктивную объемную геометрию (CSG) в реальном времени. Это было предшественником дизайна уровней BSP с использованием « кистей », представленного в редакторе Quake и подхваченного в редакторе Unreal.
1990 Нейлор, Аманатидес и Тибо предложили алгоритм для слияния двух деревьев BSP для формирования нового дерева BSP из двух исходных деревьев. Это обеспечивает множество преимуществ, включая объединение движущихся объектов, представленных деревьями BSP, со статической средой (также представленной деревом BSP), очень эффективные операции CSG над многогранниками, точное обнаружение столкновений за O(log n * log n) и правильное упорядочение прозрачных поверхностей, содержащихся в двух взаимопроникающих объектах (использовалось для эффекта рентгеновского зрения).
1990 Теллер и Сейкин предложили автономную генерацию потенциально видимых наборов для ускорения определения видимых поверхностей в ортогональных двумерных средах.
1991 Гордон и Чен [CHEN91] описали эффективный метод выполнения рендеринга спереди назад из BSP-дерева, а не традиционный подход сзади вперед. Они использовали специальную структуру данных для эффективной записи частей экрана, которые были нарисованы, и тех, которые еще предстоит отрисовать. Этот алгоритм вместе с описанием деревьев BSP в стандартном учебнике по компьютерной графике того времени ( Computer Graphics: Principles and Practice ) использовался Джоном Кармаком при создании Doom (видеоигра) .
В своей докторской диссертации 1992 года Теллер описал эффективную генерацию потенциально видимых наборов как шаг предварительной обработки для ускорения определения видимой поверхности в реальном времени в произвольных трехмерных полигональных средах. Это использовалось в Quake и внесло значительный вклад в производительность этой игры.
1993 Нейлор ответил на вопрос о том, что характеризует хорошее дерево BSP. Он использовал ожидаемые модели случаев (а не анализ наихудшего случая) для математического измерения ожидаемой стоимости поиска в дереве и использовал эту меру для построения хороших деревьев BSP. Интуитивно дерево представляет объект в многоразрешительной манере (точнее, как дерево приближений). Проведены параллели с кодами Хаффмана и вероятностными бинарными деревьями поиска.
В докторской диссертации 1993 года Хайдера Радхи были описаны (естественные) методы представления изображений с использованием деревьев BSP. Это включает разработку оптимальной структуры построения BSP-дерева для любого произвольного входного изображения. Эта структура основана на новом преобразовании изображения, известном как преобразование Least-Square-Error (LSE) Partitioning Line (LPE). В диссертации Х. Радхи также были разработаны оптимальная структура сжатия изображений по скорости и искажению (RD) и подходы к манипулированию изображениями с использованием деревьев BSP.
Обзор
Пример рекурсивного бинарного разбиения пространства квадродерева для двумерного индекса.
Бинарное разбиение пространства — это общий процесс рекурсивного деления сцены на две части до тех пор, пока разбиение не удовлетворит одному или нескольким требованиям. Его можно рассматривать как обобщение других пространственных древовидных структур, таких как k -d деревья и квадродеревья , где гиперплоскости, разделяющие пространство, могут иметь любую ориентацию, а не быть выровненными с осями координат, как в k -d деревьях или квадродеревьях. При использовании в компьютерной графике для рендеринга сцен, состоящих из плоских полигонов , плоскости разбиения часто выбираются так, чтобы совпадать с плоскостями, определяемыми полигонами в сцене.
Конкретный выбор плоскости разбиения и критерий завершения процесса разбиения варьируются в зависимости от цели BSP-дерева. Например, при рендеринге компьютерной графики сцена делится до тех пор, пока каждый узел BSP-дерева не будет содержать только полигоны, которые могут быть отрисованы в произвольном порядке. При использовании отбраковки задних граней каждый узел, таким образом, содержит выпуклый набор полигонов, тогда как при рендеринге двухсторонних полигонов каждый узел BSP-дерева содержит только полигоны в одной плоскости. При обнаружении столкновений или трассировке лучей сцена может быть разделена на примитивы, на которых тесты на столкновение или пересечение лучей являются простыми.
Бинарное разбиение пространства возникло из компьютерной графики, требующей быстрой отрисовки трехмерных сцен, состоящих из полигонов. Простым способом отрисовки таких сцен является алгоритм художника , который создает полигоны в порядке удаления от зрителя, сзади вперед, закрашивая фон и предыдущие полигоны с каждым более близким объектом. Этот подход имеет два недостатка: время, необходимое для сортировки полигонов в порядке сзади вперед, и возможность ошибок в перекрывающихся полигонах. Фукс и соавторы [2] показали, что построение BSP-дерева решило обе эти проблемы, предоставив быстрый метод сортировки полигонов относительно заданной точки обзора (линейной по количеству полигонов в сцене) и разделив перекрывающиеся полигоны, чтобы избежать ошибок, которые могут возникнуть с алгоритмом художника. Недостатком бинарного разбиения пространства является то, что генерация BSP-дерева может занять много времени. Обычно он выполняется один раз на статической геометрии, как предварительный этап расчета, перед рендерингом или другими операциями в реальном времени на сцене. Расходы на построение дерева BSP затрудняют и делают неэффективным непосредственное внедрение движущихся объектов в дерево.
Поколение
Каноническое использование BSP-дерева — для рендеринга полигонов (двусторонних, то есть без отсечения задней грани ) с помощью алгоритма художника. Каждый полигон обозначается передней и задней сторонами, которые могут быть выбраны произвольно и влияют только на структуру дерева, но не на требуемый результат. [2] Такое дерево строится из несортированного списка всех полигонов в сцене. Рекурсивный алгоритм построения BSP-дерева из этого списка полигонов: [2]
Выберите многоугольник P из списка.
Создайте узел N в дереве BSP и добавьте P в список полигонов в этом узле.
Для каждого другого полигона в списке:
Если этот многоугольник полностью находится перед плоскостью, содержащей P , переместите этот многоугольник в список узлов перед P.
Если этот многоугольник полностью находится позади плоскости, содержащей P , переместите этот многоугольник в список узлов позади P.
Если этот многоугольник пересекается плоскостью, содержащей P , разделите его на два многоугольника и переместите их в соответствующие списки многоугольников позади и перед P.
Если этот многоугольник лежит в плоскости, содержащей P , добавьте его в список многоугольников в узле N.
Применим этот алгоритм к списку полигонов перед P.
Применим этот алгоритм к списку полигонов позади P.
Следующая диаграмма иллюстрирует использование этого алгоритма при преобразовании списка линий или полигонов в дерево BSP. На каждом из восьми шагов (i.-viii.) алгоритм выше применяется к списку линий, и к дереву добавляется один новый узел.
Конечное число полигонов или линий в дереве часто больше (иногда намного больше [2] ), чем исходный список, поскольку линии или полигоны, пересекающие плоскость разбиения, должны быть разделены на две части. Желательно минимизировать это увеличение, но также поддерживать разумный баланс в конечном дереве. Поэтому выбор того, какой полигон или линия используются в качестве плоскости разбиения (на шаге 1 алгоритма), важен для создания эффективного дерева BSP.
Обход
Дерево BSP обходит за линейное время в порядке, определяемом конкретной функцией дерева. Снова используя пример рендеринга двусторонних полигонов с использованием алгоритма художника, для правильного рисования полигона P требуется, чтобы сначала были нарисованы все полигоны за плоскостью, в которой лежит P , затем полигон P , затем, наконец, полигоны перед P . Если этот порядок рисования выполняется для всех полигонов в сцене, то вся сцена отображается в правильном порядке. Эту процедуру можно реализовать путем рекурсивного обхода дерева BSP с использованием следующего алгоритма. [2] Из заданного местоположения просмотра V , чтобы отрисовать дерево BSP,
Если текущий узел является конечным узлом, визуализируйте полигоны в текущем узле.
В противном случае, если точка просмотра V находится перед текущим узлом:
Рекурсивное применение этого алгоритма к сгенерированному выше дереву BSP приводит к следующим шагам:
Алгоритм сначала применяется к корневому узлу дерева, узлу A. V находится перед узлом A , поэтому мы сначала применяем алгоритм к дочернему дереву BSP, содержащему полигоны позади A.
Это дерево имеет корневой узел B1 . V находится за B1, поэтому сначала мы применяем алгоритм к дочернему дереву BSP, содержащему полигоны перед B1 :
Это дерево представляет собой просто конечный узел D1 , поэтому отображается полигон D1 .
Затем мы визуализируем полигон B1 .
Затем мы применяем алгоритм к дочернему дереву BSP, содержащему полигоны позади B1 :
Это дерево представляет собой просто конечный узел C1 , поэтому отображается полигон C1 .
Затем мы рисуем многоугольники A
Затем мы применяем алгоритм к дочернему дереву BSP, содержащему полигоны перед A.
Это дерево имеет корневой узел B2 . V находится позади B2 , поэтому сначала мы применяем алгоритм к дочернему дереву BSP, содержащему полигоны перед B2 :
Это дерево представляет собой просто конечный узел D2 , поэтому отображается полигон D2 .
Затем мы визуализируем полигон B2 .
Затем мы применяем алгоритм к дочернему дереву BSP, содержащему полигоны позади B2 :
Это дерево имеет корневой узел C2 . V находится перед C2 , поэтому сначала мы применим алгоритм к дочернему дереву BSP, содержащему полигоны позади C2 . Однако такого дерева нет, поэтому мы продолжаем.
Мы визуализируем полигон C2 .
Применяем алгоритм к дочернему дереву BSP, содержащему полигоны перед C2.
Это дерево представляет собой просто конечный узел D3 , поэтому отображается полигон D3 .
Дерево обходит за линейное время и отображает полигоны в порядке от дальнего к ближнему ( D1 , B1 , C1 , A , D2 , B2 , C2 , D3 ), подходящем для алгоритма художника.
Приложение
BSP-деревья часто используются в 3D- видеоиграх , особенно в шутерах от первого лица и в играх с внутренним окружением. Игровые движки, использующие BSP-деревья, включают Doom (id Tech 1) , Quake (вариант id Tech 2) , GoldSrc и Source . В них BSP-деревья, содержащие статическую геометрию сцены, часто используются вместе с Z-буфером для корректного объединения подвижных объектов, таких как двери и персонажи, на фоновой сцене. Хотя двоичное разделение пространства обеспечивает удобный способ хранения и извлечения пространственной информации о полигонах в сцене, оно не решает проблему определения видимой поверхности . BSP-деревья также применялись для сжатия изображений. [5]
^ ab Schumacker, RA; Brand, B.; Gilliland, MG; Sharp, WH (1969). Исследование применения изображений, созданных на компьютере, к визуальному моделированию (отчет). Лаборатория кадровых ресурсов ВВС США. AFHRL-TR-69-14.
^ abcdefg Фукс, Генри; Кедем, Цви. М.; Нейлор, Брюс Ф. (1980). «О генерации видимых поверхностей априорными древовидными структурами» (PDF) . SIGGRAPH '80 Труды 7-й ежегодной конференции по компьютерной графике и интерактивным технологиям . ACM. стр. 124–133. doi :10.1145/965105.807481.
^ ab Тибо, Уильям К.; Нейлор, Брюс Ф. (1987). «Операции над множествами на многогранниках с использованием деревьев двоичного разбиения пространства». SIGGRAPH '87 Труды 14-й ежегодной конференции по компьютерной графике и интерактивным технологиям . ACM. стр. 153–162. doi :10.1145/37402.37421.
^ Этерингтон, Томас Р.; Морган, Фрейзер Дж.; О'Салливан, Дэвид (2022). «Двоичное разбиение пространства генерирует иерархические и прямолинейные нейтральные модели ландшафта, подходящие для ландшафтов, в которых доминирует человек». Landscape Ecology . 37 (7): 1761–1769. Bibcode :2022LaEco..37.1761E. doi : 10.1007/s10980-022-01452-6 .
^ Х. Радха, М. Веттерли и Р. Леонарди, «Сжатие изображений с использованием деревьев двоичного разбиения пространства», в IEEE Transactions on Image Processing , т. 5, № 12, стр. 1610-1624, декабрь 1996 г., doi: 10.1109/83.544569.
Дополнительные ссылки
Naylor, B.; Amanatides, J.; Thibault, W. (август 1990 г.). «Слияние деревьев BSP дает операции над многогранными множествами». ACM SIGGRAPH Computer Graphics . 24 (4): 115–124. CiteSeerX 10.1.1.69.292 . doi :10.1145/97880.97892.
Нейлор, Б. (май 1993 г.). "Построение хороших деревьев разбиения". Графический интерфейс . CiteSeerX 10.1.1.16.4432 .[ мертвая ссылка ]
Чен, С.; Гордон, Д. (сентябрь 1991 г.). «Отображение деревьев BSP спереди назад». IEEE Computer Graphics and Applications . 11 (5): 79–85. doi :10.1109/38.90569. S2CID 19056967.
Радха, Х.; Леонарди, Р.; Веттерли, М.; Нейлор, Б. (1991). «Двоичное представление изображений в виде дерева разбиения пространства». Журнал визуальных коммуникаций и обработки изображений . 2 (3): 201–221. doi : 10.1016/1047-3203(91)90023-9 .
Радха, Х. М. С. (1993). Эффективное представление изображений с использованием деревьев двоичного разбиения пространства (PhD). Колумбийский университет. OCLC 30775044.
Радха, ХМС (1994). «Эффективное представление изображений с использованием деревьев разбиения двоичного пространства». Обработка сигналов . 35 (2): 174–181. doi :10.1016/0165-1684(94)90047-7.
Радха, Х.; Веттерли, М.; Леонарди, Р. (декабрь 1996 г.). «Сжатие изображений с использованием деревьев двоичного разбиения пространства». Труды IEEE по обработке изображений . 5 (12): 1610–24. Bibcode : 1996ITIP....5.1610R. doi : 10.1109/83.544569. PMID 18290079.https://ui.adsabs.harvard.edu/abs/1996ITIP....5.1610R/abstract
Winter, AS (апрель 1999 г.). «Исследование рендеринга 3D-полигонов в реальном времени с использованием деревьев BSP». CiteSeerX 10.1.1.11.9725 .
Эриксон, Кристер (2005). "8. Иерархии дерева BSP". Обнаружение столкновений в реальном времени . Серия Моргана Кауфмана по интерактивной 3-D технологии. Морган Кауфманн. стр. 349–382. ISBN 1-55860-732-3.
Внешние ссылки
Нейлор, Б.Ф. (2005). «Учебник по деревьям разбиения двоичного пространства».
Презентация деревьев BSP
Еще одна презентация деревьев BSP
Апплет Java, демонстрирующий процесс генерации дерева
