这篇文章是Intel在2016年输出的软件光栅化技术方案，很多项目的软件光栅化实现都是以这个方案为基础开发的，参考文献[1]中给出了原文链接，有兴趣了解详情的同学可以前往一探究竟。

在深入论文细节之前，我们需要带着几个问题前行：

1. 什么是软件光栅化？

• 是一种在CPU上对面片进行光栅化以实现物件上传到GPU之前就完成遮挡剔除

2. 为什么要用软件光栅化（CPU）而不用硬件光栅化（GPU）

• 硬件光栅化的遮挡剔除因为GPU/CPU之间的传输时延，导致使用这种方式进行遮挡剔除性能较差

3. 软件光栅化的具体实施方案与流程是怎么样的？

• 这个后面会细说，简要流程描述直接看后面conclusion部分

4. 软件光栅化的性能表现与使用局限又是怎么样的？

• 性能上从测试数据来看，已经远远超出纯粹frustum culling的性能表现（也就是说有了occlusion culling之后，就不需要frustum culling了），使用局限暂不清楚。

以下是原文正文核心点的抽离与分析。

---

0. Abstract

要想避免高频Overdraw带来的渲染消耗，高效的动态遮挡剔除就变得十分重要了。Intel受到硬件光栅化的启发，借用CPU的SIMD特性（下图给出了Intel的CPU并行架构发展历程图。），给出了一套软件光栅化技术方案，这个方案可以剔除掉全分辨率深度贴图下硬件光栅化剔除结果98%的物件，相比此前的软件光栅化方案，性能还提升了3x以上，整个方案支持interleaving式的遮挡体光栅化（具体含义不明，等待补充）以及毫无消耗的遮挡查询，因此使用起来十分方便。

1. Introduction

为了增强沉浸感，现代游戏中场景的动态要素越来越多，而这也对剔除方案带来了越来越高的要求。因此传统如PVS的预计算遮挡剔除方案就逐渐满足不了需求，在这种情况下，众多的厂商开始将目标转向如HZB、硬件光栅遮挡剔除、软件光栅遮挡剔除等方案。

软件光栅遮挡剔除的基本做法，就是在每一帧update完成之后，在CPU侧对场景进行一遍光栅化，输出一个depth buffer，之后使用这个depth buffer对场景物件进行剔除，避免将那些不可见的数据塞入渲染列表，从而减轻渲染压力。

在软光栅方案中，剔除精度与性能是一对冤家，没有办法同时兼顾，因此通常需要在算法上做一个平衡。Andersson [And09] 跟Collin [Col11]的软光栅方案采用了一个低分辨率的depth buffer来降低消耗，但是这种做法在精度上就会存在问题，为了降低精度不足导致的问题，这个方案的做法是采用inner-conservative（将原始mesh逐像素的向内坍缩以形成一个极简的遮挡mesh）的mesh来作为遮挡体生成遮挡depth buffer，但是inner-conservative mesh的生成十分困难，可能会导致false-negative（即将一些可见的物件剔除）的情况出现，此外对于美术同学建模也有一定要求，显然十分的影响开发效率。Intel的方案采用的是全精度的depth buffer，但是在性能上就相对更低一点。

本文给出的方案相对于此前的软光栅方案的特点在于，输出的coverage数据（即那些区域被遮挡，遮挡的具体数值是多少）不再是depth buffer，而是经过编码的其他数据。为了提升处理效率，降低时间消耗，此方案处理的最小单位不再是pixel，而是tile（每个tile的尺寸为32 x 8个pixels），给出了一种快速计算某个tile的coverage数据的算法，从而才使得此方案在保持较高计算精度的情况下，其消耗并没有相应的大幅增加。

这个方案是在[AHAM15]的硬件masked depth culling方案的基础上经过如下扩展得到的：

1. 给出了一个通过少数几条SIMD指令就能够实现多个tile的coverage数据的并行生成的算法
2. 在[AHAM15]的depth更新算法的基础上进行了一定程度的修正，以一定的精度损失来换取性能的增幅
3. 给出了一个对SIMD指令友好的depth层级结构，这个结构是专为Occlusion Culling设计的，具有较低的内存消耗
4. 设计了一个高性能的Occluder渲染算法与遮挡查询方案，以实现对场景简洁而高效的遍历访问。

