毁灭战士1(应用二叉空间分割是何等天才之举?)

提问时间:2022-10-17 17:28:16阅读数:1084

推荐答案
作者admin

admin

收藏

1993 年,游戏制作公司 id Software 发售了一款第一人称射击手机游戏 《毁灭战士DOOM》,手机游戏一经发售快速爆红。在今日来看,《毁灭战士》可以说迄今为止最具影响力手机游戏之一。

《毁灭战士》发售以后的第十年(2003 年),新闻记者 彼得·库什纳David Kushner 出版发行了一本有关 id Software 的书籍,标题为《Doom 启示录Masters of Doom》,却被誉为纪录毁灭战士写作史的代表读本。多年前我曾读过这书,现如今具体内容已还记得不是很真实了,可是书中有一个有关 id Software 顶尖程序猿 罗伯特·卡马克John Carmack 故事,我印象特别深入。这儿仅对小故事做粗略地叙述(具体的剧情请继续阅读文章)。事实上,早就在《毁灭战士》开发设计早期,卡马克就察觉自己为这个游戏整理的 3D 渲染器在3D渲染一些副本时慢得像爬一样。针对《毁灭战士》这一对炫酷和效率拥有非常高标准的射击类游戏而言,这是一个比较严重的难题。意识到这一问题的严重性,卡马克需要一个更为高效的3D渲染优化算法,于是他就阅读有关毕业论文。最终,他完成了一种称为“二叉空间分割binary space partitioning(BSP)”的专业技术,很好地提高了《毁灭战士》游戏制作引擎的启动速度,而此项技术性先前从没用以网络游戏之中。

一直以来,我对这个整个故事印像十分深入。卡马克将学科前沿科学研究应用于网络游戏当中,我觉得这个恰好是他之所以是风云人物的主要原因。不管从哪个角度来说,卡马克其实都是网络游戏行业里众人皆知的常见真正的天才程序猿,只不过是上边这篇故事就是我最开始可以想起理由。

不言而喻,“二叉空间分割”这一专业术语听上去便是难度系数非常高的课题研究,可以自主阅读论文并把它大肆宣扬实属不易,因此这篇故事帮我留下了深刻印象。我一直认为卡马克的处理方式十分具有创见性,不过因为我既不明白二叉空间分割究竟是什么一项技术性,也不知道此项技术的应用那时候到底有多创新,所以我也并不确定性自己的想法正确与否。如果按从 霍默·辛普森Homer Simpson(LCTT 译注:《辛普森一家人》中那个老爸)到 阿尔伯特·牛顿Albert Einstein 顺序为奇才列举一套等级管理体系,那样卡马克将二叉空间分割技术性应用于《毁灭战士》的处理方式到底处于什么级别奇才之事呢?

与此同时,我也在想,二叉空间分割这一概念最开始是以哪儿来的,又是怎样吸引卡马克的?所以,本文不但会叙述罗伯特·卡马克和《毁灭战士》故事,还会讨论二叉空间分割树(BSP 树)算法设计的发展历程。有趣的是,BSP 树和电子信息科学行业别的很多技术性一样,最开始都始于国防研究方向。

没有错,《毁灭战士》的第一副本 E1M1 就得到了美军的启迪。

VSD 难点

BSP 树是计算机图形行业极具趣味性难点解决方案之一。举例说明,为了能3D渲染出三维场景,渲染器务必可以区别在一个特殊视角中的由此可见物体和看不到物体。假如3D渲染时间比充裕,这一规定也不算是问题;但就理想化状况而言,即时游戏制作引擎在 1 秒需要至少进行 30 次区别每日任务。

这一难题有时候被称作 可碰面检验visible surface determination(VSD)难题。之后与卡马克联合开发《雷神之锤Quake》(id Software 继《毁灭战士》以后开发设计的网络游戏)的程序猿 麦克尔·亚伯拉什Michael Abrash,在自己经典著作《图形程序开发人员指南Graphics Programming Black Book》 中写到:

我觉得探讨一下我认为 3D 里最繁杂的一个问题:可碰面检验难题(在每一个像素数上制作适宜的表层)及其与此息息相关的隐面清除难题(快速除去看不到的不规则图形,用以加速由此可见表面检测速率)。简单考虑,我们将在下文选用简称 VSD 来描述可碰面和检测隐面清除。

