原文链接

1993 年，id Software 发布了 FPS 游戏 Doom

，此游戏一经发售就立刻成为现象级作品。如今也已被视为影响最为深远的游戏之一。

在 Doom 发售十年后的 2003 年，记者 David Kushner 出版了一本关于 id Software 的书《Doom 启示录》，并从此成为了关于 Doom 诞生的重要文献。我在几年前阅读了《Doom 启示录》，其中的大部分内容已经被我遗忘。但唯独有一个关于首席程序员 John Carmack 的故事一直萦绕在我心头。我们会在后面详细回顾这个故事，但简单地说，在 Doom 的开发初期，Carmack 发现到他编写的 3D 渲染器在渲染一些特定关卡的时候会慢到令人发指。这是令人无法接受的，因为 Doom 理应是一款动力十足充满激情的游戏。Carmack 意识到这是一个触及根基的问题，他需要找到一个更好的渲染算法来解决它。于是他开始阅读论文，并最终实现了一个叫做 Binary Space Partitioning （BSP）的技术。这项技术在此之前从来没有被应用在电子游戏中，却极大地提高了 Doom 引擎的运行速度。

这个 Carmack 将最尖端的技术应用在电子游戏上的故事总是能打动我。对我来说，这正是 Carmack 之所以能成为一个传奇的原因。尽管他在诸多方面都无愧于天才游戏程序员的称号，这段关于学术论文和 BSP 技术的历史却在我心中位列榜首。

当然了，这个故事让人印象深刻的原因之一就是，Binary Space Partitioning 这个技术的名字听起来很高深，感觉很难自己动手实现它。很长一段时间我都认为这是 Carmack 做出的一个智力飞跃，但我一直以来都没有真正理解 BSP 是什么，或者在 Carmack 决定使用它的时候这项技术有多先进，所以我一直都不确定，如果绘制一条从辛普森到爱因斯坦的智力光谱，Carmack 把 BSP 添加到 Doom 中这件事能排到哪？

同时我也好奇，BSP 的技术最初是从哪来，它最后又是如何被 Carmack 发现的。所以这篇文章不仅是关于 Carmack 和 Doom，也是关于 Binary Space Partitioning Tree （BSP 树）这一数据结构的历史。有趣的是，BSP 树和许多其他的计算机技术一样，源自军方的研究活动。

没错：E1M1，也就是 Doom 的第一关，由美国空军为您呈现。

VSD 问题

BSP 树的设计是为了解决计算机图形学中一个非常棘手的问题：为了渲染一个三维空间，给定一个视角的情况下，渲染器必须能够区别出什么能被看到而什么不能。如果你有很多时间的话，这不是什么大问题，但一个实时的游戏引擎需要在一秒内判断至少 30 次。

这个问题有时会被称作可见表面决策（Visible Surface Determination）。 Michael Abrash，一个和 Carmack 一起开发 Quake（id Software 在 Doom 之后的作品）的程序员，曾经在他著名的《图形编程黑皮书》（Graphics Programming Black Book

）中提到 VSD 问题：

我想谈一下我认为最棘手的 3-D 问题：可见表面决策（在每个像素上绘制正确的表面），以及它的近亲问题，多边形剔除（通过尽快剔除不可见的多边形来加速可见表面决策）。为了表述的简洁，我在下文会用 VSD 来同时指代这两者。为什么我会认为 VSD 是 3-D 技术中最棘手的挑战？虽然类似纹理映射这种光栅化相关的问题也很有趣且重要，但他们的应用范围相对有限，而且可以被移交给诸如 3-D 加速器之类的硬件来处理；同时，他们的处理难度只和屏幕的分辨率相关，所以相对来说比较容易应对。然而，VSD却是一个开放性的问题，已经有几十种应用方法。最重要的是，如果不能用恰当的方法应对，VSD的规模会随着场景的复杂度呈平方甚至立方级数增长，所以它很快就会变成渲染真实世界的一个限制因素。

