Введение в BSP деревья или BSP для самых «маленьких». Часть первая, теоретическая. (3 стр)

Автор: Антон В. Звягинцев

Рендеринг

Итак, мы подошли к тому самому процессу визуализации. Еще раз напомню читателю, что все приведенные выше действия будут справедливы и для трехмерного случая построения Bsp дерева. Вернемся к нашему примеру на рисунке 1 и попробуем использовать построенное нами BSP дерево. Не буду словесно описывать процесс, и воспользуюсь более лаконичным в данном случае методом — Си/псевдокод:

void RenderBSP(Node *node)
{
  int result = ClassifyPoint(camera_position,node->splitter_polygon);

  if (result == FRONT)
  {
    if (node->back != NULL) RenderBSP(node->back);
    DrawPolygon(node->splitter_polygon);
    if (node->front != NULL) RenderBSP(node->front);
  }
  else
  {
    if (node->front != NULL) RenderBSP(node->front);
    DrawPolygon(node->splitter_polygon);
    if (node->back != NULL) RenderBSP(node->back);
  }

  return;
}

Немного рекурсии и вуаля. Как уже догадался читатель, функция ClassifyPoint(), исходя из положения камеры и текущего узла дерева, определяет положение камеры относительно плоскости сплиттера (которую мы всегда можем получить, ведь в узле дерева хранится полигон и мы всегда можем рассчитать плоскость, на которой он расположен) — расположена ли камера перед или за плоскостью. Функция DrawPolygon() — ни что иное, как рисование самого полигона. Попробуем разобрать псевдокод на примере обхода дерева по рисунку 1. Напомню, что красная точка на рисунке — положение камеры. Причем, пока мы не занялись совершенствованием алгоритма, ориентация камеры и ее область просмотра (frustum) не имеют никакого значения. Первым узлом в функцию передается корневой узел построенного нами дерева b (Смотри рисунок 4).

• Камера расположена перед b. Таким образом, result == FRONT. Исходя из этого, функция вызывается рекурсивно, но в качестве базового узла мы передаем a-узел.
• Камера расположена перед a. Как видно из рисунка 4, у узла a нет полигонов позади его плоскости. Таким образом, мы отображаем полигон a.
• У узла a есть полигоны перед плоскостью, на которой он лежит. Еще один рекурсивный вызов RenderBSP() с узлом с1.
• В данном случае, не важно где расположена камера относительно плоскости сплиттера c1, т.к. он не имеет узлов потомков. Отображаем полигон c1.
• Покинув третий, а затем и второй рекурсивный вызов, возвращаемся к первому.

Как уже обратил внимание читатель, мы полностью закончили с левой частью дерева. Переходим к правой части.

• Поскольку мы вернулись в первый рекурсивный вызов, мы отображаем полигон b. Затем вызываем рекурсивно функцию с узлом c2.
• Камера расположена перед узлом c2. Рекурсивно вызываем функцию с узлом e.
• У узла e нет узлов потомков, поэтому мы просто отображаем полигон e.
• Возвратившись из рекурсивного вызова, отображаем полигон c2.
• Вызываем рекурсивно функцию c узлом d.
• У узла d нет узлов потомков, поэтому мы просто его отображаем.

Все! Теперь опишем порядок отображения полигонов, который мы только что получили:

a, c1, b, e, c2, d

Данный метод отображения называется back-to-front. Обрати внимание, что по разным направлениям сначала отображаются наиболее удаленные полигоны, что отражено в названии метода. Читатель может убедиться в правильности работы еще раз, но уже самостоятельно, попробовав пройти алгоритм при расположении камеры в другой точке. Back-to-front не единственный метод отображения полигонов. В программном рендеринге Quake I Майк Абраш (еще одна практически легендарная личность в сфере компьютерной графики) и Джон Кармак использовали front-to-back подход. Грани полигонов выносились ими в отдельный список, а затем растеризовались только их видимые порции. Главным преимуществом такого подхода было отсутствие повторных прорисовок пикселей (overdraw), однако такой подход, как нетрудно заметить, скорее полезен и легко реализуем для программного рендеринга, чем для аппаратного при использовании OpenGL или Direct3D. Кроме того, front-to-back подход позволяет использовать в программе так называемый early-out, завершение процедуры обхода дерева и его рендеринга ранее, при условии, что все пиксели на экране уже растеризованны. Как ты уже заметил, преимущества front-to-back подхода было бы неоспоримым на достаточно комплексных сценах.

