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

Немного математики BSP компилятора.

В этом абзаце мы кратко рассмотрим основные функции, которые могут понадобиться при создании BSP компилятора. Прежде всего, нам понадобится функция классифицирующая положение точки в пространстве относительно плоскости. Как многие помнят, плоскость может быть задана уравнением Ax+By+Cz+D = 0, где A, B, C — координаты нормали к плоскости, а D — расстояние до начала координат. Как же нам поступить, спросит читатель — ведь у нас нет плоскости! У нас есть полигоны. В самом простом и логичном случае это треугольники. Желательно просчитать плоскости для всех полигонов заранее, а не делать это во время работы рендеринга или BSP компилятора.

Итак, нормаль плоскости, на которой лежит треугольник, будет совпадать с нормалью самого треугольника. Для того чтобы найти нормаль треугольника заданного тремя точками (против часовой стрелки) нужно найти два ребра этого треугольника, а затем векторно их перемножить и нормализовать результат. Функция расчета нормали будет иметь приблизительно такой вид:

void getNormal(float *n,float *v1,float *v2,float v3)
{
  float edge1[3],edge2[3];
  int j;

  for (j=0;j<3;j++)  
  {  
    edge1[j] = v1[j] - v2[j];
    edge2[j] = v3[j] - v2[j];
  }

  cp(n,edge1,edge2);
  norm(n);
  return;
}

Функция cp() вычисляет векторное произведение векторов, а norm() - нормализует вектор. Формулы, которые, я надеюсь, ты знаешь:

void cp(float *v,float *v1,float *v2)
{
  v[0] = v1[1]*v2[2] - v2[1]*v1[2];
  v[1] = v1[2]*v2[0] - v2[2]*v1[0];
  v[2] = v1[0]*v2[1] - v2[0]*v1[1];
  return;
}

void norm(float *v)
{
  float c;

  c = 1/sqrt(v[0]*v[0]+v[1]*v[1]+v[2]*v[2]);

  v[0] *= c; 
  v[1] *= c;
  v[2] *= c;
  return;
}

Перенесем D компонету уравнения плоскости в его правую часть:

Ax + By + Cz = –D

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

#define EPSILON   0.0001

#define ONPLANE  0
#define FRONT    1
#define BACK    2

int ClassifyPoint(float *p,float *v1,float *v2,float *v3)
{
  float result;
  float n[3],dir[3];

  for (int j=0;j<3;j++)  
  {
    dir[j] = v1[j] - p[j];
  }

  getNormal(n,v1,v2,v3);

  result = dp(dir,n);

  if (result < -EPSILON) return FRONT;
  if (result > EPSILON) return BACK;
  return ONPLANE;
}

где dp() - это скалярное произведение векторов, формулу которого я приводить не буду просто из уважения к читателю.

Поскольку вычисления и представление чисел с использованием чисел с плавающей точкой одинарной точности зачастую дают погрешности, в сравнении вместо использования 0.0 лучше использовать некоторую константу EPSILON.

Псевдокод BSP компилятора.

Не мудрствуя лукаво я приведу в пример С++ псевдокод из BSP FAQ:

void Build_BSP_Tree (BSP_tree *tree, list polygons)
{
  polygon   *root = polygons.Get_From_List ();

  tree->partition = root->Get_Plane ();

  tree->polygons.Add_To_List (root);

  list      front_list,back_list;

  polygon   *poly;

  while ((poly = polygons.Get_From_List ()) != 0)
  {
    int   result = tree->partition.Classify_Polygon (poly);

    switch (result)
    {
    case COINCIDENT:
      tree->polygons.Add_To_List (poly);
      break;
    case IN_BACK_OF:
      backlist.Add_To_List (poly);
      break;
    case IN_FRONT_OF:
      frontlist.Add_To_List (poly);
      break;
    case SPANNING:
      polygon   *front_piece, *back_piece;
      Split_Polygon (poly, tree->partition, front_piece, back_piece);
      backlist.Add_To_List (back_piece);
      frontlist.Add_To_List (front_piece);
      break;
    }
  }

  if ( ! front_list.Is_Empty_List ())
  {
    tree->front = new BSP_tree;
    Build_BSP_Tree (tree->front, front_list);
  }
  
  if ( ! back_list.Is_Empty_List ())
  {
    tree->back = new BSP_tree;
    Build_BSP_Tree (tree->back, back_list);
  }
}

По сути, весь процесс, выполненный нами в диалоге, формализован и описан кодом программы. Рассмотрим те функции, которые могут вызвать вопросы читателя.

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