为什么我会觉得 VSD 是 3D 里最严峻的问题呢?虽然纹理映射等光栅化难题令人有兴趣并且也更为重要,可是相对来说,它们都是范畴相对性有限的资源每日任务。伴随着 3D 网络加速器的诞生,他们慢慢被转移至硬件配置中。与此同时,他们只伴随着分辩率的提高而变化,而屏幕分辨率的提高是相当平和的。

反过来,VSD 却像是一个无底深潭,现阶段解决计划方案也有许多。可事实上,在选用最简单的方法解决 VSD 时,其特性就会直接遭受情景复杂性产生的影响,而场景下的复杂性一般会以m2级或立方米级的方式扩大。因此在3D渲染环节中,VSD 很快就变成限制因素。[1]

亚伯拉什是在上世纪九十年代末所写的有关 VSD 难题的那些艰难,这就是在《毁灭战士》以后多年,这个游戏验证了平常人盼望可用自己家电脑玩很吃图型的配置手机游戏。九十年代初期,id Software 成立后推出了一些游戏。虽然当年的电子计算机还就是用来解决文本与报表或是实行别的每日任务,未曾想过要在墙上游戏运行,id Software 一定要对发售的网络游戏开展程序编写,使之可在电脑中顺畅运作。要实现这一飞越,特别是为了让在《毁灭战士》以前 id Software 公开发行的极少数 3D 电脑游戏电脑上运作,id Software 务必作出创新。在各种游戏里面,每一个副本在设计的时候都受到一定限定,便于比较容易处理 VSD 难题。

比如,在《毁灭战士》以前,id Software 推出了《德军总部 3D 版Wolfenstein 3D 版》,这款手游的每一个副本均是由与纵坐标齐平的墙面构成。换句话说,在《德军总部 3D 版》的游戏界面里,你所看到的仅有南北方方位或是东西方向的墙面。在游戏里,墙面与墙间拥有固定间距,全部过身的总宽或者一个格子,或者2个格子这些,但绝不会发生 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渲染具体的全过程。这一优化算法一样应用到了《毁灭公爵 3D 版》之中,这个游戏在 《毁灭战士》 发布三年之后发售,那时候 CPU 性能也更强大了。1993 年,虽然在硬件配置上已经能够游戏运行了,可是应用这一算法的《毁灭战士》渲染器在繁杂的层级结构上依然主要表现费劲,尤其是在屋子切分出的各部件互相嵌入的情形下。不巧合的是,这种层级结构恰好是结构环状室内楼梯等物体的唯一方法。顺着环状室内楼梯一直走下去,直至踏入早已制作好的地区,因为这当中涉及到数次循环系统降低健身运动,造成游戏制作引擎的启动速度大幅度降低。

在 id Software 团队精神到《毁灭战士》游戏制作引擎速度很有可能太慢时,公司已面临别的每日任务:将《德军总部 3D 版》迁移到非常任天堂游戏机(通称“超任”)上。那时候,超任的性能提升 IBM 一机多用还需要差。结果显示,虽然光线投影渲染器比较简单,但是要想在超任上更快运作根本不可能。因此,卡马克下手科学研究更加高效率的优化算法。实际上,正是为了能成功将《德军总部》迁移到超任,卡马克初次探讨了二叉空间分割技术性,并把它付诸于运用。因为《德军总部 3D 版》的墙面与纵坐标齐平,因此二叉空间分割关键技术下去也非常简单立即;可是《毁灭战士》的现象则较为复杂。但是,卡马克发觉,二叉空间分割树一样可用于处理《毁灭战士》速率太慢问题。

二叉空间分割

二叉空间分割binary space partitioning(BSP)会提前把 3D 情景切分为多个一部分,使 VSD 难题便于处理。说到这里,你必须先了解一下为何切分情景能够见效:假如你在情景上印根线(相匹配三维空间里的一个平面图),你还可以强调游戏玩家或是监控摄像头角度在这个位置的哪一侧,在这个位置另一侧的物体没法挡住游戏玩家所属一侧的物体。假如反复多次这一实际操作,该三维场景最终都会被切分为好几个范围,这也不是对初始场景下的改善,不过现在你知道了想要了解更多关于场景下的不一样一部分会怎样互相阻拦。

