Наше комьюнити:   OpenGL Shader Lab  •  Half-Life FX  •  Форум  
OpenGL Shader Lab

Просмотр комментариев

Показаны комментарии 1-0 из 0

Shadow Volume BSP 26-11-2009 12:58

Основное предназначение Shadow Volume BSP (SVBSP) – отбрасывание поверхностей, закрытых теневыми объемами данного источника света. Очевидно, что они сами не будут им освещаться и отбрасывать тени, поэтому их можно не обсчитывать в дальнейшем. Итак, BSP-дерево строится для всех поверхностей, отбрасывающих тени. В нашем случае оно строится только для статичной (world) геометрии и статичных источников света, так как процесс его построения довольно ресурсоемкий. Дерево потребляет большой объем памяти, поэтому не сохраняется.
Построение статичных теней с использованием SVBSP идет в несколько этапов:

  1. Построение «пустого» дерева.
  2. Выявление потенциальных отбрасывателей теней (Potential Shadow Caster, PSC) и потенциально освещенных поверхностей (Potential Lit Surface, PLS). Изначально они считаются не отбрасывающими тень и не освещенными.
  3. Для каждого PSC и PLS происходит обход дерева. Если существует занятая PSC/PLS область, не закрытая теневыми объемами, то PSC считается отбрасывающим тень и сам добавляется в SVBSP. PLS в этом случае считается освещенным.


Обратите внимание: мы не снимаем флаги освещенности и отбрасывания тени во время обхода дерева! Мы снимаем их заранее и выставляем назад во время обхода. Это связано с тем, что поверхность может быть разбита на несколько частей, и если ее часть закрыта теневыми объемами, а вторая часть – не закрыта, то в целом поверхность считается освещенной. В противном случае мы бы получали неосвещенную поверхность, даже если бы небольшой ее кусок был закрыт теневыми объемами, что неправильно.

Аллокация узлов и плоскостей
Для ускорения процесса расчета SVBSP заранее выделяется память под большое число узлов и плоскостей. Впоследствии они берутся из этого заранее выделенного массива. Плоскости, помимо того, ищутся в имеющемся массиве. Если такая плоскость (reference plane) уже имеется, то возвращается имеющаяся плоскость.
Плоскость содержит следующую информацию: нормаль, расстояние.


C++ Source Code:
typedef struct svplane_s
{
    vec3_t normal;
    float dist;
} svplane_t;


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


C++ Source Code:
typedef struct svnode_s
{
    svplane_t  *splitplane;
    struct svnode_s *children[2];
} svnode_t;



Построение «пустого» дерева
Пустое дерево строится таким образом, что охватывает все пространство целиком. Какой бы PSC в него не добавлялся, он всегда попадет в один из его узлов. Пустое дерево состоит из двух узлов и содержит две плоскости.
Пустое дерево выглядит следующим образом:

         plane
         /   \
      -plane  open
       /  \
   solid   open


open – это незанятая область, куда можно добавлять новые узлы.
solid – это область, закрытая другими кастерами, никакие узлы туда попасть не могут, и следовательно, указатель на узел будет всегда равен NULL.
Таким образом, построение пустого дерева осуществляется так:

  1. Очищаем все глобальные данные (например, кол-во выделенных узлов и плоскостей).
  2. Выделяем две плоскости (refplane = NULL). Задаем две противоположные нормали (1 0 0) и (-1 0 0). Плоскости должны проходить через источник света, поэтому рассчитываем расстояния: d = dot(lightPos, n);
  3. Выделяем два узла.
  4. Для первого узла задаем разделяющую плоскость – первую плоскость. Тому, что перед ней – т.е. первый дочерний узел – присваиваем адрес второго узла. То, что за ней – свободное пространство (NULL).
  5. Делим второй узел второй плоскостью. То, что перед ней – solid (т.к. разделяющая плоскость проходит по краю узла), а за ней – свободное пространство. Оба дочерних указателя равны NULL.

Пустое SVBSP-дерево построено и готово к работе.
 
Добавление PSC/PLS в дерево
Важный момент – PSC/PLS должны добавляться в дерево в порядке «от ближних к дальним». Только в этом случае будет происходить эффективное отсеивание дальних полигонов, закрытых ближними. Поэтому добавление PSC должно происходить строго в соответствии с BSP-деревом уровня (где они уже рассортированы от ближних к дальним)! О проблемах, возникающих при игнорировании этого правила, читайте в конце статьи.

