Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
См. Также: k -d дерево , Octree и Quadtree.
Процесс создания BSP-дерева

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

Разделение двоичного пространства было разработано в контексте трехмерной компьютерной графики в 1969 году. [1] [2] Структура BSP-дерева полезна при рендеринге, поскольку она может эффективно предоставлять пространственную информацию об объектах в сцене, например, об упорядочиваемых объектах. спереди назад по отношению к зрителю в данном месте. Другие приложения BSP включают: выполнение геометрических операций с формами ( конструктивная твердотельная геометрия ) в САПР , [3] обнаружение столкновений в робототехнике и трехмерных видеоиграх, трассировка лучей.и другие приложения, которые связаны со сложными пространственными сценами.

Обзор [ править ]

Разделение двоичного пространства - это общий процесс рекурсивного разделения сцены на две, пока разделение не удовлетворяет одному или нескольким требованиям. Его можно рассматривать как обобщение других структур пространственных деревьев, таких как k -d деревья и квадродеревья , где гиперплоскости, разделяющие пространство, могут иметь любую ориентацию, а не быть выровненными по осям координат, как в k -d деревьях или квадродеревья. При использовании в компьютерной графике для визуализации сцен, состоящих из плоских многоугольников , плоскости разделения часто выбираются так, чтобы они совпадали с плоскостями, определяемыми многоугольниками в сцене.

Конкретный выбор плоскости разделения и критерия завершения процесса разделения зависит от цели BSP-дерева. Например, при визуализации компьютерной графики сцена разделяется до тех пор, пока каждый узел дерева BSP не будет содержать только многоугольники, которые можно визуализировать в произвольном порядке. Когда используется отбраковка задней поверхности , каждый узел, следовательно, содержит выпуклый набор многоугольников, тогда как при визуализации двусторонних многоугольников каждый узел дерева BSP содержит только многоугольники в одной плоскости. При обнаружении столкновений или трассировке лучей сцена может быть разделена на примитивы, на которых тесты столкновения или пересечения лучей являются простыми.

Разделение двоичного пространства возникло из-за необходимости компьютерной графики быстро рисовать трехмерные сцены, состоящие из многоугольников. Простым способом рисования таких сцен является алгоритм художника , который создает многоугольники в порядке удаления от зрителя, от задней части к передней, закрашивая фон и предыдущие многоугольники каждым более близким объектом. Этот подход имеет два недостатка: время, необходимое для сортировки полигонов в обратном порядке, и возможность ошибок в перекрывающихся полигонах. Фукс и соавторы [2]показали, что построение BSP-дерева решает обе эти проблемы, предоставляя быстрый метод сортировки полигонов относительно заданной точки обзора (линейной по количеству полигонов в сцене) и путем подразделения перекрывающихся полигонов, чтобы избежать ошибок, которые могут возникнуть при работе художника. алгоритм. Недостатком разделения двоичного пространства является то, что создание BSP-дерева может занять много времени. Обычно это выполняется один раз на статической геометрии в качестве шага предварительного расчета перед рендерингом или другими операциями в реальном времени на сцене. Стоимость построения BSP-дерева затрудняет и неэффективно прямую реализацию перемещаемых объектов в дерево.

Деревья BSP часто используются в 3D- видеоиграх , особенно в шутерах от первого лица и в играх с внутренним окружением. Игровые движки, использующие деревья BSP, включают движки Doom (id Tech 1) , Quake (вариант id Tech 2) , GoldSrc и Source . В них деревья BSP, содержащие статическую геометрию сцены, часто используются вместе с Z-буфером для правильного объединения подвижных объектов, таких как двери и персонажи, в фоновую сцену. Хотя двоичное разбиение пространства обеспечивает удобный способ хранения и извлечения пространственной информации о многоугольниках в сцене, оно не решает проблему определения видимой поверхности .

Поколение [ править ]

Каноническое использование BSP-дерева - для рендеринга многоугольников (которые являются двусторонними, то есть без отбраковки обратной стороны ) с помощью алгоритма рисовальщика. Каждый многоугольник имеет лицевую и обратную стороны, которые могут быть выбраны произвольно и влияют только на структуру дерева, но не на требуемый результат. [2] Такое дерево строится из несортированного списка всех полигонов в сцене. Рекурсивный алгоритм построения BSP-дерева из этого списка многоугольников: [2]

  1. Выберите многоугольник P из списка.
  2. Создайте узел N в дереве BSP и добавьте P в список многоугольников в этом узле.
  3. Для каждого другого многоугольника в списке:
    1. Если многоугольник полностью перед плоскостью , содержащей Р , переместите многоугольник в список узлов в передней части P .
    2. Если многоугольник целиком за плоскостью , содержащей Р , переместите многоугольник в список узлов позади P .
    3. Если многоугольник пересекает плоскость , содержащую Р , разделить его на два многоугольника и переместить их в соответствующих списках многоугольников позади и перед P .
    4. Если этот многоугольник лежит в плоскости , содержащей P , добавьте его в список полигонов в узле N .
  4. Применение этого алгоритма к списку многоугольников перед P .
  5. Применение этого алгоритма к списку многоугольников за P .