遮挡剔除后结果 场景顶视图，灰色区域表示被剔除的场景物件 层级depth buffer，越远越黑

2. Previous Work

对于静态场景而言，常用的做法是预计算的PVS或者portal/mirror算法，但是随着场景中的动态元素越来越多，这种算法已经难堪重任。

[GKM93,Gre96]提出了第一个使用层级depth结构的算法，且这个算法对后续硬件的发展产生了很大的影响。[ZMHH97]则第一次提出了层级遮挡贴图（occlusion maps）算法，基于其创建层级遮挡贴图的方式，还给出了近似的遮挡查询方案。[Mor00]则给出了层级Z算法（HiZ，这个算法是伴随一个叫做HyperZ的芯片架构给出的，HyperZ架构包含三项特性：1. Z Compression，给出了一种无损的Depth压缩算法，可以降低Depth的读写带宽消耗；2. Fast Z Clear，通过将Depth Block整个标记成Cleared来避免此前通过大量带宽消耗实现的Depth Write；3. HiZ，与传统pixel 沙丁完成后再进行depth test（late depth test）不同，新的架构允许在光栅化时通过一张HiZ来提前进行Depth Test，详情参考文献[2]中的wiki链接），这个算法的Hierarchy只包含一个Level（那为什么叫层级，是指单个mip吗？指的是从全分辨率的depth buffer中构建出一个hierarchical depth buffer，算上全分辨率depth buffer，就有两个level，但是由于只使用后面生成的这个hierarchical depth buffer，因此准确来说只包含一个level），这个算法充分考虑到了硬件的设计架构，因此具有很多的优点，后续很多GPU硬件的设计都添加了类似于HiZ的遮挡剔除方案。

[AM04]通过将众多的遮挡剔除方案集成到一起，给出了所谓的dPVS（dynamic PVS）方案，以实现对大量具有众多动态物件场景的剔除支持（剔除界的要你命三千？）。早期的Umbra Engine [SSMT11]是能够支持CPU & GPU支持的，不过目前就只剩下CPU方案了。[BWPP04]基于硬件遮挡查询构建了一个方案，在这个方案中，要想得到更好的剔除效果，就需要对场景按照从前到后的顺序进行遍历，此外还需要对此前可见（上一帧？）的物件的绘制结果与查询结果进行interleaving（从后面interleaving的含义推测，这个地方指的是需要在将查询跟渲染放到一起，一次性完成处理？）。

由于硬件提供了predicted rendering（只有当occlusion query成功之后，才会执行对应的draw call，这种做法可以尽量减少GPU/CPU之间的通信消耗）功能，使用近似遮挡查询（比如使用GPU的HiZ buffer）加上“any fragments”优化（在这个优化开启时，只要找到任意一个可见的像素，那么就认为此物件可见，终止后续的查询），就能使得硬件遮挡查询成为一项可用的技术。

说到软件光栅化方案，[Val11]绘制了一张全精度的depth buffer，并按照一定的算法对齐进行下采样以实现对遮挡测试的加速。[Per12]则是从inner conservative occluder boxes中生成凸遮挡体，并将那些完全被这些凸遮挡体完全包裹的物件剔除来实现加速。

还有一些算法如[KSS11, HA15]则是通过将上一帧GPU生成的depth贴图经过下采样与reprojection，之后按照一定的补洞逻辑填补上reprojection产生的数据缺失来实现遮挡贴图的创建。然而这类算法的问题在于可能会有一些错误的剔除，此外对于两帧之间的变化幅度有一定限制（不能出现较大的变化，比如快速移动的动态物件就是一个非常大的问题），因此使用起来非常不方便。

3. Algorithm and Implementation

先来介绍一下Intel的软件遮挡剔除框架[CMK*16]，本文介绍的这个方案最开始就是在这个框架中实现的。

Intel框架的遮挡剔除主体包括两个pass：

第一个pass会对场景物件进行筛选，取出一系列比较重要的（屏占比高）、大尺寸的遮挡体物件，同时对这些物件进行frustum & backface culling，那些没有被剔除的物件就会进行变换以及软件光栅化，结果会被存入到一张全分辨率depth buffer中，这个buffer之后会以8 x 8个像素（对应一个pixel cache line size）为一个tile，对每个tile中的像素的depth取最大值，来得到一张降分辨率的depth buffer，从而如[GKM93, Mor00]一般，得到一张单层的Hierarchical Depth Buffer（one-level hierarchical depth buffer，每个像素对应全分辨率下的一个tile）。

