Обзор

Книга скомпелирована в chm для сайта gamedev.clan.su

Учись создовать игры с нами!

Двоичное разбиение пространства

Двоичное разбиение пространства (англ. binary space partitioning) — метод рекурсивного разбиения евклидова пространства в выпуклые множества и гиперплоскости. В результате объекты получают представление в виде структуры данных, называемой BSP-деревом.

BSP-дерево используется для эффективного выполнения следующих операций в трёхмерной компьютерной графике:

  • Сортировка визуальных объектов в порядке удаления от наблюдателя;
  • Обнаружение столкновений.

BSP-деревья были впервые применены специалистами компании Lucas Arts в начале 80-х годов. Популярность у разработчиков они завоевали благодаря компании id Software, разработавшей движки Doom (1993) и Quake (1996).

Обзор

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

  1. Скалярное произведение больше 0 — точка лежит с фронтальной стороны плоскости;
  2. Скалярное произведение равно 0 — точка лежит на плоскости;
  3. Скалярное произведение меньше 0 — точка лежит с обратной стороны плоскости.

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

Построение дерева

Пример построения
1. A — корень и набор отрезков на плоскости целиком.
2. A делится на B и C.
3. B делится на D и E.
4. D делится на полностью выпуклые F и G, которые и становятся листьями дерева.

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

  1. Если заданное множество полигонов пустое, то закончить алгоритм;
  2. Для заданного множества полигонов выбрать разбивающую плоскость S;
  3. Рассечь все полигоны, пересекающиеся с S;
  4. Отнести все полигоны, находящиеся с фронтальной стороны S, к фронтальному поддереву F, а все полигоны, находящиеся с обратной стороны S, к оборотному поддереву B;
  5. Выполнить алгоритм рекурсивно для множества полигонов фронтального поддерева F;
  6. Выполнить алгоритм рекурсивно для множества полигонов оборотного поддерева B.

Выбор разбивающей плоскости

Разбивающая плоскость выбирается таким образом, чтобы сбалансировать дерево, то есть чтобы число полигонов во фронтальном и оборотном поддереве было приблизительно одинаково:

min(|N(Fi) — N(Bi)|)

где N(Fi) — число полигонов с фронтальной стороны некоторой разбивающей плоскости i, N(Bi) — число полигонов с оборотной стороны разбивающей плоскости i.

Сортировка объектов в порядке удаления от наблюдателя

При сортировке объектов в порядке удаления от наблюдателя с помощью BSP-дерева исследуются взаимное расположение вектора и точки наблюдения (POV) и нормалей разбивающих плоскостей. Если нормаль разбивающей плоскости и вектор наблюдения сонаправлены, то фронтальное поддерево находится от наблюдателя дальше, чем оборотное, в противном случае оборотное поддерево находится от наблюдателя дальше, чем фронтальное. При этом, если разбивающая плоскость находится сзади наблюдателя, то сама плоскость, а также фронтальное или оборотное поддерево может быть не видны полностью. Рекурсивный алгоритм сортировки полигонов с помощью BSP-дерева следующий:

Процедура ОбойтиУзел(Узел)
  Если Узел <> ПустойУказатель
    Если ВекторыСонаправлены(ВекторНаблюдения, Узел.НормальРазбивающейПлоскости)
      Если СкалярноеПроизведение(ТочкаНаблюдения, Узел.НормальРазбивающейПлоскости) >= 0
        // Плоскость находится сзади наблюдателя, наблюдатель видит только фронтальное поддерево
        ОбойтиУзел(Узел.ФронтальноеПоддерево);
      Иначе
        // Плоскость находится спереди наблюдателя,
        // фронтальное поддерево находится дальше оборотного
        ОбойтиУзел(Узел.ФронтальноеПоддерево);
        ДобавитьПолигонВСписокОтображения(Узел.Полигон);
        ОбойтиУзел(Узел.ОборотноеПоддерево);
      КонецЕсли;
    Иначе
      Если СкалярноеПроизведение(ТочкаНаблюдения, Узел.НормальРазбивающейПлоскости) >= 0
        // Плоскость находится спереди наблюдателя,
        // оборотное поддерево находится дальше фронтального
        ОбойтиУзел(Узел.ОборотноеПоддерево);
        ДобавитьПолигонВСписокОтображения(Узел.Полигон);
        ОбойтиУзел(Узел.ФронтальноеПоддерево);
      Иначе
        // Плоскость находится сзади наблюдателя, наблюдатель видит только оборотное поддерево
        ОбойтиУзел(Узел.ОборотноеПоддерево);
      КонецЕсли;
    КонецЕсли;
  КонецЕсли;