Вызов tree->polygons.Add_To_List (root); заносит выбранный полигон в узел дерева, а затем с той же целью используется в случае, если тестируемый полигон лежит на одной плоскости со сплиттером.

Наибольший интерес, наверное, будет представлять функция Classify_Polygon(). Она определяет, расположен ли полигон перед плоскостью сплиттера (IN_FRONT_OF), позади нее (IN_BACK_OF), на ней (COINCIDIENT) или же разделяется ею (SPANNING). Как будет выглядеть такая функция? Давай немного подумаем. Полигон задается точками в пространстве. В данном случае полигон — многоугольник, все точки которого лежат в одной плоскости. Функцию ClassifyPoint(), определяющую положение точки относительно плоскости, мы уже описали выше. Теперь, мы воспользуемся ею внутри Classify_Polygon(). Для каждой точки полигона мы определим ее положение относительно плоскости сплиттера. А теперь подсчитаем количество точек, расположенных перед, позади и на плоскости. Как читатель уже понял, если ВСЕ точки полигона лежат перед плоскостью и на ней, наша Classify_Polygon() вернет IN_FRONT_OF; если позади нее (и на ней) — IN_BACK_OF; а если на плоскости — COINCIDIENT. Случай, когда Classify_Polygon() вернет SPANNING, может возникнуть, если часть точек полигона лежат перед и позади плоскости сплиттера. В этом случае полигон нужно "распилить", чем и займется функция Split_Polygon(). Реализация этой функции будет домашним заданием читателю.

Если сформированные в процессе классификации списки полигонов front_list и back_list не пусты, мы рекурсивно вызываем Build_BSP_Tree уже для этих "новоиспеченных" списков.

Leaf BSP Tree

Наиболее распространенная вариация BSP в наше время — leaf bsp tree. Она имеет ряд кардинальных отличий, как в используемой структуре данных, так и в алгоритме построения и рендеринга BSP дерева. Именно leaf BSP tree с некоторыми усовершенствованиями использовано в играх Quake 1-3, примеры рендеринга игровых уровней которых мы рассмотрим во второй части статьи.

Попробуем кратко изучить основные различия node и leaf bsp деревьев:

• узлы в leaf based bsp теперь не несут информации о геометрии уровня. Вся геометрия хранится в листьях дерева. Отсюда и название leaf bsp.
• при построении дерева и выборе плоскости сплиттера мы не сохраняем полигон-сплиттер, лишь его плоскость. Сам сплиттер остается в одном из двух списков входных полигонов, а именно — в списке полигонов расположенных ПЕРЕД плоскостью сплиттера. Однако, его плоскость уже не может использоваться для разбиения пространства — он "помечается" как "уже использованный" в роли сплиттера.
• если полигон, который уже был сплиттером, (его плоскость использовалась для "рассечения" пространства) будет рассечен другой сплиттер-плоскостью на два полигона, каждый из них наследует историю предка — они уже не могут выступать в роли сплиттеров в будущем.
• после каждой итерации разделения пространства и формирования списков входных полигонов, если все полигоны во входном списке расположены друг перед другом, они формируют выпуклый объем и не пересекаются. В этом случае, все полигоны списка заносятся в лист дерева, и использование этого списка в качестве входного параметра прекращается.

Рассмотрим простой пример. Для этого нам нужно вернутся к рисунку 5. Теперь давай посмотрим на то, как будет выглядеть Leaf BSP дерево для этого случая:

Почему так? В качестве сплиттера нами была выбрана плоскость полигона b. В результате, мы как всегда получаем два новых списка. Отмечу, что полигон b был помещен в список входных параметров, расположенных перед сплиттером, а не помещен в узел, как это было в случае Solid варианта. Как уже было сказано ранее, в узел попадает только плоскость полигона-сплиттера. После первого же разбиения в каждом из списков все полигоны расположены друг перед другом, а значит, они образовывают выпуклый объем. Соответственно представляют собой листья нашего дерева. Сравните полученное дерево с рисунком 6, на котором изображено Solid Node BSP. Классическое Node BSP дерево, как ты понимаешь, не намного бы отличалось от Solid варианта.

Без использования каких либо усовершенствований, рендеринг Leaf BSP дерева ничем не отличается от рендеринга Node BSP. Тем не менее, процесс обхода всего дерева будет происходить гораздо быстрее, т.к. Leaf BSP содержит гораздо меньше узлов, чем его прародитель. Все так же, во время процедуры рендеринга нам не будет нужен Z-Buffer. У читателя может возникнуть вопрос, почему так, ведь в листьях порядок отображения полигонов не задан? А он нам и не нужен. Поскольку все полигоны в листьях не пересекаются и расположены один перед другим, при включении Back Face Culling'а (будь то OpenGL или Direct3D), независимо от порядка отображения полигонов мы будем иметь верный результат.

