当时的技术巅峰。1993年，id Software发行了第一人称射击游戏《
毁灭战士》（Doom） ，很快就变成了一种现象。 今天，人们相信这是历史上影响最大的游戏之一。
在《
毁灭战士 》发行十年后，2003年，记者大卫·库什纳（David Kouchner）出版了一本名为
《毁灭大师 》的id软件书，从此成为对
毁灭战士创作过程的典型描述。 几年前，我读过《
世界末日大师》 ，但几乎什么也没记得，但我的记忆中一直保留着一本书中有关首席程序员约翰·卡马克的故事。 我的描述并不完全准确（请参阅下文以获取更多详细信息），但是简而言之，在《
毁灭战士》开发的初期，卡马克意识到他为游戏编写的3D渲染器在渲染某些关卡时开始放慢速度。 这是不可接受的，因为《
毁灭战士》必须成为一款活跃甚至疯狂的游戏。 Carmack意识到渲染器问题非常基本，以至于他不得不寻找一种更好的渲染算法，因此他开始阅读研究文章。 结果，他实施了一种称为二进制空间分区（BSP）的技术，该技术以前从未在视频游戏中使用过，因此大大加速了
Doom引擎。
关于Carmack如何将尖端科学研究应用于视频游戏的这个故事一直令我印象深刻。 我认为，正是由于这一点，卡马克才成为了一个传奇人物。 由于许多原因，他值得被称为原型杰出的视频游戏程序员，但作为主要角色，我始终记得那集读科学文章和二进制空间划分的情节。
显然，这个故事令人印象深刻，因为术语“空间的二进制划分”似乎不仅对实现而言甚至对于理解来说都是复杂的。 很长时间以来，我一直认为卡马克是一个智能的飞跃，但是由于我不知道什么是空间的二进制分区，以及当卡马克决定使用它时该技术有多新，因此我不确定。 从Homer Simpson到Albert Einstein的规模，在
Doom上增加一个二进制空间分区是多么的巧妙？
我还想知道BSP的来源以及这个想法如何运用于Carmack。 因此，这篇文章将不仅致力于John Carmack和
Doom ，还将致力于“二进制空间分区树”（或BSP树）的数据结构历史。 事实证明，BSP树与计算科学的许多其他方面一样，源于为军事开展的研究。
是的，没错：由于美国空军的出现，第一个
Doom级E1M1出现了。
VSD任务
BSP树是计算机图形学中最困难的任务之一的解决方案。 为了渲染三维场景，渲染器必须确定从当前点可见的内容和不可见的内容。 如果您有很多时间，这并不是特别困难，但是具有自尊心的实时游戏引擎应该至少每秒30次确定世界上可见和不可见的部分。
此任务通常称为可见表面确定（VSD）任务。 与Carmack合作开发
Quake （《
毁灭战士》之后的下一个id软件游戏）的程序员Michael Abrash在他着名的《
图形编程黑皮书》中写道了VSD任务：
我想谈谈最困难的3D图形任务：确定可见表面（在每个像素中绘制所需的表面）及其近亲-剔除任务（尽快浇铸不可见多边形以加快确定可见表面）。 为了简洁起见，我将用缩写VSD表示可见曲面的定义和修剪。
为什么我认为VSD是最困难的3D任务？ 尽管诸如纹理贴图之类的光栅化问题也是令人惊奇且重要的任务，但这些任务规模相当有限，其解决方案已转变为在设备上使用3D加速器。 此外，它们仅在提高屏幕分辨率时才缩放，这是可以忍受的。
相比之下，VSD是一项无限的任务，现在使用了数十种解决方案来解决它。 更重要的是，VSD的天真表现直接随场景的复杂性而缩放，通常随着正方形或三次方函数的增加而增加，因此它很快成为渲染现实世界的限制因素。
Abrash在90年代末撰写了有关VSD问题的复杂性的文章，这是
Doom证明普通人希望能够在其家用计算机上玩图形丰富的游戏之后的几年。 在90年代初，id Software刚开始发行游戏时，它们必须在不合适的计算机上有效地工作：家用计算机被设计为可以处理文本，电子表格和其他类似应用程序。 为了实现这一目标，该公司必须采取虚构的方法，尤其是在ID Software在
Doom之前发行了多个3D游戏的情况下。 在这些游戏中，以简化VSD问题解决方案的方式限制了所有级别的设计。
例如，在
Wolfenstein 3D中 ，id Software在《
毁灭战士》之前发布了游戏，每个关卡均由沿轴对齐的墙组成。 换句话说，在德军总部的宇宙中可能有北/南壁或东/西壁，而没有其他。 此外，可以在网格中以固定的距离放置墙-所有走廊的宽度要么是一个网格单元，要么是两个网格单元，等等，但绝不能是2.5个单元。 尽管这意味着id Software团队可以创建看起来几乎相同的级别，但此限制使Carmack可以很轻松地为
Wolfenstein编写渲染器。
Wolfenstein渲染器通过将光线（光线行进）从屏幕移动到虚拟世界中解决了VSD问题。 通常，光线渲染的渲染器是光线投射的渲染器-它们通常很慢，因为解决raycaster中的VSD问题需要找到光线与世界上某些对象之间的第一个交点，这需要大量的计算。 但是，由于
德军总部的所有墙壁都衬有网格，因此，唯一可以使光束穿过墙壁的地方就是网格线。 因此，渲染器只需检查这些交点即可。 如果渲染器首先检查与玩家视点最接近的交点，然后检查第二个相近点，依此类推，直到遇到第一个墙就结束，那么VSD问题将以最简单的方式解决。 光束只是从每个像素向前移动，直到遇到某个东西为止，这在处理器时钟速度方面非常便宜。 而且由于所有墙壁的高度都相同，因此我们为每一
列像素发出光线就足够了。
渲染的这种简化使
Wolfenstein的速度足够快，可以在没有专用图形卡的那个时代的弱家用PC上工作。 但是这种方法在《
毁灭战士》中是行不通的，因为id团队决定在其新游戏中将增加诸如斜墙，台阶和天花板等不同高度的新元素。 光线行进不再适合，因此Carmack编写了另一种类型的渲染器。 将
Wolfenstein渲染器（用于每个像素列）从图像中剔除，而将
Doom渲染器从对象中剔除。 这意味着
Doom渲染器无需遍历屏幕像素并确定其颜色，而必须遍历场景中的对象并将每个对象依次投影到屏幕上。
在这种渲染器中，解决VSD问题的一种简单方法是使用z缓冲区。 每次将对象投影到屏幕上时，都会对要绘制的每个像素执行检查。 如果要绘制的对象部分比像素中已绘制的对象更靠近播放器，则可以重写其信息。 否则，您需要保持像素不变。 这种方法很简单，但是z缓冲区需要大量内存，并且渲染器仍然可以在处理器无法看到的投影级几何体上花费大量处理器时钟。
在1990年代初期，z缓冲区解决方案还有一个缺点：在使用视频适配器系统VGA的IBM兼容PC上，写入输出帧缓冲区是一项昂贵的操作。 因此，花在渲染像素上的时间将被简单地覆盖，从而大大降低了渲染器的性能。
由于写入帧缓冲区非常昂贵，因此理想的渲染器是从绘制最靠近播放器的对象开始，然后绘制紧靠其后的对象，依此类推，直到完成写入屏幕的每个像素为止。 在此阶段，渲染器应该已经知道该停止了，因此可以节省所有时间来探索玩家看不到的远处物体。 但是，以这种方式（从最近到最远）订购场景对象，无异于解决了VSD问题。 问题再次摆在我们面前：玩家可以看到什么？
刚开始，卡马克（Carmack）试图依靠“
毁灭战士”等级方案来解决这个问题。 他的渲染器首先绘制了玩家所在房间的墙壁，然后将其倒入相邻的房间，以在这些房间中绘制墙壁，这在当前房间中是可见的。 如果每个房间都是凸面的，这将解决VSD问题。 非凸房间可以分为凸“扇区”。 您可以在
上面的视频中看到这种渲染技术的运行情况，看起来像是放慢脚步，其中昵称Bisqwit的YouTuber用户演示了自己的渲染器，该渲染器可以按照相同的通用算法工作。 该算法已成功应用于
Doom发行三年后的Duke Nukem 3D游戏中，当时处理器变得更加强大。 但是在1993年，当时使用该算法的
Doom渲染器遇到了复杂级别的问题。 当两个扇区彼此内置时，这尤其明显，这是创建圆形楼梯的唯一方法。 圆形楼梯需要多个递归下降到已经绘制的扇区，大大降低了引擎的速度。
大约在同一时间，当id团队意识到
Doom引擎可能太慢时，id Software被要求将
Wolfenstein 3D移植到Super Nintendo。 SNES当时的功能甚至不如IBM兼容的PC强大，事实证明，具有光线行进技术的
Wolfenstein渲染器尽管简单，却无法在Super Nintendo设备上以足够的速度运行。 因此，卡马克开始寻找更好的算法。 实际上，正是Carmack首先探索并实现了二进制空间分区，这是针对
Wolfenstein的Super Nintendo端口的。 在
Wolfenstein，这很简单，因为所有的墙都平行于轴线。
厄运使它变得更加困难。 但是Carmack意识到BSP树也可以解决
Doom中的速度问题。
二进制空间分割
通过对3D场景进行预分割，二进制空间分区简化了VSD问题的解决方案。 现在，您已经足够了解分区为什么有用：如果您在整个场景中绘制一条线（实际上是3D平面），并且知道播放器或摄像头位于该线的哪一边，那么我们也将知道什么都没有线的另一侧将无法从相机所在的线的一侧遮挡物体。 如果您多次重复此过程，我们将获得3D场景，分为多个部分。 除了我们现在更加了解场景的不同部分如何重叠之外，这不会对原始场景有所改善。
关于3D场景划分的第一篇文章是研究人员试图为美国空军弄清楚计算机图形学是否足够先进，可以在飞行模拟器中使用。 他们在1969年的一份报告中发表了他们的发现，该报告的标题是“视觉模拟中计算机生成图像的使用研究”。 该报告的结论是，计算机图形学可用于培训飞行员。 同时，研究人员警告说，VSD的任务将使系统的实施变得复杂：
实时计算图像时需要解决的最重要的任务之一是优先级任务或隐藏线。 在我们对周围世界的日常视觉感知中，自然本身以简单的方式解决了这个问题。 不透明物体的点与位于同一视线且距离较远的所有其他点重叠。 对于计算机，此任务非常困难。 通常，确定优先级所需的计算量随着环境的复杂性呈指数增长，并且很快超过了与考虑到视角的对象图像搜索相关的计算负担。
这些研究人员提到的一种解决方案是基于创建我称之为“重叠矩阵”的解决方案，他们说这些解决方案以前曾在NASA项目中使用过。 研究人员指出，将场景分为两部分的平面可用于解决平面相对两侧对象之间的“优先级冲突”。 在一般情况下，您可能需要将这些平面显式添加到场景中，但是如果具有特定的几何结构，则可以依赖于对象的现有面。 研究人员演示了以下示例，其中
p1 ，
p2和
p3是分隔表面。 如果摄影机的视点位于其中一个平面的正面或“真”侧，则
pi为1。该矩阵根据三个分离平面和摄影机视点的位置显示了三个对象之间的关系-如果对象
ai与对象
aj重叠，则矩阵的元素
aij将等于1。
研究人员建议在硬件中实现此矩阵，并在每个帧中重新计算。 实际上，矩阵应充当大型开关或内置的z缓冲区。 渲染当前对象时，在对象列中为1时不输出部分对象的视频，但会绘制相应的行对象。
该方法的严重缺点
是需要大小为
n 2的矩阵来描述具有
n个对象的场景。 因此，研究人员决定检查是否有可能以“优先级列表”的形式显示重叠矩阵，该矩阵的大小仅为
n，并指定绘制对象的顺序。 他们立即注意到，在某些场景中，例如，在上图中所示的场景中，排序是不可能完成的（因为存在重叠周期），因此他们将大量时间用于“正确”和“错误”场景的数学定义。 最后，他们得出的结论是，至少对于“正确”的场景（场景设计人员可以轻松避免“错误”的情况），可以生成优先级列表。 但是他们把列表生成留给读者练习。 看来，这项1969年工作的主要贡献是表明，至少从
理论上讲，应该有可能使用划分平面在场景中布置对象。
仅在1980年的一篇题为“关于先验树结构的可见表面生成”的文章中，针对此算法进行了演示。 在由Henry Fuchs，Zvi Kedem和Bruce Naylor撰写的本文中，首先描述了BSP树。 这组作者说，他们的新数据结构是“一种解决方案，一种替代方法，十年前首次使用，但是由于一些困难还没有广泛传播”，因此他们对1969年美国空军工作中选择的决定做出了回应。 构建BSP树后，可以轻松地使用它来组织场景中具有优先级的对象。
Fuchs，Kedem和Naylor对BSP树的操作进行了相当清晰的描述，但是我将尝试给出一个不太正式但简短的内容。
我们从场景中选择一个多边形开始，然后将多边形所在的平面作为分割平面。 该单个多边形也成为树的根节点。 场景的其余多边形将在根分割平面的一侧或另一侧。 平面的“前”侧或“前”半空间中的多边形出现在根节点的左子树中，而平面的“后”侧或“后”半空间中的多边形出现在右子树中。 然后，我们递归地重复此过程，从左侧和右侧子树中选择多边形作为它们自己的半空间的新分割面，从而生成更多的半空间和子树。 当多边形结束时，该过程结束。
假设我们要从头到尾渲染场景的几何形状。
（这被称为“艺术家的算法”，因为这意味着距离摄像机更远的多边形将被更靠近摄像机的多边形填充，从而创建正确的渲染。）为此，我们只需要按顺序遍历BSP树即可；根据是在相对于与此节点关联的分割平面的前半部或后半部空间中，摄像机的视点所在的位置来决定是应绘制左还是右子树。也就是说，在树的每个节点中，我们首先在平面的“远”侧渲染所有多边形，然后在分离平面上渲染多边形，然后在平面的“近侧”渲染多边形。相对于相机的视点定义了“近”和“远”多边形。这解决了VSD问题，因为正如我们在几段前学到的，分离平面远端的多边形在正面不能重叠。下图显示了描述简单2D场景的BSP树的构造和遍历。在2D中，使用分割线代替分割平面，但是基本思想保持不变。Fuchs，Kedem和Naylor多次强调的BSP树的一个非常方便的功能是，它只需构建一次。这似乎令人惊讶，但是无论摄像机的视点如何，都可以使用一棵BSP树来渲染场景。在场景多边形移动之前，BSP树将一直可用。这就是BSP树对实时渲染如此有用的原因-构建树的所有复杂工作都可以提前完成，而不是在渲染时完成。Fuchs，Kedem和Naylor报告说，进一步的研究需要创建一个“好的” BSP树。 BSP树的质量取决于您选择用来定义分离平面的多边形。之前，我略过了这一点，但是如果在拆分时使用的平面与其他多边形相交，则为了使BSP算法正常工作，您需要将交叉的多边形分为两部分，以使一半指的是一个半空间，另一半指的是另一半空间。如果经常发生这种情况，那么构建BSP树会大大增加场景中的多边形数量。布鲁斯·内洛（Bruce Naylor）是1980年的文章的作者之一，后来在他1993年的文章《构建良好的分区树》中谈到了这个问题。根据Carmack的同事和id Software共同创始人John Romero的说法，本文是Carmack尝试在Doom中实现BSP树时阅读的著作之一。厄运的 BSP树
回想一下《毁灭战士》渲染器的初稿，卡马克试图通过将渲染器填充到玩家在相邻房间中的房间之外来为关卡几何图形建立渲染顺序。 BSP树是确定此顺序的一种更方便的方法，因为它们避免了渲染器不得不重复访问一个房间（或扇区）的问题，从而浪费了处理器周期。实际上，“将BSP树添加到Doom ”意味着将BSP树生成器添加到Doom级别编辑器。完成末日关卡的创建后从关卡几何生成BSP树。根据Fabien Sanglar的说法，第一个Doom的生成过程可能需要花费8秒才能达到一个级别，而所有级别则需要11分钟。生成过程是如此漫长，部分原因是Carmack BSP生成算法试图使用各种启发式方法来寻找“好的” BSP树。八秒的延迟在游戏中是不可原谅的，但考虑到BSP树为渲染器提供的性能提高，在初步生成时这似乎是完全可以接受的。生成的单个关卡BSP树在启动时被保存为装入游戏中的关卡数据的一部分。Carmack对1980年文章中描述的BSP树算法进行了重要更改：Doom发行后然后将当前级别的BSP树读取到内存中，渲染器使用该树来绘制对象，而不是从前到前，而是从前到后。 Fuchs，Kedem和Naylor在1980年的一篇文章中演示了如何使用BSP树实现具有背对背渲染的美工算法，但是该美工算法中发生了大量的重新绘制，这在IBM兼容PC上可能是昂贵的。因此，《毁灭战士》渲染器从靠近播放器的几何图形开始，然后绘制最远的图形。使用BSP树很容易实现这种反向排序，因为您可以在树的每个节点上简单地做出回溯决策。为了防止在关闭器的顶部绘制更远的几何图形，Doom渲染器使用一种隐式z缓冲区，它提供了常规z缓冲区的许多好处，同时消耗的内存更少。在屏幕的上方和下方，有一个沿水平方向跟踪重叠的数组，而在垂直方向上沿屏幕垂直方向跟踪的其他两个数组。严格来说，《毁灭战士》并不是一个完全三维的游戏，因此《毁灭战士》渲染器可以不使用真正的z缓冲区。较便宜的数据结构之所以起作用，是因为在Doom中不可能使用某些元素：水平重叠阵列起作用是因为没有倾斜的墙，而垂直重叠阵列起作用了，因为没有墙在其中放置了两个一个在其他窗口上方。《毁灭战士II》，与其前作一样复杂。但是没有人抱怨重复的血液。Quake技术的新词汇剩下的唯一棘手任务是如何将移动的Doom角色集成到使用BSP树绘制的关卡的静态几何图形中。厄运中的敌人因为正在移动而不能成为BSP树的一部分。BSP树仅适用于固定几何体。因此，Doom渲染器首先绘制关卡的静态几何图形，（使用另一个内存有效的数据结构）跟踪在其中执行绘制的屏幕的各个部分。然后，他从后到前绘制敌人，并沿着与敌人重叠的屏幕部分将其截断。这个过程并不像使用BSP树进行渲染那样理想，但是由于敌人通常少于几何体，因此速度不是问题。在Doom中使用BSP树是一个巨大的胜利。显然，Carmack机灵，足以意识到BSP树将是理想的解决方案。但是这个决定是巧妙的吗？在他关于《毁灭战士》游戏引擎的精彩著作中Fabien Sanglar引用John Romero的话说，Bruce Naylor的文章“构建良好的分区树”主要是关于使用BSP树修剪3D模型的背面。根据Romero的说法，卡马克认为该算法对于Doom仍然可能有用，因此他实现了它。对于Carmack来说，这是非常值得称赞的，因为他暗示即使其他人仍然使用此技术来渲染静态场景，他也可以看到BSP树在实时视频游戏中的有用性。厄运大师中也有同样讨人喜欢的故事：Kouchner建议Carmack阅读Naylor的文章，并想知道：“您是否可以使用BSP树不仅创建一个3D图像，还可以创建整个虚拟世界？”这些发现忽略了BSP树的历史。当美国空军研究人员首次意识到分割场景可以帮助加快渲染速度时，他们对实时加速渲染很感兴趣，因为最终他们试图创建一个飞行模拟器。 1980年的文章中再次提到了飞行模拟器示例。 Fuchs，Kedem和Naylor写道，BSP树可在飞行员用来在同一机场进行多次降落的飞行模拟器中有用。由于机场的几何形状永远不会改变，因此只能生成一次BSP树。显然，他们正在考虑实时仿真。在文章的引言中，他们甚至通过测试使用实时图形系统在不超过1/30秒的时间内创建图像的可能性来解释他们的研究。也就是说，Carmack并不是第一个考虑在实时图形仿真中使用BSP树的人。当然，预测BSP树可以以这种方式使用以及实现这一点是完全不同的。但是，即使实施了该计划，卡马克仍可能拥有比通常认为更多的背景信息。有关BSP树的WSP文章表明Carmack引用了Chen和Gordon的1991年文章，以及1990年的《计算机图形学：原理与实践》教科书。尽管引号不支持该语句，但它可能是正确的。 Chen和Gordon在1991年发表的一篇文章中描述了使用BSP树进行从前到后的渲染，这基本上与Doom使用的解决方案相同，直到“隐式z缓冲区”数据结构为止，该数据结构不允许在相邻的多边形顶部绘制远的多边形。本文提供了BSP树的出色概述，以及用于构建和显示树的伪代码。 （由于我大学的图书馆很棒，我得以浏览1990年版。）《计算机图形学：原理和实践》教科书是计算机图形学的经典著作，因此Carmack也可以拥有一本。子部门级别的E1M1：机库。可能的是，卡马克面临着一项新任务-“我如何创建一个第一人称射击游戏，该计算机在运行甚至无法执行浮点运算的处理器的计算机上运行？”-进行了自己的研究，并证明了BSP树是这是用于实时视频游戏的有用数据结构。我仍然认为这是一个令人印象深刻的结果，即使BSP树是十年前发明的，并且在Carmack读到它时已经在理论上进行了足够详细的研究。也许我们应该赞扬的主要成就是整个Doom引擎，它已成为代码的一个很好的例子。我已经讲过一次，但是我要重复一遍Fabien Sanglar撰写的有关游戏引擎的书《毁灭战士》（《Doom》（游戏引擎黑皮书：DOOM））很好地概述了游戏引擎的所有周到组件及其交互。我们一定不要忘记，VSD任务只是Carmack为使Doom引擎正常运行而必须解决的许多任务之一。除了所有内容之外，他还能够阅读并理解大多数程序员所不知道的复杂数据结构，并将其实现。这充分说明了他的技术知识水平和对理想的承诺。