ПрограммированиеСтатьиОбщее

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

Автор:

Рендеринг leaf BSP + PVS

Как же теперь выглядит процесс рендеринга bsp-дерева? Очень просто. Как обычно, от корневого узла мы опускаемся вниз до самых листьев. Оказавшись в листе, мы последовательно анализируем его pvs-информацию и, если другой лист видим из того, в котором мы сейчас находимся, мы его отображаем. Имеет место быть цикл, в котором мы последовательно анализируем все листья относительно текущего найденного. К примеру, псевдокод рендеринга дерева в таком случае может выглядеть следующим образом:

void RenderTree(int thisLeaf)
{
  for (int i=0; i<NumberOfLeafs; i++)
  {
    If ( Leafs[ thisLeaf ].pvsdata[i] == true )
    {
      RenderLeaf(i);
    }
  }
}

На заметку:

Конечно же, лист виден сам из себя, именно поэтому в PVS информации примера, когда thisLeaf == i условие всегда должно быть истинным.

Отмечу, что для такого подхода к отображению Z-buffer НЕОБХОДИМ. Еще раз —  при таком подходе обход от корня дерева до листа проходит только ОДИН РАЗ за отображаемый кадр — до первого листа, в котором, по сути, мы находимся. То есть нам не нужно выполнять полный обход всего дерева, как ты уже понял из повествования. Теперь кратко рассмотрим еще несколько усовершенствований алгоритма отображения.

Отсечение по области просмотра (Frustum culling)

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

Я не буду рассматривать процесс отсечения по области просмотра и некоторые другие усовершенствования, которые были упомянуты выше или еще будут упоминаться по ходу статьи, поскольку это выходит за рамки темы статьи, а также потому, что в Интернете вполне достаточно информации по приведенным примерам.

На заметку:

Небольшое рассуждение на тему совершенствования алгоритма. Давай поразмыслим, если игровой мир имеет не такие уж и большие "размеры", стоит ли использовать, к примеру, отсечение по области просмотра? К чему я клоню? Сейчас современные видеокарты (даже не самые мощные их представители) способны отображать уровни Quake 2 с приемлемой частотой кадров даже "грубой" отрисовкой всех полигонов уровня. Стоит ли использовать тесты и расчеты, сопутствующие отсечению по области просмотра, если мы могли бы задействовать вычислительные мощи процессора под другие цели, например AI? Нет, я не убеждаю тебя в том, что это не нужно. Отнюдь. Я стараюсь склонить читателя к тому, что, прежде всего, он как разработчик должен будет сам определить для себя какие алгоритмы использовать, выяснить оптимальность их применения для текущей задачи, минимальные конфигурации аппаратного обеспечения, необходимые для запуска его детища.

Порталы

Порталы и деление игрового мира на «зоны» или «сектора» (area в контексте того же Quake) — еще один из способов повысить эффективность bsp дерева. Тем не менее, порталы и их применение вполне самостоятельно и не зависят от самого bsp дерева. Мы же рассмотрим их применение в PVS BSP рендере. Читателю в очередной раз придется напрячь воображение, и снова представить себе две комнаты, но уже объединенных не коридором, а дверью. Когда дверь открыта - из одной из комнат видно другую и наоборот. Это и лежит в основе применения порталов. Дверь будет представлять собой портал. Если портал «закрыт» независимо от того, валидна ли pvs-информация, мы не отображаем те листья, что находятся в другой «зоне-комнате».

Портал — это необязательно дверь. Это может быть невидимый полигон, расположенный на стыке двух игровых «зон» или «секторов» — комнат или целых территорий на уровне. В таком случае, порталы стоит связать с отсечением по области просмотра (frustum culling). Порталы — обширная тема, выходящая за рамки нашей статьи.

PVS и объекты в игровом мире