Глубина leaf bsp дерева, конечно же, гораздо меньше глубины node bsp. Как следствие — дерево можно обойти гораздо быстрее. Однако, мы не будем использовать классический подход для отображения мира при помощи обхода всего дерева. Почему? Дело в том, что Leaf BSP не решат одной сложной проблемы, а именно зависимости времени, затрачиваемого на рендеринг от размеров уровня. С увеличением полигонов, в нашем мире будет расти время на обход дерева и отображение всех его полигонов. К примеру, в Solid варианте BSP дерева мы использовали Node culling, для неполного снятия этой зависимости, но тут мы пойдем совершенно иным путем. Следует рассмотреть несколько усовершенствований классического варианта алгоритма.

PVS

PVS — это potentially visible set. Это, грубо говоря, массив, содержащий для каждого листа дерева информацию о том, видим ли потенциально любой другой лист из данного листа. Это может показаться слишком запутано. Как обычно обратимся к простому примеру. Предположим, что две комнаты - А и B типичного игрового уровня объединены поворачивающим коридором C таким образом, что из комнаты A не видно комнату B, а из комнаты B, соответственно, не видно комнату A. Но из каждой комнаты можно увидеть коридор. Предположим, что A, B и С — это листья нашего bsp дерева. В памяти они расположены в виде массива с индексами 0 — A, 1 — B, 2 — C. Потенциально, находясь в комнате A, мы можем видеть лишь A и C. Точно так же можно сказать, что, находясь в B, мы можем видеть лишь B и C. Из C потенциально мы можем видеть любой из листьев. Таким образом, опишем PVS массив для каждого из трех листьев:


       A B C

A PVS: 1 0 1

B PVS: 0 1 1

C PVS: 1 1 1

На заметку:
Всегда не следует забывать, что PVS не берет в расчет ориентацию камеры и не «отбрасывает» части игрового мира, не попадающие в область просмотра камеры.

Да, по сути, это просто логические флажки. Если для хранения PVS флага использовать один байт, то в нашем случае на сохранение pvs массива уйдет 9 байт. А теперь представь, что листьев не три а 10000. 10000*10000 = 100 000 000 - около 100 Mбайт информации! Так дело не пойдет, конечно же. Выходов из сложивщейся ситуации несколько. К примеру, велика вероятность того, что pvs информация может совпадать для разных листьев. Таким образом, нам не нужно сохранять несколько одинаковых последовательностей байт. Массив Pvs информации называют массивом кластеров, и из него исключаются повторяющиеся элементы. Соответственно, каждый лист дерева будет содержать индекс в массив кластеров. Однако это не сможет решить проблему целиком. Объем pvs информации все равно останется достаточно велик. В качестве следующего усовершенствования можно использовать бит вектор, вместо байта на один флаг. Объем используемого пространства сократится в 8 раз. Для тех, кому в наше время этого мало, могут использовать компрессию.

Zero Run Lenght Encoding

Zero RLE модификация RLE алгоритмов известных достаточно давно (к примеру, PCX файлы используют именно RLE компрессию). Алгоритм ZRLE достаточно прост и может быть легко реализуем даже в реальном времени без ущерба производительности. Рассмотрим пример компрессии некой последовательности битовой информации:

12, 0, 23, 2, 243, 0, 15

В этой строчке, состоящей из 7 байт, закодирован 41 байт pvs-информации. Учитывая, что в одном байте у нас содержится информация для восьми листев, мы получаем достаточно экономичное представление. Каким образом? Нет — это не сверхэффективный метод компрессии. Он просто берет во внимание тот факт, что в потоке pvs-информации очень много нулей. Поскольку для достаточно больших игровых уровней из некоторого листа зачастую видна ограниченная часть листьев, составляющая несколько процентов от общего их числа, pvs информация перегружена нулевыми значениями. Обрати внимание на закодированную строку. Сейчас мы рассмотрим процесс декомпрессии, исходя из которого, читатель легко сможет представить для себя обратный процесс упаковки. Если значение не равно нулю — мы пишем его в поток без изменений. Если значение равно нулю, то следующий байт задает количество нулевых байт в потоке. Таким образом, приведенная выше строка не что иное как:

12, двадцать три нуля, 2, 243, пятнадцать нулей.

Страницы: 1 2 3 4 5 Следующая »

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

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

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