Следующая диаграмма иллюстрирует использование этого алгоритма при преобразовании списка линий или многоугольников в дерево BSP. На каждом из восьми шагов (i.-viii.) Описанный выше алгоритм применяется к списку строк, и к дереву добавляется один новый узел.

Начните со списка линий (или в 3D, многоугольников), составляющих сцену. На древовидных диаграммах списки обозначены скругленными прямоугольниками, а узлы в дереве BSP - кружками. На пространственной диаграмме линий направление, выбранное в качестве «передней» линии, обозначено стрелкой.
я.Следуя шагам описанного выше алгоритма,
  1. Выбираем из списка линию A и ...
  2. ... добавить его в узел.
  3. Мы разделяем оставшиеся строки в списке на те, что перед A (т.е. B2, C2, D2), и те, что позади (B1, C1, D1).
  4. Сначала мы обрабатываем строки перед A (шаги ii – v), ...
  5. ... сопровождаемые теми, кто находится позади (на этапах vi – vii).
II.Теперь применим алгоритм к списку строк перед A (содержащему B2, C2, D2). Мы выбираем линию B2, добавляем ее к узлу и разделяем оставшуюся часть списка на те строки, которые находятся перед B2 (D2), и те, которые находятся за ним (C2, D3).
iii.Выберите строку D2 из списка строк перед B2 и A. Это единственная строка в списке, поэтому после добавления ее к узлу больше ничего делать не нужно.
iv.Мы закончили с линиями перед B2, поэтому рассмотрим линии позади B2 (C2 и D3). Выберите одну из них (C2), добавьте ее в узел и поместите другую строку из списка (D3) в список строк перед C2.
v.Теперь посмотрите на список строк перед C2. Есть только одна линия (D3), поэтому добавьте ее в узел и продолжайте.
vi.Теперь мы добавили все строки перед A в дерево BSP, поэтому теперь мы начинаем со списка строк за A. Выбирая строку (B1) из этого списка, мы добавляем B1 к узлу и разделяем оставшуюся часть список на строки перед B1 (т.е. D1) и строки за B1 (т.е. C1).
vii.Сначала обрабатываем список строк перед B1, D1 - единственная строка в этом списке, поэтому добавьте ее в узел и продолжайте.
viii.Теперь посмотрим на список строк после B1, единственная строка в этом списке - C1, поэтому добавьте ее к узлу, и дерево BSP готово.

Конечное количество многоугольников или линий в дереве часто больше (иногда намного больше [2] ), чем исходный список, поскольку линии или многоугольники, пересекающие плоскость разделения, должны быть разделены на две части. Желательно минимизировать это увеличение, но также сохранить разумный баланс в конечном дереве. Поэтому выбор полигона или линии для использования в качестве плоскости разделения (на шаге 1 алгоритма) важен для создания эффективного BSP-дерева.

Обход [ править ]

Дерево BSP проходит за линейное время в порядке, определяемом конкретной функцией дерева. Снова используя пример рендеринга двухсторонние многоугольники с использованием алгоритма живописца, чтобы нарисовать многоугольник P правильно требует , чтобы все полигоны позади плоскости P лежит в должны быть сделаны первые, то многоугольник P , затем , наконец, многоугольники перед P . Если этот порядок рисования выполняется для всех полигонов в сцене, тогда вся сцена отображается в правильном порядке. Эта процедура может быть реализована путем рекурсивного обхода дерева BSP с использованием следующего алгоритма. [2] Из заданного места просмотра V для визуализации дерева BSP,

  1. Если текущий узел является листовым, визуализируйте полигоны в текущем узле.
  2. В противном случае, если точка просмотра V находится перед текущим узлом:
    1. Визуализировать дочернее дерево BSP, содержащее многоугольники за текущим узлом
    2. Отрисовываем полигоны в текущем узле
    3. Визуализируйте дочернее дерево BSP, содержащее многоугольники перед текущим узлом
  3. В противном случае, если точка просмотра V находится за текущим узлом:
    1. Визуализируйте дочернее дерево BSP, содержащее многоугольники перед текущим узлом
    2. Отрисовываем полигоны в текущем узле
    3. Визуализировать дочернее дерево BSP, содержащее многоугольники за текущим узлом
  4. В противном случае точка просмотра V должна находиться точно в плоскости, связанной с текущим узлом. Потом:
    1. Визуализируйте дочернее дерево BSP, содержащее многоугольники перед текущим узлом
    2. Визуализировать дочернее дерево BSP, содержащее многоугольники за текущим узлом