第二个pass，则会对场景中物件的bounding box执行软件遮挡查询（CPU）。bounding box会先进行frustum culling，通过之后经过CPU转换到屏幕空间，得到一个屏幕空间的rectangle，这个rectangle的最小depth，可以计算得到为，之后就以tile为处理单位，对上述rectangle进行遍历，对遍历的各tile的最大depth 与进行比对（越小表示越近，这个结论跟最前面展示的深度图表现不太一样，推测可能是使用了reverseZ逻辑），判断在这个tile中，rectangle是否是可见的（ > 表示可见，否则不可见），如果所有tile都是不可见，那么这个物件就会被认为是不可见了（从这个描述来看，单层的depth buffer指的就是每个像素对应全分辨率中的一个tile的depth level，不像HiZ算法中的Depth Mipmap）。

本文给出的算法大致流程跟常见的两层（two-level）hierarchy软光栅算法相同，不同的地方主要有如下两点：

1. 如上图所示，整个2D图像空间会被分割成一个个的tile，每个tile包含32 x 8个像素，本文算法会借助CPU的SIMD特性（8路SIMD，每路包含32个bits，后续SIMD并行能力如果升级，性能还可以进一步提升）根据三角面片的边缘数据对同一个tile中的多个像素进行并行计算，一次性输出整个tile的coverage masks。
2. 本文所使用的depth数据表达方式跟传统的不太一样（具体后面会细说），在这种表达方式下，可以无需使用全精度的depth buffer就能得到较高的裁剪精度，且同时还可以实现depth数据与coverage mask的解耦（作用是可以用较低分辨率的depth buffer来进行遮挡剔除查询），在这种表达方式下，最终的coverage数据消耗的内存要比depth buffer低一个数量级。

下面给出了本算法的大致流程图：

总体来说分成两大块，其中triangle setup对应的是scanline的遍历逻辑，而tile traversal部分对应的则是depth buffer的遮挡查询与软光栅更新。

下面借用参考文献[5]中的图来逐一介绍各个阶段的功能逻辑：

Transform & Clip阶段主要是对面片进行空间变换，按照frustum culling完成面片的clip处理。

为每个三角面片，计算其屏幕空间的rectangle范围，以32x8的tile作为最小的覆盖单元。

可以只计算某个顶点的数值，之后根据平面斜率按照一定的策略直接增减某个数值来得到后续的覆盖情况，可以参考后面scanline的处理逻辑。

覆盖情况知道了之后，就是使用scanline对这个三角形进行扫描并光栅化。

scanline处理是借助SIMD功能并行完成的，在那之前，先来看下AVX的寄存器布局，这里AVX包含8个SIMD处理单元，每个单元负责32x1或者8x4个像素的处理逻辑。

在三角形scanline处理的时候，使用的是32x1的处理模式。

三角形的每条边，我们可以计算其对应的斜率，这个计算只需要进行一次。

3.1. Efficient Triangle Coverage

除了利用SIMD的并行计算特性来加速计算过程之外，本文在coverage计算上的算法流程跟[AW80]中的边缘填充（edge fill）光栅化算法基本一致。

先考虑不需要并行计算的部分，三角形的光栅化过程是通过计算left event与right event来实现的，整个屏幕2D空间被一条条等间隔的水平scanline分割成一个个的Pixel/Fragment，而所谓的left event指的是三角形与某条scanline相交的左边界，right event则是相交的右边界，通常来说left event是三角形某条边跟scanline的交点，而right event则是另一条边与scanline的交点，对于某条固定的边而言，如果我们已经找到了其最下端与scanline的交点，我们只需要计算出（斜率）即可随着scanline序号的增加（即y增加一个）加上一个对应的数值（比如是）即可得到对应的新的scanline的交点，因此其计算过程十分简单。

这里的一个问题是，如果三角形某条边（线段）在scanline序号递增的过程中已经到达了终点，从而需要另外更换一条新的边进行left/right event的计算，这种情况就不能直接通过对一个数值进行相加来得到了，而是应该重新启动初始化过程（新的边与scanline的初始交点计算过程）了，其实简单来说，就是要以y方向上的中间顶点为界，画一条水平线，将三角形拆成两个三角形，top/bottom triangle。

