Эта статья документации для платформы "GoldSrc". Нажмите для получения дополнительной информации.

BSP (GoldSrc)

From Valve Developer Community
< Ru
Jump to navigation Jump to search
English (en)Русский (ru)Translate (Translate)
Go back to: BSP(en)
<(en)
Edit Tabs

Данный документ посвящен структуре BSP файлов карт версии 30 для игрового движка Gold Source (Half-life 1).

Введение

Начнём с определения структуры трехмерного вектора, который является незаменимой частью 3D геометрии: 

#include <stdint.h>

typedef struct _VECTOR3D
{
    float x, y, z;
} VECTOR3D;

Версии

This table gives an overview over the different BSP versions being used in some games based on GoldSrc GoldSrc Engine.

  • The 0.52 alpha build of Half-Life Half-Life uses the version number 29, like Quake Quake, but is much more similar to BSP30 than BSP29.
  • GoldSrc GoldSrc normally uses BSP30, as described on this page.
  • Half-Life: Blue Shift Half-Life: Blue Shift flips the positions of the plane and entity lumps. The version number remains the same.
Tip.pngСовет: BSPFix can be used to losslessly convert between standard BSP30 and Blue Shift BSPs.
  • Paranoia 2: Savior Paranoia 2: Savior uses a modified version of BSP30, called BSP31. This format is deprecated, as BSP30 can be extended to support BSP31's features without breaking compatibility (using BSPX lumps).
  • James Bond 007: Nightfire James Bond 007: Nightfire uses a modified version of BSP30, called BSP42.
Подтвердить:Are the formats used by Counter-Strike Neo Counter-Strike Neo, Counter-Strike Nexon Counter-Strike Nexon, and Cry of Fear Cry of Fear different from BSP30?

Заголовок

Файл состоит из заголовка фиксированного размера и блоков данных, позиция и размер каждого, а также его наличие, определяемое заголовком файла. Карта ограничена 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 Описание геометрии элементов карты

Структура блоков

Далее опишем информационную структуру BSPLUMP: 

typedef struct _BSPLUMP
{
    int32_t nOffset; // Смещение блока от начала файла
    int32_t nLength; // Размер блока в байтах
} BSPLUMP;

Размер данной структуры: 8 байт, массив lump содержит 15 таких структур. Тогда весь размер фиксированного заголовка файла карты занимает: 124 байта. Поле nLength Отрицательным быть не может, нулевое значение означает отсутствие блока в файле карты. На этом описание заголовка завершаем.

Блоки

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

#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 (128*1024) // Байт

#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. 

#define PLANE_X 0     // Плоскость перпендикулярна (нормаль параллельна) оси Х 
#define PLANE_Y 1     // Плоскость перпендикулярна оси Y 
#define PLANE_Z 2     // Плоскость перпендикулярна оси Z 
#define PLANE_ANYX 3  // Non-axial plane is snapped to the nearest
#define PLANE_ANYY 4
#define PLANE_ANYZ 5

typedef struct _BSPPLANE
{
    VECTOR3D vNormal; // Вектор нормали к плоскости
    float fDist;      // Уравнение плоскости: vNormal * X = fDist
    int32_t nType;    // Предварительная ориентация плоскости
} BSPPLANE;

Плоскость описывается следующим уравнением Dot(vNormal, r) - fDist = 0;

  • vNormal – нормаль к плоскости,
  • r – радиус-вектор любой точки на плоскости
  • fDist – расстояние плоскости от начала координат.

Поле nType принимает значение от 0 до 5, определяемое полями #defines: первые три определяют строгую ориентацию нормали по\против конкретной оси, остальные три параметра определяют для какой оси угол между нормалью и данной осью мал, иначе говоря к какой оси нормаль ближе (без учета знака) – эти параметры помогают игровому движку в ускорении проверки видимости плоскости пользователем.

Текстуры

Этот блок содержит описания текстур в том виде, как они хранятся в WAD3(en) упаковочных файлах. Блок начинается с очень кратного заголовка – поля uint32_t указывающее число текстур в этом блоке. На одну текстуру приходится 4 mip уровня (включая основной уровень) и имя текстуры ограничено 16 символами включая нулевой символ конца строки. 

typedef struct _BSPTEXTUREHEADER
{
    uint32_t nMipTextures; // Количество структур BSPMIPTEX
} BSPTEXTUREHEADER;

Далее следует массив из int32_t, которые определяют смещения к структурам BSPMIPTEX, относительно начала этого блока. Описание этих текстур ниже. 

