毁灭战士额外生命模式在毁灭战士中应用二叉空间分割

导读1993年，游戏开发公司idSoftware发行了一款第一人称射击游戏《毁灭战士DOOM》，游戏一经发行迅速爆火。在今天看来，《毁灭战士》可谓有史以来最具影....

1993 年，游戏开发公司 id Software 发行了一款第一人称射击游戏 《毁灭战士DOOM》，游戏一经发行迅速爆火。在今天看来，《毁灭战士》可谓有史以来最具影响力的游戏之一。

《毁灭战士》发行之后的第十年（2003 年），记者 大卫·库什纳David Kushner 出版了一本关于 id Software 的书，书名为《Doom 启示录Masters of Doom》，后被奉为记录毁灭战士创作史的典范读物。几年前我曾读过这本书，如今内容已记得不太真切了，但是书中有一个关于 id Software 首席程序员 约翰·卡马克John Carmack 的故事，我印象特别深刻。这里只对故事做粗略描述（具体情节请往下阅读）。实际上，早在《毁灭战士》开发前期，卡马克就发现自己为这款游戏编写的 3D 渲染器在渲染某些关卡时慢得像爬一样。对于《毁灭战士》这一对动感和速度有着相当高要求的射击游戏来说，这是一个非常严重的问题。意识到了这一问题的严重性，卡马克需要一个更加有效的渲染算法，于是他开始阅读相关论文。最后，他实现了一种叫做“二叉空间分割binary space partitioning（BSP）”的技术，极大地提升了《毁灭战士》游戏引擎的运行速度，而这项技术此前从未用于电子游戏当中。

一直以来，我对这个故事的印象十分深刻。卡马克将学术前沿研究运用于电子游戏之中，我觉得这正是他之所以成为传奇人物的原因。无论从哪个角度来看，卡马克都应该是电子游戏行业中人尽皆知的典型的天才程序员，只不过上面这个故事是我最先能够想到的理由。

显而易见，“二叉空间分割”这个术语听起来就是难度相当高的课题，能够自行阅读论文并将其付诸实施实属不易，所以这个故事给我留下了深刻的印象。我一直认为卡马克的做法十分具有创见性，不过由于我既不懂二叉空间分割到底是怎样的一项技术，也不晓得这项技术在当时究竟有多么革新，所以我也并不确定自己的观点是否正确。如果按照从 霍默·辛普森Homer Simpson（LCTT 译注：《辛普森一家人》中的那个老爹）到 阿尔伯特·爱因斯坦Albert Einstein 的顺序为天才列出一套级别体系，那么卡马克将二叉空间分割技术运用于《毁灭战士》的做法究竟属于什么级别的天才之举呢？

同时，我也在想，二叉空间分割这个概念最初是从哪儿来的，又是怎样吸引到卡马克的？因此，本篇文章不仅仅会讲述约翰·卡马克和《毁灭战士》的故事，也会探讨二叉空间分割树（BSP 树）数据结构的发展历史。有意思的是，BSP 树和计算机科学领域其他许多技术一样，最初都起源于军事研究领域。

没错，《毁灭战士》的第一关卡 E1M1 就受到了美国空军的启发。

VSD 难题

BSP 树是计算机图形领域最具挑战性难题的解决方案之一。举个例子，为了渲染出三维场景，渲染器必须能够区分在一个特定角度下的可见物体和不可见物体。如果渲染时间比较充足，这一要求也算不上大问题；但是就理想情况来说，实时游戏引擎在 1 秒内至少需要完成 30 次区分任务。

这一问题有时被称为 可见面检测visible surface determination（VSD）问题。后来与卡马克合作开发《雷神之锤Quake》（id Software 继《毁灭战士》之后开发的游戏）的程序员 迈克尔·亚伯拉什Michael Abrash，在自己的著作《图形程序开发人员指南Graphics Programming Black Book》 中写道：

我想探讨一下在我看来 3D 中最棘手的一个问题：可见面检测问题（在每个像素点上绘制合适的表面）以及与之密切相关的隐面消除问题（迅速去除不可见的多边形，用于加快可见表面检测速度）。简略起见，我将在下文采用缩写 VSD 来表示可见面检测和隐面消除。

为什么我会认为 VSD 是 3D 中最棘手的问题呢？尽管纹理映射等光栅化问题更让人感兴趣而且也更重要，但是相对而言，它们是范围相对有限的任务。随着 3D 加速器的出现，它们逐渐被转移到硬件中。同时，它们只随着屏幕分辨率的增加而增加，而分辨率的增加是相对温和的。

