一个码农是如何用游戏推动计算机图形学的？

本文首发于“天美妙妙屋”知乎号
https://zhuanlan.zhihu.com/p/408570779

天美妙妙屋 是天美游戏工作室群内部由游戏策划、运营和热爱游戏的朋友组成的非官方组织，都是有感而发的游戏及产业研究，并不构成游戏开发及投资建议。

自上世纪70年代光栅显示器诞生以来，计算机图形学便在创造社会价值方面做了不少贡献。往逼格高了讲，曾经用于国土信息和自然资源的绘制，为国家提供了治理和开发的科学依据。从小的层面来看，无论是社畜拿CAD画几张工程图，还是拖着疲惫的躯体回家打开游戏抚慰一下身心，我们都能看到图形学的影子。

归根究底，它就是用数学算法让二维和三维画面在屏幕上显示的科学，非常亲民。

所以图形学研究有个很有意思的现象，虽然许多前沿技术都诞生在军事或者科研领域，但将其普及并「用之于民」的，游戏可以说是其中的中坚力量 —— 开发了《Doom》的约翰·卡马克（John Carmack），背后就有几个很有代表性的例子。

凡是涉猎过计算机技术的人，应该都听过他的名字，这是个被誉为「编程界莫扎特」的男人，能力离谱到面对任何需求，都能在一周内完成基础设计工作。

作家大卫·库什纳（David Kushner）也在《Doom启示录》中写提过一段轶事，说这人在读初中的时候为了从学校弄台苹果II型电脑，用铝热剂和凡士林调制了一种粘性物质把窗户给融给了，结果被抓去少管所服刑一年，可见他对计算机技术已经痴迷到了魔怔的程度。


稍微列举一下卡马克在计算机图形学领域的成就，就包括「自适应贴图刷新」（Adaptive tile refresh）、「二叉空间分割」（Binary space partitioning）和「卡马克反转」（Fast Inverse Square Root）等技术的应用，他们全都和游戏有关，最后又惠及医疗和教育等其它领域。

自适应贴图刷新

约翰·卡马克对游戏产生兴趣是从1978年的一个暑假开始的，那时只有八岁的他，在游乐场初次体验到了《太空侵略者》（Space Invaders），这是一款在全球引爆过热潮的街机STG。

火爆到什么程度呢？甚至一度有传闻称它导致了日本的百元硬币出现短缺，就连卖粗点心的商店外面都要摆上几台来招揽顾客。


娱乐与技术的美妙融合，迅速在卡马克心中埋下火种，这颗种子随着年龄增长生根发芽。他在密苏里堪萨斯城大学进修期间，仅读了两个学期，就迫不及待跑去做了一名自由程序员。

为了拿到路易斯安那州Softdisk公司的程序员岗位，这人在雪地里步行了五公里才赶到招聘现场。好在得偿所愿，最终有机会与和艺术家阿德里安（Adrian Carmack)、设计师汤姆·霍尔（Tom Hall）以及约翰·罗梅罗（John Romero）等才华横溢的人共同开发游戏。

80年代北美的游戏行业仍由主机所统治，但编写主机游戏得配备一套昂贵的开发环境，通常需要公司支持。而个人电脑（PC）在很大程度上被视为仅供商业使用，毕竟屏幕上的颜色少得可怜，内置刺耳的音效也很难提供消费者所需的感官刺激。即使如此，Softdisk的几个小伙认为PC对编程爱好者的门槛更低，而且还有可以挖掘的技术空间。


他们最初的想法，是在PC上重现当时市场中最热门的游戏《超级马力欧兄弟3》。任天堂为了获得更强的图形性能，除了以主机作为基础外，还在扮演载体的卡带中加入了图形存储元件，使得《超级马力欧兄弟3》背景板和人物的横向滚动非常流畅。

其实相当一部分NES上的作品都能做到这一点，还有一些厂商为了让画面效果更好，在主机上搭载了专用的图形处理和加速硬件，然而当时的PC并不具备这种条件。

在80年代末期，几乎没有面向游戏的图形加速硬件兼容IBM的PC，程序员只能摸着限定标准，利用软件技巧变着法子来创建看似蹩脚的图形效果，这也是为什么角色扮演、策略模拟等对实时画面变化要求不高的内容在当时主导PC游戏市场的原因。


如果对比今天显卡的运行逻辑，应该说正常情况下，每帧整幅画面就是得重新渲染，但30多年前由于硬件性能受限，想要得到流畅的画面，计算机也只能说一声「臣妾做不到」了。

为了解决这些问题，卡马克决定围绕20世纪70年代出现的、用于滚动卫星照片等大型图像的原理，去编写一个图形显示引擎。

要让原本用于科研的技术民用化，得依赖IBM推出的一种叫做「EGA」（增强图形适配器）的显卡，它相比老的CGA（彩色图形适配器）有更多板载显存，虽然只能存储一个相对高分辨率的屏幕图像，但也可以变通一下，同时存储多个低分辨率图像，这让程序员有了一些操作空间。尽管通常只有300*200像素，不过对于当时的游戏来说已经够用了。