对于某条scanline而言，如果已经知道了left/right event，那么下一步就是计算这个三角形在这条scanline上的coverage情况了。这里的做法是为32个像素生成一个32bit的coverage mask，每个bit对应一个像素（如果三角形的覆盖数据超出32个像素，那么就会对应多个coverage mask，每个coverage mask占用一次循环调用，处于一般性考虑，这里只考虑单个coverage mask能够覆盖的情况），之后整个coverage mask可以用一个register来表示，register在初始化时可以直接将每一位设置为1（表示有像素覆盖），之后根据left/right event数据使用移位操作来清除left/right边界之外的像素对应bit上的数值（表示没有像素覆盖）：

// Compute coverage for the 32-pixels at pos. x,
// given the left and right triangle events
function coverage(x, left, right)
{
  return (~0 >> max(0, left - x)) & ~(~0 >> max(0, right - x));
}

每路SIMD对应一个coverage mask，8路SIMD分别对应水平坐标一致的8个相邻scanline上的coverage mask。这种做法的一个问题是什么呢，那就是对于某个scanline而言，我们只有两个event需要追踪，但是每个triangle却有三条edge会对这两个数据造成影响，因此使用上面的移位操作是不准确的，更为恰当的做法应该是使用如下的函数进行计算：

// Compute coverage for 32x8 pixel tile. Params
// are SIMD8 registers with 32 bits per lane
function coverageSIMD(x, e0, e1, e2, o0, o1, o2)
{
  m0 = (~0 >> max(0, e0 - x)) ^ o0;
  m1 = (~0 >> max(0, e1 - x)) ^ o1;
  m2 = (~0 >> max(0, e2 - x)) ^ o2;
  return m0 & m1 & m2;
}

上面这个算法可以理解成对每条边，都clear掉其右侧的像素区域（三角形按照逆时针设置每条边的方向，如果对三角形的edge按照一定的顺序进行排序的话，还可以省掉上面的xor计算消耗），最后将clear结果进行相交计算，以得到最终的mask结果，整个过程如下图所示：

上面这个算法只是一个示意计算过程，实际上原文还给了一些指令优化的实施方案，因为无助于整个算法框架的介绍，这里就不展开了。

Precision
因为上面这个coverage算法并没有依赖于具体的edge function（这是什么？三角形每条边的坐标公式吗？），因此其最终光栅化的结果跟DX光栅化规则作用下的结果可能不太一样。比如前面说过，left/right event的计算是根据对初始交点进行递增来实现的，而计算结果并不是十分精确的（比如经过四舍五入，会有精度损失；又比如假设三角形某条边接近水平，这个数值将变得十分巨大，其精度将进一步下降（浮点数越靠近零点，精度越高）），因此使得在光栅化的过程中会有累计误差的存在。而这种不精确的光栅化结果会使得遮挡剔除出现false positive（某个物件被判定为可见，实际上是不可见的，导致渲染消耗的浪费，倒并不会导致渲染结果的异常）问题，不过从此前的软件光栅化方案来看，各个方案或多或少都有这样的问题，因此也并不是不能容忍。

如果要想做得更好，也可以按照[Bre65]中介绍的Bresenham插值算法来实现一个遵循DX光栅化规则的对应算法版本，从而消除上面提到的精度误差，原文说到Intel做了一个demo版本，经过测试在大量的随机三角形输入下，都能取得跟GPU光栅化一致的结果，不过SIMD优化版本还没搞定，因此这里就不介绍具体性能数据了。

之后只需要得到这条边上的第一个交点，根据斜率就可以推算出其他的交点，因为使用了AVX，我们可同时完成8个scanline的处理。

之后就是对三角形的left/right event进行处理，得到三角形的coverage mask，具体逻辑后面有详细描述。

先将整个tile设置成完全被覆盖的，之后对每条scanline找到三角形与之相交的left/right event

得到最终结果

3.2. Hierarchical Depth Buffer

上一节我们介绍过，经过coverage计算后，每路SIMD的mask包含32个bits，8路SIMD对应32 x 8个bits，出于计算效率的考虑，depth test & update就不再适用与32 x 1这样的长条状processing unit，因此这一节会对SIMD的覆盖区域进行重新划分，将32 x 8个bits分成8 x 4为一个tile的4 x 2个tiles array，每个tile（注意不是每个像素）会分配两个浮点数（表示depth）以及一个32bits的mask，这个mask用于指示这个tile中的每个像素使用的是上面两个浮点数中的哪个浮点数。

