BSP (GoldSrc)
Данный документ посвящен структуре BSP файлов карт версии 30 для игрового движка Gold Source (Half-life 1).
Введение
Начнем с определения структуры трехмерного вектора, который является незаменимой частью 3D геометрии:
#include <stdint.h>
typedef struct _VECTOR3D
{
float x, y, z;
} VECTOR3D;
Заголовок
Файл состоит из заголовка фиксированного размера и чанков данных, позиция и размер каждого, а также его наличие, определяемое заголовком файла. Карта ограничена 15 чанками в файле, соответственно всего 15 типов чанков, и чанк данного типа может войти лишь единожды в файл. Описание заголовка ниже:
#define HEADER_LUMPS 15
#define LUMP_ENTITIES 0
#define LUMP_PLANES 1
#define LUMP_TEXTURES 2
#define LUMP_VERTICES 3
#define LUMP_VISIBILITY 4
#define LUMP_NODES 5
#define LUMP_TEXINFO 6
#define LUMP_FACES 7
#define LUMP_LIGHTING 8
#define LUMP_CLIPNODES 9
#define LUMP_LEAVES 10
#define LUMP_MARKSURFACES 11
#define LUMP_EDGES 12
#define LUMP_SURFEDGES 13
#define LUMP_MODELS 14
typedef
{
struct _BSPHEADER
int32_t nVersion; // Версия карты = 0x0000001E = 30
BSPLUMP lump[HEADER_LUMPS]; // блок описания чанков
} BSPHEADER;
Константа HEADER_LUMPS указывает на максимальное число чанков = 15. Далее идет набор 15 констант: индексов в массиве lump заголовка, который описывает чанк данного типа. Таблица ниже подробнее описывает каждый чанк по его индексу в массиве lump заголовка:
| Индекс | Название | Краткое описание |
|---|---|---|
| 0 | Entities | Описание сущностей карты, в текстовом виде |
| 1 | Planes | Описание плоскостей на карте |
| 2 | Textures | Данные текстур, упакованные в карту |
| 3 | Vertexes | Описание всех вершин геометрии на карте |
| 4 | Visibility | Видимость между вид. листами |
| 5 | Nodes | Описание BSP дерева |
| 6 | TexInfo | Данные о методах отображения текстур |
| 7 | Faces | Описание Фэйсов – итоговых полигонов на карте |
| 8 | Lightmaps | Данные статически расчитанного освещения |
| 9 | ClipNodes | Описание физики столкновения |
| 10 | Leaves | Описание виз-листов BSP дерева |
| 11 | MarkSurfaces | Какие Фэйсы преналжедат виз-листам |
| 12 | Edges | Описание ребер, соединяющих вершины геометрии |
| 13 | SurfEdges | Какие ребра описывают данную поверхность |
| 14 | Models | Описание Брашевой геометрии карты |
Структура Lump
Далее опишем информационную структуру BSPLUMP:
typedef struct _BSPLUMP
{
int32_t nOffset; // Смещение к чанку от начала файла
int32_t nLength; // Размер чанка в байтах
} BSPLUMP;
Размер данной структуры: 8 байт, массив lump содержит 15 таких структур. Тогда весь размер фиксированного заголовка файла карты занимает: 124 байта. Поле nLength Отрицательным быть не может, нулевое значение означает отсутствие чанка в файле карты. На этом описание заголовка завершаем. Чанки.
Чанки
В общем случае чанки в карте представляют собой массив определенных структур (без информативного заголовка), хранящих данные. И компиляторами hlbsp устанавливаются свои ограничения на размеры массивов каждого чанка, так как компиляторы используют статические массивы. Ниже представлены константы максимальных размеров:
#define MAX_MAP_HULLS 4
#define MAX_MAP_MODELS 400 // Штук
#define MAX_MAP_BRUSHES 4096 // Штук
#define MAX_MAP_ENTITIES 1024 // Штук
#define MAX_MAP_ENTSTRING 131072 // Байт
#define MAX_MAP_PLANES 32767 // Штук
#define MAX_MAP_NODES 32767 // Штук
#define MAX_MAP_CLIPNODES 32767 // Штук
#define MAX_MAP_LEAFS 8192 // Штук
#define MAX_MAP_VERTS 65535 // Штук
#define MAX_MAP_FACES 65535 // Штук
#define MAX_MAP_MARKSURFACES 65535 // Штук
#define MAX_MAP_TEXINFO 8192 // Штук
#define MAX_MAP_EDGES 256000 // Штук
#define MAX_MAP_SURFEDGES 512000 // Штук
#define MAX_MAP_TEXTURES 512 // Штук
#define MAX_MAP_MIPTEX 0x200000 // Байт
#define MAX_MAP_LIGHTING 0x200000 // Байт
#define MAX_MAP_VISIBILITY 0x200000 // Байт
#define MAX_MAP_PORTALS 65536 // Штук
Начнем с описания каждого чанка последовательно, в соответствии с их индексом.
Чанк Сущностей
Представляют собой чистый текстовый ASCII код, который копируется из исходного файла. Каждая энтитя обернута фигурными кавычками (каждая в отдельной строке) и полями «ключ – значение», где имя ключа и значения константы обернуто двойными кавычками "", ключ и значения отделяются пробелом. Одна пара «ключ – значение» описывается в одной строке (с завершающим переносом строки и концом). Компиляторами определено ограничение на максимальную длину строки "ключа" = 32 символа, и максимальную длину строки "значения" = 1024 символов.
Чанк Плоскостей
Чанк представляет собой массив плоскостей, на каждую плоскость приходится 20 байт. Тогда число плоскостей легко определяется делением размера этого чанка на 20.
typedef struct _BSPPLANE
{
VECTOR3D vNormal; float fDist;
int32_t nType; // предварительная ориентация плоскости
} BSPPLANE;
#define PLANE_X 0 // Нормаль параллельна/антипараллельна оси Х #define PLANE_Y 1 // Нормаль параллельна/антипараллельна оси Y #define PLANE_Z 2 // Нормаль параллельна/антипараллельна оси Z #define PLANE_ANYX 3
#define PLANE_ANYY 4
#define PLANE_ANYZ 5
Плоскость описывается следующим уравнением Dot(vNormal, r) - fDist = 0;
- vNormal – нормаль к плоскости,
- r – радиус-вектор любой точки на плоскости
- fDist – расстояние плоскости от начала координат.
Поле nType принимает значение от 0 до 5, определяемое полями #defines: первые три определяют строгую ориентацию нормали по\против конкретной оси, остальные три параметра определяют для какой оси угол между нормалью и данной осью мал, иначе говоря к какой оси нормаль ближе (без учета знака) – эти параметры помогают игровому движку в ускорении проверки видимости плоскости пользователем.
Чанк Текстур
Этот чанк содержит описания текстур в том виде, как они хранятся в WAD3 упаковочных файлах. Чанк начинается с очень кратного заголовка – поля uint32_t указывающее число текстур в этом чанке. На одну текстуру приходится 4 mip уровня (включая основной уровень) и имя текстуры ограничено 16 символами включая нулевой символ конца строки.
Далее следует массив из int32_t, которые определяют смещения к структурам BSPMIPTEX, относительно начала этого чанка. Описание этих текстур ниже.
Далее следует массив из структур BSPMIPTEX по 40 байт, описывающих имя текстуры szName, ее ширину nWidth, высоту nHeight и смещения nOffsets к четырем mip уровням относительно начала данной структуры в массиве структур. Пиксельные данные текстур могут следовать как сразу после этого массива, так и в любом месте BSP карты (не мешая остальным чанкам) и обычно располагаются в конце карты. Если же текстуру необходимо загрузить из внешнего WAD3 файла, смещения к mip уровням записываются нулями и используется поле имени текстуры для поиска текстуры.
О пиксельных данных – текстуры хранятся в формате 256 индексированной палитрой на одну текстуру (на 4 mip уровня приходится одна палитра). Палитра идет с после 4 mip уровня с относительным смещение в 2 байта, в виде таблицы из 256 цветов RGB888 (в итоге вся палитра весит 786 байт).
#define MAXTEXTURENAME 16
#define MIPLEVELS 4
typedef struct _BSPMIPTEX
{
char szName[MAXTEXTURENAME]; uint32_t nWidth, nHeight; uint32_t nOffsets[MIPLEVELS];
} BSPMIPTEX;
Чанк Вершин
typedef VECTOR3D BSPVERTEX; // Повторяем тип структуры
Простой массив структур типа VECTOR3D размером 12 байт. Число вершин есть размер данного чанка деленный на 12. Вершины нужны геометрии карты для определения ребер и соответственно граней.
Чанк Видимости
Это массив видимости Potentially Visible Set (потенциально видимый набор, PVS или же VIS-список) между виз-листами (1 видит и 0 не видит), который хранится побитно в RLE сжатии для нулей. Используется только в процессе рендера геометрии. Просчетом данного чанка занимается отдельный компилятор: hlvis.
Декодирование блока происходит следующим образом: Чтобы найти PVS данного кластера, начните с байта, заданного смещением в массиве смещений. Если текущий байт в буфере PVS равен нулю, следующий байт, умноженный на 8, - это количество пропущенных кластеров, которые не видны. Если текущий байт не равен нулю, установленные биты соответствуют кластерам, видимым из этого кластера. Продолжайте, пока не будет достигнуто количество кластеров с PVS на карте.
Чанк Нодов (BSP дерево)
Хранится массивом структур нодов\листов фиксированного размера = 24 байта, и число их определяется делением размера чанка на 24.
typedef struct _BSPNODE
{
uint32_t iPlane; int16_t iChildren[2];
int16_t nMins[3], nMaxs[3]; uint16_t firstFace, nFaces;
} BSPNODE;
- iPlane – номер плоскости в чанке массива плоскостей, которая делит пространство этого узла.
- firstFace и nFaces – определяют какие Фэйсы (с какого и сколько штук в чанке массивов фэйсов) принадлежат данному ноду\листу (Узлу BSP дерева). * Вектора nMins и nMaxs задают bounding box данного нода\листа.
- Два-вектор iChildren определяет двух «детей» этого узла после деления пространства плоскостью («дети» хранятся в этом же чанке).
Если индекс положителен, то следующий по глубине узел будет нодом, если отрацителен – то следующий будет конечным виз-листом в чанке виз-листов, а сам индекс рассчитывается как побитовое инвертирование этого отрицательного значения (например, для числа -100 это означает индекс 99 после инверсии) и применяется к чанку виз-листов.
Данный блок не участвует в рендере, а только в детектировании коллизии, положении камеры игрока и иных вспомогательных работах.
Чанк TexInfo
Данный чанк хранит информацию как текстура накладывается на поверхность (грань браша): вращение, трансляция, скейл и флаги. Данные хранятся в виде массива структур фиксированного размера = 40 байт, соответственно число структур есть размер этого чанка деленый на 40.
Структура
typedef struct _BSPTEXTUREINFO
{
VECTOR3D vS;
float fSShift; VECTOR3D vT;
float fTShift;
uint32_t iMiptex; // индекс текстуры в чанке Текстур
uint32_t nFlags; // флаги, обычно всегда = 0
} BSPTEXTUREINFO;
Первые 4 параметра используются для вычисления текстурных координат по точке на плоскости в игровом мире (x, y, z → s, t) следующим образом: s = dot(Vertex, vS) + fSShift t = dot(Vertex, vT) + fTShift
По-хорошему, vS и vT должны быть ортогональными и лежать на плоскости поверхности, но ничто не запрещает их брать произвольными, однако это может приводить к необычным преобразованием текстурам (отсутствие тайлинга, перспективные преобразования). Тестами получено, что к fSShift и fTShift «масштабирование» текстуры не применяется (при работе с VHE).
Чанк Фэйсов
Чанк хранит массив структур фэйсов фиксированного размера = 20 байт. Фэйсы являются результатом разбиения граней брашей на простейшие треугольники (полигоны). Структура фэйса
typedef struct _BSPFACE
{
uint16_t iPlane; uint16_t nPlaneSides; uint32_t iFirstEdge; uint16_t nEdges; uint16_t iTextureInfo; uint8_t nStyles[4];
uint32_t nLightmapOffset;
} BSPFACE;
iPlane определяет индекс плоскости, которой данный фэйс параллелен (нужна лишь информация нормали). Если nPlaneSides = 0, то нормаль из плоскости для фэйса берется без изменения, иначе (для не равного нулю значения), нормаль плоскости нужно умножить на −1, иначе говоря направить в противоположную сторону, что бы применить ее к фэйсу. iFirstEdge и nEdges определяют индекс первого ребра и их количество для чтения, что бы можно было построить полигон фэйса. iTextureInfo это индекс к предыдущему чанку TexInfo, для нанесения текстуры на фэйс. Массив nStyles описывает предварительный способ рендера текстуры. И наконец nLightmapOffset дает смещение в чанке лайтмапов для карты лайтмапов, применяемой на данном фэйсе.
В соответствии со спецификацией Quake 2 формата bsp карт, интервал между лайтмапами фиксирован в 16 единиц мировых координат, если быть точнее, то в системе координат фэйса. Получая на фэйсе самые максимальные и минимальные UV текстурные координаты, размера лайтмап карты определяются следующим образом: 𝐿𝑚𝑝𝑊𝑖𝑑𝑡ℎ = 𝑐𝑒𝑖𝑙 (𝑈𝑚𝑎𝑥) − 𝑓𝑙𝑜𝑜𝑟 (𝑈𝑚𝑖𝑛) + 1,
16 16 𝐿𝑚𝑝𝐻𝑒𝑖𝑔ℎ𝑡 = 𝑐𝑒𝑖𝑙 (𝑉𝑚𝑎𝑥) − 𝑓𝑙𝑜𝑜𝑟 (𝑉𝑚𝑖𝑛) + 1;
16 16 Где ceil – округление к ближайшему целому в сторону положительной бесконечности, floor – округление к ближайшему целому в сторону отрицательной бесконечности. А размеры исходной текстуры будет определяться следующим образом: 𝑊𝑖𝑑𝑡ℎ = (𝐿𝑚𝑝𝑊𝑖𝑑𝑡ℎ − 1) ∗ 16; 𝐻𝑒𝑖𝑔ℎ𝑡 = (𝐿𝑚𝑝𝐻𝑒𝑖𝑔ℎ𝑡 − 1) ∗ 16;
Чанк Лайтмапов
Это непрерывный массив структуры лайтмапов, лайтмап представляет собой RGB888 цвет этого лайтмапа, размер структуры 3 байта. Число лайтмпов есть размер этого чанка деленный на 3.
Чанк КлипНодов
Данный чанк создает второе BSP дерево, используемую для физики столкновений на карте. Хранится в виде массива структур фиксированного размера = 8 байт. Число Клип Нодов есть размер чанка деленный на 8. Данное дерево образуется от Первичного BSP дерева Нодов, но намного проще для ускорения расчета столкновений. Структура: typedef struct _BSPCLIPNODE { uint32_t iPlane; int16_t iChildren[2]; } BSPCLIPNODE;
Отрицательные индексы iChildren означают что за ним никто не следует. В соответствии с Quake спецификацией, КлипНоды строятся так, что плоскости смещены вдоль осей 𝑋, 𝑌 на 16 единиц (смещение в направлении компонент нормали, с учетом знака), и на 24 единицы по оси 𝑍 с учетом знака. iChildren может принимать только два отрицательных значения, тогда первый элемент массива (iChildren[0]) интерпретируется как Front часть клипнода, если второй
• Back часть клипнода (относительно нормали плоскости):
1) Если встречается значение -1, то переднее «Front» (соответственно заднее
«Back») полупространство находится за пределами Браша, и столкновение невозможно.
2) Если значение -2 выполнено, то передняя «Front» (соответственно задняя «Back») половина пространства находится внутри Браша, и узлы дерева нодов BSP должны быть проверены.
Для этих узлов не определен ограничивающий прямоугольник, поскольку ограничивающий прямоугольник - это ограничивающий прямоугольник браша. Если вы модифицируете клипнод, например, изменяя определения плоскостей или устанавливая -1 значения для каждого дочернего элемента, то модель становится полностью сквозной. Это очень забавный спецэффект. Также позаботьтесь о том, чтобы плоскости клипнода были ориентированы по направлению к внешней части модели, а не к внутренней части. Если вы измените ориентацию, то игрок сможет пройти модель, как если бы она не существовала ... даже падая сквозь пол.
Чанк виз-листов
Представляет собой массив структур фиксированного размера = 28 байт. Число виз-листов есть размер чанка деленый на 28. Структура описывает листья, на которые ссылается чанк нодов BSP дерева. Структура:
- define
CONTENTS_EMPTY -1
- define
CONTENTS_SOLID -2
- define
CONTENTS_WATER -3
- define
CONTENTS_SLIME -4
- define
CONTENTS_LAVA -5
- define
CONTENTS_SKY -6
- define
CONTENTS_ORIGIN -7
- define
CONTENTS_CLIP -8
- define
CONTENTS_CURRENT_0 -9
- define
CONTENTS_CURRENT_90 -10
- define
CONTENTS_CURRENT_180 -11
- define
CONTENTS_CURRENT_270 -12
- define
CONTENTS_CURRENT_UP -13
- define
CONTENTS_CURRENT_DOWN -14
- define
CONTENTS_TRANSLUCENT -15 typedef { struct _BSPLEAF
int32_t nContents; int32_t nVisOffset; int16_t nMins[3], nMaxs[3]; int16_t iFirstMarkSurface, nMarkSurfaces; uint8_t nAmbientLevels[4]; } BSPLEAF;
nContents описывает тип содержимого данного виз-листа, значение берется из списка #define описанного выше. nVisOffset определяет смещение в чанке видимости для определения PVS остальных виз-листов. Если же это значение отрицательно, то данный виз-лист не использует PVS. Далее следует описание Bounding Box, аналогично описываемый в чанке Нодов. iFirstMarkSurface и nMarkSurfaces описывает первый индекс в массиве чанк Marksurfaces (фактически набор индексов фэйсов в этом виз- листе). Массив nAmbientLevels определяет свойства звука в данном виз-листе (эхо, громкость и т.д.).
Чанк Marksurfaces
Это массив из значений типа uint16_t (2 байта), который служит для перенаправления на индексы фэйсов в списке фэйсов. Т.е. вместо того что бы в виз- листе прямо указывать динамический массив индексов всех фейсов в данном виз-листе (так как фэйсы упорядочены относительно чанка нодов и брашей), то данный массив служит набором таких «динамических массивов». К примеру, что бы получить 10 фэйсов для некоторого виз-листа, виз-лист ссылается на этот массив к 𝑖-ому элементу, и из этого массива по 𝑖-элементу читает индекс 𝑗-ого фэйса в чанке фэйсов.
Чанк Ребер
Это массив структур ребер фиксированного размера = 4 байта. Структура хранит два uint16_t, определяющих индекс вершин в чанке вершин. Указывает соответственно на начальный и конечный индекс, определяя проход по вершинам (по часовой и против часовой в совокупности на фэйсе).
Чанк Конечных Ребер
Это массив элементов типа int32_t, который выполняет функцию подобную MarkSurface, но для чанка ребер, к которому ссылается чанк Фэйсов через этот чанк. Если элемент отрицателен, то знак убирается, а вершины ребра идут в обратном порядке.
Чанк Брашевой "модельной" геометрии
Данный чанк, являясь своего рода мини BSP деревом, описывает браши на карте. Данная структура не изменилась с описанием этого же чанка в Quake. Чанг хранит массив структур фиксированного размера = 64 байт.
typedef struct _BSPMODEL
{
float nMins[3], nMaxs[3]; VECTOR3D vOrigin;
int32_t node_id0; int32_t node_id1; int32_t node_id2; int32_t node_id3; int32_t nVisLeafs;
int32_t iFirstFace, nFaces;
} BSPMODEL;
Первая пара троек чисел определяет Bounding Box данного браша, vOrigin определяет местоположения (перемещение) данного браша в мировой системе координат (тогда все геометрические данные записываются относительно данной позиции). iFirstFace и nFaces определяют первый индекс и число фэйсов в чанке фэйсов, которые принадлежат данному брашу, при этом указывая напрямую, без перенаправления на чанк маркеров. node_id0 указывает на индекс Нода в дереве нодов, который режет данный браш. Следующие два индекса принадлежат чанкам КлипНодов, описывающих физику столкновений данного браша, последний индекс неизвестен, но предположительно является третьим индексов на чанк КлипНодов. Информация по nVisLeafs отсутствует, но если верить спецификации Quake формата BSP карт, то данный параметр описывает сколько виз-кластеров касаются либо охватывают данный браш (браш может быть на границе между двумя виз-кластерами), который нужен для «выделения памяти» и корректности рендера. Первый элемент массива описывает карту целиком, определяя ограничения игрового пространства всей карты, и входы клип нодов и нодов, а так же количество фэйсов карты, которым необходимы PVS данные для корректного чтения PVS. Прочее.
- Задача определения принадлежности точки полупространству, разделенной плоскостью и заданной в виде 𝑑𝑜𝑡(⃗v⃗⃗N⃗⃗⃗⃗o⃗⃗⃗r⃗⃗m⃗⃗⃗⃗a⃗⃗ l, ⃗𝒓 ) − fDist = 0. Точку подставляем в ⃗𝒓 , и считаем выражение 𝑑𝑜𝑡(⃗v⃗⃗N⃗⃗⃗⃗o⃗⃗⃗r⃗⃗m⃗⃗⃗⃗a⃗⃗ l, ⃗𝒓 ) − fDist. Если результат равен нулю,
точка на плоскости. Если результат больше нуля, точка в «Переднем» полупространстве. Если результат меньше нуля, точка в «Заднем» полупространстве. «Передним» называют полупространстве, в которую обращена нормаль плоскости, «Задним» – наоборот. Данный алгоритм будет пригоден при определении принадлежности точки виз-листу при поиске в двоичном дереве.
- Особенность построения двоичного дерева в том, что Bouding Box более верхних узлов окутывает Bouding Box узлов поглубже и их размеры соответственно меньше. Это значит, что если точка не вошла в одно из полупространств узла, то дальше в этом полупространстве искать нечего.