Конец;

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

Алгоритм для ускорения из рекурсивного может быть преобразован в итеративный.

Отсечение невидимых поверхностей

Отсечение невидимых поверхностей реализуется путём введения дополнительной информации в BSP-дерево, такой как рамки (bounding boxes, bounding spheres). Рамки — это прямоугольники или параллелепипеды, окружности или сферы, которые ограничивают область расположения полигонов некоторого поддерева. Таким образом, каждый узел имеет две рамки. Поддерево гарантированно невидимо, если зрительная пирамида не пересекается с ограничивающим объектом. Обратное неверно. Однако прямого утверждения достаточно, чтобы отсечь обработку существенного количества объектов.

Выбор геометрических объектов, которыми представлены рамки, исходит из простоты алгоритма проверки пересечения зрительной пирамиды с рамкой.

Поиск столкновений

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

Пример:

Процедура ПоискСтолкновения(Узел, Объект)
  Если Узел <> ПустойУказатель
    Если Расстояние(Узел.Плоскость, Объект.ЦентрОграничивающейСферы) > Объект.РадиусОграничивающейСферы
      Если СкалярноеПроизведение(Объект.ЦентрОграничивающейСферы, Узел.НормальРазбивающейПлоскости) >= 0
        // Объект находится с фронтальной стороны разбивающей плоскости,
        // обходим только фронтальное поддерево
        ПоискСтолкновения(Узел.ФронтальноеПоддерево, Объект);
      Иначе
        // Объект находится с обратной стороны разбивающей плоскости,
        // обходим только оборотное поддерево
        ПоискСтолкновения(Узел.ОборотноеПоддерево, Объект);
      КонецЕсли;
    Иначе
      Вернуть ЕстьСтолкновение;
    КонецЕсли;
  Иначе
    Вернуть НетСтолкновения;
  КонецЕсли;
Конец;

Алгорим для ускорения из рекурсивного может быть преобразован в итеративный.

Copyright © 2018. All rights reserved. (To change the copyright info, just edit it in template.)


Обзор

Help > Введение в BSP деревья или BSP для самых «маленьких». Часть первая, теоретическая. >
Обзор

Планируемая структура статьи

В этой статье мы рассмотрим тот самый алгоритм, который для многих уже стал притчей во языцех — BSP (Binary Space Partitioning). Вопрос по структуре статьи, количеству ее частей и примеров к ней остается открытым. В данном случае решающим фактором будет являться мое свободное время. Только оно в конечном итоге определит, будет ли у статьи несколько частей, будут ли рассмотрены такие интересные вопросы, как использование BSP деревьев для контроля столкновений, полная процедура рендеринга игрового мира в играх уровня Quake III, создание BSP компилятора и много других интересных моментов достойных нашего с вами внимания. Пока что, планируется две части.

На заметку:

Надо честно признать, что, находясь за полярным кругом, в командировке в поселке со звучным названием поселок городского типа Мыс Шмидта, меня, как автора статьи, больше волнует наличие теплых носков у меня в дорожной сумке и отсутствие холодной воды в номере гостиницы, нежели количество этих самых интересных моментов при рассмотрении BSP деревьев. :) Хотя, ничего другого не остается, как продолжать с лозунгом «ноутбук тоже калорифер». :)

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

Прежде всего отмечу, часть информации (скажем, касающаяся использования в рендере Node based BSP), описанная в этой статье, по сути уже устарела. Время не стоит на месте. Новые вычислительные мощности изменяют первоначальные алгоритмы. Но не рассмотреть базовые аспекты было бы просто преступно.

На заметку:

Не стоит бояться «новых» терминов. Все непонятное, что будет встречаться в начале статьи, будет подробно раскрыто далее по тексту. Тебе, читатель, стоит лишь запомнить термин и ждать дальнейших пояснений. Возможно, нелишним будет прочитать статью несколько раз.

Кстати, сейчас, в результате «метаморфоз» алгоритма, само по себе BSP дерево играет гораздо меньшую роль в процедуре рендеринга, чем это было раньше.

Статья будет представлять из себя достаточно подробный обзор самого алгоритма и его основных вариаций. После текстового введения, во второй части статьи мы на примерах рассмотрим создание ПРОСТЕЙШИХ программ рендеринга BSP уровней Quake I, II и III, параллельно отслеживая развитие одного из наиболее популярных «движков» нашего времени. Сами примеры написаны с использованием С++ и OpenGL, но рендеринг может быть легко портирован, скажем, под Direct3D. Как я уже упомянул выше, вопрос о дальнейших продолжениях остается открытым.

На заметку:

В свое время Джон Кармак в своих проектах предпочитал Си. Его аргументацией были, приблизительно, «code effeciency and speed». Однако некоторые источники в Интернет анализировавшие код украденной альфа версии Дум 3 предполагают, что при ее написании было использовано объектно-ориентированное программирование и Си++. Надеюсь, эта заметка не породит очередную волну войн сторонников классического С и его ++ собрата :)

Статья описывает только BSP. Никаких сравнительных характеристик с 4-арными (quadtree) или 8-арными деревьями (octree) (все это k-D tree) приведено не будет. Это выходит за рамки рассмотрения проблемы.

Для «злословов» — я никоим образом не присваиваю себе авторство решений и конечных выводов. Вся информация, собранная в этой статье — это, по сути, формализация всех моих знаний полученных из различных статей и источников в Интернет и исходных текстов программ — своеобразная "летопись времен", и, прежде чем начать, я хотел бы выразить огромную благодарность всем авторам этих разношерстных источников информации. Все они будут упомянуты в списке литературы статьи. Кроме того, возможно опытные читатели обнаружат ошибки или недочеты в самой статье. Исправления только приветствуются.

Базовые знания

Для полного понимания информации, изложенной в этой статье, тебе, читатель, просто необходимо иметь базовые знания в векторной геометрии и понимание базовых формул, таких как скалярное произведение векторов (dot product), векторное произведение векторов (cross product), уравнение плоскости, а также понимание структур данных типа дерево, связный список и принципов их построения. Все примеры исходных текстов представляют собой С/C++ подобный псевдокод или же функции на языке С/С++. Примеры программ написаны с использованием С++. Кроме того, читателя не должен вводить в ступор термин рекурсии.

Фольклор программиста:

«Чтобы понять рекурсию, нужно сначала понять рекурсию... »; «Рекурсия — удел Богов, человеку свойственны итерации»

DISCLAIMER или «я не я и корова не моя»

В примерах отсутствует оптимизация, она не ставилась во главу угла при написании этой статьи. В угоду читабельности и наилучшего понимания проблемы стоит принести в жертву производительность и чистоту. Также, не смотря на всю простоту изложения, к которой я стремлюсь и которую, надеюсь, достиг, эта статья не пошаговое руководство, а лишь изложение базовых идей и принципов. Читатель не найдет в ней полных исходных текстов реализации того же bsp компилятора. Кроме того, я не ас в С++ программировании и предпочитаю классический С. Именно поэтому моя попытка написания ++ примеров ко второй части статьи может выглядеть смешно. Просто прошу обойтись без гнилых помидоров и тухлых яиц, а если невтерпеж, присылайте их лучше бандерольками.

BSP как оно есть

Binary Space Partitioning представляет собой рекурсивное иерархическое разбиение в n-мерном пространстве. Построение дерева — процесс, использующий гиперплоскость для разбиения пространства. Под гиперплоскостью в n-мерном пространстве подразумевается (n-1)-мерный объект, который позволяет разделить пространство на две части. Например, в 3-мерном пространстве гиперплоскость это просто плоскость, а в двумерном — линия.

Пугаться еще рано :) Дальше все будет гораздо проще и в то же время сложнее. BSP дерево строится заранее. Этим занимается набор из одной или нескольких утилит, которые в общем можно назвать BSP компилятором.