如下图所示，为了后面计算方便，coverage mask计算完成后需要对SIMD lane覆盖的方式进行一下调整与重排，在调整之前，每条lane对应一个scanline

调整后，每条SIMD lane对应一个8x4的tile，结果如下图

4 x 2个tiles就有8个struct，从而组成一个Struct of Array（Struct包含三个Array，对应上面的三个数据），之后通过使用AVX2指令，就可以实现对8个tiles的depth test & update的并行计算。

如上图所示，左侧小图表示的是一个8 x 4个像素组成的一个tile，前面说过，每个tile分配了三个数据，从右图可以看出，表示的是较远的一个depth值，而表示的则是较近的一个depth值。即左图中黄色三角形距离相机更近，而蓝色三角形距离相机较远，另外剩下的32bits的mask则表示的是tile中每个像素所对应的depth数值，因为只有两个depth可选，因此只需要一个bit表示。

Depth Buffer Update
由于整个场景中不止一个三角面片，而多个三角面片之间是有重叠的，因此我们需要一个算法来对被三角面片所覆盖的tile数据进行更新，精确的可供参考的算法有[AHAM15]，但是这个算法太过复杂，因此Intel又参考[FBH*10]的quad fragment merging算法写了一个相对简单但是结果不那么精确的算法，相对于原算法而言，这里对渲染顺序的要求更为严格，实际上，我们在做occlusion culling的时候，最好使用经过良好排序的物件列表（即距离近的优先处理），这样得到的性能最高。

function updateHiZBuffer(tile, tri)
{
  // Discard working layer heuristic
  // zMax1 < zMax0, zMax1 -> More Near
  dist1t = tile.zMax1 - tri.zMax;
  dist01 = tile.zMax0 - tile.zMax1;//positive
  // Not Occluded And Far From Tile, Using Cur Triangle As New Near Plane
  if (dist1t > dist01)
  {
    tile.zMax1 = 0;// Reset The Near Plane
    tile.mask = 0;// Reset The Tile PixelDepth Selection Data
  }

  // Merge current triangle into working layer
  // dist1t > dist01, Not Occluded, Using tri.zMax, Near One
  // dist1t < dist01, but dist1t >= 0, Not Occluded, Using tile.zMax1, Far One?
  // dist1t < 0, Occluded, Using tri.zMax, Far One?
  tile.zMax1 = max(tile.zMax1, tri.zMax);
  // dist1t > dist01, Coverage Area Select zMax1, Other zMax0
  // dist1t > 0, Union Older zMax1 Area, Using zMax1
  // dist1t <= 0, Union Older zMax1 Area, Using zMax1?
  tile.mask |= tri.coverageMask;
  // Overwrite ref. layer if working layer full
  if (tile.mask == ~0)
  {
    tile.zMax0 = tile.zMax1;
    tile.zMax1 = 0;
    tile.mask = 0;
  }
}

tile中的两个深度数值，近的我们成为working layer，远的，我们成为reference layer，伪代码中的逻辑总的来说可以分成三部分：

1. 如果当前triangle在这个tile范围内的最大深度远远小于working layer深度：那么这个时候就将working layer重置到近平面处，并同时将tile中所有像素的深度设置为reference layer的深度（这个更新逻辑是基于什么考虑？这是因为，当depth出现一个较大的不连续性，比如下图中下方小图中右边的triangle的depth远远小于当前tile的两个参考depth，就表明目前参与光栅化的是一个新的物件，这个triangle只是先遣部队，后续的triangle会逐步将整个tile覆盖住的，所以可以直接放弃之前的working layer的积累，迎接全新的数据的到来。上方小图左侧对应的是不做这个处理的HiZ，右侧对应的是做完这个处理的HiZ，原文中说是会存在背景物件轮廓处的depth泄露，我的理解是如果不做这个处理的话，考虑到后面working layer的合并逻辑，最终tile的working layer深度会更多的使用前一个物件的depth，导致当前更近物件的depth无法覆盖上去，从而使得working layer depth相对更远一点（更黑一点））；其他情况则维持tile数据不变。