相反，VSD 却像是一个无底洞，目前应对方案也有很多。但实际上，在采用简单的方法处理 VSD 时，其性能会直接受到场景复杂程度的影响，而场景的复杂程度通常会以平方级或立方级的形式增大。所以在渲染过程中，VSD 很快就会成为制约因素。[1]

亚伯拉什是在上个世纪九十年代末写的关于 VSD 问题的这些困难，这是在《毁灭战士》之后数年，这款游戏证明了普通人盼望着能用自家电脑玩很吃图形配置的游戏。九十年代早期，id Software 成立后发行了一些游戏。尽管当时的计算机还只是用来处理文字与表格或者执行其他任务，未尝想过要在上面运行游戏，id Software 必须对发行的游戏进行编程，使其能在计算机上流畅运行。为了实现这一飞跃，尤其是为了能让在《毁灭战士》之前 id Software 发行的少数 3D 游戏在电脑上运行，id Software 必须做出革新。在这些游戏中，所有的关卡在设计时都受到了一定限制，以便更容易解决 VSD 问题。

例如，在《毁灭战士》之前，id Software 发行了《德军总部 3D 版Wolfenstein 3D 版》，该游戏的每一个关卡都是由与坐标轴平齐的墙壁组成。换言之，在《德军总部 3D 版》的游戏画面里，你看到的只有南北方向或者东西方向的墙壁。在游戏中，墙壁与墙壁之间有着固定的间隔，所有过道的宽度或是一个方格，或是两个方格等等，但绝不会出现 2.5 个方格。如此一来，尽管 id Software 团队只能设计出外观十分相似的关卡，但这也让卡马克为 《德军总部 3D 版》 编写渲染器的工作简单了不少。

通过将屏幕上的光线“齐射”入虚拟游戏世界，《德军总部 3D 版》的渲染器解决了 VSD 问题。通常来说，使用光线的渲染器叫做“光线投射”渲染器。这种渲染器的速度一般较慢，因为解决内部的 VSD 问题涉及到在光线和游戏中的物体之间找到第一个交点，这通常需要进行大量的计算。但在 《德军总部 3D 版》，由于所有的墙壁都与网格平齐，所以光线与墙壁相交的位置只能在网格线上。如此一来，渲染器只需逐个检查这些交点即可。如果渲染器先从离玩家视角最近的交点开始检查，接着检查下一个最近的交点，以此类推，最后遇到第一面墙壁时停止检查。这样，VSD 问题便轻而易举地得到了解决。光线从每一个像素点向前投射，与画面物体接触时停止，这一方法是可行的。因为从 CPU 资源来看，投射的成本很低。事实上，由于每面墙壁高度相同，因此针对同列的像素点，投射的光线只需一条。

尽管当时还没有专业的图形显卡，《德军总部 3D 版》凭借这一取巧之法得以在配置较低的个人电脑上正常运行起来。然而，这个办法并不适用于《毁灭战士》。因为 id Software 为这款新游戏增添了许多新元素 —— 倾斜的墙面、楼梯以及高低不一的天花板。光线投射的办法自然也就不好用了，于是卡马克编写出了一个新的渲染器。《德军总部 3D 版》的渲染器关注的是图像，将光线投射到屏幕像素表示的列上，而 《毁灭战士》 关注的则是物体。换句话说，《毁灭战士》 的渲染器会记录游戏场景中的所有物体，继而将其投射到屏幕当中；而非记录屏幕上的像素点，判断每个像素点的颜色。

对于强调物体的渲染器来说，可以使用 Z 缓冲区来解决 VSD 问题，比较简单。每次将物体投射到屏幕上时，需要对每个用于绘制的像素点进行检查。如果你想绘制出的物体的部分和已经绘制在目标像素点上的物体相比更加靠近玩家，可以将其覆盖。否则，必须保持像素不变。尽管办法很简单，但是 Z 缓冲区对内存的要求较高，而且渲染器可能仍然要花费大量的 CPU 资源来投射玩家永远不会看到的水平几何体。

在 20 世纪 90 年代，使用 Z 缓冲区的方法还存在着其他缺陷：IBM 兼容机（PC）搭载的是一种叫 VGA 的显示适配器系统，在这类电脑上，将图像写入帧缓冲区的成本非常之高。因此，在只会以后被覆盖的像素上绘制花费的时间拖慢了渲染器的性能。