На заметку:

В Quake-движках для создания BSP дерева из входного набора полигонов используется одна утилита - qbsp. Остальные утилиты выполняют другие цели, к примеру, генерируют лайтмапы для уровня.

Поскольку BSP дерево строится заранее, одним из его недостатков является невозможность модификации его в реальном времени в процессе исполнения программы. Возможно, читатель после прочтения статьи сможет частично решить эту проблему? :) Насколько я знаю, такие примеры есть.

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

Doom и игры на его базе (Doom2,Heretic,Hexen);
Очевидно, Unreal и игры на его базе;
Quake 1,2 и 3, а также игры на их базе (или движке, кому так более привычно);
Hexen 2, Half Life 1-2 (наследие Quake 1 engine);
Sin, KingPin (все тот же Quake 2 engine как он есть);
Jedi Knight II: JediOutcast, Medal of Honor, Star Trek (достойные продолжатели Quake 3 engine);
Shogo:Mobile Armor Division, Blood 2,Aliens vs Predator 1-2,DieHard Nakatomi Plaza,NOLF2 (все это LithTech 1-2);
очевидно Doom3.
...и многие другие...

Краткий экскурс в историю

Многие воспринимают имя Джона Кармака и BSP алгоритмы как слова синонимы. :) Это не так. :) Нет, я нисколько не умаляю вклада и таланта этого человека в индустрию создания компьютерных игр.

На заметку:

Вероятно, именно Джоном Кармаком была первым озвучена и воплощена на практике идея компрессии PVS данных, а также использование бит-векторов для их представления. О PVS информации и ее использовании совместно с BSP деревьями мы поговорим немного позже.

Обратим взоры в недалекое прошлое. Как ни странно, основы BSP алгоритма были заложены в далеком для нас 1969. Мы не будем сейчас углубляться в седую старину. Скажу лишь, что в 1980-83 годах Funch et al (и другие) освежили идеи, заложенные в 1969 году, и формализовали процесс известный сейчас как Binary Space --*Partitioning Tree. В 1990 году Teller и Sequin предложили процесс генерации PVS (Potentially visible set) для ускорения определения видимости в ортогональной 2д среде, а в 1992 году Teller описал генерацию PVS информации для полигонального 3д окружения. В 1991 году Gordon и Chen описали эффективный метод рендеринга BSP дерева от первых к последним (front-to-back), отличный от используемого тогда при рендеринге BSP от последних к первым (back-to-front). Время переходить к практике?

На заметку:

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

10 декабря 1993 года, выпуск Doom. Shareware версия Doom в обеденные перерывы приковывает к себе тысячи человек. Очевидно многие рестораны быстрого питания несут огромные убытки (Или наоборот, прибыль ?) :)

10 октября 1994 года выпуск Doom II. Тот же движок, все то же т.н. 2,5D, по сути, аддон к базовой версии. Сетевые баталии в самом разгаре.

1996 год — выход Quake. Майк Абраш пока что с id. «Серая» на вид, но атмосферная, с честным 3D игра завоевывает миллионы поклонников по всему миру. Полигональные монстры. Открытая архитектура, встроенный язык QuakeC (С которым успел побаловаться и Ваш покорный слуга) дает простор для создания модов и полных переделок игры. На базе Quake созданы "мариообразные" платформеры, гонки, шахматы, футбол и даже аркадный авиасимулятор, не говоря уже о десятках изменений к основным правилам игры: CTF, Team Fortress, Head Hunters и многие-многие другие.

Декабрь 1997 года — выход Quake 2. Разделение лагеря поклонников - Q1 vs. Q2. Разительное отличие аппаратной и неакселерированной версий «Ку2». Да, конечно, немного раньше были созданы OpenGL версии «Ку1». Уже устоявшаяся дружба с 3dfx. Среди неосведомленных потребителей имя 3dfx становиться нарицательным для всех графических акселераторов. Несмотря на всю, казалось бы, продвинутость Quake2, внутренние архитектурные различия с Quake1 минимальны... QuakeC больше нет. Взамен виртуальной машины, мы пишем моды на Си, компилируем Си компилятором в динамическую библиотеку операционной системы.

