三维图形编程资深人士Michael Abrash以开发第一个Quake的示例为例，讨论了编程中创造性思维的必要性。许多年前，我为现已倒闭的Video Seven视频适配器公司工作。 在那里，我帮助开发了VGA克隆。 我的同事汤姆·威尔逊（Tom Wilson）全天候工作了7个月，开发了Video Seven VGA芯片，他试图使VGA尽可能快地运行，并确保将其性能优化到最大程度。 但是，当汤姆（Tom）已经在芯片设计中引入点睛之笔时，我们听到有谣言说，竞争对手天堂通过添加FIFO在他的开发克隆中取得了甚至更高的性能。
这就是谣言的结尾-我们不知道什么是FIFO，也不知道他提供了多少帮助。 但是，汤姆通常是一个友好而放松的人，他变成了一个活跃的，痴迷于血液中咖啡因的狂热者。 根据这些信息，他试图弄清楚Paradise可以做什么。 最后，他得出的结论是，Paradise可能在系统总线和VGA之间插入了FIFO写缓冲区，因此，当CPU记录到视频存储器时，正在写入的数据将立即进入FIFO，这将允许CPU继续处理而不是每次都保持空闲状态当他正在写显示存储器时。
Tom既没有逻辑元素，也没有足够的时间来实现完整的FIFO，但是他设法实现了具有单个操作深度的FIFO，这使得处理器可以通过一次写操作来取代VGA芯片。 Tom不确定这样做是否会带来良好的结果，但这是他唯一能做的，因此他实施了该系统并将芯片投入生产。
事实证明，一次操作的FIFO运作起来非常酷：当时，视频七个VGA芯片是市场上最快的。 它们成为汤姆天才的证据，也证明了创作者在环境压力下的能力。 但是，这个故事的妙处在于，Paradise FIFO设计与Tom设计无关，并且
根本不起作用 。 Paradise在显示存储器和VGA芯片视频输出级之间插入了一个
读 FIFO缓冲区，这使得可以提前读取视频输出，以便当CPU需要访问显示存储器时，可以从FIFO中获取像素，并立即执行CPU命令。 这实际上提高了性能，但没有Tom的FIFO写缓冲区大。
这种情况可以说是一个人可以实现的创造性过程的本质的一个很好的寓言。 有关Paradise芯片的新闻报导几乎没有任何事实信息，但它们迫使Tom超越了他下意识设置的界限，从而开发了芯片的初始设计。 我认为，这是任何巧妙设计的最重要元素，无论是在硬件，软件还是任何其他创意领域，正是他出生在汤姆有关天堂的新闻中：能够检测您在项目开发过程中建立的边界并克服这些缺陷的能力边界。
当然，问题是如何克服边界，您甚至不知道边界的存在。 没有成功的秘诀，但是有两个原则可以很好地达到这个目的：首先，简化，其次，不断尝试新事物。
通常，当您觉得代码变得越来越复杂时，您会开始对冻结的结构进行较小的更改，并且很有可能通过再次发明设计来提高生产率并减少代码量。 当一切都准备就绪时，一个真正好的结构应该会带给您深深的满足，并且您对所需的代码量如此之小以及所有边界情况的工作情况感到惊讶。
在审查结构的过程中，重要的是研究任何想到的想法，无论它们看起来多么疯狂。 一开始我听到的许多真正的好主意似乎都是胡说八道，因为它们不适合我现有的世界情况。 这些想法通常真的很疯狂，但是就像乐园芯片新闻激发了汤姆的想象力一样，对看似妄想的想法的积极探索可以为您打开新的可能性。
很好的例证：Quake 3D图形引擎的发展。
世界上最复杂的3D图形任务
我花了最后七个月的时间在id Software的DOOM继承人Quake上工作，我假设再过三个月，当您阅读本文时，Quake将作为共享软件发布。
在图形方面，Quake对于DOOM而言将是DOOM的前身Wolfenstein 3D。 雷神之锤添加了真正的任意3D（玩家可以上下看，倾斜到侧面甚至跌落到一侧），详细的灯光和阴影，3D怪物和角色，而不是DOOM精灵。 很快，我将更详细地讨论所有这些问题，但是本月我想谈一谈这个问题，在我的书中，我将其称为三维图形中最困难的问题：确定可见的表面（为每个像素绘制相应的表面），以及一个非常接近它的任务-关于裁剪（尽快丢弃不可见的多边形，以加快确定可见表面的方式）。 为了简洁起见，我将使用缩写VSD表示可见表面确定和剔除的定义。
为什么我认为VSD是3D图形中最困难的任务？ 尽管栅格化任务（例如纹理映射）同样令人惊讶和重要，但它们的范围非常有限，并且在3D加速器问世之后，其解决方案将被转移到硬件上。 另外，它们的比例仅取决于屏幕分辨率，即它们相当适中。
相比之下，VSD是一项无限制的任务，并且使用了数十种方法来解决它。 但更重要的是，天真的解决方案中的VSD性能取决于场景的复杂性，而场景的复杂性通常会随着二次或三次函数的增加而增加，因此迅速成为创建现实世界的限制因素。 我相信，在未来几年中，VSD将成为PC 3D实时图形中越来越占主导地位的问题，因为3D世界的细节将不断增加。 如今，实体尺寸的Quake级别可以包含大约10,000个多边形，几乎是同类DOOM级别的三倍。
地震等级结构
在深入研究VSD之前，让我提到，Quake的每个级别都存储为一个巨大的三维BSP树。 与其他BSP一样，此BSP树在这种情况下沿多边形的平面划分空间。 但是，与我之前演示的BSP树不同，Quake BSP树不将多边形作为划分平面的一部分存储在树节点中，而是存储在空的（未填充）叶中，如顶视图中的图1所示。
图1.在Quake中，多边形存储在空的叶子中。 较暗的区域是充满的叶子（充满的体积，例如墙壁的内部）可以通过以“从前到后”或“从后到前”的BSP顺序渲染叶子来获得正确的渲染顺序。 另外，由于BSP叶片始终是凸形的，而多边形是向内看的BSP叶片的边界，因此任何图纸的多边形都不会重叠，并且可以按任何顺序绘制。 （这是凸多面体的一般属性。）
裁剪和定义可见表面
理想情况下，VSD过程应按以下方式工作：首先，您需要丢弃可见度金字塔之外的所有多边形，并切除部分可见的多边形的所有不可见部分。 然后，您只需要绘制从当前视点实际可见的每个多边形的像素（如顶视图中的图2所示），而不会浪费时间重复绘制像素。 请注意，您需要绘制图2中的多边形数量。 最后，在理想的世界中，检查多边形各个部分的可见性应该是廉价的，并且对于所有可能的视点，处理时间都应该相同，因此游戏可以顺利进行。
图2.理想的VSD体系结构仅呈现可见多边形的可见部分。在完成此任务的过程中，很容易确定哪些多边形完全在可见性金字塔的范围之外或被部分切除，并且完全有可能准确地找出要绘制的像素。 遗憾的是，世界还远非理想，所有这些检查的成本都很高，因此诀窍是加快或跳过不同的检查，所有这些检查都会创造出必要的结果。
正如我在之前的文章中详细解释的那样，借助BSP，您可以轻松，廉价地从前到后或从后到前的顺序遍历世界。 最简单的VSD解决方案是简单地将树从头到尾遍历，用可见性金字塔截断每个多边形，然后将其面朝着相机而不是完全切掉的方式绘制（艺术家的算法）。 但这是一个适当的解决方案吗？
对于相对简单的世界，它非常适用。 但是，它的伸缩性不好。 问题之一是，当将新的多边形添加到世界中以切除不可见的多边形时，需要进行越来越多的变换和检查。 在达到一定阈值后，这将开始显着降低性能。
幸运的是，此特定问题具有很好的解决方法。 如上所述，BSP树中的每个叶子都描述了一个凸子空间，并且连接到叶子的节点限制了该空间。 不太明显的是，BSP树中的每个节点还描述了一个子空间-由该节点的所有子级组成的子空间，如图3所示。您可以这样处理：每个节点将位于上方的节点创建的子空间分为两部分。树，节点的子元素进一步将这个子空间分为来自该节点的所有叶子。
图3：节点E描述了一个变暗的子空间，其中包含叶子5、6、7和节点F。由于节点的子空间是有界的和凸的，因此我们可以检查它是否完全在可见性金字塔之外。 如果是这样，那么该节点的
所有子节点肯定会被完全切断，并且无需进行其他处理即可将其丢弃。 由于世界的主要部分通常位于能见度金字塔之外，因此世界上的许多多边形几乎可以被巨大的子空间节点碎片切断。 对剪切子空间执行理想检查非常昂贵，因此，通常对于每个节点，将约束平行四边形或球形用于剪切检查。
也就是说，沿着可见性金字塔进行剪切不是问题，您可以使用BSP向后绘制。 那怎么了
重画
DOOM和Quake技术的主要作者John Carmack在开发Quake时面临的问题是，在复杂的世界中，能见度金字塔中的许多场景都有大量的多边形。 这些多边形中的大多数与其他多边形部分或完全重叠，但是上述画家的算法要求在可见性金字塔中绘制每个多边形的每个像素。 但是，它们通常只被他人重绘。 在10,000个Quake多边形的Quake级别上，绘制像素10次或更多次时，很容易出现最坏的重画情况； 也就是说，在某些帧中，每个像素平均会被绘制10次或更多次。 没有光栅器能够足够快地补偿渲染场景所需的数量级。 更糟糕的是，艺术家的算法会在最佳情况和最坏情况之间造成巨大的性能差异，从而导致移动观看者时帧频发生重大变化。
因此，约翰面临将重绘数量减少到可接受水平的问题。 理想情况下，每个像素只能绘制一次，但在最坏的情况下，不应绘制两次或三遍。 至于裁剪可见性金字塔，理想情况是要求将金字塔中不可见的所有多边形都切掉，且几乎不增加成本。 还有一个好处是，可以只绘制部分可见的多边形的可见部分，但同时应保持平衡：该操作的花费应少于重新绘制。
当我在三月初进入id时，John已经有了引擎的原型和大纲计划，因此我认为我们的工作仅仅是完成和优化该引擎。 但是，如果我知道id的故事，就可以弄清楚是什么。 John不仅为DOOM创建了游戏，还为Wolf 3D和其他几款以前的游戏创建了引擎，在开发过程中，他为每个引擎制作了多个不同版本（一次他在四个星期内创建了四个引擎），也就是说，在四年中，他编写了大约20个引擎。 John对Quake引擎越来越多的新技术和高质量技术的不懈追求只有在游戏发布后才能结束。
在我到达三个月后，引擎中只保留了原始VSD结构中的一个元素，而约翰对“尝试新事物”的渴望如此之大，以至于我从未见过这样的事情。
束树
在John最初的Quake项目中，渲染是使用第二个BSP树从头到尾完成的，该树跟踪已绘制的屏幕和需要填充其余多边形的空白部分。 逻辑上，该BSP树可以视为描述屏幕的填充部分和空白部分的二维区域，如图4所示，但实际上，它是三维树，称为“光束树”。 波束树是一组3D扇区（束），由从某个中心点（在我们的情况下为视点）投影的平面所界定，如图5所示。
图4. Quake梁树有效地将屏幕分割成2D区域图5. Quake梁树由从视点投影到多边形边缘的3D扇形或梁组成。在约翰的项目中，一棵捆树最初是由一个描述可见度金字塔的捆组成。 此捆绑包之外的所有内容都被视为已填充（也就是说，无需在那里绘制任何内容），并且捆绑包内的所有内容均被视为空。 当从前到后绕着世界的BSP树到达一个新的多边形时，通过从视点从其边缘绘制平面来将此多边形转换为光束，并且将与光束树中的空光束交叉的光束的所有部分都视为已绘制并作为填充光束添加到光束树中。 这种情况一直持续到多边形结束或捆树完全变满为止。 束树完成后，绘制束树中捕获的多边形的可见部分。
使用三维束树而不是2D区域的优势在于，确定多边形顶点在束平面的哪一侧，足以检查射线到顶点的矢量积的符号以及该平面的法线，因为所有束平面都通过起点坐标（视点）。 另外，由于光束平面完全由单个法线描述，因此要从多边形的边缘生成光束，仅边缘与光束从该边缘到视点的标量积就足够了。 最后，对于上述可见性金字塔进行的组裁剪，可以使用BSP节点的边界球。
最初，捆绑树属性（捆绑树变满时结束）似乎很有吸引力，因为它看起来在最坏的情况下会限制性能。 不幸的是，仍然有可能看到天空或世界后墙的所有场景，因此在最坏的情况下，您仍然必须检查可见金字塔中关于束树的所有多边形。 由于数值精度的限制，小裂纹也可能发生类似的问题。 例如，从水平仪的顶部观察时，在光束可见度较高的场景中，花很多时间来修剪光束树，处理光束的总成本降低了Quake到乌龟速度的帧速率。 就是说，最后证明了使用捆绑树的解决方案与艺术家算法所遭受的疾病几乎相同：最坏的情况比平均情况要糟得多，并且随着复杂性的增加，它无法很好地扩展。
每天都有新的3D引擎
梁树开始工作后，John孜孜不倦地致力于加速3D引擎，不断尝试改善其结构，而不是对实现进行更改。
至少每周一次，每天，至少每天一次，他去我的办公室说：“昨晚我无法入睡，所以这就是我的想法……”，我知道他再次使我的大脑有些紧张。约翰尝试了许多方法来改善束树，并取得了一些成功，但更有趣的是他产生了完全不同的方法。其中几乎没有提到其中的一些，而其他一些则在一夜之间或在密集编码的周末实施。在这两种情况下，它们都被丢弃或进化，直到它们开始满足必要的标准。这是此类方法的一些示例。我将以最小的细节来讨论它们，希望它们能像天堂的FIFO缓冲区唤醒汤姆·威尔逊的想象力一样唤醒您的想象力。细分射线广播：将光线发射到分成8x8网格的屏幕中；这是非常有效的操作，因为可以简单地通过将光束限制在BSP树上来找到与表面的第一个相交点，从角度出发，直到到达填充的图纸为止。如果相邻光线不在同一表面上，则光束会在它们之间的中间发射，并且一直持续到所有相邻光线都落在一个表面上或在相邻像素中为止。然后围绕着光线所落到的多边形的每条光线绘制一个块。这种方法的缩放比例非常好，并且受像素数量的限制，并且不会发生重绘。它的问题正在解决：很有可能在射线之间出现小的多边形并消失。无峰表面：世界表示为一组平面。多边形间接出现在平面的相交处，并在渲染前的最后阶段从平面移除。这提供了快速裁剪和非常少量的数据（与多边形相比，平面的描述要紧凑得多），但是从平面提取多边形需要花费大量时间。绘图缓冲区：类似于z缓冲区，但每个像素只有一位，指示像素是否已绘制。这消除了重绘，但是以检查缓冲区中的内部循环，其他写入操作和高速缓存未命中为代价，最糟糕的是，代码的复杂性显着增加。这种方法的选项：一次检查渲染缓冲区一个字节，然后完全跳过完全重叠的字节，或者将渲染缓冲区的每个字节分支到256个已部署的内部循环之一中，以渲染0-8像素；在此过程中，理论上可以在处理8个像素时利用x86处理器执行并行透视分数分割的功能。间隔渲染：将多边形栅格化为间隔，这些间隔将添加到间隔的全局列表中，并从该列表中切除，以便每个像素中仅保留最接近的间隔。从前到后需要进行一些排序，因为如果有交叉点，则列表中已有的间隔会更近。这样就无需重画，但要以算术计算间隔为代价。此外，每个多边形仍必须转换为间隔。门户网站：会跟踪表面上没有多边形的孔，因为可见范围只能通过此类门户扩大。渲染是从前到后进行的，当检测到门户时，其后的多边形和门户将受到限制，直到没有可见的多边形和门户为止。使用此原理的递归应用，它可以使您仅绘制可见多边形的可见部分，但要花费大量穿过门户的裁剪的代价。突破
最后，John决定波束树是反映世界BSP树中已经间接包含的信息的二阶结构，因此他着手解决了直接从世界BSP树中提取可见性信息的问题。他花了一个星期的时间，创建了理想的DOOM（2D）可见性体系结构，在该体系结构中，DOOM BSP树的单个线性遍历创建了2D重绘的可见性。但是，解决3D的相同问题却变得更加复杂，并且到本周结束时，约翰已经因为可见性代码中复杂性的增加和故障的不断出现而发脾气。尽管具有直接处理BSP的解决方案已经接近工作版本，但它需要越来越多的完善，而简单明了的体系结构根本没有加起来。当我一个星期五离开工作时John正准备在周末使用直接的BSP处理解决方案。星期一早上，约翰看上去像是一个闯入另一个世界的人，也像是一个睡得不多的人。整个周末，他都在研究直接处理BSP的解决方案，取得了令人满意的工作，并记录了如何完成BSP。周一凌晨3:30，当约翰躺在床上思考门户时，他认为您可以预先计算并在每张表中保存该表中所有可见叶子的列表，然后在程序执行期间绘制可见的叶子视点所处的页面而定，从左到右移动，完全忽略所有其他叶子。复杂程度在于大小：最初未压缩的潜在可见集（PVS）集占用了几兆字节。但是，PVS可以存储为每张1位的位向量。用零字节的简单压缩来压缩这样的结构是非常容易的。 John还建议更改BSP启发式方法，以使其生成的叶子更少。这与我几个月前提出的建议相反，即选择下一个多边形分隔符，分隔最少数量的其他多边形，根据最新数据，结果证明是最好的启发式方法。 John的方法允许将空间限制在关卡之外，以便BSP处理人员可以移除玩家永远看不见的外部表面，结果，将足够大级别的PVS大小减小到20 KB。为了交换这20 KB，加速了对可见性金字塔范围之外的叶子的裁剪（因为只考虑了PVS中的叶子），并且为了对可见性金字塔内部进行裁剪，您只需要进行小幅重绘（叶子的PVS包含从叶子中任何位置可见的所有叶子，因此一小笔重绘，通常为50％左右，但最高可以达到150％）。更好的是，预先计算PVS可实现性能均衡。现在，最坏的情况不会比最好的情况差很多，因为您不再需要额外的VSD处理，在复杂场景的情况下，仅需要更多的多边形，也许还需要进行一些额外的重绘。当John首次向我展示他的工作原型时，我特别推出了最困难的场景-帧频降低到个位数的地方，并且工作顺利，没有明显的放缓。约翰说，PVS的初步计算是他正在考虑的方法的逻辑发展，没有“尤里卡”的时刻。不过，这是发现了一个全新的，质量更好的设计，它与带有分选边缘的光栅化器一起完全消除了重绘，非常接近我们从一开始就选择的“理想”要求。简化并尝试新事物
这是什么意思？
正是我刚开始所说的：简化并尝试一些新的东西。预先计算的PVS比我们之前讨论过的任何其他方案都更简单（尽管预先计算的PVS是一项有趣的任务，我们将在以后再讨论）。本质上，预先计算的PVS只是程序执行过程中艺术家算法的有限版本。这是否意味着这种方法不是特别深入？一点也不。
所有真正优秀的结构看起来都很简单，甚至显而易见，但是只有在它们被发明之后。但是发明的过程本身需要令人难以置信的毅力和愿意尝试许多不同的想法，直到您找到合适的想法为止，在这种情况下就是这样。我的朋友克里斯·赫克（Chris Hecker）的理论是，所有方法最终都归结为一种，因为它们都反映了相同的内部状态和功能。从基础理论的角度来看，这是正确的：无论如何计算透视纹理贴图-使用除法或增量双曲计算，数字都执行相同的任务。但是，在实现方面，可以通过在时间上简单地转移解决方案，或者通过改进硬件功能或缓存的优化来实现巨大的差异。我的朋友Terje Mathisen喜欢重复一遍，“几乎所有的编程都可以看作是缓存中的练习”。这正是约翰所做的。无论他执行VSD计算有多快，它们都不会像预计算和寻找可见性那样快。他最聪明的举动是他摆脱了“代码加速”的思想，意识到实际上，您可以预先计算（基本上缓存）PVS并进行搜索。世界上最困难的事情是放弃通常的，相当好的解决方案来解决一个复杂的问题，并尝试寻找另一个更好的解决方案。在我看来，为此，最好尝试新的疯狂想法，并始终尝试简化。John的目标之一是在每个后续3D游戏中使用比以前更少的代码；他相信，如果他学到更多，他将能够用更少的代码来更有效地解决问题。虽然这个系统对他来说运作良好。立即学习，提前付款
我想在文章末尾提到一件事。我记得多少，博士。 《多布杂志》一直说，共享编程信息是一种祝福。我知道很多程序员在开发方面取得了飞跃，这要感谢Tiny C Hendrix或D-Flat Stevens，或者仅仅是因为阅读了年度DDJ资料夹。 （例如，我就是其中的一个。）许多公司都完全可以理解，将信息交换以完全不同的方式视为潜在的利润损失，这就是DDJ对程序员社区如此有价值的原因。出于这种理念，id Software允许我在本文中讲述Quake的工作原理，甚至在它发布之前。这就是为什么id在ftp.idsoftware.com/idstuff/source上发布完整的Wolfenstein 3D源代码的原因。翻译：现在源代码放在github ]上；您不仅可以重新编译代码并将其出售，还可以了解全面成功的游戏的工作原理；检查上述目录中的wolfsrc.txt文件，以获取有关如何使用该代码的详细信息。因此，请记住：在合法的情况下，从长远来看，信息交换对我们所有人都有利。您可以预先为这里和其他地方收到的信息偿还债务，通过撰写文章或书籍，或通过在网络上发布知识来共享您所能拥有的一切。我们谁也不能真空学习。我们所有人都站在巨人的肩膀上-威斯，纳特和成千上万的其他人。用你的肩膀来构建未来！参考文献
Foley，James D. 等。，计算机图形学：原理与实践，Addison Wesley，1990，ISBN 0-201-12110-7（捆绑，BSP树，VSD）。Teller，Seth，《在密集的多面环境中的可见性计算》（学位论文），以及其他有关可见性定义的文章，可在http://theory.lcs.mit.edu/~seth/上找到。Teller，Seth，《交互式演练的可见性预处理》，SIGGRAPH 91会议论文集，第2页。61-69。