Основная функция добавления PSC принимает следующие аргументы:
Главный узел SVBSP – в принципе, это может быть любой узел, но по логике алгоритма это должен быть именно Head Node.
Массив вершин – все вершины, которые участвуют в генерации теневого объема.
Количество вершин – количество вершин, переданных в массиве.
Указатель на структуру, хранящую информацию о вершине.
Стартовая глубина – при внешнем вызове надо указать 0. Используется внутри функции для того, чтобы определить зацикливание в дереве (т.к. функция рекурсивная).
Общий алгоритм функции таков:

  1. Проверяем глубину. Если она очень большая (скажем, больше 1500) – мы, вероятно, зависли в дереве. Выводим сообщение об этом и возвращаемся из функции.
  2. Проверяем входные данные. Если количество вершин меньше 1, или указатель на поверхность, или указатель на массив вершин пустые - то нам нечего считать. Возвращаемся.
  3. Собираем информацию о положении вершин относительно делящей плоскости. Для каждой вершины считаем dot(vertex, split->Normal) – split->Dist и определяем знак этого значения (т.е. с какой стороны плоскости находится точка). Получение знака мы делаем путем сравнения не с 0, а с неким эпсилоном (допустим, 0.1). Если точка за плоскостью (значение меньше -0.1), то возвращаем 1 (двоичный 01). Если перед (больше 0.1), возвращаем 2 (двоичный 10). Иначе возвращаем 0 – точка совпала с плоскостью. Объединяем все эти значения логическим OR. Понятно, что если полигон лежит целиком по одну сторону поверхности, то мы получим либо 1, либо 2. Если же по обе, то получим 3 (двоичное 11) и в этом случае его придется делить.
  4. Если полигон целиком лежит за делящей плоскостью, мы проверяем первый дочерний узел. Если он пуст, значит, мы попали в место, закрытое другими кастерами, возвращаемся. Если же узел не пуст, то перед возвращением мы рекурсивно проверяем его, не забывая увеличить глубину на единицу.
  5. Если полигон целиком лежит перед делящей плоскостью, мы проверяем второй дочерний узел. Если он пуст, значит мы в открытом пространстве, и поверхность будет освещена и будет отбрасывать тень. Следовательно, мы должны отметить соответствующие флаги поверхности (которые были изначально, но были сняты нами перед построением SVBSP). Но перед возвращением мы можем добавить наш кастер в SVBSP, если хотим. Для этого вызываем специальную функцию добавления объема в SVBSP и присваиваем возвращаемый ею узел второму дочернему узлу текущего. Не хотим – не вызываем, в этом случае мы просто проверили перекрывание, но сам вклад в дерево не сделали (например, если наша поверхность очень сложная в плане геометрии). Возвращаемся. Если же узел не пуст, то аналогично перед возвращением мы рекурсивно проверяем его, не забывая увеличить глубину на единицу.
  6. Если делящая плоскость пересекает полигон, то нам придется разбить полигон на две части строго по этой плоскости, и выполнить обе вышеописанные операции для каждого дочернего полигона.

Помимо рекурсивного обхода SVBSP-дерева, эта функция вызывает две другие очень важные функции: добавление объема в SVBSP и деление полигона плоскостью.
 
Добавление объема в SVBSP
Функция выполняет построение объема и правильно встраивает его в SVBSP-дерево.
Входные аргументы следующие:
Массив вершин – все вершины, которые участвуют в генерации теневого объема.
Количество вершин – количество вершин, переданных в массиве.
Указатель на структуру, хранящую информацию о вершине.
Возвращаемое значение: указатель на первый узел встроенного фрагмента дерева. Если возвращается NULL, значит, построение дерева по той или иной причине не произошло.
Общий алгоритм функции:

  1. Проверяем входные данные. Если количество вершин меньше 1, или указатель на поверхность, или указатель на массив вершин пустые - то нам нечего считать. Возвращаем NULL.
  2. Получаем узел для первого ребра. Для этого вызываем функцию создания узла для ребра (см. ниже). Если узел создать не удалось, возвращаем NULL.
  3. Устанавливаем полученный узел как текущий.
  4. Для всех оставшихся ребер делаем следующую операцию. Получаем узел для ребра. Если узел создать не удалось, прерываем построение дерева. Иначе – присваиваем его указателю на первый дочерний узел текущего узла и заменяем значение указателя текущего узла на данный узел. Таким образом, узлы для всех ребер оказываются связаны в одно дерево.
  5. Возвращаем узел для первого ребра (являющийся Head Node для данного объема).