2 декабря 1999 года — Quake 3. Ставка только на аппаратное ускорение. Кармак патриарх OpenGL в среде Windows. Активное использование Безье патчей (кривые или подмножество NURBS если хотите). Снова возврат к виртуальной машине, использование QASM, но в то же время, по всей видимости, поддержка и динамических библиотек операционной системы (по крайней мере, в ранних тестовых версиях).

Я намеренно опустил все id игры до выхода Doom. Ни одна из них, очевидно, не использовала BSP-алгоритмы. Wolf3d? Wolf3d — ray casting (не путать с ray tracing)...

Node BSP Tree

Прежде всего, стоит отметить какие проблемы решает Node based bsp дерево. Некоторые из проблем в наше время, возможно, покажутся не столь актуальными, тем не менее, это основы которые нельзя пропускать:

•Отображение полигонов (в том числе перекрывающихся) в правильном порядке, скажем от дальних к ближним, что автоматически решает проблему с отображением прозрачных и полупрозрачных полигонов. Как уже знает читатель, для правильного отображения прозрачные и полупрозрачные объекты должны отображаться после объектов, которые они перекрывают.
•Нам не нужен для этого Z-buffer.
•Небольшая модификация представления данных в алгоритме и мы имеем практически бесплатный контроль столкновений.

На заметку:

Еще раз замечу - сказанное выше относительно Z-buffer'а справедливо именно в случае классического Node based bsp!


1.Строим дерево на примерах

1.Строим дерево на примерах

Строим дерево на примерах

Так как проще всего информация воспринимается именно на примерах, рассмотрим простейший пример создания такого дерева. Поскольку генерация BSP дерева в двумерном пространстве ничем не отличается от генерации BSP дерева в трехмерном, в примерах мы рассмотрим именно «двумерный случай», хотя терминология будет соответствовать трем измерениям.

На рисунке 1 представлен «типичный игровой» уровень. Вид сверху. Красная точка — положение игрока или камеры в сцене. В данном случае нам не важна его ориентация (направление «взгляда камеры»). Синим обозначены стены и направление их нормалей. В нашем «двумерном» мире нас не интересует высота этих стен просто потому, что у нас нет высоты :) Начнем...

В основе построения BSP дерева лежит разбиение пространства плоскостью, на которой расположен тот или иной полигон. Опять же, для простоты примем еще одно допущение - каждая из наших "стен" на рисунке 1 представляет собой единый полигон. В качестве первого разделителя возьмем полигон b. Перед плоскостью, на которой лежит наш новоиспеченный сплиттер (далее по тексту я буду звать "разделяющий" полигон или кандидата в таковой именно так), находятся полигоны d и e. Полигон a располагается позади. Полигон c рассекается сплиттером.

На заметку:

Рассечение плоскостью сплиттера достаточно важный момент, позволяющий решить проблему, которая может возникать в простейших алгоритмах сортировки полигонов по глубине, например, в алгоритме художника. Алгоритм художника — простейший алгоритм, сортирующий полигоны в сцене по их удаленности. Однако, ситуация с двумя перекрывающимися полигонами, изображенная на рисунке 2, не может быть корректно решена этим алгоритмом.

Проблему с перекрывающимися полигонами ранее могли наблюдать любители авиа симуляторов уважаемой мною фирмы Digital Integration (Tornado, Ah-64 Apache, Mi-24 Hind и другие). В играх с программным рендерингом, например Hind, включив внешний вид на вертолет и немного повертев камеру, игрок мог порой наблюдать "наезд" шасси и некоторых других деталей вертолета на каркас даже тогда, когда эти детали, казалось бы, должны находиться позади каркаса.

Рассмотрим рисунок 3:

В результате первого разбиения пространства полигон c был рассечен плоскостью нашего сплиттера на два: c1 и c2. Оба полученных полигона унаследовали от предка направление. После первого рассечения пространства мы имеем два списка полигонов:
•расположенные перед плоскостью сплиттера: c2, d и e
•расположенные позади плоскости сплиттера: a и c1

