0 序言
大家好，我是m明天灬过后。《简单解析》的第三期终于来啦！《简单解析》系列专栏是一个科普专栏，科普的内容围绕金源引擎。本期为大家带来bsp、rmf和map文件的历史、文件结构以及解析方法，他们是金源引擎里常见到的地图格式，读完这篇文章后，你就可以自己制作一个软件，读取并渲染金源地图啦（大概）。
之前的文章可能太过在意严谨性，过多的补充说明反而让阅读体验变差，这篇文章可能会试着弱化严谨的用词或说明，让文章更易读。如遇到疑问，请理智讨论~
1 各式各样的地图文件
这是一张地图：
VHE中的地图
一张地图的产出有两个阶段，现在这张地图处于编辑阶段，它以rmf或者map文件存储，能用地图编辑器（如图中的VHE）编辑。编辑完成后，通过编译器将map文件编译成bsp文件，这张地图便到达了成品阶段，可以在游戏中游玩啦。
CS中的地图
map文件，取自英文单词“地图”（map），它结构简单，包含了编译所需的全部信息。map文件被用于Quake、金源等引擎，可以用VHE编辑，是编译器所需的文件格式。
rmf文件，全称“富地图格式”（Rich Map Format），是VHE使用的地图格式之一。rmf专为VHE设计，除了包含地图基本数据外，还包含了组（Group）、可见组(VisGroup）、路径点和摄像机等信息（如果不了解这些功能，可以去上期“VHE冷知识”里查阅哦：cv5299107）。rmf不能直接编译，编译时需要先转换为map文件。此外，VHE3.5以及之前版本使用rmf文件，而起源引擎使用的VHE4.0及以上版本改为了vmf文件（Valve Map Format），vmf文件修改了文件结构以适应VHE的新功能。
bsp文件，是二元空间划分（Binary Space Partion）的缩写，二元空间划分是一种隐藏面消除方法。bsp文件压缩了空间，针对渲染进行了优化，但不方便修改。它是Quake、金源乃至起源引擎的地图文件名称。
三种地图文件
2 存储格式
以上文件的作用想必大家有所了解，但很少有人提及这些文件中到底存了什么。要读取这些文件，你需要知道这些文件的存储格式。经过搜索、整理和验证，这里给出全网最详细（大概？）的文件格式说明~
2.1 map文件
map是文本文件（记事本打开就能看到内容），一个简单的map如下：
注意：map格式里没有用于注释的格式，这里使用//代表注释是为了方便解释
// 方便查看进行了缩进排版
{
"classname" "worldspawn"
"MaxRange" "32768"
"mapversion" "220"
"wad" "\valve\halflife.wad"
{
( -10 -10 10 ) ( -10 10 10 ) ( 10 10 10 ) WHITE [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( -10 10 10 ) ( -10 10 10 ) ( -10 -10 10 ) WHITE [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 10 -10 10 ) ( 10 -10 10 ) ( 10 10 10 ) WHITE [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 10 10 10 ) ( 10 10 10 ) ( -10 10 10 ) WHITE [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( -10 -10 10 ) ( -10 -10 10 ) ( 10 -10 10 ) WHITE [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( -10 10 10 ) ( -10 -10 10 ) ( 10 -10 10 ) WHITE [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
}
}
{
"classname" "light"
"_light" "255 255 255 300"
"origin" "0 0 0"
}map的内容很直观，一个map中有很多个实体，每个实体用一对花括号{}扩起。
{
实体1信息...
}
{
实体2信息...
}
...
{
实体n信息...
}实体的前几行是实体的属性，我们设置“名称”、“目标”和“角度”等等都是在设置实体的属性，属性后面跟着这个实体包含的所有固体。在VHE中，我们点击“固体转实体”时，实际上就是创建了一个新的实体，然后把固体放入这个实体中。
// 一个实体
{
"键1" "值1"
"键2" "值2"
"键3" "值3"
...
"键n" "值n"
{
固体1信息...
}
{
固体2信息...
}
{
固体3信息...
}
...
{
固体n信息...
}
}
如
{
"classname" "func_button" // 实体类型为func_button
"targetname" "myName" // 实体名称为myName
"target" "myTarget" // 实体目标为myTarget
"angle" "0 0 0" // 实体角度为0 0 0
// 不需要把实体拥有的属性都列出来，没有列出来的属性默认为空值
{
( -10 -10 10 ) ( -10 10 10 ) ( 10 10 10 ) WHITE [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( -10 10 10 ) ( -10 10 10 ) ( -10 -10 10 ) WHITE [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 10 -10 10 ) ( 10 -10 10 ) ( 10 10 10 ) WHITE [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 10 10 10 ) ( 10 10 10 ) ( -10 10 10 ) WHITE [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( -10 -10 10 ) ( -10 -10 10 ) ( 10 -10 10 ) WHITE [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( -10 10 10 ) ( -10 -10 10 ) ( 10 -10 10 ) WHITE [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
}
}
实体属性比较直观，而固体稍微复杂一些。一个固体由多个平面组成（注意是平面而不是面），每个平面包含了平面位置、方向、纹理名称、纹理坐标系、纹理缩放与偏移量，这些信息用于确定固体的形状以及纹理贴附的方式。
// 一个固体
{
平面1
平面2
平面3
...
平面n
}
// 一个平面
(x1 y1 z1) (x2 y2 z2) (x3 y3 z3) 纹理名称 [ ux uy uz u偏移量] [ vx vy vz v偏移量 ] 旋转量 u缩放 v缩放
如
( 0 0 0 ) ( 0 1 0 ) ( 1 0 0 ) WHITE [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 此外有一点要注意，map里所有固体都包含在实体中，但我们做地图时用到的固体呢？它们不是非实体吗？实际上这些物体统一被放在叫做worldspawn的实体当中了，worldspawn和固体一样不具备特殊功能。 结合以上的说明，再看下开头的样例，便可以理解了：
// worldspawn实体，存储所有的固体
{
"classname" "worldspawn" // 类型为worldspawn
"MaxRange" "32768" // 地图最大范围，固定为32768？
"mapversion" "220" // 地图版本信息，固定为220
"wad" "\valve\halflife.wad" // wad文件路径，如有多个，以分号隔开
// 一个盒子固体，有六个面，都贴有名为WHITE的纹理
{
( -10 -10 10 ) ( -10 10 10 ) ( 10 10 10 ) WHITE [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( -10 10 10 ) ( -10 10 10 ) ( -10 -10 10 ) WHITE [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 10 -10 10 ) ( 10 -10 10 ) ( 10 10 10 ) WHITE [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 10 10 10 ) ( 10 10 10 ) ( -10 10 10 ) WHITE [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( -10 -10 10 ) ( -10 -10 10 ) ( 10 -10 10 ) WHITE [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( -10 10 10 ) ( -10 -10 10 ) ( 10 -10 10 ) WHITE [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
}
}
// 一个点实体，不包含固体
{
"classname" "light" // light代表灯光点实体
"_light" "255 255 255 300" // 灯光颜色和亮度
"origin" "0 0 0" // 灯光位置
}2.2 rmf文件
注意：因为文件结构复杂，详细的文件结构放到了附录，本节只讲一下大致的文件内容。
rmf是二进制格式，需要用二进制的方式读取。rmf文件包含了许多信息，下面会逐一列举。
文件头信息 rmf的开头是版本号，四个字节为CD CC 0C 40，对应float类型约2.2，紧跟着是"RMF"三个字符，用于识别是否是rmf文件。
可见组（VisGroup）信息 rmf中包含可见组信息，包括了名称、显示颜色等。可见组用于辅助地图制作，快速显示、隐藏地图某个区域。
路径信息 对应rmf中的路径工具，保存路径工具生成的路径。它包含了路径及路径点的名称、位置、设置等信息。编译前路径会被转换为点实体并写入map文件。
摄像机信息 VHE提供了摄像机功能，可以添加、删除摄像机。摄像机的信息很简单，只保存了位置和视线方向。
地图信息 rmf最关键的部分，保存了地图中的固体、实体以及组（Group）数据。在rmf中，固体的存储很直接。一个固体包含多个面，一个面包含多个顶点和纹理贴附信息；rmf的实体里，除了有它包含的固体外，还存储了它的实体属性；最后，一个组包含了多个固体、实体或组（组可以嵌套）。此外，固体、实体和组都包含了可见组信息以及显示颜色，这些信息也是为了提高地图编辑效率。
2.3 bsp文件
注意：bsp文件详细的结构也放到了附录。
bsp的格式最复杂，它除了包含几何数据，还包含了许多编译后产生的额外数据。 bsp文件也是二进制文件，其主要分为两个大的版块，文件头（Header）和块（Lump）。
文件头信息 bsp的文件头包含版本信息，以及每个块在文件中的位置。
块信息 bsp文件中一共有15个块，按顺序分别是
接下来会逐一介绍每个块的内容。
2.3.1 实体数据块
实体数据块中，实体信息以字符串的形式存储，格式和map中的实体很像，唯一的区别在于，实体中不再包含固体。如果一个实体对应了固体，会多一个属性"model" "*n"，这里的n说明“模型块”的第n个模型属于这个实体。比如一个实体属性包含"model" "*9"，说明9号实体模型属于这个实体。
2.3.2 平面数据块
以数组形式存储了地图中用到的所有的平面。bsp里的平面用单位法向+到原点的有向距离表示，对应了平面的一般式：
2.3.3 纹理数据块
以数组形式存储了用到的纹理，包括纹理名称，大小等信息。纹理数据可以直接存储在bsp文件中，也可以存储在wad文件中，但无论存储在哪儿，所有地图使用的纹理在这里都有记录，并且纹理名称和纹理大小是填写了的。 如果纹理存储在bsp中，其存储格式和wad中相同，都是8位索引存储+调色板，4层mipmap。调色板数据跟在mipmap数据后面。
2.3.4 顶点数据块
以数组形式存储了所有顶点的数据。顶点用三个float表示，分别对应x、y、z坐标。
2.3.5 可见性数据块
存储了编译VIS阶段生成的VIS信息。VIS信息被用于可见性检测，用来剔除掉不可见的区域，优化渲染效率。可见性数据的读取非常简单，它是单纯的位数组，但解析比较复杂。 （关于VIS数据的解析和使用，大概会在以后编译程序的文章中说明。)
2.3.6 内部节点数据块
以数组形式存储了BSP树的内部节点，一个节点存储了平面、子节点以及其包含的面的信息。 关于BSP树，在下一章会详细讲解。
2.3.7 纹理贴附数据块
以数组的形式存储了纹理的贴附信息，包括UV坐标、偏移量、使用的纹理索引。
2.3.8 面数据块
以数组形式存储了所有面的信息，包括所属平面，方向，包含的边，纹理贴附数据的索引以及光照信息索引。
2.3.9 光照数据块
以数组形式存储了所有面的光照数据。金源使用了Lightmap烘焙技术，即在地图编译时计算光照，并将亮度、阴影等信息写入贴图中，之后使用无需实时计算光照，直接使用预先计算的贴图覆盖在原贴图上即可达到静态光照的视觉效果。这个数据块存储的就是这些贴图，称为Lightmap。所以所谓光照数据，其实就是一张张贴图。
有无lightmap的对比
（关于光照数据的解析和使用，大概会在以后编译程序的文章中说明。)
2.3.10 碰撞节点数据块
以数组形式存储了存储了碰撞节点。碰撞节点属于碰撞BSP树，专用于碰撞检测，和渲染没有关系，本文略过不谈。 （关于碰撞检测我了解也不多，可能之后会出一期碰撞检测的文章吧~）
2.3.11 叶节点数据块
以数组形式存储了bsp中所有叶节点。叶节点是金源引擎的渲染单位之一，存储了VIS、包围盒和包含的面等信息。
2.3.12 面索引过渡数据块
名称有些拗口，但功能很简单。块中只有一个uint16_t的数组，每一个uint16_t都对应了一个面（LumpFace）的索引，起到过渡的作用。比如叶节点存储的就是面索引过渡数据，通过过渡数据可以找到对应的面数据。
2.3.13 边数据块
以数组形式存储了边的数据。一条边包含两个顶点。
2.3.14 边索引过渡数据块
和“面索引过渡数据”相似，块中只有一个int16_t的数组，每一个int16_t都对应了一个边（LumpEdge）的索引，起过渡作用。 注意，这里用的是有符号的整型，有符号的索引还能代表边的方向。索引的绝对值对应了一条边，而>0指方向是从点0到点1，而<0指方向是从点1到点0。
2.3.15 实体模型数据块
终于到最后一个块了！这个块以数组形式存储了实体对应的固体信息，它和叶节点存储的数据类似，且也是金源引擎渲染的一个单位。
就是通过这些信息，你在可以用金源引擎的游戏打开地图，在里面激情对枪、蹦蹦跳跳、游山玩水~
3 文件解析和渲染
在地图文件里，形状都是以几何数据的形式存储的。比如要存储一个正方形，存储正方形的四个顶点就可够了。把几何数据转换成看到的图像，称为“渲染”。一般而言，三角形是渲染的基本单位，在渲染前，复杂的图形会被分成很多个三角形，再全部用三角形的方式进行渲染。因此，渲染地图的第一步，就是把地图数据解析、转换为三角形，这也是本章的主要内容。
注意：三种地图使用的坐标系相同，都是右手系，且指定z轴正方向为“上方”。
本文内容是有代码支撑的，我使用Vulkan+ImGui开发了可以解析并渲染bsp、rmf和map文件的渲染器，目前也还在更新中，地址如下： https://github.com/AllocBlock/goldsrc-renderer
3.1 map文件的解析和渲染
map的解析和渲染早在Stefan Hajnoczi大佬的文章中（见参考文献）有详细说明，以下内容是结合了翻译以及我的理解。
从“固体”到“多面体”前面提到，一个map文件大概长成这样：
{
"classname" "worldspawn"
"MaxRange" "32768"
"mapversion" "220"
"wad" "\valve\halflife.wad"
{
( -10 -10 10 ) ( -10 10 10 ) ( 10 10 10 ) WHITE [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( -10 10 10 ) ( -10 10 10 ) ( -10 -10 10 ) WHITE [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 10 -10 10 ) ( 10 -10 10 ) ( 10 10 10 ) WHITE [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 10 10 10 ) ( 10 10 10 ) ( -10 10 10 ) WHITE [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( -10 -10 10 ) ( -10 -10 10 ) ( 10 -10 10 ) WHITE [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( -10 10 10 ) ( -10 -10 10 ) ( 10 -10 10 ) WHITE [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
}
}
{
"classname" "light"
"_light" "255 255 255 300"
"origin" "0 0 0"
}实体属性和三角形数据无关，暂且不谈。我们所需的三角形信息都在固体里，比如这是一个长方体：
{
( -10 -10 10 ) ( -10 10 10 ) ( 10 10 10 ) WHITE [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( -10 10 10 ) ( -10 10 10 ) ( -10 -10 10 ) WHITE [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 10 -10 10 ) ( 10 -10 10 ) ( 10 10 10 ) WHITE [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 10 10 10 ) ( 10 10 10 ) ( -10 10 10 ) WHITE [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( -10 -10 10 ) ( -10 -10 10 ) ( 10 -10 10 ) WHITE [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( -10 10 10 ) ( -10 -10 10 ) ( 10 -10 10 ) WHITE [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
}固体的六个平面正好对应了长方体的六个面。之前提到，平面的前三个数据是三个顶点，用来确定平面的位置，那么我们能否用这三个坐标点得到三角形呢？ 答案是否定的，这三个坐标点只用来确定平面位置，它们不一定在固体上，而且一个平面上不一定只有三个顶点。 实际上，map存储固体利用了凸多面体的性质。如果我们把上面的平面都画出来，可以发现这些平面围起来得到了一个长方体。
map文件的固体也利用了这个性质，通过每三个平面计算交点，能得到这些平面包围起的凸多面体，而这些交点也是凸多面体的顶点。 下面是将固体转换为凸多面体的算法伪代码：
// 设平面的数量为n，得到的多面体也有n个面，我们存储每一个面包含的顶点即可
初始化面数组，大小为n
for (a从1到n-2)
{
for (b从a+1到n-1)
{
for (c从b+1到n)
{
点I = 计算平面交点(平面a, 平面b, 平面c) // 计算交点的具体算法可在原文章中查阅
if (I存在)
将点I加入面a, 面b, 面c
}
}
}我们得到了凸多面体的所有多边形面，但是面上的点顺序是不定的。要正确绘制一个多边形，还要将这些面按顺时针或逆时针排好序（因为是凸多边形，可以很方便的排序，原文中有排序算法，这里不做赘述），最后我们把多边形分割成三角形就可以进行渲染了。
然而，上面的方法有缺陷，有一种情况需要额外考虑：
图中红色虚线三个面的交点显然位于固体外，应该被剔除掉。要剔除掉这种顶点也不困难，依旧需要凸多面体的特性： 对凸多面体上的一个顶点P，任意指定一个面F，顶点P一定在面F的后方（包括正好在面上）。换句话说，如果一个点在凸多面体外部，那么它一定在凸多面体的某个面“前方”。因此，对每个顶点，只需要测试它是否在每个面后方（包括正好在面上），就知道需不需要剔除它了。比如上图的例子中，固体外的点P位于面F1的前方，不满足条件，因此需要被剔除。
纹理贴附 有了三角形，还要把纹理贴上去，纹理给简单的三角形增加了漫反射信息，这样一来，这些三角形便拥有了材质，让它看起来像某种东西了。map文件中不包含纹理图片，而是存储在wad文件中，map文件所需的wad文件列表在worldspawn实体的wad键值中，每个wad文件路径由分号(;)隔开。 得到了纹理图片，接下来要算出纹理坐标。纹理的贴附是通过纹理坐标实现的，给顶点指定纹理坐标，便能从纹理里找到每个像素对应的颜色。计算纹理坐标需要用到UV的方向、偏移量和缩放，每个面都附带这些数据：
// (x1 y1 z1) (x2 y2 z2) (x3 y3 z3) 纹理名称 [ ux uy uz u偏移量] [ vx vy vz v偏移量 ] 旋转量（角度） u缩放 v缩放
( -10 -10 10 ) ( -10 10 10 ) ( 10 10 10 ) WHITE [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 一般而言我们使用规范化纹理坐标，纹理坐标的范围在[0,1]之间。规范化纹理坐标的计算公式如下：
其中p是顶点，u和v对应uv方向，su和sv对应uv缩放，ou和ov对应uv偏移量，而w和h分别代表纹理宽度和高度。 （关于wad文件的格式和解析，以及UV坐标的意义，都在简单解析第一期中详细解释了 cv4682202）
最后得到的渲染效果：
注意：Stefan Hajnoczi大佬的文章中还介绍了CSG算法以减少不可见面，为生成BSP树做准备，以及BSP树的生成，不在本文范围内，这里也不做赘述（其实我也还没看哈哈）
3.2 rmf文件的解析和渲染
rmf文件的解析和渲染简单许多。它直接保存了固体的面以及上面的顶点，可以直接生成三角形用于渲染。 rmf文件的物体数据都存储在RmfWorld中，其中包含了若干个实体和固体，一个实体中又包含了若干固体，这里只需要把固体数据都解析出来。 固体的数据也非常简单，一个固体有很多个面，面数据里包含了面的所有顶点，用于生成三角形，并且包含了纹理贴附信息，用于索引、贴附纹理。
注意：rmf文件中不包含任何wad的路径信息，因为决定wad路径的是VHE的设置。
3.3 bsp文件的解析和渲染
bsp中存在和rmf中类似的面数据，以数组形式保存在面数据块种。每个面数据其中保存了索引，通过索引可以找到面的顶点和纹理贴附数据。 理论上读取所有这些面并绘制，就可以得到整个地图的结果，这其中会涉及一些问题，下面会逐一讲解。
隐藏面消除 场景里有两个方块1和2，我们在渲染时应该先绘制方块1还是方块2呢？
之所以绘制顺序很重要，是因为渲染的结果类似一张图片，后物体会覆盖掉前面渲染的物体。如果我们使用的绘制的顺序有误，会导致结果看起来奇怪。
那么要怎么确定正确的渲染顺序呢？
画家算法（Painter's Algorithm) 现实中，近的物体会挡住远的物体。要让渲染看起来自然，把物体从后往前排序，然后依次渲染不就行了吗。就像绘画时，画家会先绘制远景，然后在远景的上面叠加中景，最后再叠加上近景，这便是画家算法的思想。
画家算法
画家算法简单易实现，但有很大的缺陷。让我们来看一下更复杂的情况，图中两个面相互交叉，这种情况下，无论先绘制谁，结果都是有误的：
画家算法无法解决交叉物体绘制的问题，我们需要更强大的算法...
深度缓冲算法（Z-buffer Algorithm) 现在我们知道，简单对物体排序不能解决全部问题，我们需要粒度更小的算法。 之前提到，渲染的结果类似一张图片，图片的单位是像素，我们可以把渲染的每个像素保存下来，并记录它的远近（称为深度）。等所有物体都渲染完了，对像素排序，从远到近渲染，这样我们把排序的粒度降到像素级。当然，因为近的像素会覆盖远的像素，所以只需要渲染最近的像素就够了，在渲染过程中我们只记录最近的像素，就可以避免最后排序了。记录最近距离使用了一张灰度图，它被称为深度缓冲；判断当前像素是覆盖还是丢弃的过程叫做深度测试。
经过颜色变换后便于观察的深度图，越白代表越近，越黑代表越远
利用深度缓冲算法，我们总算解决了交叉物体渲染的问题。 然而深度缓冲算法依旧不是万能的。图中蓝色方块在后，红色方块在前，而红色方块是半透明的。
使用深度缓冲算法后，近的像素会粗暴的覆盖远的像素，不再能透过红色方块看到蓝色方块了，透明效果会变得奇怪。
既然覆盖会出问题，那么我们不再粗暴的覆盖，而是把前后两种颜色“混合”在一起呢？
透明物体的混合常使用AlphaBlend算法：对两个颜色A和B，将B混合到A，结果C为：
这样，我们得到了正确的结果，吗？
不幸的是，混合是顺序依赖的，这意味着把“B混合到A”和“把A混合到B”的结果是不同的，这也是导致会出现两种结果的原因。要混合的颜色正确，就要保证像素是从后向前混合的，而深度缓冲不能保证这一点。有趣的是，因为画家算法始终是从后向前渲染的，它可以很好地解决半透明物体的问题。 这类问题属于次序无关的半透明（OIT, Order-Independent Transparency）渲染。解决OIT有许多方法，它们不在我们的讨论范围内。而本文的主角，BSP二元空间划分，在一定程度上也可以解决OIT问题。
3.3.1 二元空间划分（Binary Space Partition, BSP）
“众所周知”，金源游戏中是有许多半透明物体的，物体交叉也是“完全允许”的，所以单纯的画家算法或是深度缓冲算法都不足以处理其渲染。金源引擎使用了二元空间划分（以下简称BSP）技术，解决了物体交叉，优化渲染流程，一定程度上也可以解决半透明渲染。 BSP将场景转换为一颗二叉树，树每个内部节点对应一个切割平面，它将一个区域分割成两个子区域；树的每个叶节点对应场景的一个区域。在生成BSP的同时，通过不断生成切割平面，切开物体，并将空间划分成一个个小的区域，最后不再有交叉的物体存在。因为没有交叉物体，一个区域可以直接使用画家算法渲染，而区域和区域之前的先后关系，也可以使用BSP树进行判断。
BSP树的生成 只听了BSP的功能，大概会比较懵吧。现在我们试着手动生成一个BSP树，这能帮助你理解BSP树的设计理念。生成BSP树的方法很简单，这里以2D俯视角进行说明，假设有这么一个场景，里面有F1-F4四个面：
我们随机选择一个面，比如F1，将它作为切割平面，将场景切成两个部分，并得到二叉树的根节点，同时生成两个子节点。根节点包含了正好在切割平面上的面，而两个子节点分别包含两侧的物体：
F1将F2切割成F2-1和F2-2两个部分
现在空间被分成两个部分了，我们对这两部分重复上面的操作：随机选择一个面，作为切割面将这部分场景分成两个部分，同样生成两个子节点。比如对左子节点，我们选择F3作为切割平面：
切割后一个部分没有物体了，对应的子节点是叶节点，代表了一个区域
重复这个过程，依次选择F2-1，F4，F2-2作为切割平面。最后场景便被转换成了一颗二叉树了。
F2-1
F4
F2-2
回到之前的问题，我们怎么判断先绘制哪个区域呢？ 假设相机位置如下：
按照画家算法的思想，我们希望从后往前绘制物体。如果以F为切割平面，F将空间分成两个部分，而相机处于平面的前方，那么我们只用按平面后->平面上->平面前的顺序绘制就可以了。反之如果相机在平面后面，那么按照平面前->平面上->平面后的顺序绘制。 而对于“平面前”和“平面后”，使用同样的方法，绘制它们的“平面前”和“平面后”，直到到达一个完整区域。因为这个区域内的物体不存在交叉，使用画家算法排序绘制即可。 这个过程反映在BSP树上，就是对BSP树的一次中序遍历。
BSP树遍历动画
绘制bsp文件 bsp文件中包含了上述的BSP树信息，内部节点对应了NODE块，叶节点对应了LEAF块。将BSP还原后，首先从根节点进行中序遍历绘制即可。 其实，BSP树还没有发挥出其优势，因为bsp文件中的BSP树存储的都是固体信息，不存在半透明物体。然而除了固体数据，bsp文件还有实体数据需要绘制，绘制实体时，需要判断实体位于BSP树的哪个叶节点，并在其叶节点绘制时一起绘制，便可以得到正确的结果。
4 结语
这篇文章的筹备也是很久了，开始写文章之前，花了整个寒假开发渲染器，初次接触Vulkan和ImGui的开发也踩了很多坑，不过踩坑说明能学到东西嘛，事实上也学到了挺多的。 BSP地图是BSP技术第一次在游戏行业应用，其背后的Quake引擎也是图形学技术应用的一大里程碑。透过这些文件的设计，可以看到开发者的思想，看到他们为高质高效渲染做出的努力。正是他们的努力，这些游戏才得以在当初的电脑配置下流畅运行，保证良好的游戏体验。我认为这是宝贵的财富，并且值得我花时间整理并分享给各位。 最后非常感谢各位看到这里，感谢各位一直以来的支持，下期再见！
上期地址：【简单解析】VHE冷知识 CV5299107
5 参考文献
(rmf格式的V社官方维基) Rich Map Format, https://developer.valvesoftware.com/wiki/Rich_Map_Format
(vmf格式的V社官方维基) Valve Map Format, https://developer.valvesoftware.com/wiki/Valve_Map_Format
(很不错的金源bsp文件结构说明，但对每个块的解析说明太少) Unofficial bsp v30 File Spec, http://hlbsp.sourceforge.net/index.php?content=bspdef
(一篇Quake2 bsp文件的解析) Dissecting the Quake 2 BSP format, http://jheriko-rtw.blogspot.com/2010/11/dissecting-quake-2-bsp-format.html (GLToy)https://github.com/semiessessi/gltoy-from-google-code
(一个用Pascal写的金源bsp渲染器，虽然没有找到源码，但下面的参考文献给我了帮助) The GoldSrc BSP Loader, https://www.freepascal-meets-sdl.net/the-goldsrc-bsp-loader/
(另一个Pscal写的金源bsp渲染器，可视化和交互效果很棒，对我帮助非常大) GldSrcBSPditor, https://github.com/Sergey-KoRJiK/GldSrcBSPditor
(非常非常非常NB的map文件解析说明！甚至包含了解析所需算法的详细说明) map-files, https://github.com/stefanha/map-files
(一篇关于VIS数据解码的讨论) Half-Life/Quake BSP : Understanding the PVS, https://gamedev.net/forums/topic/504049-half-lifequake-bsp-understanding-the-pvs/4297228/
6 附录
注意：为方便查阅，附录会保留正文中对数据块的说明，同时使用C/C++的语法展示各个块的数据结构。
6.1 rmf详细格式
rmf是二进制格式，需要用二进制的方式读取，在讲文件的结构前，需要了解一些数据结构：
// 一些数据结构的命名参考C/C++标准
int 32位有符号整型
uint32_t 32位无符号整型
uint8_t 8位无符号整型，因为只有8位，所以表示范围是[0, 255]的整数
char 8位字符，使用ASCII编码，可以表示英文字母及标点
char[n] 长度为n的字符串，注意字符串末尾需要有\0作为终止符，且长度n里包含了终止符
nstring 可变长度字符串，开头是一个uint8_t表示字符串长度n，后紧跟着一个char[n]
float 浮点型数据，占4字节，用于表示小数
vector<T> 动态数组，元素的类型为T
RmfColor 存储一个颜色值，24位RGB，结构如下
struct RmfColor
{
uint8_t R, G, B;
}
RmfVec3 存储一个3D坐标点，每个轴对应一个float，结构如下
struct RmfVec3
{
float X, Y, Z;
}以下是rmf文件的基本格式，用C/C++的语法风格表示
struct Rmf
{
float Version; // 版本号，约等于2.2，十六进制数据为CD CC 0C 40
char Magic[3]; // 魔数，始终等于"RMF"
int VisGroupNum = 0; // 可见组的数量
vector<RmfVisGroup> VisGroups; // 可见组（使用隐藏、显示工具制作）
RmfWorld World; // 地图数据，包含了固体、实体、组的信息
int PathNum = 0; // 路径数量
vector<RmfPath>Paths; // 路径（使用路径工具制作）
char Mark[8]; // 标记字符串，始终等于"DOCINFO\0"
float CameraDataVersion; // 大概是相机数据的版本
int ActiveCameraIndex = 0; // 当前使用的相机索引，如果没有相机则是-1
int CameraNum = 0; // 相机数量
vector<RmfCamera>Cameras; // 相机（使用摄像机工具制作）
}RmfWorld的结构比较复杂，我们最后再讲 RmfVisGroup是可见组的信息，结构如下：
struct RmfVisGroup
{
char Name[128]; // 可见组的名称
RmfColor Color; // 显示颜色（指VHE中2D视图的物体边框颜色）
char Unknown; // 未知
int Index; // 可见组索引，在物体中有引用
uint8_t IsVisible; // 是否可见，1代表可见，0代表不可见
char Unknown2[3]; // 未知
}RmfPath是路径的信息，结构如下：
// 一条路径
struct RmfPath
{
char Name[128]; // 路径的名称，用于路径点名称的生成
char ClassName[128]; // 路径的点实体类型，"path_corner"或者"path_track"
int PathType; // 路径类型，0=单程，1=循环，2=往返
int CornerNum; // 路径点数量
vector<RmfCorner> Corners; // 路径点，按顺序排列
}
// 路径中的一个路径点
struct RmfCorner
{
RmfVec3 Origin; // 路径点原点
int Index; // 索引号，用生成路径名称
char Name[128]; // 节点名称
int PropertyNum; // 属性数量
vector<RmfProperty>Properties; // 属性
}
// 实体属性，后面的实体也会用到
struct RmfProperty
{
nstring Key; // 变长字符串，属性的键名
nstring Value; // 变长字符串，属性的值
}RmfCamera是相机的信息，结构如下：
struct RmfCamera
{
RmfVec3 EyePosition; // 摄像机位置
RmfVec3 Direction; // 摄像机朝向
}以上这些数据和地图的几何数据都无关，物体的几何数据都在RmfWorld结构中。rmf中一共有四种物体，世界（World）、固体（Solid）、实体（Entity）和组（Group），他们拥有类似的头部结构：
// 四种物体头部是相同的，这里以继承表示
struct RmfObject
{
nstring Type; // 物体类型，可以是"CMapWorld"、"CMapSolid"、"CMapEntity"或者"CMapGroup"
int VisGroupIndex; // 可见组索引
RmfColor Color; // 显示颜色，即VHE中2D视图显示的物体颜色
}一个rmf中只包含一个RmfWorld，它的结构是这样的
struct RmfWorld : RmfObject
{
// 开头是继承自RmfObject的三个属性，以下是特有的属性
int ObjectNum; // 物体数量
vector<RmfObject*> Objects; // 物体，可能是固体、实体或者组
nstring ClassName; // 始终等于"worldspawn"
char Unknown[4]; // 未知
int EntityFlags; // 实体标记，应该未使用
int PropertyNum; // 属性数量
vector<RmfEntityProperty>Properties; // 属性，一般包含"classname" = "worldspawn", "MaxRange" = "32768", "mapversion" = "220"等
char Unknown2[12]; // 未知
};RmfObject*这里使用了一个RmfObject指针，代表它可能是固体RmfSolid，实体RmfEntity或者组RmfGroup，下面是这三种物体的结构
/*
* RmfSolid包含了固体信息
*/
struct RmfSolid : RmfObject
{
// 开头是继承自RmfObject的三个属性，以下是特有的属性
char Unknown[4]; // 未知
int FaceNum; // 面数量
vector<RmfFace> Faces; // 面，一个固体包含很多个面
};
/*
* RmfFace包含了一个面的顶点位置和纹理信息
* 和map中不同，这里直接保存了顶点位置
*/
struct RmfFace
{
char TextureName[256]; // 纹理名称
float Unknown; // 未知
// 以下是纹理坐标、缩放、偏移和旋转角
RmfVec3 TextureDirectionU;
float TextureOffsetU;
RmfVec3 TextureDirectionV;
float TextureOffsetV;
float TextureRotation; // 旋转量冗余数据，用于VHE编辑，实际存储的UV方向是已经旋转过的
float TextureScaleU;
float TextureScaleV;
char Unknown2[16]; // 未知
int VertexNum; // 顶点数量
vector<RmfVec3>Vertices; // 顶点，顺时针方向
RmfVec3 PlanePoints[3]; // 对应的平面，冗余数据，VHE直接使用前三个顶点计算平面
}
/*
* RmfEntity包含了实体信息，如实体属性和实体包含的固体
* 不需要存储实体的全部可用属性，没有列出来的属性默认为空值
*/
struct RmfEntity : RmfObject
{
int SolidNum; // 固体数量，点实体的固体数量为0
vector<RmfSolid*>Solids; // 固体
nstring ClassName; // 实体类型，最大128字节
char Unknown[4]; // 未知
int EntityFlags; // 实体标记（对应VHE中实体属性里的标记）
int PropertyNum; // 属性数量
vector<RmfProperty>Properties; // 实体属性
char Unknown2[14]; // 未知
RmfVec3 Origin; // 实体原点位置
char Unknown3[4]; // 未知
};
/*
* RmfGroup包含了组信息，一个组里可以有固体、实体以及其他组（形成嵌套组）
*/
struct RmfGroup : RmfObject
{
int ObjectNum; // 物体数量
vector<RmfObject*>Objects; // 物体
};基于以上内容，便可以解析出rmf中的地图数据了。
6.2 bsp详细格式
bsp的格式最复杂，它除了包含几何数据，还包含了许多编译后产生的额外数据，解析的步骤较多。 bsp文件也是二进制文件，文件主要有两个版块：头部（Header）和块（Lump）。 bsp的头部包含bsp版本信息，以及块的位置信息：
struct BspHeader
{
int BspVersion; // 对于金源引擎，版本始终为30
BspLumpInfo LumpInfos[15]; // 各个块的信息
}
struct BspLumpInfo
{
int Offset; // 块相对文件开头的偏移量
int Size; // 块的大小，单位为字节
}之前提到，bsp文件中一共有15个块，下面会详细介绍每个块的存储结构。
6.2.1 实体数据块
实体数据块中，实体信息以字符串的形式存储，格式和map中的实体基本一致，唯一的区别在于，实体中不再包含固体的信息，而是使用一个属性"model" "*n"，对应到实体模型数据中的物体。如一个实体中有"model" "*9"的属性，说明⑨号实体模型属于这个实体。
struct LumpEntity
{
vector<char> Data;
}6.2.2 平面数据块
以数组形式存储地图中用到的所有的平面。bsp里的平面用单位法向+到原点的有向距离表示，对应了平面的一般式：
其具体结构如下：
struct BspVec3 // 和RmfVec3相同
{
float X, Y, Z;
}
enum class PlaneType
{
X = 0, // 垂直于X轴
Y = 1, // 垂直于Y轴
Z = 2, // 垂直于Z轴
ANY_X = 3, // 法线靠近X轴
ANY_Y = 4, // 法线靠近Y轴
ANY_Z = 5 // 法线靠近Z轴
}
struct BspPlane
{
BspVec3 Normal; // 归一化的法向
float DistanceToOrigin; // 到原点的有向距离
int32_t Type; // 平面类型PlaneType，属于冗余信息，大概是用于计算加速？
}
struct LumpPlane
{
vector<BspPlane> Planes;
}6.2.3 纹理数据块
以数组形式存储用到的纹理，包括纹理名称，大小等。你可把纹理数据直接存储在bsp文件中，或者存储在wad文件中，但无论如何，所有使用的纹理都会在这里有记录，并且一定存有纹理名称和纹理大小。 本块的结构如下：
struct BspColor // 和RmfColor相同
{
uint8_t R, G, B;
}
struct BspTexture
{
char Name[16]; // 纹理名称
uint32_t Width, Height; // 纹理大小
uint32_t Offsets[4]; // 数据偏移量（以本结构体的起始位置开始计算）
// 数组大小为4，因为金源使用了4层的mipmap，四个偏移量分别对应四张图片的数据
// 如果偏移量为0，代表纹理未存储在bsp文件中，需要使用纹理名称去wad文件中查找纹理数据
}
struct LumpTexture
{
uint32_t NumTexture; // 纹理数量
vector<int32_t> TexOffsets; // 每张纹理的起始偏移量（以本结构体的起始位置开始计算）
vector<BspTexture>Textures; // 纹理
}如果纹理存储在bsp中，其存储格式和WAD中相同，都是8位索引存储+调色板，4层mipmap
// 对一张宽m，高m的纹理
uint8_t Mipmap1[m*n];
uint8_t Mipmap2[m*n/4];
uint8_t Mipmap3[m*n/16];
uint8_t Mipmap4[m*n/64];
uint16_t PaletteSize; // =256
BspColor Palette[256];
uint16_t Padding;6.2.4 顶点数据块
以数组形式存储了所有顶点的数据。
struct LumpVertex
{
vector<BspVec3> Vertices;
}6.2.5 可见性数据块
存储了编译VIS阶段生成的VIS信息，VIS信息被用于可见性检测，用来剔除掉不可见的区域，优化渲染效率。可见性数据的读取非常简单，它是单纯的“位”（bit）数组。 C/C++中不方便以“位”为单位处理数据，这里直接当作字节（byte，这里用uint8_t替代）读取即可。
struct LumpVisibility
{
vector<uint8_t> Vis;
}6.2.6 内部节点数据块
以数组形式存储了BSP树的内部节点，一个节点存储了平面、子节点以及其包含的面的信息。
struct BspNode
{
uint32_t PlaneIndex; // 切割平面的索引
int16_t ChildrenIndices[2]; // >0前后子节点的索引，<=0则按位取反得到叶节点索引
int16_t BoundingBoxMin[3]; // 包围盒最小值，BSP使用AABB（Axis-Aligned Bounding Box)
int16_t BoundingBoxMax[3]; // 包围盒最大值，BSP使用AABB（Axis-Aligned Bounding Box)
// 关于包围盒，在第一篇简单解析WAD文件中有说明
uint16_t FirstFaceIndex; // 起始面索引
uint16_t NumFace; // 面的数量
}
struct LumpNode
{
vector<BspNode>Nodes;
}6.2.7 纹理贴附数据块
以数组的形式存储了纹理的贴附信息，包括UV坐标、偏移量、使用的纹理索引。
struct BspTexInfo
{
// UV坐标方向和偏移量
BspVec3 TextureDirectionU;
float TextureOffsetU;
BspVec3 TextureDirectionV;
float TextureOffsetV;
uint32_t TextureIndex; // 纹理索引，对应纹理数据块
uint32_t Flags; // 作用未知，似乎总是0
}
struct LumpTexInfo
{
vector<BspTexInfo> TexInfos;
}6.2.8 面数据块
以数组形式存储了所有面的信息，包括所属平面，方向，包含的边，纹理贴附数据的索引以及光照信息索引。
struct BspFace
{
uint16_t PlaneIndex; // 所属平面索引
uint16_t PlaneSide; // 朝向，0=和平面法线相同，1=和平面法线相反
uint32_t FirstSurfedgeIndex; // 边索引过渡数据的索引
uint16_t NumSurfedge; // 边数量
uint16_t TexInfoIndex; // 纹理贴附数据索引
uint8_t LightingStyles[4]; // 光照样式
uint32_t LightmapOffset; // 光照数据偏移量
}
struct LumpFace
{
vector<BspFace> Faces;
}6.2.9 光照数据块
以数组形式存储了所有面的光照数据。金源使用了Lightmap烘焙技术，即在地图编译时计算光照，并将亮度、阴影等信息写入贴图中，之后使用无需计算光照，直接使用预先计算的贴图覆盖在原贴图上即可达到静态光照的视觉效果。这个数据块存储的就是这些贴图，称为Lightmap。所以所谓光照数据，其实就是一张张贴图。 每一个面都对应了一张Lightmap，但这个块中并没有存储面和光照贴图的对应关系，要读取一个面对应的光照贴图，需要一些较复杂的计算，这会在之后的文章中说明。光照数据块是简单的颜色数组：
struct LumpLightmap
{
vector<BspColor> Lightmaps;
}6.2.10 碰撞节点数据块
以数组形式存储了存储了碰撞节点。碰撞节点属于碰撞BSP树，专用于碰撞检测，和渲染没有关系。
enum class BspContent
{
EMPTY = -1,
SOLID = -2,
WATER = -3,
SLIME = -4,
LAVA = -5,
SKY = -6,
ORIGIN = -7,
CLIP = -8,
CURRENT_0 = -9,
CURRENT_90 = -10,
CURRENT_180 = -11,
CURRENT_270 = -12,
CURRENT_UP = -13,
CURRENT_DOWN = -14,
TRANSLUCENT = -15
};
struct BspClipNode
{
int32_t PlaneIndex; // 所属平面索引
int16_t ChildrenIndices[2]; // >0代表子节点索引，<0代表子节点是叶节点，值对应了内容类型BspContent
}
struct LumpClipNode
{
vector<BspClipNode>ClipNodes;
}6.2.11 叶节点数据块
以数组形式存储了bsp中所有叶节点。叶节点是金源引擎的渲染单位之一，存储了VIS、包围盒和包含的面等信息。
struct BspLeaf
{
int32_t Content; // 内容类型，和上一节的BspContent对应
int32_t VisOffset; // 可见性数据的索引
int16_t BoundingBoxMin[3]; // 包围盒
int16_t BoundingBoxMax[3]; // 包围盒
uint16_t FirstMarkSurfaceIndex; // 面索引过渡数据的索引
uint16_t NumMarkSurface; // 面数量
uint8_t AmbientLevels[4]; // 音效等级？可能和声音传播有关
}
struct LumpLeaf
{
vector<BspLeaf> Leaves;
}6.2.12 面索引过渡数据块
名称有些拗口，但功能很简单。块中只有一个uint16_t的数组，每一个uint16_t都对应了一个面（LumpFace）的索引，起到过渡的作用。比如叶节点存储的就是面索引过渡数据，通过过渡数据可以找到对应的面数据。
struct LumpMarkSurface
{
vector<uint16_t> FaceIndices;
}6.2.13 边数据块
以数组形式存储了边的数据。一条边包含两个顶点。
struct BspEdge
{
uint16_t VertexIndices[2]; // 一条边包含起始和终止两个顶点的索引
}
struct LumpEdge
{
vector<LumpEdge> Edges;
}6.2.14 边索引过渡数据块
和“面索引过渡数据”相似，块中只有一个int16_t的数组，每一个int16_t都对应了一个边（LumpEdge）的索引，起过渡作用。 注意，这里用的是有符号的整型，有符号的索引还能代表边的方向。索引的绝对值对应了一条边，而>0指方向是从点0到点1，而<0指方向是从点1到点0。
struct LumpSurfedge
{
vector<int16_t> EdgeIndices;
}6.2.15 实体模型数据块
以数组形式存储了实体对应的固体信息，它和叶节点存储的数据类似，且也是金源引擎渲染的一个单位。
struct BspModel
{
float BoundingBoxMin[3]; // 包围盒
float BoundingBoxMax[3]; // 包围盒
BspVec3 Origin; // 实体原点，也是变换的基准点
int32_t NodeIndices[4]; // 分别是BSP以及三个碰撞BSP的节点（具体作用我还没有完全弄清楚，第一个值应该是会影响渲染的）
int32_t VisLeafs; // 也许是实体可能出现的VIS索引，用位域（bitfield）表示
int32_t FirstFaceIndex; // 面起始索引
int32_t NumFaces; // 面数量
};
struct LumpModel
{
vector<BspModel> Models;
}从文件头到各个块都是按顺序存储的，按照以上的顺序读取即可。