Размышления о совершенствовании. Node culling или отсечение узлов

Теперь читателю стоит напрячь свое воображение и представить огромный игровой уровень, который нужно визуализировать. Так как BSP дерево само по себе никоим образом не упрощает геометрию уровня и не является алгоритмом отсечения невидимых граней, при достаточно большом количестве полигонов частота кадров в секунду будет стремиться к нулю. Одним из способов получения "независимости" отображаемых полигонов от сложности геометрии уровня является PVS алгоритм, о котором мы поговорим позже. Сейчас мы рассмотрим другой, достаточно несложный способ, который так же рассчитывается в процессе создания дерева, а затем может быть легко использован для визуализации. Для этого нам понадобится рассчитывать ограничивающие параллелепипеды или сферы (bounding box, bounding sphere). Сферы, как уже знает читатель, более просты в вычислениях и их использовании, однако часто дают менее точный результат. Идея заключается в том, чтобы для каждого узла рассчитать ограничивающий его объем (будь то сфера или параллелепипед), причем в объем также должны входить ВСЕ узлы потомки. Исходя из этого, достаточно вначале нашей функции RenderBSP() добавить функцию, проверяющую находится ли узел и его потомки в области просмотра камеры:

void RenderBSP(Node *node)
{
  if ( ! IsInFrustum(node) ) return;

  int result = ClassifyPoint(camera_position,node->splitter_polygon);

  //...

а в структуру узла включить члены, описывающие ограничивающий объем.

Описание структур данных

В предыдущем примере структура, описывающая BSP узел, могла бы выглядеть следующим образом:

struct Node
{
  Polygon *splitter_polygon;
  Node *front;
  Node *back;
};

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

struct Node
{
  int polyindex;
  int plane;
  int front;
  int back;
};

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

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

struct Polygon
{
...
Polygon *same;
Polygon *opposite;
};

Указатели same и opposite будут представлять собой часть связного списка, который будет построен в процессе компиляции bsp дерева. Соответственно, same будет содержать ссылку на сонаправленный полигон, а opposite - на направленный в обратном направлении. Модификация кода рендеринга будет следующей:

void RenderBSP(Node *node)
{
  Polygon *shared;
  int result = ClassifyPoint(camera_position,node->splitter_polygon);

  if (result == FRONT)
  {
    shared  = node->splitter_polygon->same;

    if (node->back != NULL) RenderBSP(node->back);
    DrawPolygon(node->splitter_polygon);
    while(shared != NULL) { DrawPolygon(shared); shared = shared->same; }
    if (node->front != NULL) RenderBSP(node->front);
  }
  else
  {
    shared = node->splitter_polygon->opposite;

    if (node->front != NULL) RenderBSP(node->front);
    DrawPolygon(node->splitter_polygon);
    while(shared != NULL) { DrawPolygon(shared); shared = shared->opposite; }
    if (node->back != NULL) RenderBSP(node->back);
  }

  return;
}

Solid Node BSP Tree

Solid в переводе — твердый; прочный; сплошной. Нет, BSP дерево, которое мы строили до этого, не было «мягким». :) Дело в применении. Дело в том, что Solid Node BSP дерево может эффективно использоваться для контроля столкновений. Рассмотрим отличия Solid Node BSP:
• Как ты уже заметил, в нашем примере, в случае если у узла нет потомков, мы заносим во front и/или back указатели NULL. В такой же ситуации для Node BSP Tree мы будем добавлять еще один узел. Соответственно, у этого узла указатели front и back будут установлены в NULL. Кроме того, в структуре данных Node будет добавлено поле IsSolid. Это поле будет сигнализировать нам о том, что позади плоскости родительского узла — пространство, в котором камера не должна или не может находиться.
• Второе отличие в том, как мы поступаем с полигонами, лежащими на плоскости сплиттера. В базовом варианте мы заносили эти полигоны в тот же узел, в который заносили и сам полигон сплиттер. Теперь, в случае если полигон лежит на одной плоскости со сплиттером, мы просто добавляем его в список входных параметров полигонов, расположенных перед плоскостью сплиттера.

