在《毁灭战士》中应用二叉空间分割（BSP）是何等天才之举？

来源：网络浏览：39 2022-11-05 21:28:01

1993年，游戏开发公司id Software发行了第一人称射击游戏《毁灭战士DOOM》，游戏一发行就爆炸了。今天，《毁灭战士》可以说是历史上最有影响力的游戏之一。

《毁灭战士》发布后的第十年，也就是2003年，记者大卫库什纳David Kushner出版了一本关于身份软件的书，标题为《Doom 启示录Masters of Doom》。之后，被认为是记录破坏战士创作史的典范读物。几年前读过这本书，现在内容不太记得了，但是有id Software的首席程序员约翰卡马克John Carmack的故事，我印象非常深刻。这里大致说明一下故事。具体故事请往下读。事实上，卡马克在《毁灭战士》开发之前，就发现为这个游戏编写的3D渲染器在渲染几个关卡时像爬一样慢。对于《毁灭战士》这一对动感和速度要求相当高的射击游戏来说，这是一个非常严重的问题。意识到这个问题的严重性，卡马克需要更有效的渲染算法，开始阅读相关论文。最后，他实现了一种叫做“二叉空分binaryspacepartitioning(bsp )”的技术，这种技术大大提高了之前没有用于电子游戏的《毁灭战士》游戏引擎的运行速度。

一直以来，我对这个故事的印象很深。卡马克将学术前沿研究应用于电子游戏，我想这就是他成为传奇人物的原因。无论从哪个角度看，卡马克都应该是电子游戏行业家喻户晓的典型天才程序员，但上面的话是我首先想到的原因。

显然，“二叉空分”这个术语听起来是一个相当高难度的课题，很难自己阅读和运行论文，所以这个故事令人印象深刻。我曾认为卡马克的做法非常有创意，但由于不知道二叉空分是什么技术，也不知道该技术当时是如何创新的，我不知道自己的看法是否正确。从荷马辛普森HomerSimpson(LCTT译注：《辛普森一家人》的那位大叔)到阿尔伯特爱因斯坦Albert Einstein依次列举了天才的一系列等级体系，卡马克将二叉空分技术划分为0755

同时，我在想，二叉空分这个概念最初是从哪里来的，以及是如何被卡马克吸引的。因此，本文不仅讨论约翰卡马克和《毁灭战士》的故事，还讨论二叉树( BSP树)数据结构的发展历史。值得一提的是，BSP树和计算机科学领域的许多其他技术一样，最初起源于军事研究领域。

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

VSD难题BSP树是计算机图形学领域最困难的难题的解决方案之一。例如，要渲染三维场景，渲染器必须能够区分在特定角度可见的对象和不可见的对象。如果渲染时间足够的话，这个要求也不是大问题；但理想情况下，实时游戏引擎每秒至少需要完成30次划分任务。

该问题有时被称为面检测可视化( VSD )问题。之后，与卡马克合作开发《毁灭战士》(idsoftware继《雷神之锤Quake》之后开发的游戏)的程序员迈克尔艾布拉什Michael Abrash在自己的著作《毁灭战士》中写道

在我看来，我想探讨3D中最棘手的问题之一。面对面检测问题(在每个像素点绘制合适的表面)以及与之密切相关的隐藏面去除问题)用于快速去除不可见的多边形，提高可见表面的检测速度。为了简单起见，以下采用缩写的VSD表示面对面检测和隐藏面消除。

你为什么认为VSD是3D中最棘手的问题？光栅化问题(如纹理映射)是一项更令人感兴趣、更重要但范围相对有限的任务。随着3D加速器的出现，它们逐渐转移到硬件上。同时，只是随着屏幕分辨率的提高而增加，分辨率的增加比较温和。

相反，VSD就像一个无底洞，现在的应对方案也有很多。但实际上，使用简单的方法处理VSD时，其性能会直接受到场景复杂性的影响，场景复杂性通常会在平方或三次方级别上增加。因此，在渲染过程中，VSD会立即成为限制因素。 [1]在[1]中