Применение этого алгоритма рекурсивно к дереву 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 , В1 , С1 , , D2 , В2 , С2 , D3 ) подходит для алгоритма художника.

Хронология [ править ]

  • 1969 Schumacker et al. [1] опубликовал отчет, в котором описывалось, как тщательно расположенные плоскости в виртуальной среде могут быть использованы для ускорения упорядочения полигонов. В технике использовалась когерентность глубины, которая гласит, что многоугольник на дальней стороне плоскости никоим образом не может препятствовать более близкому многоугольнику. Это использовалось в авиасимуляторах, сделанных GE, а также Evans и Sutherland. Однако создание полигональной организации данных было выполнено дизайнером сцены вручную.
  • 1980 г. Fuchs et al. [2] расширил идею Шумакера на представление трехмерных объектов в виртуальной среде, используя плоскости, которые совпадают с многоугольниками, для рекурсивного разделения трехмерного пространства. Это обеспечило полностью автоматизированное и алгоритмическое создание иерархической многоугольной структуры данных, известной как дерево разделения двоичного пространства (BSP Tree). Процесс происходил как этап предварительной обработки в автономном режиме, который выполнялся один раз для каждой среды / объекта. Во время выполнения упорядочение видимости в зависимости от вида создавалось путем обхода дерева.
  • Кандидатская диссертация Нейлора 1981 года обеспечила полное развитие как BSP-деревьев, так и теоретико-графического подхода с использованием сильно связанных компонентов для предварительного вычисления видимости, а также связь между двумя методами. Особое внимание было уделено деревьям BSP как структуре пространственного поиска, не зависящей от размеров, с приложениями для определения видимой поверхности. В диссертацию также были включены первые эмпирические данные, демонстрирующие, что размер дерева и количество новых многоугольников были разумными (с использованием модели космического челнока).
  • 1983 Fuchs et al. описал реализацию микрокода алгоритма дерева BSP в системе буфера кадра Ikonas. Это была первая демонстрация определения видимой поверхности в реальном времени с использованием деревьев BSP.
  • 1987 Тибо и Нейлор [3] описали, как произвольные многогранники могут быть представлены с использованием BSP-дерева в отличие от традиционного b-rep (граничного представления). Это обеспечило твердое представление по сравнению с представлением на основе поверхности. Для описания операций над многогранниками использовался инструмент, позволяющий создавать твердотельную геометрию (CSG) в реальном времени. Это был предшественник дизайна уровней BSP с использованием « кистей », представленных в редакторе Quake и использованных в редакторе Unreal.
  • 1990 Нейлор, Аманатидес и Тибо предложили алгоритм слияния двух деревьев BSP, чтобы сформировать новое дерево BSP из двух исходных деревьев. Это дает множество преимуществ, в том числе: объединение движущихся объектов, представленных деревьями BSP, со статической средой (также представленной деревом BSP), очень эффективные операции CSG с многогранниками, точное обнаружение столкновений в O (log n * log n) и правильное упорядочение прозрачные поверхности, содержащиеся в двух взаимопроникающих объектах (использовалось для эффекта рентгеновского зрения).
  • 1990 Теллер и Секен предложили автономную генерацию потенциально видимых наборов для ускорения определения видимой поверхности в ортогональных 2D-средах.
  • 1991 Гордон и Чен [CHEN91] описали эффективный метод выполнения сквозного рендеринга из BSP-дерева, а не традиционный прямой подход. Они использовали специальную структуру данных для эффективной записи частей экрана, которые были нарисованы, и тех, которые еще предстоит визуализировать. Этот алгоритм вместе с описанием BSP-деревьев в стандартном учебнике компьютерной графики того времени ( Computer Graphics: Principles and Practice ) был использован Джоном Кармаком при создании Doom (видеоигры) .
  • В 1992 году докторская диссертация Теллера описывала эффективное создание потенциально видимых наборов как этап предварительной обработки для ускорения определения видимой поверхности в реальном времени в произвольных трехмерных полигональных средах. Это использовалось в Quake и значительно повлияло на производительность этой игры.
  • 1993 Нейлор ответил на вопрос о том, что характеризует хорошее дерево BSP. Он использовал модели ожидаемого случая (а не анализ наихудшего случая) для математического измерения ожидаемой стоимости поиска в дереве и использовал эту меру для построения хороших деревьев BSP. Интуитивно дерево представляет объект с несколькими разрешениями (точнее, как дерево приближений). Проведены параллели с кодами Хаффмана и вероятностными деревьями двоичного поиска.
  • В 1993 году докторская диссертация Хайдера Радхи описывала (естественные) методы представления изображений с использованием BSP-деревьев. Это включает в себя разработку оптимальной структуры построения BSP-дерева для любого произвольного входного изображения. Эта структура основана на новом преобразовании изображения, известном как преобразование линии разделения по методу наименьших квадратов (LSE) (LPE). В диссертации Х. Радхи также была разработана система сжатия изображений с оптимальным соотношением искажений (RD) и подходы к управлению изображениями с использованием деревьев BSP.