正如上图所示，卡马克不按重新渲染整幅画面的常规逻辑出牌，而是将每帧的中心位置（黄框内）保留到下一帧。简单来说，玩家向任意方向移动一格的时候只需要重渲黄圈外面的部分就行了，里面的部分接着用。如此一来显存里存的东西变少，运算压力也更小。

又因为从显存中转移数据的速度也要比从电脑主存中拿出来更快，通过指向不同的存储地址，EGA能够以每秒60次左右的速度切换屏幕上的图像，从而实现流畅的动画。


使用新硬件特性的「自适应贴图刷新」技术，首次出现在未发布的测试游戏《侵犯版权的危险戴夫》（Dangerous Dave in Copyright Infringement）中，由于它提高了硬件处理2D动画的能力，让很多跨领域的人才发现了计算机图形学的可能性。

卡马克的同事罗梅罗当时就觉得这小子不简单，待在Softdisk算是屈才了，团队经理杰伊·威尔伯（Jay Wilbur）也建议做个Demo给任天堂看看。于是他们花了两个周末（准确的说是72小时）的时间，借着办公室的设备在PC上重现了《超级马力欧兄弟3》里的一个小片段。


只可惜任天堂收到Demo后的回应并没有像预期中那样热烈，虽然这家公司对他们的成果印象深刻，但并不想把自己的主要IP带到其它平台。

除此之外，卡马克一行人的雇主Softdisk对基于EGA显卡的PC游戏也不感兴趣，更倾向于CGA的老市场。于是他们只能并利用这项技术兼职开发了横版卷轴游戏《指挥官基恩》（Commander Keen），最后又自立门户，成立了后来在游戏行业中人人皆知的id Software。


当时有一家发行商如此评价《指挥官基恩》：“对于蓬勃发展的PC游戏世界来说，这就像是一颗小小的原子弹。”而对于整个计算机行业来说，id Software也在消费级市场掀起了波澜，让软硬件开发商看到了个人电脑在处理图形数据时的潜力，开始重视并加大投入，带动了更多产品的出现，新的VGA标准也是在那个时间点开始全面普及。

二叉空间分割

如果各位对互联网和科技圈子的消息有少许关注，大概会知道卡马克2013年就跳槽到了Oculus研究虚拟现实技术，他做了几年又开始关注人工智能，还曾经搞过火箭发射器的研发，属于是有钱又有闲。


但在30年前，他创立的id Software公司才刚刚接着借着横版卷轴游戏《指挥官基恩》赚到第一桶金，在那段不算富庶的日子里，他对3D技术的普及同样做出了难以忽视的贡献。

如果说得夸张一点，游戏3D化就是由卡马克一手推进的。由于80年代末到90年代初计算机硬件性能不足，他当时萌生了一个想法 —— 通过「光线投射算法」（Ray Casting）的2D成像技术，来模拟出3D空间纵深的视觉效果。

本质上是2D游戏的《德军总部3D》，便是在这样的思路下诞生。


从原理来看，游戏中图像的每个像素会沿固定方向（视线方向）发射一条光线，当它碰到障碍物时，程序会在障碍物的相应位置创建单维深度缓存，建立纹理图像。


上面这段话没看懂不要紧，总之最终目的就是「将三维体数据投影在二维图像平面上」，用2D画面表现出3D世界的透视效果，PC算力不会被浪费在绘制人们看不到的表面上。


「光线投射算法」实际上并非由卡马克首创，在1980年左右，来自罗彻斯特大学和通用汽车研究实验室的几个学者就建立了相关理论，后来计算机科学家马克·勒沃伊（Marc Levoy）又在1988年的论文中对如何应用进行了更深入的探讨，主要是围绕几何建模展开的。

但将这种前沿技术应用得如此接地气的，卡马克绝对是第一批贡献者，他在1991年发售的游戏《Hovertank 3D》中便初步实现了这一点，而1992年上市的《德军总部3D》在完善代码和加入纹理映射后，甚至还提高了运行效率。

一个小插曲是，当年英特尔向记者展示新奔腾芯片的性能时，用的就是一个安装了《德军总部3D》的系统，可见当时这款游戏已经成为PC是否强劲的基准，而「光线投射算法」时至如今也有了更广泛的应用，比如看病时测核磁共振和CT，将数据转化为可以打印出来的片子，也经常在流体动力学和遥感技术等领域见到。


在做完《德军总部3D》后，卡马克和罗梅罗都打算在简单的关卡设计上更进一步。罗梅罗当时说到：“我的想法是做一些超出《德军总部3D》的事情，（关卡纵深）要有不同的亮度，不同的高度，四处不仅仅只有90度垂直的墙壁，要通过不同的东西来展示卡马克的新技术。”

随着支持更多颜色的VGA卡开始取代EGA卡，在游戏中实现不同的亮度已经不难做到，卡马克得以用16种色度，让计算机根据玩家在《Doom》房间中的位置来显示不同色调。例如远景用暗色调呈现出模糊的阴影感，越靠近玩家越亮，就像现实中一样，这比灯火通明的《德军总部3D》提供了更多沉浸感。