阿布拉什在20世纪90年代末写的关于VSD问题的这些困难，这是在《图形程序开发人员指南Graphics Programming Black Book》的后几年，这个游戏证明了普通人在家用电脑上玩图形配置的游戏。 90年代初，id Software成立以来发行了几款游戏。当时的计算机只用于处理文字和表格，以及执行其他任务，但你可能从未想过运行游戏。 id Software必须对发布的游戏进行编程，以便在计算机上顺利运行。为了实现这一飞跃，特别是为了能够在电脑上运行id Software在《毁灭战士》以前发行的少数3D游戏，id Software必须进行革新。在这些游戏中，所有级别在设计时都受到限制，以便更容易解决VSD问题。

例如，在《毁灭战士》之前，id Software发布了《毁灭战士》。这个游戏的每一级都由坐标轴和平的墙壁组成。也就是说，在《德军总部 3D 版Wolfenstein 3D 版》的游戏画面中，只能看到南北方向或东西方向的墙壁。在游戏中，墙壁和墙壁之间有一定的间隔，所有的通道都有宽度、一个方格、两个方格等，但2.5个方格是绝对不会出现的。这样，id Software团队只能设计看起来很相似的级别，但是制作卡马克为《德军总部 3D 版》的渲染器很简单。

通过将屏幕上的光线“一齐”照射到虚拟游戏世界中，《德军总部 3D 版》的渲染器解决了VSD的问题。通常，使用光线的渲染器称为“光线投射”渲染器。此渲染器通常速度较慢，因为要解决内部VSD问题，必须找到光线与游戏中物体之间的第一个交点。通常需要很多计算。但是，在《德军总部 3D 版》中，所有的墙壁都与网格平齐，因此光与墙壁相交的位置只能在网格线上。这样，渲染器只需逐个检查这些交点。当渲染器最后遇到第一面墙时，渲染器首先从离玩家视点最近的交点开始检查，然后检查下一个最近的交点。这样就很容易解决了VSD问题。光从各像素点向前方投射，可以在与画面物体接触时停止。因为从CPU资源来看，投影的成本很低。实际上，由于每面墙的高度相同，所以对于同一列中的像素点，投影的光只需要一条。

虽然当时还没有专门的显卡，但《德军总部 3D 版》通过这种巧妙的方法在低配置的电脑上正常工作。但是，这个方法不适用于《德军总部 3D 版》。因为id Software在这个新游戏中添加了很多新元素——的倾斜墙面、楼梯和高低不平的天花板。光照的方法当然也行不通，所以卡马克制作了新的渲染器。《毁灭战士》的渲染器关注图像，将光线投影到屏幕上由像素表示的列上，而《德军总部 3D 版》关注物体。换言之，《毁灭战士》的渲染器记录游戏场景中的所有物体，并将其投影到屏幕上；判断每个像素点的颜色，而不是记录屏幕上的像素点。

强调物体的渲染器可以使用z缓冲区来解决VSD问题，相对简单。每次将物体投影到屏幕上时，都必须检查用于绘制的每个像素点。如果想要描绘的物体的部分比已经在对象像素点上描绘的物体更接近玩家，则可以将其覆盖。否则，你必须保持像素不变。虽然方法很简单，但是z缓冲区的内存要求很高，渲染器仍然可能需要大量的CPU资源来投影玩家看不到的水平几何体。

在20世纪90年代，使用z缓冲区的方法还有其他缺点。 IBM交换机( PC )具有名为VGA的显示适配器系统，在这些计算机中，将图像写入帧缓冲区的成本非常高。因此，绘制到稍后复盖的像素会花费很长时间，从而降低渲染器的性能。

考虑到将图像写入帧缓冲区的成本非常高，理想的渲染器需要先绘制最接近玩家的对象，然后绘制相对接近的对象，将信息写入屏幕上的每个像素点。在这种情况下，渲染器将停止行为，从而大大缩短渲染远处看不见的物体的时间。这种将物体从近处和远处排列的方法也可以解决VSD问题。那么，问题又来了。玩家能看到的是什么？