2. 在working layer depth与中取较大（较远）的作为新的working layer depth（这个是基于什么考虑呢？首先，当前参与tile参数更新的triangle需要是能够通过当前tile的depth test的，不然这样一更新，可能就会使得working layer比reference layer还远，这是不符合设定的；其次，如果working layer depth小于triangle的max depth，那么如果以扩大coverage mask为目的，为了避免更新后的误剔除，就应该以较远的一个为准，从而保证在大于这个深度的数据是肯定会被遮挡住的，而以较近的为准，就没有做出绝对正确的判断了），并合并当前triangle的coverage mask到tile中。
3. 如果当前tile的coverage mask已经满了，这个时候就需要用近的working layer depth来替换远的reference layer，从而保证tile的遮挡面片是不断向前推进的，这个过程可以参考下图示意。

为了对这个过程有一个更为直观的认识，借用参考文献[5]中的几张图来说明：

depth test是与depth update同步进行的，这里介绍了两种用于对depth进行更新的方法，后者虽然精度上有所下降，但是速度上有很大提升。

每个tile有两个代表不同深度的浮点数：

1. 是reference layer，指的是整个tile的最大深度（最远距离）
2. 是working layer，表示的是tile中部分区域的最大深度（更近一点的遮挡面），这是depth update的焦点，会按照如下模式进行更新
   2.1 ，取三角形的最大深度与当前深度的最大值
   2.2 新的selection mask取三角形的coverage mask与原始tile的selection mask的并集
3. 当working layer对应的selection mask已经被填满了，此时就可以将reference layer往前提到working layer上，并重置working layer的数据

如下图所示，如果有一个面片完全覆盖了整个tile，那么没说的，直接修正reference layer

如果是部分覆盖（通过了depth test），那么就修正下working layer，同时修改selection mask

而有一个新的面片通过了depth test的话，与之前的working layer depth取其中最大的数值，同时对mask求并

经过并集之后，如果working layer已经满了，就将reference layer拉上来

开始下一轮的重新处理

这里有一个特殊的处理策略，即当新的三角面片远远超过两个layer之间的深度差，会直接考虑清掉working layer的数据，使用新面片的数据，这是因为当发生这种情况时，通常意味着一个新的物件的处理流程的开始，还使用老的一套数据，会导致一些新的面片数据被老的数据所遮盖，使得新物件的遮挡效果被削弱。

在这个基础上继续进行后续处理。

完全覆盖的情况，前面已经说过了，直接修改reference layer，并重置working layer。

效果验证，update、test都比之前的方法要快。

Hierarchical Depth Test
正如前面所说，在进行过光栅化的时候还会同时对triangle进行depth test，目的不是查询当前triangle是否可见，而是为了对光栅化逻辑进行性能优化，因为，因此这里只需要检测与（用是不是更准确？后面Discussion有说）两者谁更大，如果后者更大，说明当前triangle至少部分是被tile所遮挡的（存在较大概率全部被遮挡？），这时候就放弃使用triangle对tile的更新。实践证明，虽然这个做法非常简单，但是却可以极大的加速光栅化流程。

虽然这种做法十分合理，但很多软光栅算法都没有使用。

depth test是逐tile进行的，每个tile包含两个代表一前一后深度的浮点数以及表示8x4个像素所对应的深度的uint32 mask。

Discussion
本文给出的算法跟[AHAM15]的很像，不同的是，本文算法放弃了参数的使用，而这个参数通常会被用于判断triangle是否完全被遮挡，不过通常来说，可见物件的遮挡查询消耗都不会很高（因为只要发现一个像素可见，就可以随时终止查询，对于可见物件而言，这个过程会很快），因此完全遮挡情况下的跳过后续的遮挡查询在tile模式下可能作用不大，后续在使用中再判断是否需要保留这个数值。

4. Results

上图给出了HiZ算法与本文的Mask算法的性能对比，实线表示的是单帧绘制总消耗，虚线表示的是遮挡剔除的时间消耗，虽然Mask算法剔除的triangle数量相对于HiZ少了2%，但是其表现还是要远远超出HiZ算法。作为对比，不使用任何软光栅时的单帧消耗用红线的Frustum来表示（软光栅可以极大的提升渲染性能，不只是因为减少了CPU/GPU之间的数据传输，同时也降低了CPU一侧的消耗；不过需要注意的是，如果场景很复杂，瓶颈处在GPU侧，那么软光栅的作用就没有那么明显了，因为CPU优化并不能降低瓶颈位置的消耗）。上述测试是在提交顺序按照物件从近到远的条件下完成的。