Abrash 所谈及的是在 90 年代末期时想要解决 VSD 问题的难度。此时 Doom 的成功已经证明普通玩家想要在他们的家用电脑上玩到图形密集性游戏（graphically intensive games）。在 90 年代初期 id Software 该开始发行游戏的时候，游戏开发必须精打细算，以图能够在那些不是为了游戏而设计的电脑上运行。本来这些电脑只会用来运行一些文字处理软件或者表格应用之类的小玩意。为了让游戏能跑得起来——特别是 id Software 在 Doom 之前开发的一些 3D 游戏——id Software 必须非常有创造力，因为在这些游戏中，他们的关卡设计需要保证 VSD 问题易于解决。

举例来说，id Software 在 Doom 之前发售了一款叫做重返德军总部 3D 的游戏。在这款戏中，每个关卡的墙壁都是轴对齐（axis-aligned）的。换句话说，在重返德军总部的世界里，你只能有南北朝向或者东西朝向的墙。每面墙的间隔必须是格子的整数倍，也就是说走廊要么是一格宽，要么是两格宽，但绝对不可能是 2.5 格宽。尽管这种限制使得软件团队设计的关卡看起来都很相似，但却令 Carmack 对重返德军总部渲染器的编写工作变得轻松了许多。

重返德军总部通过从屏幕向虚拟世界发射光线来解决 VSD 问题。基于光线的渲染器一般叫做「光线投射渲染器」（raycasting render）。这种渲染器通常都很慢，因为要通过光线投射来解决 VSD 问题需要找到光线和虚拟世界世界中的某个物体第一次相交的位置，而这通常会带来大量的计算。但是对重返德军总部来说，因为所有的墙面都是轴对齐的，所以光线只能在网格线上和墙壁相交。因此渲染器要做的事情就只是检查这些交点。渲染器会从离玩家最近的交点开始检查，然后是次近的交点，以此类推，最终当它遇到一面墙时就停止检查。通过这种方式，只需要一点微不足道的代价就可以解决 VSD 问题，因为这种算法就只是从每一个像素射出一条光线，令光线一直行进直到击中一面墙，而光线的行进对 CPU 周期来说则非常廉价。实际上，因为所有墙体的高度都是一样的，所以对每一列像素都只需要发射一条光线即可。

这个渲染技巧足以让重返德军总部在专用的图形卡问世之前就可以运行在性能孱弱的家用 PC 上，但这个方法无法套用在 Doom 上，因为 id 团队当时已经决定他们的新作必须支持更多新特性，包括斜向的墙壁、楼梯、不同高度的单元格等等。光线投射方案不再可行，因此 Carmack 编写了一个新的渲染器。重返德军总部这种为每一列像素发射一条光线的渲染器是「图像优先」(image-first)， Doom 的渲染器则是「物体优先」（object-first）。这意味着不同于遍历所有屏幕上的像素来决定它们的颜色， Doom 的渲染会遍历场景中的所有物体，并将它们投影到屏幕上。

对于物体优先的渲染器来说，解决 VSD 问题最简单的办法就是使用 z 轴缓存（z-buffer）。每次你要把一个物体投影到屏幕上并绘制相应的像素时，你都可以进行一次检查。如果你要绘制的部分比已经绘制完成的物体距离玩家更近，你就可以覆盖当前的像素。否则你就跳过绘制过程。这个方法非常简单，但问题是 z 轴缓存需要很多内存，而且渲染器很可能会花费很多 CPU 周期来投影一些玩家永远都看不到的几何体。

在 1990 年代早期，基于 z 轴缓存的方案还有一个问题：当时 IBM 兼容机使用了一个叫做 VGA 的图形调制系统，这导致对输出缓存的写入操作非常昂贵。如果你绘制的像素在之后会被覆盖重绘，这些被浪费的时间就会大大拖累渲染器的性能。因此比较理想的做法是，优先绘制离玩家最近的物体，然后是那些物体之后的物体，直到所有的像素都绘制完成。此时渲染器需要停止渲染，避免把时间花费在那些玩家永远都看不到的远处的物体上。但是把物体由近及远地排序，实际上和 VSD 是等价的。也就是说，我们又回到这个问题：玩家到底能看到什么？

