Двоичное разбиение пространства | это... Что такое Двоичное разбиение пространства? (original) (raw)

BSP-дерево — это структура данных, используемая в трехмерной графике. Аббревиатура BSP означает Binary Space Partition — двоичное разбиение пространства. BSP-дерево используется для эффективного выполнения следующих операций:

BSP-деревья были впервые применены специалистами компании Lucas Arts в начале 80-х годов. Популярность у разработчиков они завоевали благодаря компании id Software, разработавшей движки Doom (1993) и Quake (1996).

Содержание

Обзор

В BSP-дереве каждый узел связан с разбивающей прямой или плоскостью в 2-мерном или 3-мерном пространстве соответственно. При этом все объекты, лежащие с фронтальной стороны плоскости относятся к фронтальному поддереву, а все объекты, лежащие с оборотной стороны плоскости относятся к оборотному поддереву. Для определения принадлежности объекта к фронтальной или оборотной стороне разбивающей прямой или плоскости необходимо исследовать положение каждой его точки. Положение точки относительно плоскости определяется скалярным произведением нормали плоскости и координат точки в однородных координатах. Возможно три случая:

  1. Скалярное произведение больше 0 — точка лежит с фронтальной стороны плоскости;
  2. Скалярное произведение равно 0 — точка лежит на плоскости;
  3. Скалярное произведение меньше 0 — точка лежит с обратной стороны плоскости.

Если для всех точек объекта скалярное произведение больше или равно 0, то он относится к фронтальному поддереву. Если для всех точек объекта скалярное произведение меньше или равно 0, то он относится к оборотному поддереву. Если для всех точек объекта скалярное произведение равно 0, то не играет роли к какому поддереву он принадлежит. Если скалярные произведения для точек объекта имеют разный знак, то он рассекается разбивающей плоскостью так, чтобы полученные объекты лежали только с фронтальной или только с оборотной стороны. Для каждого подузла BSP-дерева справедливо вышеприведенное утверждение, с тем исключением, что рассмотрению подлежат только те объекты, которые принадлежат к фронтальной или оборотной стороне разбивающей плоскости родительского узла.

Построение дерева

Пример построения
1. A — корень и набор отрезков на плоскости целиком.
2. A делится на B и C.
3. B делится на D и E.
4. D делится на полностью выпуклые F и G, которые и становятся листьями дерева.

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

  1. Если заданное множество полигонов пустое, то закончить алгоритм;
  2. Для заданного множества полигонов выбрать разбивающую плоскость S;
  3. Рассечь все полигоны, пересекающиеся с S;
  4. Отнести все полигоны, находящиеся с фронтальной стороны S, к фронтальному поддереву F, а все полигоны, находящиеся с обратной стороны S, к оборотному поддереву B;
  5. Выполнить алгоритм рекурсивно для множества полигонов фронтального поддерева F;
  6. Выполнить алгоритм рекурсивно для множества полигонов оборотного поддерева B.

Выбор разбивающей плоскости

Разбивающая плоскость выбирается таким образом, чтобы сбалансировать дерево, то есть чтобы число полигонов в фронтальном и оборотном поддереве было приблизительно одинаково:

min(|N(Fi) — N(Bi)|)

где N(Fi) — число полигонов с фронтальной стороны некоторой разбивающей плоскости i, N(Bi) — число полигонов с оборотной стороны разбивающей плоскости i.

Применение

Сортировка объектов в порядке удаления от наблюдателя

При сортировке объектов в порядке удаления от наблюдателя с помощью BSP-дерева исследуются взаимное расположение вектора и точки наблюдения (POV) и нормалей разбивающих плоскостей. Если нормаль разбивающей плоскости и вектор наблюдения сонаправлены, то фронтальное поддерево находится от наблюдателя дальше, чем оборотное, в противном случае оборотное поддерево находится от наблюдателя дальше, чем фронтальное. При этом, если разбивающая плоскость находится сзади наблюдателя, то сама плоскость, а также фронтальное или оборотное поддерево может быть не видны полностью. Рекурсивный алгоритм сортировки полигонов с помощью BSP-дерева следующий:

Процедура ОбойтиУзел(Узел) Если Узел <> ПустойУказатель Если ВекторыСонаправлены(ВекторНаблюдения, Узел.НормальРазбивающейПлоскости) Если СкалярноеПроизведение(ТочкаНаблюдения, Узел.НормальРазбивающейПлоскости) >= 0 // Плоскость находится сзади наблюдателя, наблюдатель видит только фронтальное поддерево ОбойтиУзел(Узел.ФронтальноеПоддерево); Иначе // Плоскость находится спереди наблюдателя, // фронтальное поддерево находится дальше оборотного ОбойтиУзел(Узел.ФронтальноеПоддерево); ДобавитьПолигонВСписокОтображения(Узел.Полигон); ОбойтиУзел(Узел.ОборотноеПоддерево); КонецЕсли; Иначе Если СкалярноеПроизведение(ТочкаНаблюдения, Узел.НормальРазбивающейПлоскости) >= 0 // Плоскость находится спереди наблюдателя, // оборотное поддерево находится дальше фронтального ОбойтиУзел(Узел.ОборотноеПоддерево); ДобавитьПолигонВСписокОтображения(Узел.Полигон); ОбойтиУзел(Узел.ФронтальноеПоддерево); Иначе // Плоскость находится сзади наблюдателя, наблюдатель видит только оборотное поддерево ОбойтиУзел(Узел.ОборотноеПоддерево); КонецЕсли; КонецЕсли; КонецЕсли; Конец;

Этот алгоритм можно оптимизировать, если учесть, что для некоторого набора полигонов дерево имеет вырожденную структуру, в том случае, когда для каждого полигона из этого набора все оставшиеся лежат только с фронтальной или только с оборотной стороны. Именно так сделал Джон Кармак в движке DOOM.

Алгоритм для ускорения из рекурсивного может быть преобразован в итеративный.

Отсечение невидимых поверхностей

Отсечение невидимых поверхностей реализуется путем введения дополнительной информации в BSP-дерево, такой как рамки (bounding boxes, bounding spheres). Рамки — это прямоугольники или параллелепипеды, окружности или сферы, которые ограничивают область расположения полигонов некоторого поддерева. Таким образом, каждый узел имеет две рамки. Поддерево гарантированно невидимо, если зрительная пирамида не пересекается с ограничивающим объектом. Обратное неверно. Однако прямого утверждения достаточно, чтобы отсечь обработку существенного количества объектов.

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

Поиск столкновений

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

Пример:

Процедура ПоискСтолкновения(Узел, Объект) Если Узел <> ПустойУказатель Если Расстояние(Узел.Плоскость, Объект.ЦентрОграничивающейСферы) > Объект.РадиусОграничивающейСферы Если СкалярноеПроизведение(Объект.ЦентрОграничивающейСферы, Узел.НормальРазбивающейПлоскости) >= 0 // Объект находится с фронтальной стороны разбивающей плоскости, // обходим только фронтальное поддерево ПоискСтолкновения(Узел.ФронтальноеПоддерево, Объект); Иначе // Объект находится с обратной стороны разбивающей плоскости, // обходим только оборотное поддерево ПоискСтолкновения(Узел.ОборотноеПоддерево, Объект); КонецЕсли; Иначе Вернуть ЕстьСтолкновение; КонецЕсли; Иначе Вернуть НетСтолкновения; КонецЕсли; Конец;

Алгорим для ускорения из рекурсивного может быть преобразован в итеративный.

Ссылки

Просмотр этого шаблона Дерево (структура данных)
Двоичное дерево поиска · Дерево (теория графов) · Древовидная структура
Двоичные деревья Двоичное дерево · T-дерево
Самобалансирующиеся двоичные деревья АА-дерево · АВЛ-дерево · Красно-чёрное дерево · Расширяющееся дерево · Дерево со штрафами · Декартово дерево · Дерево Фибоначчи
B-деревья B-дерево · 2-3-дерево · B+ дерево · B*-дерево · UB-дерево · 2-3-4 дерево · (a,b)-дерево · Танцующее дерево
Префиксные деревья Суффиксное дерево · Radix tree · Ternary search tree
Двоичное разбиение пространства k-мерное дерево · VP-дерево
Недвоичные деревья Дерево квадрантов · Октодерево · Sparse Voxel Octree · Экспоненциальное дерево · PQ-дерево
Разбиение пространства R-дерево · R+-дерево · R*-дерево · X-дерево · M-дерево · Дерево Фенвика · Дерево отрезков
Другие деревья Куча · TTH · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree
Алгоритмы Поиск в ширину · Поиск в глубину · DSW-алгоритм · Алгоритм связующего дерева