初次论述以上三维场景分离的是美军的研究者,她们曾试着向美军证实计算机图形已经相当优秀,能够运用到飞行模拟器行业。1969 年,他将研究表明发表于一份名为《计算机生成图像在图形仿真中的应用研究》的声明中。该的报告汇总一部分强调,计算机图形适合于练习航空员,却也警示说,其实践应用可能受限于 VSD 难题:

即时数字图像处理要解决的一个关键问题是优先难题,亦称隐藏线难题。在我们平常用眼睛观查外部时,自然界替我们轻易克服了这一难题:透明物体上的一个点,冲淡了同一视觉效果方位、且间距很远的所有其他物体。但在计算机中,此项每日任务却很困难。数字图像处理要解决的优先难题,伴随着自然环境复杂性的提高,计算量会呈指数级增长,随后便会超出制作物体透视图所需要的测算负荷。[2]

这些人在声明中给出了一项根据结构“挡住引流矩阵”的解决方案,这一计划方案据说早些时候曾被应用于 NASA 的项目当中。研究员指出,平面将场景一分为二,可用来解决平面两侧物体之间存在的“任何优先级问题”。通常情况下,可能需要明确将这些平面添加到场景中,但对某些几何体,只需借助你已经拥有的几何体的表面即可。他们举了一个例子,如下图:p1、p2以及 p3是三个不同的平面,如果摄像机视角位于其中一个平面的前方,即“正”面,pi的值就等于 1。这种矩阵展示出基于三个不同平面和摄像机视角位置的三个物体之间的关系 —— 如果物体 ai遮挡了物体 aj,那么 aij在此矩阵中的数值等于 1。

研究人员指出,这种矩阵可以应用到硬件中,对每一帧进行重新评估。该矩阵基本上可以用作大型的开关,或者一种预置的 Z 缓冲区。在绘制给定的物体时,如果在物体所在列上得出数值 1,并且所在行已经在绘制中,那么物体被遮挡的部分就不会绘制出来。

不过,该矩阵方法的主要缺点在于,为了在场景中表示出 n 个物体,你需要一个尺寸为 n2的矩阵。于是,研究人员们继续深入,探究将遮挡矩阵表示为“优先级列表”的可行性,该列表的尺寸是 n,可确定物体绘制的顺序。他们随即发现,诸如上图此类场景根本无法确定顺序(因为它存在循环阻塞的现象)。因此,他们花了很多时间来阐明“合适”与“不合适”场景之间的数学区别。最后,他们得出了一个结论:至少对于“合适的”场景下,优先级列表是可以制作出来的;而对场景设计师来说,避免设计出“不合适”的场景也不是一件难事。但是,他们并没有说明如何生成该列表。可以说,这份 1969 年的研究的首要贡献在于提出了:至少,在理论上,可以采用平面分割的方法,对场景中的物体进行渲染排序。

直到 1980 年,一份题为《基于优先级树结构的可见表面生成》的论文提出了解决该问题的具体算法。在这份论文中,作者 亨利·福克斯Henry Fuchs、泽维·凯德姆Zvi Kedem 以及 布鲁斯·内勒Bruce Naylor 介绍了 BSP 树。他们指出,这种新的数据结构“可以替代十年前首次使用,但由于一些问题未得到广泛发展的方案”(即前文 1969 年美国空军相关研究中的方案)。[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]

《毁灭战士》中的 BSP 树

别忘了,卡马克首次为《毁灭战士》设计渲染器时,通过让渲染器渲染玩家所在房间之外的临近房间,试图为关卡几何图形建立一套渲染顺序。对此,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 树渲染静止的场景时,发现该技术可以用于实时游戏领域。在《Doom 启示录》中也有给卡马克戴高帽的故事。该书作者库什纳认为,卡马克在阅读内勒的论文之后,问了自己,“如果使用 BSP 技术创造一整个虚拟世界,而不仅仅是一张 3D 图像,会怎么样呢?”[7]。