См. Также [ править ]

  • kd дерево
  • Octree
  • Quadtree
  • Иерархическая кластеризация , альтернативный способ разделения данных 3D-модели для эффективного рендеринга.
  • Гильотинная резка

Ссылки [ править ]

  1. ^ a b Шумакер, Роберт А .; Бренд, Бриджитта; Гиллиланд, Морис Дж .; Шарп, Вернер Х. (1969). Исследование по применению компьютерных изображений для визуального моделирования (отчет). Лаборатория людских ресурсов ВВС США. п. 142. AFHRL-TR-69-14.
  2. ^ a b c d e f g Фукс, Генри; Кедем, Цви. M; Нейлор, Брюс Ф. (1980). «О генерации видимой поверхности с помощью априорных древовидных структур» (PDF) . SIGGRAPH '80 Материалы 7-й ежегодной конференции по компьютерной графике и интерактивной технике . ACM, Нью-Йорк. С. 124–133. DOI : 10.1145 / 965105.807481 .
  3. ^ a b Тибо, Уильям С .; Нейлор, Брюс Ф. (1987). «Установить операции над многогранниками с помощью деревьев разбиения двоичного пространства». SIGGRAPH '87 Материалы 14-й ежегодной конференции по компьютерной графике и интерактивной технике . ACM, Нью-Йорк. С. 153–162. DOI : 10.1145 / 37402.37421 .

Дополнительные ссылки [ править ]

  • [NAYLOR90] Б. Нейлор, Дж. Аманатидес и У. Тибуалт, «Слияние BSP-деревьев дает многогранные операции над множеством», Компьютерная графика (Siggraph '90), 24 (3), 1990.
  • [NAYLOR93] Б. Нейлор, «Построение хороших деревьев разбиения», Graphics Interface (ежегодная канадская конференция CG), май 1993 г.
  • [CHEN91] С. Чен и Д. Гордон. «Отображение деревьев BSP спереди назад». Компьютерная графика и алгоритмы IEEE, стр. 79–85. Сентябрь 1991 г.
  • [RADHA91] Х. Радха, Р. Леонарди, М. Веттерли и Б. Нейлор «Древовидное представление изображений в двоичном пространстве», Журнал визуальных коммуникаций и обработки изображений, 1991, том. 2 (3).
  • [RADHA93] Х. Радха, «Эффективное представление изображений с использованием деревьев разделения двоичного пространства», доктор философии. Диссертация, Колумбийский университет, 1993.
  • [RADHA96] Х. Радха, М. Веттерли и Р. Леонарди, «Сжатие изображений с использованием деревьев разделения двоичного пространства», IEEE Transactions on Image Processing, vol. 5, № 12, декабрь 1996 г., стр. 1610–1624.
  • [WINTER99] ИССЛЕДОВАНИЕ 3D-ПОЛИГОНОВ В РЕАЛЬНОМ ВРЕМЕНИ С ИСПОЛЬЗОВАНИЕМ BSP TREES. Эндрю Стивен Винтер. Апрель 1999 г. доступно онлайн
  • Марк де Берг ; Марк ван Кревельд ; Марк Овермарс и Отфрид Шварцкопф (2000). Вычислительная геометрия (2-е изд., Перераб.). Springer-Verlag . ISBN 978-3-540-65620-3.Раздел 12: Разделы двоичного пространства: стр. 251–265. Описывает рандомизированный алгоритм художника.
  • Кристер Эриксон: Обнаружение столкновений в реальном времени (серия Моргана Кауфмана в интерактивной трехмерной технологии) . Verlag Morgan Kaufmann , S. 349–382, Jahr 2005, ISBN 1-55860-732-3 

Внешние ссылки [ править ]

  • Учебник по деревьям BSP
  • Презентация BSP-деревьев
  • Еще одна презентация BSP-деревьев
  • Java-апплет, демонстрирующий процесс создания дерева.
  • Магистерская диссертация о создании BSP
  • Деревья BSP: теория и реализация
  • BSP в 3D пространстве