Что же теперь? Как уже отметил для себя читатель, в качестве входных параметров для построения дерева служат полигоны (списки полигонов). После первого разбиения мы "убираем" полигон b из кандидатов для последующего разделения (удаляем полигон из входных параметров) пространства и заносим его в "узел" дерева. У тебя ведь есть представление о такой структуре данных как дерево? Если нет, попробуй забежать немного вперед и рассмотри рисунок 4. Надеюсь, мои рассуждения уже натолкнули тебя, читатель, на последующие действия, а именно: мы продолжаем разбивать пространство плоскостью полигона, выполнять все те действия, что мы выполнили до этого до тех пор, пока во входных параметрах у нас не останется полигонов. Но тут есть одно НО — после первого разбиения мы имеем уже целых два списка входных параметров. Ты наверняка уже догадался. Да, именно! Это те самые две группы полигонов, расположенные перед плоскостью сплиттера и позади него. Начнем с первой группы, в которую входят c2, d и e. В качестве претендента-сплиттера на дальнейший процесс разбиения я выбираю полигон c2 (Конечно же, кандидат в сплиттеры выбирается из самого списка).

На заметку:

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

После второго разбиения пространства мы имеем следующую картину:
•расположенные перед плоскостью сплиттера: d
•расположенные позади плоскости сплиттера: e

Третье разбиение пространства мы выполним для входных параметров a и c1. Это второй набор полигонов, который возник у нас при первом разбиении пространства полигоном b. В качестве сплиттера я выберу a:
•расположенные перед плоскостью сплиттера: c1
•расположенные позади плоскости сплиттера: отсутствуют

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

По правую сторону от узлов на рисунке изображены дочерние сплиттеры, расположенные перед сплиттером-предком, по левую — позади него. В корневом узле располагается полигон b. Уфф! Мы это сделали! По сути, мы выполнили работу BSP компилятора, создающего bsp дерево из набора полигонов. Именно в его задачи входит построение дерева в пространстве, решение "конфликтных" ситуаций с перекрывающимися полигонами, полигонами, лежащими на одной плоскости, выбор оптимальной сплиттер-плоскости.

На заметку:

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

Оптимальный сплиттер и сбалансированное дерево

Выбор оптимального сплиттера — достаточно сложный вопрос. С одной стороны, в угоду процедуре рендеринга мы должны минимизировать количество «распиливания» полигонов плоскостью выбранного сплиттера, поскольку это увеличивает число полигонов в сцене, и соответственно полигонов, которые затем нужно отобразить. Во многих источниках именно минимизация количества полигонов и снижение количества узлов ставится во главу угла создания оптимального BSP дерева. В то же время возникает необходимость построения сбалансированного дерева. Под сбалансированным деревом подразумевается дерево, по возможности, с равным количеством узлов по обе стороны от корневого узла. Кроме того, это же правило справедливо и для узлов-потомков, т.к. они также являются корневыми узлами для своих потомков. Чем же чревата несбалансированность дерева? Дело в том, что при несбалансированном дереве частота кадров в разных участках игрового мира будет достаточно сильно "скакать". Отмечу, что классическое BSP дерево, используемое ТОЛЬКО для рендеринга без каких либо модификаций самого алгоритма, не будет этому подвержено, т.к. независимо от того, какую структуру имеет дерево, мы в любом случае должны его обойти целиком и отрисовать ВСЕ полигоны в мире. Совершенно иная ситуация складывается при усовершенствовании алгоритма или, скажем, использовании его для контроля столкновений в Solid BSP варианте, о котором подробнее мы поговорим позже. За счет того, что для проверки столкновения с полигоном в разных частях уровня мы должны будем опуститься на разную "глубину" по узлам дерева, в одной части уровня мы будем иметь частоту кадров, к примеру, 60+, а в другой его части менее 10. Слишком утрировано? Возможно, но проблема все же есть. Если бы мы использовали сбалансированное дерево, частота кадров была бы приблизительно постоянна и держалась бы, к примеру, около 30 кадров в секунду.

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