typedef int32_t BSPMIPTEXOFFSET;

Далее следует массив из структур 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;     // Extends of the texture
    uint32_t nOffsets[MIPLEVELS]; // Offsets to texture mipmaps BSPMIPTEX;
} BSPMIPTEX;

Вершины

typedef VECTOR3D BSPVERTEX; // Повторяем тип структуры

Простой массив структур типа VECTOR3D размером 12 байт. Число вершин равно размеру данного блока деленному на 12. Вершины нужны геометрии карты для определения ребер и соответственно граней.

Видимость

Это массив видимости Potentially Visible Set(en) (потенциально видимых областей, PVS или же VIS-список) между областями видимости (1 видит и 0 не видит), который хранится побитно в RLE сжатии для нулей. Используется только в процессе отображения геометрии. Расчётом данного блока занимается отдельный компилятор: hlvis(en).

Декодирование блока происходит следующим образом: Чтобы найти PVS данного кластера, начните с байта, заданного смещением в массиве смещений. Если текущий байт в буфере PVS равен нулю, следующий байт, умноженный на 8, - это количество пропущенных кластеров, которые не видны. Если текущий байт не равен нулю, установленные биты соответствуют кластерам, видимым из этого кластера. Продолжайте, пока не будет достигнуто количество кластеров с PVS на карте.

Узлы (BSP дерево)

Хранится массивом структур узлов\областей фиксированного размера = 24 байта, и число их определяется делением размера блока на 24. 

typedef struct _BSPNODE
{
    uint32_t iPlane;            // Index into Planes lump
    int16_t iChildren[2];       // If > 0, then indices into Nodes // otherwise bitwise inverse indices into Leafs
    int16_t nMins[3], nMaxs[3]; // Defines bounding box
    uint16_t firstFace, nFaces; // Index and count into Faces
} BSPNODE;
  • iPlane – номер плоскости в массиве блока плоскостей, которая делит пространство этого узла.
  • firstFace и nFaces – определяют, какие грани (с какого и сколько штук в массиве блока граней) принадлежат данному узлу\области (Узлу BSP дерева). * Вектора nMins и nMaxs задают ограничивающий короб (bounding box) данного узла\области.
  • Два-вектор iChildren определяет двух «потомков» этого узла после деления пространства плоскостью («потомки» хранятся в этом же блоке).

Если индекс положителен, то следующий по глубине узел будет узлом, если отрацителен – то следующий будет конечным областью видимости в блоке областей видимости, а сам индекс рассчитывается как побитовое инвертирование этого отрицательного значения (например, для числа -100 это означает индекс 99 после инверсии) и применяется к блоку областей видимости.

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

Информация текстур

Данный блок хранит информацию о текстурах, примененым к поверхностям (граням элементов): вращение, трансляция, масштабирование и признаки. Данные хранятся в виде массива структур фиксированного размера = 40 байт, соответственно число структур равно размеру этого блока делёный на 40.

Структура 

typedef struct _BSPTEXTUREINFO
{
    VECTOR3D vS;
    float fSShift;    // Смещение текстуры в S-направлении
    VECTOR3D vT;
    float fTShift;    // Смещение текстуры в T-направлении
    uint32_t iMiptex; // Bндекс текстуры в массиве текстур
    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;          // Plane the face is parallel to
    uint16_t nPlaneSide;      // Set if different normals orientation
    uint32_t iFirstEdge;      // Index of the first surfedge
    uint16_t nEdges;          // Number of consecutive surfedges
    uint16_t iTextureInfo;    // Index of the texture info structure
    uint8_t nStyles[4];       // Specify lighting styles
    int32_t nLightmapOffset; // Offsets into the raw lightmap data; if less than zero, then a lightmap was not baked for the given face.
} BSPFACE;

iPlane определяет индекс плоскости, которой данная грань параллелена (нужна лишь информация нормали). Если nPlaneSides = 0, то нормаль из плоскости для грани берётся без изменения, иначе (для не равного нулю значения), нормаль плоскости нужно умножить на −1, иначе говоря направить в противоположную сторону, что бы применить её к грани. iFirstEdge и nEdges определяют индекс первого ребра и их количество для чтения, чтобы можно было построить полигон грани. iTextureInfo это индекс к предыдущему блоку текстур, для нанесения текстуры на грань. Массив 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
{
    int32_t iPlane;       // Index into planes
    int16_t iChildren[2]; // negative numbers are contents
} 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;                         // Contents enumeration
    int32_t nVisOffset;                        // Offset into the visibility lump
    int16_t nMins[3], nMaxs[3];                // Defines bounding box
    uint16_t iFirstMarkSurface, nMarkSurfaces; // Index and count into marksurfaces array
    uint8_t nAmbientLevels[4];                 // Ambient sound levels
} BSPLEAF;