最初，卡马克试图依靠《毁灭战士》的关卡布局来解决VSD问题。首先用渲染器画出玩家当前所在房间的墙壁，然后玩家冲进隔壁房间，画出隔壁房间的墙壁。由于各房间互不遮挡，用该方法也可以解决VSD的问题。被相互遮挡的房间可以分割成几个相互不遮挡的“区域”。在YouTube的视频中，Bisqwit展示了使用自己制作的相同算法的渲染器。以非常慢的速度运行时，可以知道渲染的具体过程。该算法也应用于《毁灭战士》。这款游戏在《毁灭公爵 3D 版》发售三年后发布，当时的CPU性能也得到了进一步的提升。 1993年，尽管可以在硬件上运行游戏，但使用该算法的《毁灭战士》渲染器在复杂的分层结构中非常棘手，尤其是当房间被分割的部分相互嵌套时。不巧的是，这种分层结构是制造环状楼梯等物体的唯一方法。沿着环形楼梯向下，直到进入绘制的区域，其中涉及多次循环下降运动，使得游戏引擎的运行速度大幅降低。

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

二叉空分二叉空分二叉空分( binaryspacepartitioning，bsp )预先将三维场景分成几个部分，有助于解决VSD问题。现在，您需要了解为什么分割场景很有效。在场景中绘制一条线时，可以指出玩家或摄像机的视点位于这条线的哪一侧，而这条线另一侧的物体无法遮挡玩家所在一侧的物体。如果多次重复此操作，则该三维场景最终将被分割为多个区域。虽然这并不是对原始场景的改进，但我们知道场景的不同部分如何相互阻塞。

第一次描述上述三维场景分割的是美国空军的研究员，他们试图向美国空军证明计算机图形非常先进，可以应用于飞行模拟器领域。 1969年，他们发现发表在一份名为《毁灭战士》的报告中。该报告总结指出计算机图形可以用于飞行员训练，但警告说实际使用可能取决于VSD问题。

实时图像处理中需要解决的一个重要问题是优先级问题或隐藏线处理问题。当我们平时用眼睛观察外界的时候，大自然为我们很容易地解决了这个问题。不透明物体上的一个点掩盖了同一视觉方向且分开的所有其他物体。但是，在计算机上，这个任务非常困难。图像处理中应该解决的优先顺序问题，随着环境复杂性的增加，计算量会呈指数函数增加，会超过制作物体透视图所需的计算负荷。 [2]根据[1]或[2]

他们在报告中提出了基于“屏蔽矩阵”构建的方案。据悉，该方案早些时候已应用于美国航天局的项目。研究人员表示，平面可以将场景分为两部分，用于解决平面两侧物体之间存在的“优先级问题”。通常，您可能需要将这些平面显式添加到场景中，但根据几何体的不同，您只需使用已有的几何体曲面即可。他们举了一个例子。如下图所示，p1、p2和p3是三个不同的平面，如果相机视角位于任何平面的前方，即“正”面，则pi值为1。此矩阵描述了三个不同的平面以及基于摄像机的视角位置的三个物体之间的关系。 ——如果物体ai遮挡了物体aj，则该矩阵中的aij的数值等于1。

研究人员表示，该矩阵可以应用于硬件，并逐帧重新评估。该矩阵基本上可以用作大型交换机，也可以用作预置的z缓冲器。绘制一个物体时，如果物体在某一列中出现数值1，并且该行已经在绘制中，则物体被隐藏的部分将不会被绘制。