这些“片面之词”忽视了 BSP 树的发展历史。当美国空军研究人员开始意识到场景分割可能会加快渲染任务的时候,他们就对提升 实时渲染的速度产生了兴趣,毕竟他们当时试图创建一个飞行模拟器。1980 年,同样的案例再次出现在了福克斯等人的论文中,他们探讨了 BSP 树如何应用于飞行模拟器中,帮助飞行员进行训练:飞行员用它来反复练习将飞机降至同一空港。由于空港的地形不会发生改变,BSP 树只需生成一次,即可一劳永逸。很明显,他们考虑的是实时模拟。在论文的引言部分,福克斯等人还谈到实时图形系统必须在至少 1/30 秒内生成一张图像,由此激励了他们的研究。

因此,卡马克不是第一个想到在实时图形模拟中应用 BSP 树的人。诚然,设想与付诸实践是两码事。但是即使在实施的过程中,卡马克受到的帮助与指导可比人们想象的要多得多。至少是到这篇文章写成之时,BSP 树的 维基百科词条页面显示,卡马克参考了 1991 年 陈Chen 和 戈登Gordon 的一篇论文,以及 1990 年的一本教材《计算机图形学:原理及实践》。尽管该页面并未提供引用信息,但可信度没什么问题。陈和戈登的论文介绍了运用 BSP 树由前向后的渲染方法,这种方法与《毁灭战士》中用到的方法基本一致,还包括了我称之为“隐式 Z 缓冲区”的数据结构,可用于防止远处的图形在绘制时遮挡近处的图形。《计算机图形学:原理及实践》详细介绍了 BSP 树,以及一些构建并展示 BSP 树的伪代码(非常感谢我大学的图书馆,让我能够一睹这本教材 1990 年的版本)。因为这本书是计算机图形学的经典之作,所以卡马克很可能也有一本。

然而,卡马克发现自己遇到一个新问题:如何让第一人称射击游戏在一台 CPU 甚至都无法进行浮点操作的电脑上运行呢?通过调查研究,他证明了 BSP 树的数据结构非常适用于实时电子游戏渲染。尽管 BSP 树早已提出,而且到了卡马克的时代,相关理论已经非常成熟了,但我始终认为,卡马克的做法可谓惊人之壮举。也许,得到人们称誉的应该是整个《毁灭战士》的游戏引擎,它的确非常精致。我在前文也提及过,但是桑格勒德的《游戏引擎黑皮书:毁灭战士Game Engine Black Book: DOOM》 很好地讲解了这款游戏引擎的非凡之处,以及这些优势相互契合之法。要明白,VSD 问题只是卡马克在编写《毁灭战士》游戏引擎时需要解决的诸多问题之一。不得不说,面对不为大多数程序员所知的复杂的数据结构,卡马克能够查阅相关文献,将其付诸实践,仅此一点就足以说明其技术之精湛、匠心之独到。

如果你喜欢这篇文章,欢迎关注推特 @TwoBitHistory,也可通过RSS feed订阅,获取最新文章(每四周更新一篇)。

  1. Michael Abrash, “Michael Abrash’s Graphics Programming Black Book,” James Gregory, accessed November 6, 2019, http://www.jagregory.com/abrash-black-book/#chapter-64-quakes-visible-surface-determination.??

  2. R. Schumacher, B. Brand, M. Gilliland, W. Sharp, “Study for Applying Computer-Generated Images to Visual Simulation,” Air Force Human Resources Laboratory, December 1969, accessed on November 6, 2019, https://apps.dtic.mil/dtic/tr/fulltext/u2/700375.pdf.??

  3. Henry Fuchs, Zvi Kedem, Bruce Naylor, “On Visible Surface Generation By A Priori Tree Structures,” ACM SIGGRAPH Computer Graphics, July 1980. ??

  4. Fabien Sanglard, Game Engine Black Book: DOOM (CreateSpace Independent Publishing Platform, 2018), 200. ??

  5. Sanglard, 206. ??

  6. Sanglard, 200. ??

  7. David Kushner, Masters of Doom (Random House Trade Paperbacks, 2004), 142. ??

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

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

本文由 LCTT原创编译,Linux中国荣誉推出

0
其他回答
相关问答
关于 联系 最新 地图