Туманно? Перейдем к практике. Пример, рассмотренный нами до этого, не очень походил на игровой уровень, не так ли? Рассмотрим Solid Node BSP на более подходящем примере, изображенном на рисунке 5 (пример комнаты, который часто приводит Гарри Симонс в своих статьях):

Исходя из уже полученных знаний, попробуем выстроить Solid Node BSP дерево. В качестве сплиттера воспользуемся полигоном b. Полигон e будет рассечен плоскостью сплиттера на два полигона – e1 слева и e2 справа. В итоге мы будем иметь два входных списка параметров:
• расположенные перед плоскостью сплиттера: a, f, e1
• расположенные за плоскостью сплиттера: c, d, e2

Возьмем первый список и повторим процесс разбиения. В качестве сплиттера выберем полигон a.
• расположенные перед списком сплиттера: f, e1

Вот мы и подошли к одному из отличий Solid варианта алгоритма. Как уже заметил читатель, позади плоскости сплиттера полигонов нет. Это сигнализирует о том, что за полигоном-сплиттером недоступное пространство. Таким образом, при создании дерева мы добавим в back указатель ссылку на новый узел, у которого флаг IsSolid будет выставлен в 'истина', а указатели back и front будут равны NULL. Продолжая разбиение, аналогичным образом мы поступим, выбрав в качестве сплиттера полигон f. Перед плоскостью полигона f расположен один единственный полигон — e1. Таким образом, пространство за f также может быть помечено как solid. В качестве следующего полигона-сплиттера может выступить только e1. Здесь есть еще один момент, на который обязательно стоит обратить внимание. В случае, если полигон претендент является последним, нам необходимо создать уже два экстра узла, так как ни позади, ни перед плоскостью сплиттера нет доступных для дальнейшей обработки полигонов. При этом, для сохранения правильности формируемого BSP дерева, флажок IsSolid устанавливается в истину только в случае back-экстра узла. Почему так? В случае, когда каждый из полигонов расположен перед другим (к примеру, в случае входного списка a, f и e1 так и есть), полигоны списка образуют выпуклый объем. Внутри объема пространство не может быть отмечено как solid.

Продолжая разбиение снова и снова, в конечном итоге мы получим дерево, изображенное на рисунке 6:

В сером круге на рисунке изображены экстра-узлы с установленным в истина флажком IsSolid.

Несколько слов о контроле столкновений

Обсудим в двух словах то, как мы можем воспользоваться той информацией, что находится в нашем новоиспеченном Solid Node BSP дереве. Без наличия каких либо оптимизирующих алгоритмов, программист вынужден проводить контроль столкновений для всех без исключения полигонов в мире. Используя BSP дерево, мы просто опускаемся вниз от корневого узла до последнего дочернего (относительно текущего расположения объекта, как и при процедуре рендеринга к примеру), "в котором" расположен объект, для которого выполняется тест. Спускаясь все ниже и ниже с каждым узлом, мы автоматически отсеиваем часть полигонов, столкновение с которыми нужно было бы проверить. Добравшись по дереву до нужного нам полигона, используя простейшую трассировку луча, тестируем пересечение прямой с полигоном. Полигон нам придется получить из узла родителя, так как добавленные нами экстра узлы не будут содержать информацию о полигоне, хотя вопрос модификации базового алгоритма всегда остается открытым :)

Прямая может, к примеру, быть образованна двумя точками – той, в которой находится объект, к которому применяется контроль столкновений и той, в которую объект должен будет попасть.

#BSP, #PVS, #математика

7 мая 2004 (Обновление: 6 июля 2009)

Комментарии [91]