最开始，Carmack 尝试通过 Doom 的关卡布局来解决这个问题。他的渲染器会首先绘制玩家当前所在房间的墙壁，然后再绘制能被玩家看到的相邻房间的墙壁。如果每个房间都是凸多边形（译注：即房间内的墙壁不会相互遮挡），那么这个问题就可以被解决。那些不是凸多边形的房间则可以被切割成多个凸多边形的区域。这个算法被成功的运用在 Doom 发售三年之后的毁灭公爵 3D 上，此时 CPU 已经有了更高的性能。但是在 1993 年，在当时可用的硬件平台上使用这个算法的 Doom 渲染器在处理比较复杂的关卡时则会捉襟见肘，尤其是当凸多边形区域之间会互相嵌套的场景更是如此，比如圆形楼梯就肯定会导致这种情况。

就在 id 团队意识到 Doom 引擎不够快的时间点前后，id Software 收到了任天堂的委托，要把重返德军总部 3D 移植到 SFC 平台，而 SFC 甚至比当时的 IBM 兼容机性能还要弱。结果证明，光线投射版本的重返德军总部渲染器没办法在 SFC 上快速运行，所以 Carmack 开始寻找一个更好的算法。事实上 Carmack 正是为了 SFC 版本的重返德军总部才开始研究和实现 BSP 算法的。其实重返德军总部的问题要更容易处理一些，因为它的墙壁都是轴对齐的； Doom 的情况要更复杂一些，但是 Carmack 意识到 BSP 树也可以解决 Doom 的性能问题。

Binary Space Partitioning

BSP 方法可以通过把一个 3D 场景提前分割成不同区域来让 VSD 变得易于解决。想象你在空间中划出一条线（在 3D 空间中则是一个平面），同时你知道玩家或摄像机位于这条线的哪一边，而且你还知道位于另一边的任何物体都无法遮挡这一边的物体。只要你这样重复分割这个空间，最终你会得到很多区域，而且你可以知道不同区域之间的遮挡关系。

最早关于这种分割 3D 空间方法的论文出自美国空军的研究者。他们尝试论证计算机图形技术有没有足够的效率用于飞行模拟。它们在一篇 1969 年的一篇叫做 Study for Applying Computer-Generated Images to Visual Simulation 的报告中公开了他们的发现。报告指出计算机图形技术可以用来训练飞行员，但同时也预警了 VSD 带来的实现上的复杂度：

在实时计算图像时，我们要面对的最重要的问题之一便是优先级问题，或是隐藏线问题。在我们的日常环境的透视中，这个问题轻而易举就可以解决。一个非透明物体上的点，会遮盖住相同视线上所有更远的点。对计算机来说，这个问题却异常艰巨。通常来说，解决优先级问题所需要的计算量会随着周围环境的复杂度成指数级增长，并很快就会超出透视图像计算的负载范围。

研究人员提到一个算法，这个算法可以生成一个被我称为遮蔽矩阵（occlusion matrix）的矩阵。据说这个算法曾被运用在 NASA 的一个项目中。研究人员指出，如果一个平面将一个场景分为两块区域，那么位于不同区域的所有物体间的优先级问题都可以借助这个平面来解决。通常来说你可能需要自己将这个平面添加到场景中，但是通过一些特定的几何方法，你也可以直接使用场景中的物体已有的平面。他们给出了如下图的一个示例。 P_1， P_2 和 P_3 是分割平面。如果摄像机在一个平面的正面（“true” side），那么矩阵中 p_i 的值就是 1 。基于这三个平面和视点位置，这个矩阵可以表现出这三个物体之间的关系：如果一个物体 aiai 遮挡了物体 ajaj，那么矩阵中的 A_ij=1。

① ② ③ 为物体编号，P_1, P_2, P_3 为平面

研究人员提出，这个矩阵可以事先实现在硬件中，并对每一帧重新计算。基本上来说，这个矩阵就是一个大型的开关，或者说是一种预置的 z 轴缓存。当绘制一个物体时，如果要绘制的部分对应的这一列中有一个 1，且对应的行已经被绘制，那么这部分物体就不应该被绘制。（译注：以上图为例，物体① 的列中有一个 1，说明它被其他物体（物体③）遮挡。如果物体③ 已经被绘制了，那么已经绘制的物体③就不应该被重绘）