Процесс создания узла для ребра выглядит следующим образом. Функция получает на входе две вершины и возвращает указатель на созданный узел (либо NULL, если создать его не удалось).

  1. Рассчитываем плоскость объема по трем точкам. Две точки – это вершины ребра, третья – позиция источника света. Не забываем про порядок обхода вершин – нормаль плоскости должна «смотреть» наружу объема.
  2. Выделяем новую плоскость на основе рассчитанной (если такая уже есть – функция аллокации вернет имеющуюся). Если выделить плоскость не удалось – возвращаем NULL.
  3. Выделяем новый узел и присваиваем ему делящую плоскость. Оба дочерних узла устанавливаем в NULL.
  4. Возвращаем выделенный узел.


 
Деление полигона плоскостью
Функция принимает следующие аргументы:
Массив вершин – все вершины, которые участвуют в генерации теневого объема.
Количество вершин – количество вершин, переданных в массиве.
Массив информации об ориентации вершин относительно делящей плоскости (0 – на плоскости, 1 – за плоскостью, 2 – перед плоскостью).
Выходные массивы вершин, лежащих за плоскостью и перед плоскостью, и количества вершин в них.
Алгоритм работы функции такой:

  1. Задаем точку сравнения – это последняя точка полигона. Сохраняем ее координату и знак как vRef и sideRef.
  2. Обходим все вершины по одной. Для каждой вершины проверяем ее ориентацию относительно точки сравнения. Возможны варианты:
    a. точка лежит за плоскостью, а точка сравнения – перед плоскостью. Сохраняем точку в выходной массив точек за плоскостью. Создаем новую точку на пересечении отрезка между текущей точкой и точкой сравнения (по уравнению пересечения луча с плоскостью), и записываем ее в оба выходных массива.
    b. точка лежит перед плоскостью, а точка сравнения – за плоскостью. Сохраняем точку в выходной массив точек перед плоскостью. Создаем новую точку на пересечении отрезка между текущей точкой и точкой сравнения, и записываем ее в оба выходных массива.
    c. точка лежит по ту же сторону плоскости, что и точка сравнения. Записываем ее в соответствующий массив.
    d. точка лежит примерно на плоскости. Записываем ее в оба массива.
  3. Присваиваем информацию о текущей точке точке сравнения и продолжаем цикл.


 
Что будет, если добавлять поверхности в SVBSP не в строгом порядке «от ближних к дальним»?
В этом случае возникает две основные сложности. Первая – это потеря части возможной оптимизации. В самом деле, если мы сначала добавим дальнюю плоскость, а потом ближнюю, то дерево будет построено для обеих и обе будут помечены как освещенные и отбрасывающие тень. Стоит поменять их местами – и мы сэкономим как на размере дерева, так и при последующей отрисовке. Однако в случае, если таких поверхностей немного (большая часть их добавляется в верном порядке), то особой проблемы не возникнет – ведь в любом случае при отрисовке задняя поверхность будет затенена объемом передней.
Гораздо более серьезная проблема кроется в том, что в дерево входят лишь плоскости, строящиеся из вытянутых граней кастеров. В этом случае ближняя поверхность может попасть в объем, созданный дальней, если находится перед ней – ведь плоскость самой поверхности в дереве не предусматривается. В этом случае ее надо предусмотреть – добавить новый узел с разделяющей плоскостью – плоскостью кастера – как первый дочерний узел последнего ребра (в функции добавления объема в SVBSP).

Как видите, Shadow Volume BSP – это совсем не сложный, но достаточно эффективный метод препроцессинга динамических источников света. Однозначный must have для всех 3D-движков, использующих технику теневых объемов.


Автор: XaeroX

Новости форума
Новые статьи
Вход в систему
Имя:
Пароль:
Помнить меня

[ вход ]
[ регистрация ]
[ забыли пароль? ]

Реклама
Текущие активные пользователи: 39
В данный момент на сайте 0 участников и 39 гостей.


Наш форум: В данный момент на форуме 124 посетителей.
Временная зона GMT. Текущее время 20:47.

На основе AcademCMS v1.3
Авторское право © 2001 - 2009, Chain Studios
Техническая площадка: HLFX.Ru