nContents описывает тип содержимого данной области видимости, значение берётся из списка #define описанного выше. nVisOffset определяет смещение в блоке видимости для определения PVS остальных областей видимости. Если же это значение отрицательно, то данная область видмости не использует PVS. Далее следует описание ограничивающего короба (Bounding Box), аналогично описываемый в блоке узлов. iFirstMarkSurface и nMarkSurfaces описывает первый индекс в массиве блока меток поверхностей (фактически набор индексов граней в этой области видимости). Массив nAmbientLevels определяет свойства звука в данной области видимости (эхо, громкость и т.д.).

Метки поверхностей

Это массив из значений типа uint16_t (2 байта), который служит для перенаправления на индексы граней в списке граней. Т.е. вместо того что бы в области видимости прямо указывать динамический массив индексов всех граней в данной области видимости (так как грани упорядочены относительно блока узлов и элементов), то данный массив служит набором таких «динамических массивов». К примеру, что бы получить 10 граней для некоторой области видимости, область видимости ссылается на этот массив к 𝑖-ому элементу, и из этого массива по 𝑖-элементу читает индекс 𝑗-ой грани в блоке граней. 

typedef uint16_t BSPMARKSURFACE;

Рёбра

Это массив структур ребер фиксированного размера = 4 байта. 

typedef struct _BSPEDGE
{
    uint16_t iVertex[2]; // Indices into vertex array
} BSPEDGE;

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

Рёбра поверхностей

typedef int32_t BSPSURFEDGE;

Это массив элементов типа int32_t, который выполняет функцию подобную меткам поверхностей, но для блока рёбер, к которому ссылается блок граней через этот блок. Если элемент отрицателен, то знак убирается, а вершины рёбра идут в обратном порядке.

Геометрия элементов карты

Данный блок, являясь своего рода мини BSP деревом, описывает элементы карты. Данная структура не изменилась с описанием этого же блока в Quake(en). Блок хранит массив структур фиксированного размера = 64 байт. 

#define MAX_MAP_HULLS 4

typedef struct _BSPMODEL
{
    float nMins[3], nMaxs[3];          // Крайние точки, определяющие ограничивающий короб
    VECTOR3D vOrigin;                  // Coordinates to move the // coordinate system
    int32_t iHeadnodes[MAX_MAP_HULLS]; // Index into nodes array
    int32_t nVisLeafs;                 // ???
    int32_t iFirstFace, nFaces;        // Index and count into faces
} BSPMODEL;

Первая пара троек чисел определяет ограничивающий короб (Bounding Box) данного элемента карты, vOrigin определяет местоположения (перемещение) данного элемента в мировой системе координат (тогда все геометрические данные записываются относительно данной позиции). iFirstFace и nFaces определяют первый индекс и число граней в блоке граней, которые принадлежат данному элементу, при этом указывая напрямую, без перенаправления на блок меток поверхностей. node_id0 указывает на индекс узла в дереве узлов, который режет данный элемент. Следующие два индекса принадлежат блоку барьерных узлов, описывающих физику столкновений данного элемента, последний индекс неизвестен, но предположительно является третьим индексов на блок барьерных узлов. Информация по nVisLeafs отсутствует, но если верить спецификации Quake формата BSP карт, то данный параметр описывает сколько областей видимости касаются либо охватывают данный элемент (элемент карты может быть на границе между двумя областями видимости), который нужен для «выделения памяти» и корректности рендера. Первый элемент массива описывает карту целиком, определяя ограничения игрового пространства всей карты, и входы барьерных узлов и узлов, а так же количество граней карты, которым необходимы PVS данные для корректного чтения PVS. Прочее.

  1. Задача определения принадлежности точки полупространству, разделенной плоскостью и заданной в виде 𝑑𝑜𝑡(⃗vNormal, ⃗𝒓 ) − fDist = 0. Точку подставляем в ⃗𝒓 , и считаем выражение 𝑑𝑜𝑡(⃗vNormal, ⃗𝒓 ) − fDist. Если результат равен нулю,

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

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

Внешние сылки

Retrieved from "https://developer.valvesoftware.com/w/index.php?title=Ru/BSP_(GoldSrc)&oldid=500957"