本文系用户投稿，不代表机核网观点
本文含有AI生成，请注意甄别
最近重听了重轻老师《游戏帝国》里关于id software的两期节目，感觉卡马克实在太厉害了，但是具体怎么厉害的确实没听明白，就让GPT找了几篇好懂的文章想具体了解一下id引擎的技术。
最先吸引我注意的是这篇文章： How Much of a Genius-Level Move Was Using Binary Space Partitioning in Doom? 深入浅出地介绍了DOOM的图形技术的来源和原理，对BSP的介绍也很明白。更有意思的是里面说卡马克在《德军总部3D》中使用raycasting技术来实现3D效果，而他后来在把游戏移植到SFC这个性能更差的平台时，第一次使用了BSP技术来提升表现；然后这个技术才用在了DOOM上。
以下是相关的可参考的源代码：
《德军总部3D》的mac移植版，这个版本基于SFC版，可以近似看作BFS的初登场： Blzut3/Wolf3D-Mac: The original Macintosh Wolfenstein 3D source release.
一个芬兰老哥的手搓3D引擎的视频，但是这个技术好像是build引擎、也就是《毁灭公爵3D》所使用的： Creating a Doom-style 3D engine in C - YouTube 。这位老哥的效果非常厉害，但是我不懂C所以请大家自己在视频简介中查看吧。
- 《德军总部3D》与raycasting
《德军总部3D》的地图是非常简单的，墙只能横向或纵向排列且必须贴合固定网格，高度也是固定的。通道或说走廊的宽度也只能是整数个网格单位，俯视来看就像围棋格子一样。
因此，它可以使用一种相对简单的 ray casting（射线投射）：从屏幕的每一列发出一条射线、沿着网格边界逐步检查，射线遇到的第一面墙就是该列应该显示的墙。
基本思路如下：地图是一个二维的方形网格结构，每个方格要么为 0（即没有墙壁），要么包含一个正数值（即具有特定颜色或纹理的墙壁）。对于屏幕上的每一个x坐标点（即屏幕上的每一个垂直条带），都发射一束光线。这束光线的起点是玩家的位置，其方向取决于玩家的视线方向以及屏幕上该点的 x 坐标。然后，让这束光线在二维地图上向前移动，直到它撞到一个墙所在的地图格子。如果光线撞到了墙，那么需要计算这个撞击点距离玩家的距离，并利用这个距离来确定墙在屏幕上应该绘制的高度：墙离得越远，它在屏幕上的显示尺寸就越小；而越近的墙，在屏幕上看起来就越高。这些都是二维计算问题。
但问题是，该如何确认某条射线会撞到哪一面墙？ 最直接的办法是沿着射线方向一点一点移动，但是如果步长太大，可能直接跳过一面很薄的墙；步长太小，需要大量计算。这里就引入了DDA（Digital Differential Analysis）技术，它不按固定距离前进，而是每次直接走到射线碰到的下一条网格边界。
因为游戏地图实际上是正方形网格构成的，所以射线经过地图时，只会不断穿过水平网格线和竖直网格线。 程序每次比较到下一条竖线的距离和到下一条横线的距离，哪一个更近就先跨过哪一条网格线。射线每跨过一次边界，就进入相邻地图格子。如果这个各自是墙，那就停止，然后返回距离即可。
DDA找到墙壁后，我们就知道了某条射线撞到了哪个地图格子、撞到的是哪一侧、射线经过了多远。接下来就是绘制墙的高度。但如果我们直接使用玩家位置（这是一个点）到射线与墙壁交点的距离，就会导致视野发生畸变。
比如说玩家正对着一面平直的墙壁，那视角边缘射线到墙的距离比视角中央到墙的距离更远，绘制出来就使得中央墙柱较高、左右墙柱更矮，一面平直的墙会看起来像弯曲的鱼眼镜头。 正确做法是使用墙面交点到相机平面的垂直距离，即墙在玩家视线方向上的深度。这样才能避免鱼眼效果。
最后一句话总结： 游戏世界其实是一张二维平面网格地图。程序从玩家位置向屏幕的每一列发出一条射线，找到射线首先碰到的墙，再根据墙的远近决定这一列应该画多高。
2.我们的代码实现（这部分AI比人干的多得多）
为了尽可能降低复杂度，我只绘制了一个长方形房间，里面放了两根柱子。墙和柱子如上所述，都严格符合网格，且高度是一定的。 相机前方是一块虚拟投影平面，屏幕每一竖列对应平面上的一点，从眼睛过该点发出的射线只会命中第一面墙——第一命中即该列的最终画面。由于我们的绘制分辨率为320X200，三维可见性问题就此拆解为 320 个互相独立的一维查找问题，每个问题分四步：
- 列射线：以单位朝向向量 direction 与垂直于它的相机平面 plane = (−sin a, cos a)·tan(FOV/2) 定义相机；屏幕列线性映射为平面偏移 camera_x ∈ [−1,1]，射线 = direction + plane·camera_x。由于 plane ⟂ direction 且 |direction| = 1，所有射线满足 ray · direction = 1——这是后面免乘法去鱼眼的根基。
- DDA 网格步进：固定步长采样要么漏过薄墙、要么成本失控。DDA（数字微分分析）改为解析求解射线与下一条网格线的交点：预计算跨一格所需的参数增量 deltaDist = |1/rayDir| 与到首条边界的初始量 sideDist，每轮比较两方向、跳过较近的边界并检查新格。射线只访问它真正经过的格子，查找次数恰为穿越格数。
- 前向距离：屏幕边缘的射线斜穿同一面墙，欧氏距离更长，直接投影会使直墙两端变矮、整体外凸（鱼眼）。校正法是将命中距离投影到视线方向，得到垂直于相机平面的前向距离。
- 墙柱投影：相似三角形给出 H_screen = f·H_world / d（d 为前向距离）。墙柱以地平线为轴对称展开，近高远低，单列绘制成本为常数。
主干整体复杂度为 O(列数 × 平均穿越格数)，无排序、无遮挡判定、无 overdraw。我没有实现纹理、HUD、精灵图、移动墙壁、距离亮度衰减。而原版的性能工程也同样厉害，比如为符合硬件特性而做的16位定点整数运算、 直写 VGA 显存等等……这些都没有涉及。
3.DOOM与BSP树
早期3D游戏开发最困难的问题之一，是可见表面确定问题（Visible Surface Determination，VSD），具体来说：从当前视点看，哪些墙、地面、物体能被看到？哪些物体被其他物体挡住？而这些判断必须每秒完成几十次。
在 1990 年代初，IBM PC 的 VGA 显存写入非常昂贵，因此“先画远处、再用近处覆盖”并不理想。理想做法是先绘制离玩家最近的几何体，已经覆盖的屏幕区域就不再处理，从而避免绘制后面看不见的东西。但要做到这一点，首先必须知道物体的前后关系，也就是解决上述的VSD问题。
《德军总部3D》的世界是高度简化的，但是Doom 的目标场景复杂得多，需要支持非水平、非垂直的平面墙体，不同高度的地板和天花板，窗户等，如果继续使用上述风格的网格射线投射，原有假设会被破坏。墙不再一定落在网格边界上，射线也不能只检查固定的网格交点。
起初，卡马克试图通过设计《DOOM》中的关卡布局来解决这个问题。他的渲染引擎会先绘制玩家当前所在房间的墙壁，然后再扩展到相邻的房间，绘制从当前房间能够看到的那些墙壁。只要每个房间都是凸形的，就能解决视觉遮挡问题。对于那些非凸形的房间，则可以将其分割成多个凸形“区域”。在 Creating a Doom-style 3D engine in C - YouTube 中演示的正是这种方法。这一算法在《DOOM》发布三年后推出的《毁灭公爵3D》中得到了成功应用，当时 CPU 的性能已经更强了。不过以1993 年的硬件条件，使用这种算法的《DOOM》渲染引擎在处理复杂的关卡时遇到了困难，尤其是当各个区域相互嵌套时。 就在id Software意识到这种游戏引擎过于缓慢的时候，id Software又被要求将《德军总部 3D》移植到SNES上：它的性能比当时的主流PC要差，结果《德军总部 3D》中的raycasting技术在SNES上无法高效运行。于是，卡马克开始寻找更合适的算法。实际上，正是为了《德军总部 3D》的SNES移植版，卡马克首次研究了BSP技术并将其付诸实践。在《德军总部 3D》中，由于所有墙壁都是沿网格排列的，因此应用BSP技术相对简单；而在《DOOM》中，情况则要复杂得多。
BSP（Binary Space Partitioning，二叉空间划分）的想法其实很直观，与其在玩家移动后重新给所有墙壁排序，不如事先把整个地图切成一棵树，以后只要知道玩家位于每条分割线的哪一边，就能按正确的空间前后关系访问地图。它在DOOM中分为构建和渲染两个阶段。
首先是BSP树构建阶段。假设我们画了一个L形房间。它的两条走廊在拐角处连在一起；站在一端时，另一端的一部分墙壁会被转角挡住。现在选取房间里某段墙所在的直线，把这条直线向两端无限延长，将整个二维平面分成两侧。注意，作为分割依据的直线不等于真实墙壁，它经过房间内部的部分只是一条虚拟边界，不能因为它出现在BSP里，就在游戏中凭空画出一道墙。
接着检查地图里的每一条墙段（Seg）。如果它完全位于分割线的一侧，就归到对应一侧；如果它跨过分割线，就算出交点，把原来的一段墙切成两段，分别归入两侧。然后对两个子区域重复这套操作。原始的节点构建器还要挑选比较合适的分割线，尽量让树不要太偏，同时避免把过多墙壁切得七零八落。构建结束后就得到一棵描述空间划分关系的二叉树。
这里有一个理解DOOM原版非常重要的细节：BSP的内部节点（Node）只保存分割直线、两个子节点及其包围盒；真正要绘制的墙段保存在树末端的子区域（Subsector）里。这与上面图里描述的，把被选中的墙壁留在树杈上的经典BSP画家算法有所区别。一个Subsector可以只关联一部分真实墙段，因为它的其余边界可能只是BSP划分产生的虚拟边界。并不要求一个Subsector里的墙段自己围成完整的房间。
这样，开发者可以把地图预先绘制、编译好，直接把生成的NODES、SSECTORS、SEGS等数据保存到WAD文件中。玩家进入关卡时不需要现场把整个地图再切一遍，BSP已经准备好了。只要地图的二维布局没有改变，不管玩家在房间里怎么走，树都不用重新构建，只需在进入游戏后的渲染阶段遍历树即可。
然后是渲染阶段。现在玩家站在某个位置，程序从BSP的根节点出发。每遇到一条分割线，就判断玩家位于它哪一侧，先递归访问玩家所在的那一侧，再考虑另一侧。因为沿着从玩家发出的视线，要到达分割线另一侧，必然先经过玩家这一侧，所以这给渲染器提供了一种有用的由近到远的访问次序。注意，这不是说前子树里每个点到玩家的欧氏距离都比后子树近，而是说它们在穿越分割线的视线方向上具有确定的前后关系。
可以想象成玩家站在一堵拐角墙后：程序先走访玩家这边的空间，把可能露在画面中的墙处理掉，再去检查墙后的空间。如果近处的实体墙已经将某些屏幕列完全挡住，后面的墙即便投影到了同样的位置，也没有必要再画。这正是DOOM把BSP遍历与屏幕遮挡裁剪配合使用的关键。BSP只是负责的是以合适的顺序把可能可见的墙段送到渲染器，本身不会直接告诉我们屏幕的哪个像素怎么绘制。
而且，DOOM还能更进一步。BSP内部节点为两个子树记录了二维包围盒（Bounding Box）；处理完近侧子树后，程序可以先把远侧子树的包围盒大致投影到屏幕上。如果这块区域彻底落在已经被近处实心墙封闭的水平范围里，整棵远侧子树就不用访问了。这相当于发现一扇完全看不见的门，就连门后面的房间都不去检查。原版负责这项工作的函数叫`R_CheckBBox()`。
不过，因为窗户的存在，这个技术也不能无条件使用。假设玩家正透过窗户看向远处，如果把窗户所在的整列一律关闭，该从窗口透过来的画面就会凭空消失。因此，DOOM一方面用`solidsegs`记录被完整实体墙挡住的水平区间，另一方面用`ceilingclip`和`floorclip`等数据记录每一列上、下边缘还剩多少可见空间。对于有开口的双面墙，它会保留中间能够继续看到远处的部分。地板和天花板也不是简单地当作普通立体多边形绘制，而是通过Visplane等专门的数据结构处理。
4.我们的代码实现（全是GPT写的）
在代码实现的过程中发现BSP树的构建实际上很有讲究，我第一次生成BSP树并渲染时出现了地图破皮，后来又（让GPT）读了一下源码才修复。所以这部分就只分享一下这个问题的发现和解决。
我最初的程序是把墙壁整理成一棵树，然后利用这棵树决定墙壁的绘制顺序。或者说我给地图里的每面墙编号，把所有墙壁组织成一个便于查找、排序的数据结构。当玩家站在某个位置时，系统先找到近处的墙，再处理远处的墙，来实现类似DOOM的思路。
这个第一版就是仓库里的`main_backup.py`。地图也很简单：一个六边形房间，里面立着四根正方形柱子，总共有6条外墙加16条柱子边界，也就是22条原始墙段。墙段只有两个二维端点和一种颜色，所有墙等高，也没有窗户、台阶之类的复杂结构。我特意把场景弄得简单一点，想先看明白BSP到底在干什么。
最初的建树办法看起来非常合理。先挑一条墙段当作分割依据，判断其他墙段在它的哪一边；跨过分割线的墙段就切成两截，分别交给前后两棵子树。程序还给候选分割线打分：越少切墙越好，前后两边的墙段数量越接近越好。但最重要的处理藏在两行代码里：选中的`splitter`不会再分到子树里，而是直接留在当前`Node`上；只要一个分支剩下不超过两条墙段，就结束递归，把它们装入`Leaf`。
所以，第一版BSP树其实像一座分层存放墙壁的档案架。每一层挑出一面墙放在树杈上，把其他墙分到两边，然后继续挑。到了绘图时，玩家位于哪边，就先遍历哪边，再绘制树杈上那面作为分割依据的墙，最后遍历另一边。用伪代码写出来就是：
它确实使用了二维分割直线，也确实能利用空间前后关系为墙壁提供绘制顺序。问题在于，它是按照“墙壁怎样排序”来组织数据的，而不完全是按照原版DOOM“空间怎样被划分”来组织数据的。另外，“一个叶节点只剩两条墙”也不意味着它对应的空间一定是凸的；而程序为保险起见，在叶节点里还用“玩家到墙段的最短距离”做了一次排序。对于简单场景，这常常能凑出正确的画面，但这个距离并不保证所有屏幕方向上的遮挡顺序都正确。
更麻烦的是，我们的渲染器会在画完一列近处墙壁以后，立即把这列标记为已经封闭，远处的墙就再也不能画到这一列。如果某一次由于BSP分割或墙段处理顺序的问题，让本应在后面的墙抢先占据了一列，真正靠前的墙就可能被错误地裁掉。屏幕上于是会出现奇怪的断裂、缺口，或者某些墙角像被撕开了，这就是我最初看到的地图破皮。当然，光凭这个画面现象还不能断言唯一的bug原因：切分线段时的浮点误差、投影端点的取整、错误的叶内排序，也都可能造成类似问题。但它让我意识到，既然使用的是近处先画、画完就不准后面再覆盖的策略，那么前后顺序就绝不是一个可以随便近似的问题。
后来我让GPT继续对照原始DoomBSP构建器的跨平台移植代码（ doombsp/doombsp.cpp at master · teefoss/doombsp ），以及DOOM运行时的数据结构`r_bsp.c`里的`R_RenderBSPNode()`和`R_Subsector()`（ DOOM/linuxdoom-1.10/r_bsp.c at master · id-Software/DOOM ），才发现最关键的结构区别，就是原版DOOM的Node只负责保存分割线，不在Node上画墙；而真正的墙段归入Subsector，只有遍历到Subsector时才交给渲染器。可以把两版的差别压缩成下面这个小示意：
假设选中一段墙W，它所在的无限延长直线负责把空间分成两侧，那么W本身应该去哪里？最初的代码直接把W从后续分类中取出来，留在Node上；而新的`main_doom_bsp.py`会让W像其他墙段一样继续参加分类，最终进入某个Subsector。这样，Node保存的是“空间按哪条线切开”，Seg保存的是“地图上哪里真有墙”，两件事情就不再混在一起了。
而且，一条墙段恰好落在分割线上时，不能光凭两个端点在直线哪边来判断它的归属。新版本借鉴了原始节点构建器的处理方法：与分割线共线且同向的Seg归到一侧，反向的归到另一侧。这在真正的DOOM地图中尤其有意义，因为连接两个Sector的双面边界可能对应方向相反的两个Seg，让两侧各自保留与自己相关的边界信息。在我们的简化地图里，暂时还没有Sector和双面墙，但至少保留了这种一致的分类规则。
终止条件也跟着变了。之前的版本规定“剩下两条墙段就停”，修改后则是继续寻找能有效地把Seg分到两侧的分割线；实在找不到时，才把剩余墙段收进一个Subsector。对于标准DOOM地图，原始构建器依靠这类递归划分来获得适合渲染的凸子区域。这里有个挺反直觉的地方：一个Subsector可以是凸空间，但里面保存的真实墙段未必能围成一个闭合多边形，因为剩下的边界可能只是上层BSP分割出来的虚线。也正因为如此，我一开始让GPT尝试用`convex_hull()`判断叶节点时，反而引入了新问题。
分割线的选择也作了调整。现在会参考原始构建器的评分思路，同时考虑两侧规模与切分代价。简单来说就是并不是分得越均匀越好，因为如果为了一棵平衡树，把几十面原本完整的墙全部切碎，后续处理的数据反而可能更多。在我们这张只有22条原始墙段的地图里，两种构建方式就会得到形状不同的树，但这不意味着更接近DOOM的那棵树一定更浅或一定更快。BSP需要在建树开销、树的形状和被切碎的墙段数量之间做取舍。
最后，渲染部分反而改动很小。新的`traverse()`仍然判断玩家位于分割线的哪一侧，先递归近侧，再用远侧包围盒检查是否还有可能可见；区别仅在于它不会在中途画`node.seg`，而是到达`Subsector`时才遍历其中的墙段。墙段一旦交给`draw_seg()`，后续的透视投影、墙柱高度、倒数深度插值、逐列遮挡和Pygame绘制依旧是原来的代码。
当然，这远远不是完整复刻DOOM。我们的代码仍然只画同一高度的实心墙，用一个布尔数组表示某列是否被挡住，并没有原版的`solidsegs`区间裁剪、真正能透过窗户看到后面的双面墙、Sector地板和天花板高度，以及纹理、Visplane等系统；Subsector内部甚至还保留了一次按墙段距离排序的教学性处理。玩家碰撞也仍然是直接检查玩家到墙段的距离，完全没有利用BSP。所以更准确的说法，是我们保留原有的小型渲染器，只把BSP构建和墙段存储方式改成了更接近DOOM源码的版本。
后来还做了一个单独的BSP调试视图，把二维地图、每次生成的分割线、最后形成的Subsector以及渲染时近侧、远侧的访问顺序放在一起显示。也放在我的仓库里。
5.《雷神之锤》
这部分的内容也可以在重轻老师《游戏帝国》关于英伟达和EPIC的部分听到。稍微了解这些技术后，感觉当时最大的限制还是CPU速度太慢，且z-buffer非常昂贵。到了Quake的时代，硬件迎来了新一波的更新换代，比如Voodoo卡极大提高了三角形处理、纹理采样、z-buffer等技术的性能，上述的很多优雅的技术实际上过时了。一方面多少感觉有点唏嘘，但是另一方面也更加意识到卡马克确实是神仙，他用“神力”让我们得以提前一窥下一个时代……
另外在DOOM的开源代码中，卡马克提到自己在DOOM中没有发挥BSP的全部潜力，没有把他用到视线检测和移动碰撞检测上。在Quake中BSP正式升级为一种世界索引体系，使用分割面把3D世界分割为不相交的凸空间，并在此基础上处理快速渲染、碰撞检测、NPC视线等等。但是那个问题对我来说就太复杂了。
评论区
共 条评论热门最新