这个矩阵带来的一个主要的弊端是，如果要表现一个包括 nn 个物体的场景，那么这个矩阵的大小就会变成 n2n2 。因此，研究者随后便探索是否存在一种方法可以将遮蔽矩阵表达为一个「优先级列表」，这样之须臾一个长度为 nn 的列表就可以确定所有物体的绘制顺序。他们立刻就注意到对如上图所示的这种特定场景来说，这种顺序都是不存在的（因为他们存在循环遮挡的物体）。所以他们花费了大量的时间去从数学上区分出寻常（proper）和非寻常（improper）的场景。最终他们得出结论：至少对于寻常场景来说，这个优先级列表是可以生成的，而对场景设计者来说避免创造非寻常场景也并不困难。这个 1969 年的研究最首要的贡献也许是，它指出了通过分割平面来对物体排序是可行的，至少在理论上是可行的。

直到 1980 年的一篇叫做 On Visible Surface Generation by A Priori Three Structure 的论文才提出一个切实的算法来真正地完成这项工作。这篇出自 Henry Fuch，Zvi Kedem 和 Bruce Naylor 的论文引入了 BSP 树。论文作者声称，他们提出的这个数据结构是「另一个技术方案的替代方案，这个方案提出于十年前，却因为一些困难无法被广泛应用的。」在这里他们引用了 1969 年那个源自美国空军的研究。 BSP 树一旦被构成就可以方便的提供场景中物体的优先顺序。

Fuchs, Kedem, 和 Naylor 非常详细地解释了 BSP 树是如何工作的，但我会在这里提供一个没那么正式但更简洁的说明。（译注：原作这里的说明其实比较难懂，因此译者在这里参考维基百科中的示例进行说明，如有纰漏请多斧正。）

需要说明的是，在 BSP 算法中出现的平面都是双向平面，即需要指定一个「前方」。「前方」可以粗略的理解为在被玩家看到时面向玩家的方向。这个方向一旦确定便无需更改，并不会随视点的位置变化而变化。

BSP 树的构建

BSP 树的构建过程如下：

从将场景选取一个多边形 P，将它作为根节点 N。
对于剩下的多边形
如果它全部都在 P 的后方，则将它放在 N 左边的列表中
如果它全部都在 P 的前方，则将它放在 N 右边的列表中。
如果它只有一部分在 P 的前方，则将它分隔为前后两部分，分别放入 N 左右两边的列表中。
对 N 左右两边的列表重复以上操作。

对 BSP 树中的一个节点，所有左侧子节点都在它的后方，而所有右侧子节点都在它的前方。下图是一个具体的示例，可以详细展示这个过程的具体步骤。

BSP 的使用

在渲染多边形时有一种叫做「画家算法」的方法，核心思想是由远及近地绘制像素，如此一来近处物体的像素就会将远处物体的像素覆盖，由此来实现遮挡的效果。在 BSP 中这种方法体现在在渲染一个节点 N 时，根据视点 V 相对于 N 的位置，要先渲染 N 左边或右边的节点。具体规则如下：

如果 N 是叶子结点（N 没有子节点），则直接渲染 N
如果 V 在 N 的前方，
绘制 N 左边的节点（对应多边形位于 N 后方）
绘制 N
绘制 N 右边的节点（对应多边形位于 N 前方）
如果 V 在 N 的后方
绘制 N 右边的节点（对应多边形位于 N 前方）
绘制 N
绘制 N 左边的节点（对应多边形位于 N 后方）

下面以下图为例详细说明其操作步骤：

这里的 BSP 树的根节点为 A ，因此我们从 A 开始绘制多边形。摄像机视点 V 位于 A 的前方，所以我们先绘制 A 后方的多边形，即 {B1,C1,D1}。接着绘制 A，此时 {B1,C1,D1} 中被 AA 遮挡的部分的像素就会被 A 的像素覆盖。最后被绘制的是 A 前方的多边形，即{B2,C2,D2,D3}。同样的，此时如果有多边形遮挡了 A ，它的像素也会覆盖 A。

类似地，对 {B2,C2,D2,D3} 的绘制从 B2 开始。由于 V 在 B2 的后方， B2 会遮挡位于它前方的多边形，并可能被位于它后方的多边形遮挡。因此我们需要先绘制 B2 后方，即 BSP 树中 B2 右边的节点，即 {D2}，接着绘制 B2，最后是位于 BSP 树中位于它左边的 {C2, D3}。（译注：对 BSP 的解释至此结束。此处开始为原文内容。）