为了单纯的比对算法的效率，这里测试使用的是单线程模式（原文描述说单线程就够了，其他线程可以分配给其他工作，且就线程模式来说的话，这个算法不比任何其他算法差。。）。当前算法已经放入到Intel的Software Occlusion Culling Framework中。

4.1. Intel Software Occlusion Culling Framework

2016年1月份的Framework版本已经集成了经过AVX2指令优化后的HiZ算法版本，这个算法使用了两个pass完成遮挡剔除：

1. 首先将遮挡体软光栅到一个全分辨率的depth buffer中，之后以8 x 8为一个tile统计出这个tile中的最大depth，得到一个降分辨率的depth buffer（HiZ Buffer）
2. 使用降分辨率的Depth Buffer进行遮挡查询，以确定哪些物件需要被剔除。

本文算法对上述算法做了两个改进：

1. 放弃了此前对物件进行遮挡查询时使用的对物件的bounding box进行像素级别的软光栅，只是保留了一个粗糙的遮挡查询，即使用屏幕空间的bounding rectangle来进行查询。
2. 将场景中需要参与查询的物件组织成一棵与坐标系平齐的AABB树。因为场景中存在较多的小物件，单个单个查询费时费事，组织成树状结构就可以分层进行查询，先粗糙后精细，通过这种方式可以极大节省算法开销。

经过上述两个优化后，每帧消耗得到了极大提升。

上图给出了两种算法在各个子项上的性能数据对比。

4.2. Interleaved Rasterization and Queries（将光栅化流程跟遮挡查询流程放在一起处理）

Intel还对本文给出的算法做了一个stand-alone的实现，在这个实现中，场景是按照AABB树的格式存储的，并使用一个堆（heap）实现场景节点接近front-to-back顺序的遍历，在遍历的过程中会对节点进行frustum culling & occlusion query，从而在当前节点被判定不可见的时候，可以跳过其子节点的遍历流程，下面给出的是节点遍历的伪代码：

function traverseSceneTree(worldToClip)
{
  heap = rootNode
  while !heap.empty()
  {
    node = heap.pop()
    if node.isLeaf()
    {
      rasterizeOccluders(node.triangles)
      node.visible = true
    }
    else:
    {
      for c in node.children
      {
        culled = frustumCull(c.AABB)
        clipBB = transform(worldToClip, c.AABB)
        rect = screenspaceRect(clipBB)
        culled |= isOccluded(rect, clipBB.minZ)
        if !culled:
          heap.push(c, clipBB.minZ)
      }
    }
  }
}

虽然上面的代码看起来就跟随便从哪个关于软光栅的教科书上抄过来的一样，但实际上这里需要注意的是，传统算法中，将节点遍历（光栅化）跟遮挡剔除像这样一样放到一起是会产生问题的。

比如HiZ之类的软光栅方案，因为Hierarchical Depth Buffer的生成消耗很高（参见后面的性能消耗表格），因此想要将光栅化逻辑跟遮挡查询逻辑放在一起是不现实的（光栅化的过程会对Hierarchical Depth Buffer进行更新，如果放在一起，就会导致整个流程效率的低下？）。

同样，对于采用GPU实现的硬件光栅化算法，如果希望用硬件光栅化的结果（depth buffer）像上面代码中一样直接用来对节点进行遮挡查询的话，由于数据读取的延迟，同样会造成同步以及阻塞等问题。

本文使用的软光栅方案可以在同一个Hierarchical Depth Buffer上读取数据对节点的可见性进行判断（遮挡查询），同时还可以将通过遮挡查询的节点通过软光栅对这个Buffer进行更新，而这种做法不会存在任何的性能问题，因此使得对场景的遍历算法变得更为简单，而且由于只需要对那些可见的节点进行光栅化，因此效率也比其他算法要高一些。

上图是本文算法的测试场景以及对应的测试数据，测试过程中添加了一个较短的相机动画。整个场景包含了大概73M个面片，不过这些面片并不会全部参与到Hierarchical Depth Buffer的生成中（毕竟生成与更新也是有代价的），作为遮挡体的面片数目为143K（这些面片来自于architectural mesh，这种mesh有什么特征？）。