最大的问题，是得在2D画面的基础上，软渲染出有着多边形区块的透视效果。而问题的答案则，是一种称为「二叉空间分割」（BSP）的技术，在《Doom》之前没有任何游戏开发者察觉到了这一点。


「二叉空间分割」的想法早在1969年就有了，直到20世纪80年代初，布鲁斯·内勒（Bruce Naylor）一行人才开始推广这种技术，当时他们还在贝尔实验室尝试着渲染物体的3D模型。

一个3D模型变成平面图像，最关键是要确定哪些表面冲着观看者，哪些不可见。

原理说得简单点，好比我们处在一个由天花板、墙壁和地板组成的室内空间，每一个板都可以分为「板前」（可见）和「板后」（不可见），如果人的位置确定，就能根据人在板前还是板后，得到所能见到物体的遮挡顺序。

在「二叉空间分割」的作用下，每个平面都将空间分割为前后两个部分，而分出来的部分可以再次二分，二分的部分又能二分……最终形成一个节点众多的二叉树。它的算法很简单，只需要从树根开始，判断人的位置与所有平面的前后关系，计算机获得信息后，就可以把拥有3D透视效果的画面呈现在屏幕上。


而按照卡马克的说法，《Doom》把三维世界的表面都当做线来处理，分割和排序线要比多边形简单得多，重点是把「二叉空间分割」应用到一个平面。

「二叉空间分割」最初的研究领域，是帮助通用电气和Evans & Sutherland来制造飞行模拟器，当时这些器材的多边形数据还是由设计人员手工创建的。一定程度上，在《Doom》巧妙利用这项技术后，它才慢慢在民用领域变得常见，像是在CAD中构造立体几何，在教学中展示物理碰撞，或是用于一部分机器人的程序设计。

卡马克反转

到了20世纪90年代中期，消费市场的计算机硬件性能再次得到发展，成本也有所下降。所以当《雷神之锤》立项时，约翰·卡马克得以顺着「二叉空间分割」的思路，尝试让游戏再一次进化。他想创造一个基于真3D多边形场景和模型的世界，让算法切割真正的三维空间，而不是《德军总部3D》和《Doom》那样用2D做出来的透视效果。


1996年推出的《雷神之锤》，被不少人看成是现代3D技术的里程碑，它后期开始支持OpenGL，也倒逼着显卡等硬件的发展，来自英伟达的首席科学家大卫·柯克（David Kirk）都感叹到：“id Software的游戏总是在挑战极限。”

为了达到极限，卡马克围绕算法做了不少优化。尽管「二叉空间分割」已经拥有极高的效率了，但有些场景为了少渲染几个面，他都会去寻找分割的最优解，如果今天你把程序拿来解包估计会觉得「乱七八糟」，当然现在的硬件性能足够也没必要那么干了。


对于算法的优化，在《雷神之锤3》的源代码中同样能找到蛛丝马迹，其中有一个名为「卡马克反转」的算法（平方根倒数速算法），可用于快速计算x平方根的倒数。

在计算机图形学领域中，求取照明和投影的波动角度与反射效果时经常要计算平方根倒数，而「卡马克反转」可以减少求平方根倒数时浮点运算操作带来的巨大运算耗费。


当然这里需要澄清一下，这种算法之所以得名「卡马克反转」，是因为《雷神之锤3》在推广它时做了巨大贡献，发明者并非卡马克。

《雷神之锤3》的代码在QuakeCon 2005放出后，最初人们猜测是卡马克写下了平方根倒数速算法。获得本人否定的邮件答复后，有人顺藤摸瓜找到id Software的资深汇编程序员泰耶·马蒂森（Terje Mathisen），结果他表示只做过类似的实现，自己并非原作者。


目前仍然不知道首创「卡马克反转」的人是谁，只知道90年代初参与图形工作站SGI Indigo开发的加里·塔罗利（Gary Tarolli）是最早改进它的人。但无论如何都可以确定的一点是，游戏作为图形学的一种载体，让被掩埋的技术获得了大众的关注，游戏也作为相关前沿技术的试验场，在日后继续发光光热。

id Software、Epic Games两家围绕着实时阴影和预烘焙阴影谁更好，可能争论了有十年时间；HDR等后期图像技术从千禧年伊始逐步引入；继承了《雷神之锤》代码的《半条命2》，又再一次通过物理引擎推动了整个行业的硬件升级。而随着游戏引擎创造内容的保真度越来越高，它也成为了传统电影制作工具的一部分，卢卡斯影业就利用虚幻引擎来制作科幻电视剧《曼达洛人》，这不仅加快了生产流程，同时还减少了后期的返工时间。


游戏作为尖端技术落地、创造社会价值的桥梁，或许正如卡马克说的那样：“在信息时代，客观障碍已不复存在，所谓障碍都是主观上的。如果你想动手开发什么全新的技术，你不需要几百万美元的资金，你只需要在冰箱里放满比萨和可乐，再有一台便宜的计算机，和为之献身的决心。我们在地板上睡过，我们从河水中趟过。”


原文：https://zhuanlan.zhihu.com/p/408570779