正如 Fuchs, Kedem 和 Naylor 多次强调，BSP 树真正简洁之处在于它只需构建一次。也许这听起来有些意外，然而只要场景内的物体没有移动，不论视点位置如何变动，对一个场景的渲染都只需一棵 BSP 树。这也是为什么 BSP 树对实时渲染如此有用：最困难的工作都在于构建 BSP 树，而这个过程完全是提前完成的，无需发生在渲染过程。

Fuchs, Kedem 和 Naylor 还提出了一个需要进一步回答的问题，即什么样的 BSP 树才是一棵「良好」的 BSP 树。 BSP 树的质量主要取决于你选取的首个用于构建 BSP 树的多边形。如前文所说，如果你选取的多边形和其他多边形的平面相交，你需要用它来分割所有与其相交的多边形。如果这种操作频繁发生，那将大大增加场景中的多边形数量。

那篇 1980 年的论文的作者之一， Bruce Naylor，在 1993 年发表了另一篇论文讨论了这个问题，论文题目为 Constructing Good Partitioning Trees 。根据 Carmack 的一位 id Software 合伙人 John Romero 的说法，这篇论文是 Carmack 在尝试为 Doom 实现 BSP 树时所参考的论文之一。

Doom 中的 BSP 树

还记得 Carmack 最初设计的 Doom 渲染器吗？在那个版本中 Carmack 尝试用从当前房间延伸至相邻房间的方法来决定渲染顺序。用 BSP 树来决定渲染顺序效果更好，因为它避免了渲染器可能会重复进入某个房间或区域的情况，而这种情况会浪费很多 CPU 周期。

「给 Doom 添加 BSP 树」意味着在操作层面上为 Doom 的关卡编辑器添加一个 BSP 树的生成器。每当一个 Doom 的关卡设计完成，就会根据关卡的几何结构生成一棵 BSP 树。据 Fabien Sanglard 所说，为一个关卡生成 BSP 树大约需要 8 秒钟，而为整个原版 Doom 的所有关卡生成 BSP 树则需要大约 11 分钟。有时 BSP 树的生成可能会花费更多的时间，因为 Carmack 的生成算法会尝试找出一个「良好」的 BSP 树。一个 8 秒钟的延迟在游戏运行时是不可接受的，但是对线下场景来说这点时间完全值得等待，尤其是考虑到 BSP 树对渲染器性能带来的巨大收益。对每一个关卡生成的 BSP 树都会作为关卡数据的一部分被载入游戏。

Carmack 对 1980 年的论文所提出的 BSP 树算法做了一个翻转，因为 Doom 启动并将 BSP 树载入内存后，渲染器会通过 BSP 树由近及远地绘制物体，而非由远及近。在 1980 年的论文中，Fuchs, Kedem 和 Naylor 展示了如何通过 BSP 树来实现由远及近的画家算法，但是画家算法会涉及到很多重复绘制，这对 IBM 兼容机来说是巨大的性能代价。因此 Doom 的渲染器选择从距离玩家最近的物体开始绘制。这个转变很容易在 BSP 树中实现，因为你只需要在绘制每一个节点时使用相反的决策顺序即可。为了避免已经绘制的多边形被远处的多边形的像素所覆盖，Doom 渲染器使用了一种内存需求更小的隐式 z 轴缓存。它包括一个数组来记录水平方向上的遮挡关系，还有两个数组分别用来记录从上至下和从下至上的垂直方向的遮挡关系。 Doom 渲染器不需要使用真正的 z-buffe的原因是，它在技术上并不是完全 3D 化的游戏。这种简陋的数据结构之所以能够奏效是因为某些特定的东西绝对不会在游戏中出现：它只需要水平方向的遮挡数组是因为游戏中没有倾斜的墙壁，只需要垂直方向的遮挡数组则是因为游戏中不会出现一个窗户在另一个窗户的上方这种情况。