跟此前Intel的Demo场景相比，这个测试场景更为复杂，且遮挡体包含了数目众多的大而细长（sliver）的三角面片，而这类面片由于具有较大的屏幕空间rectangle而会导致计算效率的下降，同时也并没有提供相对应的遮挡剔除贡献，但是即使在这种情况下，比对本文算法与此前Intel算法在worst case上的表现，还是可以得到远超此前算法的性能，且跟纯粹的frustum culling算法比起来，只在一些极难遇到的情况下才会得到稍差的表现（即这个算法可以完全取代frustum culling了），而在这些情况下，帧率都是非常高的，不会造成问题。

上图是本文算法应用的第二个测试场景，这个场景包含了7M面片，且这一次直接将所有面片都用于计算hierarchical depth buffer，因此但从遮挡体复杂度来说，这应该是整篇文章中最复杂的测试场景了。

从这种设定来看，软光栅的性能可能很难超过纯粹的frustum culling算法，当然，如果将场景渲染的pixel shader设计得复杂一点，场景材质做得更多一点，那么frustum culling所需要承担的高额overdraw的消耗就会更高，软光栅算法的数据会漂亮一点，但是出于公平考虑，这里整个场景只使用一个简单的材质，且从头到尾不需要进行renderstates切换，且软光栅只使用单个CPU核来完成相关计算，但是即使在这种设定下，本文算法的性能表现依然很好，只在少数一些相机位置的表现不如frustum culling算法，且总体的时间消耗都可以控制在5ms以下。

上图还给出了不同算法最终提交到GPU的面片数目，本文算法基本上跟HiZ表现一样，在一些情况下其Culling力度甚至超越了HiZ（这是因为HiZ的Depth Buffer并不是每帧更新的，因为时间消耗的关系，是每隔几帧才更新一次）。

有限时间预算
遮挡剔除算法可以通过选择合适的遮挡体来进行加速，本文是通过将场景物件按照从前往后排序来实现这个过程的，因此遮挡效力最强的面片通常都是最先被光栅化的，而如果分配给软光栅的时间是有限的，那么这里可以在软光栅的时候开启一个计时器，当时间到了就停止软光栅，不过即使这样，遮挡查询过程还是会有一些消耗，从而使得最终的消耗超出预算，但是也算是一种比较有效的平衡CPU/GPU消耗的方案了。下图给出了在MPI informatics building场景中遮挡剔除所花费的时间以及对应的物件、面片剔除数量之间的关系（看起来似乎是一个分段的递减关系）：

4.3 Scaling

为了验证本文算法的scaling表现，使用了一个使用程序生成的测试场景，这个场景中包含了32k个等腰（isosceles）直角（right-angled）三角形，这些三角形的位置跟朝向都是随机的，且都是按照从后往前的顺序进行渲染的，从而避免数据被early test干掉。

以HiZ算法作为比对参考，从上图中上面一个小图可以看到，本文算法在三角形尺寸较大的时候，性能要远远优于HiZ，而在三角形尺寸较小的时候，性能则跟HiZ比较接近。

需要说明的是，使用低分辨率的Depth Buffer的问题是，可能会导致剔除精度的下降，从而导致错误的剔除结果，上图中的下面一个小图给出了每个光栅化像素对应的CPU时钟周期消耗，可以看到，不论在哪种三角形尺寸下，本文算法的消耗都要小于HiZ算法。

5. Conclusion

本文给出的软光栅剔除方案不论是性能表现还是剔除精度上都有不错的表现。

再来回顾一下算法的框架：

1. 使用的depth buffer是一种特殊的按照tile划分的组织结构，每个tile包含两个一前一后两个深度浮点数，以及一个表征各个像素从属深度的uint32 mask
2. 三角形的光栅化是通过SIMD edge fill算法完成，先找到第一个scanline的left/right event，之后每一个新增的scanline只需要在这个基础上按照斜率进行叠加即可得到对应的left/right event，之后就可以根据这个来计算三角形覆盖的屏幕空间像素了。
3. 本文算法所使用的depth更新是仿造quad fragment merging算法完成的，通过对三角面片的coverage mask以及来实现tile的的向前推进，从而实现最终depth buffer的构造，而occlusion query跟depth update是放在一起进行的

参考文献

[1] Masked Software Occlusion Culling
[2]. HyperZ
[3]. ATI Radeon HyperZ Technology
[4] 本文算法源码地址
[5] 本文对应PPT地址