Введение в 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);
    }
  }
}

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

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

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

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

Порталы

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

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

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

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

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

Следуя советам Дана Ройера, при отладке рендерера и в первую очередь компилятора 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.

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

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

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