最后就只剩下一个问题，那就是如何在已经提前生成 BSP 树的静态关卡场景中处理移动的角色。Doom 中的敌人无法作为 BSP 树的一部分，因为他们会移动，而 BSP 只能处理不会移动的几何结构。所以 Doom渲染器会先绘制静态的关卡结构，记录已经绘制的屏幕区域（这里用到了另一种内存高效的数据结构）。接着它会由远及近地绘制敌人，并将它们裁切到遮挡他们的屏幕区域内。这个过程不如 BSP 树的渲染过程高效，但由于通常来说敌人的数量都要比关卡的几何结构少很多，因此这里的速度并不是什么大问题。

对 BSP 树的使用是一个关键性的胜利。显而易见，Carmarck 发现利用 BSP 树完美地解决他的问题这一过程是极其干净漂亮的。但问题是，这算是一个天才级别的动作么？

在 Fabien Sanglard 关于 Doom 引擎的精彩著作中，它引用了 John Romero 关于 Bruce Naylor 的论文（Constructing Good Partitioning Trees）的评论。 John Romero 认为这篇论文主要是关于利用 BSP 树来移除 3D 模型背面的技术，而 Carmack 认为这技术可以为 Doom 所用，于是他就实现了它。这段描述是一种对 Carmack 的称赞，因为它暗示了在其他人还在使用 BSP 来渲染静态场景时， Carmack 已经看出这项技术可以被用在实时的电子游戏中。类似的评价也出现在了《Doom 启示录》中： Kushner 暗示了 Carmack 阅读了 Naylor 的论文之后问自己，「万一你不只能用 BSP 来创造 3D 图像，还能用它来创造整个虚拟世界呢？」

但这种说法忽略了 BSP 树的历史。在美国空军的研究者首次意识到通过分割空间可以加速渲染时，他们就对加速实时渲染过程产生了兴趣，毕竟他们本来就在尝试制开发一个飞行模拟器。那个飞行模拟器的样例在 1980 年 BSP 的论文中再次出现。 Fuchs, Kedem 和 Naylor 谈论了 BSP 如何在飞行模拟中发生作用：飞行员可以通过飞行模拟器在同一个机场中反复练习降落，由于这个过程机场的几何结构不会变化，因此只需要生成一次 BSP 树。很显然，他们当时就是在考虑实时模拟。在论文中关于研究动机的部分，他们甚至提到了为什么实时图形系统需要在 1/30 秒内生成一张图片。

所以，Carmack 并不是第一个想到将 BSP 树运用在实时图形模拟场景中的人。当然，诞生这个想法和将它付诸实践完全是两回事，但就算是在实现层面， Carmack 所参考的内容很可能也比通常所认为的要多。至少在本文撰写时，维基百科关于 BSP 树的页面中依然有信息指出 Carmack 参考了 Chen 和 Gordon 发表于 1991 的论文 Computer Graphics: Principles and Practice。此论文在 1990 年亦曾作为教材使用。尽管关于此条信息并没有明确的参考链接，但它很可能是属实的。 Chen 和 Gordon 这篇 1991 年的论文中给出了基于 BSP 树的由近及远的渲染方法， Doom 所使用的方法基本与其相同，其中包括我所说的「隐式z-buff」数据结构。在教材版本中则全面介绍了 BSP 树，并提供了包括构建和渲染 BSP 树的伪代码。（我曾有幸在我大学的图书馆中略读过此教材的 1990 版。） Computer Graphics: Principles and Practice 是计算机图形学的经典教材，所以 Carmack 很可能也拥有一本。

无论如何，Carmack 发现自己面临一个全新的问题——我们怎么才能在一个连支持浮点运算的 CPU 都没有的计算机上运行一个 FPS 游戏？他做了研究，证明了 BSP 树是一个对实时电子游戏非常有用的数据结构。即使 BSP 树在十年前就已经被发明，而在 Carmack 阅读到 BSP 树的相关文献时这项技术已经被充分研究，我依然认为这项工作是令人印象深刻的壮举。也许真正值得我们庆祝的成就是，Doom 游戏引擎作为一个整体是如此干净漂亮。我们不应该忽略的是， VSD 问题只是 Carmack 为了让 Doom 正常工作所需要解决的众多问题中的一个。在此同时，他还能够研究和实现一个大部分程序员闻所未闻的复杂数据结构，这些才真正体现出他在技术上的天才之处，以及对完美作品的追求。