程序员迈克尔·阿布拉什（Michael Abrash）应约翰·卡马克（John Carmack）的邀请从事90年代中期第一代Quake的引擎工作，在开发过程中写了一系列文章。 这是本系列的第二栏。 第一版的翻译在这里 。我必须承认：我已经厌倦了经典摇滚。 大约20年前，我很高兴很长一段时间以来最后一次听到汽车或波士顿的音乐。 另外，鲍勃·西格（Bob Seager）和女王（Queen）从来没有特别吸引我，更不用说猫王了，所以变化不大。 但是当我听到我想换收音机的时候，当我听到Allman Brothers，Steely Dan，Pink Floyd或上帝，请原谅我甲壳虫乐队时，情况发生了变化（但仅限于“ Hello Goodbye”和“ I'll哭吧，而不是骑车票或生命中的一天；我还没有走
那么远）。 并没有花很长时间找到原因。 我听了四分之一世纪的同一首歌，然后就厌倦了。
我这样说是因为当我和女儿一个晚上开车离开咖啡馆时，“无可替代”广播电台第一次在车上打开了。
我们正在谈论的是一个十岁的女孩，她在长期饮食中坚持不懈地饮食。 她喜欢旋律，动听的歌声和出色的歌手。 在收听备用摇滚电台时，您将找不到任何这些。 因此，当我打开收音机时，她首先说：“傅！”就不足为奇了。
但是，这让我感到惊讶：听了一会儿之后，她说：“爸爸，你知道，但这真的很有趣。”
这不仅向我暗示了她十几岁时整个房子会发出什么样的音乐。 她对替代摇滚乐的迅速采用（与我十年来对自己青年音乐的迷恋相比）使我想起了一些随着年龄的增长和生活方式的建立而容易忘记的东西。 这提醒我，必须保持开放的心态，并做好准备-而且要努力-尝试新事物。
程序员倾向于依附于熟悉的方法，并且如果他们能够充分应付任务，则倾向于使用它们。 但是编程总是有替代方法，我发现它们通常值得探索。
但是，鉴于
Quake不断变化的性质，我真的不需要这样的提醒。
创意流
一月份，我描述了一个创意流，该流导致John Carmack决定对
Quake （我们在id Software中共同开发的游戏）中的每个可能视点使用预先计算的潜在可见集（PVS）多边形。 PVS的初步计算意味着，无需花费大量时间搜索世界数据库中从当前视点可见的多边形数据库，我们只需将PVS中的所有多边形从头到尾绘制（从世界的BSP树中获取顺序；讨论BSP- （请参见1995年5月，7月和11月的专栏中的树），并无需搜索即可完全正确渲染场景，从而允许向后渲染执行隐藏表面去除（HSR）的最后一步。 这是一个很棒的主意，但是对于Quake体系结构而言，这条道路尚未完成。
绘制运动对象
例如，仍然存在关于如何正确地分类和绘制运动物体的问题。 实际上，最重要的是在1月专栏之后提出了这个问题，因此我将花点时间。 主要的问题是，移动的模型可能会落入多个BSP叶子中，并且当模型移动时，这些叶子会发生变化。 除了可以在一张工作表中找到多个模型外，这意味着没有简单的方法可以使用BSP顺序以正确排序的顺序绘制模型。 当我写一月专栏时，我们绘制了精灵（如爆炸），可移动的BSP模型（如门）和多边形模型（如怪物），并用触摸的叶子将它们截断，然后在到达每张BSP图纸时绘制相应的零件从后到前转身时的时机。 但是，这并没有解决在一张纸中相对于彼此移动多个移动模型的问题，也给复杂的多边形模型留下了不愉快的问题。
John以一种令人惊讶的低技术的方式解决了精灵和多边形模型的排序问题：现在我们将它们写入z缓冲区。 （也就是说，在渲染每个像素之前，我们将其距离或z与屏幕上已有像素的z值进行比较。仅当新像素比现有像素更近时才绘制新像素。）首先，绘制主要世界-墙壁，天花板等。这样。 在这个阶段，没有
使用 z缓冲区的
测试 （我们将很快看到，以另一种方式对世界的可见表面进行定义）； 但是，我们使用世界上所有像素的z值（实际上是1 / z值，如下所述）
填充 z缓冲区。 填充Z缓冲区要比对整个世界进行Z缓冲要快得多，因为没有读取，没有比较，而只是编写z值。 完成绘制并填充世界的z缓冲区后，我们可以简单地使用z缓冲区绘制精灵和多边形模型并获得完美的排序。
使用z缓冲区时，不可避免地会出现以下问题：这如何影响占用的内存和性能？ 在分辨率为320x200的情况下，它需要128 KB的内存，这并不是微不足道的，但是对于需要8 MB才能运行的游戏来说却不是很多。 对性能的影响：填充世界的z缓冲区时约为10％，渲染精灵和多边形模型时约为20％（指标差异很大）。 作为回报，我们得到了一个完美排序的世界，并具有创建其他效果的能力，例如，粒子爆炸和烟雾，因为z缓冲区使您可以轻松地在世界上对这些效果进行排序。 通常，z缓冲区的使用显着提高了Quake引擎的视觉质量和灵活性，并显着简化了代码，但付出了相当合理的内存成本和性能。
流平并提高生产率
正如我在上文所述，
Quake体系结构首先绘制世界本身，而无需读取或比较z缓冲区，而只是用z中世界的多边形值填充z缓冲区。 之后，使用完整的z缓冲将移动的对象绘制到世界的最上方。 到目前为止，我只讨论了如何绘制运动对象。 在本专栏的其余部分，我将讨论渲染方程式的另一部分-绘制世界本身，此时整个世界都存储为一棵BSP树，并且永不动摇。
您可以从1月份的专栏中记住，我们担心原始性能及其平均值。 也就是说，我们希望渲染代码尽快执行，但同时执行，以使中间场景的渲染速度与渲染场景中最慢的渲染速度之间的差异尽可能小。 如果以5 fps的速度绘制10％的场景，则平均每秒30帧没有什么好处，因为与平均场景相比，此类场景中的抽动会非常明显。 在100％的情况下，最好将频率平均为每秒15帧，即使平均渲染速度是原来的一半。
预先计算的PVS是迈向更高和更平衡性能的重要一步，因为它们消除了确定可见多边形的需要-这是一个相当缓慢的阶段，在最复杂的场景中表现得很差。 但是，在某些实际游戏级别的地方，预先计算的PVS包含的多边形比实际看到的多五倍； 结合向后隐藏表面去除（HSR），这创建了“热区”，其中帧速率明显降低。 数以百计的多边形从前向后绘制，并且大多数多边形立即被更接近的多边形重绘。 总体而言，原始性能也平均下降了50％，这是由于在PVS中渲染所有内容而导致的。 因此，尽管向后渲染PVS集是HSR的最后阶段，并且是对先前体系结构的改进，但这并不理想。 John认为使用PVS可能比从前向后绘制更好的方法。
他实际上是被发现的。
排序间隔
对于Quake而言，理想的HSR最后阶段是丢弃实际上证明是不可见的PVS中的所有多边形，并仅绘制其余多边形的可见像素而无需重新绘制。 也就是说，每个像素将只绘制一次，当然不会降低性能。 一种解决方案（但需要成本）是从前到后绘制，保存描述屏幕当前重叠部分的区域，并在渲染之前用该区域的边界截断每个多边形。 听起来很有希望，但实际上，它使我想起了我在一月份的专栏中描述的捆绑树解决方案。 我们发现，这种方法需要浪费额外的资源，并且在负载平衡方面存在严重的问题。
如果将最后一个HSR步骤从多边形级别移至间隔级别，然后对间隔进行排序，则可以做得更好。 本质上，这种方法包括将每个多边形变成一组间隔，如图1所示，然后相对于彼此对间隔进行排序和截断，直到只有可见间隔的可见部分保留以进行渲染，如图2所示。与z缓冲非常相似（如上所述，虽然它适用于较小的运动对象，但z缓冲太慢，无法用于渲染世界），但是存在重要区别。 与z缓冲不同，只有可见间隔的可见部分逐像素进行扫描（尽管仍需要对多边形的所有边缘进行栅格化）。 更好的是，通过z缓冲对每个像素执行的排序成为具有排序间隔的间隔操作，并且由于间隔列表的整体属性是连通性，因此每个边缘仅相对于同一行中的某些间隔进行排序，并且在出现以下情况时仅被截断几个间隔水平叠加。 尽管复杂场景的处理时间仍然比简单场景要长，但最坏的情况并没有使用束树或从后到前排序时那样糟糕，因为没有重新绘制和扫描隐藏的像素，复杂性受到像素分辨率的限制，并且间隔连接限制了最坏情况的排序屏幕上任何区域的情况。 另外，排序间隔的输出恰好是低级栅格化器所需的形式：采用一组间隔描述符的格式，每个间隔描述符都包含起点和长度的坐标。
间隔生成简而言之，按间隔排序的解决方案非常接近我们的原始标准； 尽管不能节省成本，但它们仍然不完全可怕。 它完全消除了多边形重叠部分像素的重绘和扫描，并且在最坏的情况下易于实现性能均衡。 我们不仅仅将排序间隔作为消除隐藏表面的机制，还可以通过预先计算的PVS将多边形的数量减少到足以处理排序间隔的水平。
因此，我们找到了所需的方法。 剩下的只是写代码而已，对吗？ 是的，没有。 具有排序间隔的概念性方法很简单，但是却难以实施：您需要做出几个重要的设计决策，需要一些数学运算，并且有一些陷阱。 首先让我们看一下设计解决方案。
肋骨vs.间隔
第一个决定是选择排序的对象：区间或边（这两个概念都属于“排序区间”的总分类）。 尽管两种情况下的结果都是相同的（无需重绘就需要绘制间隔列表），但是实现和性能影响却大不相同，因为排序和截断是由非常不同的数据结构执行的。
在对间隔进行排序时，这些间隔存储在按x个链表排序的存储段中，通常每栅格线一个段。 如图1所示，每个多边形又被栅格化为间隔，如图2所示，每个间隔被排序并截断到栅格线所在的内存段中，如图2所示，因此在任何时间点，每个段都包含最接近的间隔，始终没有覆盖层。 使用这种方法，必须依次为每个多边形生成所有间隔，并且每个间隔都将立即被排序，截断并添加到相应的内存段中。
图2：将图1中多边形A的间隔与多边形B的间隔进行排序和截断，而多边形A沿Z轴的距离恒定为100，而多边形B沿Z轴的距离恒定为50（多边形B更靠近相机）在对边进行排序时，这些边将存储在根据x链表按其初始栅格线排序的存储段中。 每个多边形又被划分为边缘，一起创建场景中所有边缘的列表。 将可见性金字塔中所有多边形的所有边缘添加到边缘列表后，整个列表将由上至下，从左至右一遍扫描。 活动边缘列表（AEL）的列表已保存。 在到新栅格线的每一步中，出现在该栅格线上的边都将从AEL中移除，活动边转到其新的x坐标，从新栅格线开始的边被添加到AEL，并且这些边按当前x坐标进行排序。
对于每个栅格线，存储按z排序的活动多边形列表（APL）。 它按x AEL排序。 与每个新边相遇时（即每个多边形从左向右移动时开始或结束时），与之关联的多边形被激活并分类为APL（对于起始边而言），如图3所示，或者被取消激活并从APL中删除（对于后缘），如图4所示。如果最近的多边形发生了变化（即，最近的是一个新的多边形或最近的多边形已经结束），则对于刚刚停止最接近的多边形，将从不存在该多边形的点开始创建一个间隔 VYM因为它是当前的边缘和当前的最近和结束x坐标x坐标记录在垃圾填埋场，这是目前最接近的一次。 此存储的坐标随后用作新的最近的多边形停止在前面时创建的间隔的开始。
图3：在AEL中检测到起始边时激活多边形。
图4：在AEL中检测到后沿时停用多边形。如果您不完全了解以上内容，请不要担心； 这只是排序边缘的快速概述，因此该列的其余部分更加清晰。 详细说明将在下一列中。
排序边缘产生的间隔似乎与排序间隔所产生的间隔完全相同； 区别在于用于对场景中的间隔进行排序的中间数据结构。 在对边缘进行排序时，间隔会存储在边缘内部，直到生成最终的可见间隔集为止，因此，根据边缘和活动多边形集定义的间隔状态，在每个边缘添加或删除多边形时都会执行排序，修剪和创建间隔。 在对间隔进行排序时，对每个多边形进行栅格化后，这些间隔会立即变得明显，然后将这些中间间隔相对于栅格线中的间隔进行分类和截断以创建最终间隔； 因此，间隔的状态会被明确地固定设置，并且所有的工作都直接以间隔进行。
区间分类和边缘分类都可以很好地工作；它们已经成功地用于商业项目中。 对于Quake，我们选择了边缘排序，部分原因是它看起来更高效并且具有出色的水平连通性，从而提供了最短的排序时间，而在排序间隔时可能需要昂贵的排序到链表中。
但是，一个更重要的原因是在对边缘进行排序时，我们可以在相邻的多边形之间划分边缘，这将边缘的排序，修剪和栅格化处理减少了约一半，并且由于边缘变得常见而大大减少了世界数据库。对边缘进行排序的最后一个优点是，它不区分凸多边形和凹多边形。对于大多数图形引擎而言，这并不是一个非常重要的方面，但是在Quake中，修剪，变换，投影和排序边缘已成为主要瓶颈，因此我们正在尽一切可能减少多边形和边缘的数量，凹多边形在这方面非常有帮助。尽管也可以通过排序间隔来处理凹面多边形，但这会导致性能显着下降。但是，关于最佳方法尚无确切答案。最后，排序间隔和排序边执行一项功能，而在它们之间进行选择则取决于可用性。在下一篇专栏中，我将讨论有关边缘的完整实现的更多信息。在本专栏的其余部分，我将通过讨论排序键和1 / z的计算来奠定下一个基础。在此过程中，我将对排序边缘的各个方面进行一些引用，这些方面尚未详细讨论。我很抱歉，但这是不可避免的，只有在下一篇专栏文章的末尾，一切都会变得清楚。肋排排序键
现在我们知道我们将选择边缘的排序，并使用它来创建最接近查看器的多边形的间隔，然后出现一个问题：您如何知道这些多边形是否最接近？理想情况下，我们将简单地存储每个多边形的排序键，并在出现新边时，将其表面的键与其他当前活动多边形的键进行比较，以便轻松确定哪个多边形最接近。听起来太好了，但是有可能。例如，如果您的世界数据库存储为BSP树，并且所有面都被截断为BSP叶子，则BSP遍历顺序将是正确的渲染顺序。因此，例如，如果从前到后绕BSP，为每个多边形分配一个较大的键值，则在到达该键时，将确保键值较高的多边形位于键值较小的多边形的前面。这种方法已经在Quake中使用了一段时间，但是由于我稍后将要解释的原因，现在正在采用另一种解决方案。如果您没有BSP或类似的数据结构，或者有许多移动的多边形（BSP无法非常有效地处理移动的多边形），则另一种实现目标的方法是在渲染场景之前将所有多边形彼此相对排序，并根据其空间分配相应的关键点视口中的关系。不幸的是，在一般情况下，这是一个极其缓慢的任务，因为每个多边形需要相互比较。有一些技术可以提高多边形的排序性能，但是我不知道有人会在PC上实时执行多边形的常规排序。另一种方法是按屏幕空间中距查看者的距离z进行排序；该解决方案非常适合排序边缘的出色空间连通性。与栅格线上的每个新边相遇时，您可以计算相应多边形的距离z并与其他多边形的距离进行比较，然后可以将多边形保存在APL中。但是，获得沿z的距离可能是困难的任务。别忘了我们需要能够在多边形上的任意点计算z，因为可能会出现一条边并使多边形在APL中在屏幕上的任何位置排序。我们可以直接根据屏幕坐标x和y以及多边形平面的方程来计算z，但是不幸的是，这不能很快完成，因为平面的z在屏幕空间中不会线性变化。但是，1 / z 线性变化，因此我们使用此值。 （有关屏幕空间线性度和1 / z的渐变的讨论，请参阅去年在《游戏开发者》杂志上克里斯·海克（Chris Hecker）关于纹理映射的系列。）使用1 / z的另一个优点是分辨率随着距离的减小而增加，也就是说，使用1 / z时，对于最重要的近距离物体，我们将始终具有最佳的深度分辨率。在多边形的任意点获取1 / z值的一种明显方法是在顶点处计算1 / z，在多边形的两个边上进行插值，然后在边之间进行插值以在所需点处获取值。不幸的是，这需要沿着每个肋骨做很多工作。更糟糕的是，这需要除法计算每个间隔中每个像素的1 / z步长。最好直接根据平面方程以及我们感兴趣的像素的屏幕x和y来计算1 / z。该方程式具有以下形式：其中z是投影到屏幕坐标（x'，y'）的平面上的点在z空间中的坐标（这些计算的坐标原点是投影中心，屏幕上位于视点正前方的点），[abc]为垂直于视口中的平面，并且d是从视口原点到沿着法线的平面的距离。因为每个平面的a，b，c和d是常数，所以每个平面只进行一次除法。完整的1 / z计算需要两个乘法和两个加法，并且每个运算必须以浮点数执行，以避免范围误差。如此大量的浮点计算似乎很昂贵，但实际上却并非如此，特别是在奔腾处理器上，在该处理器中，任何点的1 / z plane的值都可以用汇编语言在六个周期内计算出来。如果您有兴趣，这里是1 / z方程的快速推导。平面的平面方程式具有以下形式：其中x和y是视图空间的坐标，上面定义了a，b，c，d和z。如果我们做替代 和
（根据透视投影的定义； y更改符号，因为它在视口中增加，但在屏幕空间中减少）。执行置换，我们获得：对方程进行求逆和扩展，得到：稍后，我将展示1 / z排序的实际效果。地震并按z排序
我在上面提到Quake不再使用BSP顺序作为排序键；实际上，现在将1 / z用作密钥。尽管梯度很优美，但是从梯度中计算1 / z显然比简单地与BSP顺序键进行比较要慢，所以为什么在Quake中切换到使用1 / z？主要原因是多边形数量减少。为了按BSP顺序进行渲染，必须遵循某些规则，包括与BSP平面相交时应划分的多边形。这种分离大大增加了多边形和边的数量。由于按1 / z排序，我们可以使多边形保持未分割状态，但仍能获得正确的绘制顺序，因此我们需要处理的边缘要少得多。尽管通常会按1 / z进行排序，但渲染通常会加速。1 / z排序的另一个优点是它解决了本文开头提到的排序问题：移动模型本身就是小型BSP树。由于这些模型是单独的BSP，因此无法按BSP世界顺序进行排序，并且没有简单的方法将它们按BSP世界的顺序嵌入。我们不希望对这些模型使用z缓冲，因为它们通常是大对象（例如门），并且我们不想失去减少通过边缘列表进行渲染时关闭的门所提供的重绘的好处。使用排序间隔时，移动的BSP模型的边缘仅放置在边缘列表中（首先将多边形截断以免它们与世界的实体表面相交以避免复杂性，与相互渗透有关），而不是世界的所有边缘，其余按1 / z排序。继续前进
毫无疑问，这篇文章包含了大量信息，而您尚未想到很多。下一篇文章中的代码和解释将有所帮助；如果您想提前看一眼，请在阅读本文时，该代码应该在ftp.idsoftware.com/mikeab/ddjsort.zip上可用。同样值得一看的是计算机图形 Foley和Van Dam或计算机图形罗杰斯的程序元素。目前尚不清楚Quake的结果如何必须对边缘进行排序-以BSP顺序或1 / z。实际上，不能保证以任何形式排序的间隔都是最终的解决方案。有时候，我们似乎经常更换图形引擎，就像他们将Elvis放在专门针对50年代热门歌曲的广播电台上一样（但是，希望它能带来更加令人愉悦的效果！），而且毫无疑问，我们会考虑直到发行日期的替代方案游戏。