但是，该矩阵法的主要缺点是，为了在场景中表示n个物体，需要n2大小的矩阵。因此，研究人员继续深入，探索将屏蔽矩阵表示为“优先级列表”的可能性。这个列表的大小是n，可以确定物体描绘的顺序。他们很快发现，如上图所示的场景，因为有循环块，所以无法决定顺序。因此，他们花了很多时间来弄清楚“合适”和“不合适”场景之间的数学差异。最后，我们得出的结论是，至少在“合适的”场景中，可以创建优先级列表。另外，对于场景设计师来说，避免设计“不合适的”场景也不是一件难事。但是，他们没有说明如何生成这个列表。这项1969年研究的首要贡献，至少在理论上可以说是提出了可以用平面分割的方法来渲染和排序场景中的物体。

到1980年，《计算机生成图像在图形仿真中的应用研究》论文提出了解决这个问题的具体算法。本文作者亨利福克斯Henry Fuchs、泽维凯水库Zvi Kedem、布鲁斯内尔夫Bruce Naylor介绍了BSP树。他们指出，这一新的数据结构“可以替代10年前首次使用但在一些问题上没有广泛发展的方案”。 [3]生成bsp树后，可用于确定场景中物体的优先级。

三人在论文中对BSP树的结构做了相当易读的说明。但是，本文试着用更常见的语言向大家介绍。

首先，在场景中选择多边形，并将该多边形所在的平面作为分割平面。多边形也用作树的根节点。场景中的剩馀多边形分布在分割平面的两侧。分割曲面“向前”或与分割平面相交后“向前”一半的多边形落在根节点左侧左侧的子树中。与分割曲面的“后方”或“分割平面”相交后，“后方”一半的多边形将落入右侧的子树中。其次，递归重复这个过程。在左边的子树和右边的子树中各选定一个多边形，作为各个空间的新分割平面，再将更多的子空间和子树一分为二。直到选择了所有多边形为止，三叉空间的分割也结束。