Наилучший результат достигается при помощи построения ВСЕХ возможных BSP деревьев на заданном входном количестве полигонов и выборе наиболее оптимального из построенных, исходя из наименьшего количества полученных узлов в дереве. Но, увы... При текущих вычислительных мощностях это просто нереально и очень долговременно. Речь, конечно, идет о среднего размера игровых уровнях (и более). Приходится использовать определенные упрощения. Общепринятым способом является последовательный проход по всем потенциальным сплиттер полигонам, и подсчете неких баллов. Причем, мы никоим образом не учитываем дальнейшие попытки разбиения с заново полученными двумя списками входных параметров, а значит, мы не можем гарантировать, что выбор именно этого, на данный момент "оптимального", исходя из наших вычислений, сплиттера, не окажет негативное влияние на построение дерева в дальнейшем. Перейдем к вычислениям. Вот одна из таких формул:

Score = abs(front – back)

В данном случае, front и back - количество полигонов по обе стороны от сплиттера. Front — перед сплиттером, back — позади него. Исходя из данной формулы, сплиттер с НАИМЕНЬШИМ количеством очков признается наиболее оптимальным. Тут мы пытаемся удовлетворить требование сбалансированности для данной глубины дерева.

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

Score = abs(front – back) + (splits * 8)

Splits в этом примере — как раз количество этих самых распиливаний. Цифра восемь в данном случае является коэффициентом «веса». Условие выбора то же — полигон с наименьшим количеством очков будет признан лучшим сплиттером.

Займемся дальнейшим усовершенствованием? Мы забыли о полигонах лежащих на одной плоскости со сплиттером. Хорошо это или плохо — вопрос открытый, поэтому в формуле я ставлю знак ±:

Score = abs(front - back) + (splits * 8) ± coplanar

где coplanar — количество полигонов лежащих на одной плоскости с потенциальным сплиттером. Если использовать знак минус, сплиттер с большим количеством компланарных полигонов будет иметь больше шансов на «выигрыш».

Осталось лишь обобщить предложенную формулу до общего вида:

Score = w1*abs(front – back) + splits*w2 + coplanar*w3

где w1, w2 и w3 «вес» того или иного фактора. Кроме того, не стоит забывать, что «вес» может принимать и отрицательное значение (например: w3 = –1).


2. Рендеринг

2. Рендеринг

Рендеринг

Итак, мы подошли к тому самому процессу визуализации. Еще раз напомню читателю, что все приведенные выше действия будут справедливы и для трехмерного случая построения 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 подхода было бы неоспоримым на достаточно комплексных сценах.

На заметку:

Quake I, Quake II и Quake III используют leaf based bsp tree with pvs (PVS BSP) для эффективного определения игрока в пространстве и при рендеринге. О leaf based bsp мы говорим в дальнейшем.

Размышления о совершенствовании. 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;
}

На заметку:

Во второй части статьи, при написании рендеринга уровней Quake 1,2 и 3 мы более плотно изучим оптимальные варианты хранения и представления структуры BSP дерева в памяти и на диске.

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 дерево, мы просто опускаемся вниз от корневого узла до последнего дочернего (относительно текущего расположения объекта, как и при процедуре рендеринга к примеру), "в котором" расположен объект, для которого выполняется тест. Спускаясь все ниже и ниже с каждым узлом, мы автоматически отсеиваем часть полигонов, столкновение с которыми нужно было бы проверить. Добравшись по дереву до нужного нам полигона, используя простейшую трассировку луча, тестируем пересечение прямой с полигоном. Полигон нам придется получить из узла родителя, так как добавленные нами экстра узлы не будут содержать информацию о полигоне, хотя вопрос модификации базового алгоритма всегда остается открытым :)

На заметку:

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

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

На заметку:

Гарри Симонс в своих статьях использует одно и то же дерево для рендеринга и контроля столкновений (собственно, это и есть Solid Node BSP). С одной стороны это экономия и, казалось бы, некоторый прирост в производительности. Но ведь нам не всегда нужно контролировать столкновения с точностью до каждого полигона. В таком случае, создание простой модели поверх оригинального игрового мира было бы более оптимальным. Конечно же, это модель не для отображения. На основе нее мы можем построить второе BSP дерево, более простое и используемое лишь для контроля столкновений.


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

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

Немного математики 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, пятнадцать нулей.


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

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

Рендеринг 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.

Оригинальная статья: gamedev.ru

Copyright © 2018. All rights reserved. (To change the copyright info, just edit it in template.)