Дополнительным достоинством PVS можно назвать и то, что его можно использовать не только для определения потенциально видимых участков в мире. PVS информация может быть использована для ограничения воспроизводимых объектов в игре или передаваемых данных в сетевой игре с архитектурой клиент/сервер. Каким образом? Сервер, исходя из текущего положения клиента, достаточно легко может определить, виден ли потенциально какой-либо объект, будь то другой игрок,  NPC или предмет, так как любая из перечисленных сущностей так же находится в каком-нибудь листе дерева. Таким образом, большое количество информации при передаче данных от сервера к клиенту просто отсеивается.

На заметку:

В Quake 2 была также использована так называемая PHS информация — potentially hearable information. Это аналогичная по представлению с PVS информация использовалась для AI монстров в игре. При помощи нее игра определяла, из какой части уровня можно УСЛЫШАТЬ происходящее в соседних частях уровня.

Несколько советов по отладке

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

• Два полигона лежащих на одной плоскости.
• Два параллельных полигона направленных "друг к другу"
• Два параллельных полигона расположенных один за другим.
• Два пересекающихся полигона.
• Два полигона со смежной гранью, но не лежащие на одной плоскости.

Solid Leaf BSP Tree

В завершении теоретической части, рассмотрим так любимый Гарри Симмонсом Solid вариант дерева. В данном случае применительно к Leaf BSP.

И снова вернемся к рисунку 5. Предваряя какие либо объяснения, беря во внимание тот факт, что читатель стал уже стал достаточно опытен в вопросах связанных с BSP деревьями, рассмотрим пример Solid Leaf BSP дерева для рисунка 5:

Изображение

Сравни рисунок 8 с рисунком 7. Основное отличие Solid варианта от классического Leaf BSP связано с тем, что мы должны будем использовать для построения дерева плоскости ВСЕХ полигонов. Несмотря на то, что, к примеру, полигоны a, b, f, и e1 образуют выпуклый объем, мы продолжим использовать плоскости тех полигонов, что еще не занимали места сплиттера. Исходя из этого, мы конечно никогда не будем иметь так называемых back-листьев. Каждый из листьев, расположенных позади сплит плоскости одного из полигонов, представляет собой недоступное пространство, как и в случае Solid Node BSP.

Напоследок

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

BSP деревья — достаточно мощный и гибкий алгоритм и структура данных. Как и любые другие алгоритмы, он имеет свою область применения. Всегда помните об этом. Для тех, кому изложенной в статье информации показалось мало, рекомендую, прежде всего, изучить труд "An investigation into real-time 3d polygon rendering using bsp tree" [2]. К сожалению, практически все источники, использованные при написании этой статьи, это архивы документации, собранные мною за период занятий 3д графикой, а потому ссылки на них не сохранились. Читателю придется искать их самому, но, я думаю, при определенном навыке пользования поисковыми машинами в Интернет это не будет большой проблемой.

Теоретическая первая часть закончена. Во второй части статьи, мы рассмотрим создание простейших программ рендеринга игровых уровней  для таких игр как Quake, Quake2 и Quake3, изучим эволюцию структуры используемого в них BSP дерева.

Искренне Ваш, jm.

Использованные материалы

1. Creating a solid node based bsp tree compiler & renderer. / Gary Simmons /
2. An investigation into real-time 3d polygon rendering using bsp tree. / Andrew Steven Winter /
3. Creating a solid leaf tree, portal generation, precalculating pvs and adding frustum rejection. / Gary Simmons /
4. Dan's programming tutorial / Dan Royer /
5. Tom Hammersley's Graphics Coding Webpage
6. BSP Tree Frequently Asked Questions (FAQ) / http://www.gamedev.net /
7. Rambling in realtime: Chapter 6: Quake's 3D engine — the big picture. / Michael Abrash /
8. Исходные тексты Quake и Quake 2 / http://www.idsoftware.com /

Благодарности

Qiller — за вагон знаний, тележку ссылок и ответы на все вопросы :)
Sark7 — за компанию и эпиграф :)
Ивану Дышленко за компанию и образовательное общение, а также за экземпляр его будущей книги, который, я надеюсь, получу с автографом автора.
InQ — за помощь в редактировании статьи.
Всем тем, с кем имею честь общаться на IRC и на форуме GameDev.ru.

Страницы: 1 2 3 4 5

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

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

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