考虑到将图像写入帧缓冲区的成本非常之高，理想的渲染器需要首先绘制离玩家最近的物体，接着是比较近的物体，以此类推，直到屏幕上每个像素点都写入了信息。这时，渲染器会停止运行，大幅缩短远处不可见物体的渲染时间。这种由近及远对物体进行排序的方法也可以解决 VSD 问题。那么问题又来了：什么才是玩家可以看到的？

最初，卡马克打算依靠《毁灭战士》的关卡布局来解决 VSD 问题。首先用渲染器绘制出玩家目前所在房间的墙壁，之后玩家冲进隔壁房间，再绘制出隔壁房间的墙壁。由于每个房间互不遮挡，这一办法也能解决 VSD 问题。而互相遮挡的房间可以分割成若干互不遮挡的“区域”。在 YouTube 上的一个 视频中，Bisqwit 展示了自己制作出来的使用了相同算法的渲染器。可以看到，如果以超慢的速度运行，便能一睹渲染的具体过程。这一算法同样运用到了《毁灭公爵 3D 版》当中，这款游戏在 《毁灭战士》 推出三年之后发行，当时 CPU 的性能也更加强大了。1993 年，尽管在硬件上已经可以运行游戏了，但是使用这一算法的《毁灭战士》渲染器在复杂的层级结构上依旧表现吃力，尤其是在房间分割出来的各部分相互嵌套的情况下。不巧的是，这类层级结构正是构造环形楼梯等物体的唯一办法。沿着环形楼梯走下去，直到走入已经绘制好的区域，由于这其中涉及多次循环下降运动，导致游戏引擎的运行速度大幅降低。

在 id Software 团队意识到《毁灭战士》游戏引擎的速度可能过慢时，公司还面临着其他任务：将《德军总部 3D 版》移植到超级任天堂游戏机（简称“超任”）上。那时，超任的性能比 IBM 兼容机还要差。结果表明，尽管光线投射渲染器非常简单，但是想要在超任上快速运行是不可能的。于是，卡马克着手研究更为高效的算法。事实上，也正是为了顺利将《德军总部》移植到超任，卡马克首次研究了二叉空间分割技术，并将其付诸应用。由于《德军总部 3D 版》的墙壁与坐标轴平齐，所以二叉空间分割技术应用起来也比较简单直接；但是《毁灭战士》的情况则比较复杂。不过，卡马克发现，二叉空间分割树同样可以用来解决《毁灭战士》速度过慢的问题。

二叉空间分割

二叉空间分割binary space partitioning（BSP）会提前将 3D 场景分割为若干部分，使 VSD 问题易于解决。讲到这里，你需要先了解一下为什么分割场景可以奏效：如果你在场景上画条线（对应三维空间里的一个平面），你就可以指出玩家或者摄像机视角在这条线的哪一侧，在这条线另一侧的物体无法遮挡玩家所在一侧的物体。如果多次重复这一操作，该三维场景最终会被分割为多个区域，这并不是对原始场景的改进，只是现在你知道了更多关于场景的不同部分会如何相互阻挡。

首次阐述上述三维场景分割的是美国空军的研究员，他们曾尝试向美国空军证明计算机图形已经非常先进，可以应用到飞行模拟器领域。1969 年，他们将研究发现发表在一份题为《计算机生成图像在图形仿真中的应用研究》的报告中。该报告的总结部分指出，计算机图形可用于训练飞行员，但也警告说，其实际应用可能会受制于 VSD 问题：

实时图像处理需要解决的一个关键问题就是优先级问题，或称隐藏线问题。在我们平时用眼睛观察外界时，大自然替我们轻易地解决了这一问题：不透明物体上的一个点，掩盖了同一视觉方向上、且距离较远的所有其它物体。但在计算机中，这项任务却非常困难。图像处理需要解决的优先级问题，随着环境复杂程度的增加，计算量会呈指数级增长，随即就会超过绘制物体透视图所需的计算负载。[2]

他们在报告中提出了一项基于构造“遮挡矩阵”的方案，这一方案据说早些时候曾被应用于 NASA 的项目当中。研究员指出，平面将场景一分为二，可用来解决平面两侧物体之间存在的“任何优先级问题”。通常情况下，可能需要明确将这些平面添加到场景中，但对某些几何体，只需借助你已经拥有的几何体的表面即可。他们举了一个例子，如下图：p