假设您希望从后向前渲染场景中的几何体。 (这就是所谓的“画家算法painter's algorithm”。因为在绘制时，离相机远的多边形会被离相机近的多边形覆盖，从而正确进行渲染。要实现该算法，必须依次遍历BSP树。左右子树的渲染顺序取决于相机视点与节点所在的分割平面之间的位置关系。因此，对于树上各节点，首先渲染位于距离分割平面"远"侧的所有多边形，接着渲染位于平面上的多边形，最后渲染位于距离平面"近"侧的所有多边形——的"远"和"远" 如上所述，离分割平面远的一侧的多边形无法遮挡近的一侧的物体，因此可以用该方法解决VSD问题。

下图显示了简单的二维场景BSP树的结构和遍历过程。在二维中，分割平面是分割线，但基本原理与复杂的三维场景没有区别。

第一步：布线分割线落在d墙上，将剩下的几何图形分成两组。

第二步：继续分割D墙两侧的空间。 C墙是其一侧唯一的墙，不需要再分了。另一方面，b壁形成新的分割平面。 A墙与新的分割平面相交，因此必须分割为两堵墙。

第三步：参考右上角的视点，将墙壁从后向前排序，有助于执行画家的算法。这就是树的顺序扫描过程。

福克斯、凯达姆和内雷多次强调BSP树的优势。你只需要构建一次就可以了。虽然你可能不相信，但是实际上无论相机的视角在哪里，都可以使用同一个BSP树来渲染场景。除非场景中的多边形移动，否则不会禁用BSP树。因此，在实时渲染任务中构建BSP树非常实用的——树时，所有困难的任务都可以在渲染工作开始之前完成。

同时，三人还提到了需要进一步深入研究的问题。到底要怎样才能构筑“高质量”的BSP树呢？ BSP树的质量取决于用作分割平面的多边形的选择。虽然在上一句中跳过了这个问题，但是如果用作分割平面的多边形与其他多边形相交，则为了使BSP算法发挥作用，必须将相交的多边形分为两个，并将两个部分分成不同的空间。但是，如果这种现象反复出现，BSP树的构建将大幅增加场景中的多边形数。

内勒随后在1993年的论文《基于优先级树结构的可见表面生成》中提到了这个问题。猕猴的同事、id Software的共同创始人约翰罗梅罗John Romero指出，这篇论文是猕猴在《构建高质量的分割树》引入BSP树时阅读的论文之一。 [4]根据[1]所述的信息处理设备，其中

请不要忘记《毁灭战士》的BSP树。当卡马克首次为《毁灭战士》设计渲染器时，他试图通过渲染渲染器所在房间外的隔壁房间来建立关卡几何体的渲染顺序。相比之下，BSP树是一个不错的选择，因为当玩家进入前一个房间(区域)时，它可以避免渲染器多次工作，从而节省CPU资源。

实际上，“将BSP树引入《毁灭战士》”意味着将BSP树生成器引入《毁灭战士》的级别编辑器。《毁灭战士》标高的创建完成后，将基于标高的几何图形生成BSP树。据程序员法比安桑格拉德( Fabien Sanglard )介绍，在原始的《毁灭战士》中，生成一个级别的BSP树需要8秒钟，所有级别的总和需要11分钟[5]。生成时间长是因为卡马克使用的BSP生成算法。该算法尝试使用各种启发式方法来找到“高质量”的BSP树。在执行中，8秒的延迟可能是不可接受的；但是，离线等8秒钟，时间不会太长。特别是BSP树提高了渲染器的性能。为每个级别生成的BSP树在游戏启动时作为级别数据加载。

卡马克改造了1980年论文中提出的BSP树算法。因为当《毁灭战士》开始执行时，当前级别的BSP树被读入内存，渲染器通过BSP树从前到后而不是后描绘物体。福克斯三人在其论文中表示，BSP树可以用于执行由后向前的画家算法，但是画家算法导致了很多重复的绘制任务，对IBM交换机来说负担很大。因此，《毁灭战士》的渲染器会改变方向，首先绘制离玩家近的图形，然后绘制离玩家远的图形。由于可以在树的每个节点上反向扫描，因此可以在BSP树中轻松执行此反向排序。《毁灭战士》的渲染器使用隐式z缓冲区，以防止绘制的离散图形隐藏在附近的图形中。该缓冲区不仅具有常规z缓冲区的优点，而且具有较低的内存要求。该z缓冲器有两组排列，一组记录水平方向的遮挡关系，另两组记录来自画面上部和下部的垂直方向的遮挡关系。《毁灭战士》的渲染器可以不使用实际的z缓冲区。因为从技术上来说，这不是真正的3D游戏。 BSP树的数据结构成本不高，但之所以能发挥作用，是因为《毁灭战士》不会出现以下问题。水平方向的遮蔽排列之所以发挥作用，是因为这个游戏没有倾斜的墙壁；垂直遮挡排列之所以有效，是因为这个游戏中不存在有上下两个窗户的墙壁。

剩下的棘手问题是，如何将在《毁灭战士》中运动的角色合并到BSP树中绘制的静止级别几何体中。这个游戏的敌人不能进入BSP树中。因为他们会移动，BSP树只作用于静止的几何形状。渲染器首先绘制静止的标高几何，同时结合其他内存使用效率较高的数据结构记录屏幕上用于绘制的分区区域。然后，渲染器从后面依次描绘敌人，消除隐藏在屏幕区域的敌人。与使用BSP树进行渲染相比，此过程稍微没有效果。但是，在检查站看到的敌人数量比几何图形的数量少，所以速度不是严重的问题。

将BSP树应用于《毁灭战士》可以说是一个巨大的成功。卡马克可以认为BSP树是解决VSD问题的最佳方法，无疑非常聪明。但是，这能说是天才的行动吗？

桑格勒在一本关于《毁灭战士》游戏引擎的书中引用了罗梅罗的话。内勒的论文《毁灭战士》主要描述了使用BSP树去除3D模型的背后。 [6]罗梅罗说，卡马克认为该算法在《构建高质量的分割树》仍然有效，所以他放手将BSP技术应用于这款游戏。然而，这在一点奉承的意义上，——暗示了这种技术可以用于实时游戏领域，同时卡马克渲染其他人仍然使用BSP树静止的场景。在《毁灭战士》中也有麦当劳的故事。该书的作者库什纳认为，卡马克在阅读完内莱的论文后，问自己：“如果使用BSP技术制作出不仅仅是3D图像，而是整个虚拟世界会怎么样？” [7]。

这些“片面之词”无视了BSP树的发展历史。当美国空军的研究人员开始意识到场景分割可能会加速渲染任务时，他们对加速实时渲染产生了兴趣。结果，他们本来想做飞行模拟器。 1980年，同样的情况再次出现在福克斯等人的论文中，他们讨论了BSP树如何应用于飞行模拟器，帮助飞行员进行训练。飞行员用这个反复练习把飞机降到同一机场。由于机场地形不变，BSP树只需生成一次，就可以一次结束。很明显，他们在考虑实时模拟。在论文的引言部分，福克斯等人还表示，实时图形系统必须至少在1/30秒内产生图像，鼓励了研究。

因此，卡马克并不是第一次考虑将BSP树应用于实时图形模拟。的确，构想和实践是两回事。但在实施过程中，卡马克也得到了比人们想象中更多的帮助和指导。至少在这篇文章写作的时候，根据BSP树的维基百科的标题页，卡马克参考了1991年陈陈和戈登Gordon的论文，以及1990年的教材《Doom 启示录》。此页面不提供引用信息，但可靠性没有问题。陈和戈登的论文介绍了利用BSP树的从前到后渲染方法。该方法与《计算机图形学：原理及实践》使用的方法基本一致，包括我称为“隐式z缓冲器”的数据结构，可以用于防止远处的图形在绘制时隐藏近处的图形。《毁灭战士》详细介绍了BSP树和构建BSP树并展示的伪代码。 (感谢大学图书馆让我能看到这本教材1990年的版本。这本书是计算机图形学的经典之作，所以卡马克很可能也有一本。

然而，卡马克发现了一个新的问题：如何让第一人称射击游戏在CPU连浮点操作都没有的计算机上运行？通过调查研究，他证明了BSP树的数据结构非常适合实时游戏渲染。 BSP树已经提出，到了猕猴时代，相关理论已经非常成熟，但我认为猕猴的做法是一个惊人的壮举。也许，被人们称赞的是《计算机图形学：原理及实践》的整个游戏引擎。它确实非常精致。前文也提到过，桑格勒的《毁灭战士》很好地说明了这个游戏引擎的非凡之处，以及这些优势如何互相匹配。请理解，VSD问题只是卡马克创建《游戏引擎黑皮书：毁灭战士Game Engine Black Book: DOOM》游戏引擎时需要解决的众多问题之一。不得不说，面对众多程序员不了解的复杂数据结构，卡马克也能查阅相关文献并付诸实践，只有这样才能说明技术的精深和匠心的独特。

如果你喜欢这篇文章，请关注推特@TwoBitHistory。您也可以通过RSS订阅源订阅以获取最新文章(每4周更新一次)。

Michael Abrash，“michaela brash’sgraphicsprogrammingblackbook，”James Gregory，accessed November 6，2019，33558 ww.ja gres

R. Schumacher，B. Brand，M. Gilliland，W. Sharp，" studyforapplyingcomputer-generatedimagestovisualsimulation，" aid December 1969，accessedonnovember 6，2019，https://apps.dtic.mil/dtic/tr/full text "

Henry Fuchs，Zvi Kedem，Bruce Naylor，“onvisiblesurfacegenerationbyaprioritreestructures，”ACM SIGGRAPH Computer Graphics，jute

Fabien Sanglard，gameengineblackbook:createspaceindependentpublishingplatform，2018 )，200。

三星乐园，206

三星乐园，200

David Kushner，mastersofdoom ( randomhousetradepaperbacks，2004 )，142。

via:https://twobithistory.org/2019/11/06/doom-bsp.html

作者： Two-Bit History选题： lujun9972译者： aREversez校对： wxy

本文由LCTT原创编译，Linux中国荣誉上市