Введение в BSP деревья или BSP для самых «маленьких». Часть первая, теоретическая.
Автор: Антон В. Звягинцев
Эпиграф:
Вопрос на форуме: Какое дерево лучше использовать?
Ответ #gamedev: Sark7: Ближайшее! :)
Планируемая структура статьи
Базовые знания
DISCLAIMER или «я не я и корова не моя»
BSP как оно есть
Краткий экскурс в историю
Node BSP Tree
Строим дерево на примерах
Оптимальный сплиттер и сбалансированное дерево
Рендеринг
Размышления о совершенствовании. Node culling или отсечение узлов
Описание структур данных
Solid Node BSP Tree
Несколько слов о контроле столкновений
Немного математики BSP компилятора.
Leaf BSP Tree
PVS
Zero Run Lenght Encoding
Рендеринг leaf BSP + PVS
Отсечение по области просмотра (Frustum culling)
Порталы
PVS и объекты в игровом мире
Несколько советов по отладке
Solid Leaf BSP Tree
Напоследок
Использованные материалы
Благодарности
Планируемая структура статьи
В этой статье мы рассмотрим тот самый алгоритм, который для многих уже стал притчей во языцех — 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!
7 мая 2004 (Обновление: 6 июля 2009)