光栅化

判断一个点是否在三角形内是通过edge function完成，下面这个式子是RTR4中给出的式子，xy为像素坐标，p是边上的一点（可用顶点直接替代），n是该边朝三角形内部的法线，然后通过该式的正负判断像素点位于边的哪一侧。

其实这个式子也可用叉乘+带符号面积理解。

edge function可以写成下面的形式

该形式有个重要的优点，就是加入已经知道了(x,y)像素的结果，(x+1,y)像素的结果可以直接加a得到，(x,y+1)像素的结果可以直接加b得到。

当一个像素在两个三角形公共边上的时候如何判定该像素属于哪一个三角形。

top-left rule
如果像素中心落在top边和left边上的时候，该像素被认为在三角形内。

若该边是水平的，并且其它边低于该边，则该边是top edge。
若该边不是水平的，并且该边在三角形的左边（一个三角形可能有两条left edge），则该边是left edge。

若edge function中a=0且b<0，则为top edge
若a>0，则为left edge。

为了提高效率，光栅化过程中不会遍历所有的像素来判断是否在三角形内。而是先按块判断，判断块是否在三角形内的方法如下图所示：

首先将块的四个角的坐标投影到n上，选择值最大的点（图中黑色点）进行测试，如果edge function结果为正，则在三角形内，反之不在，移动到下一个块。

假定块大小是8X8像素大小，那么下一个块的结果可以省略上面步骤，直接计算出来，也就是8a+e，e为当前块结果。这利用了上面提到的edge function 的优点。

在三角形traversal之前，通常还会进行triangle setup，该步骤是为了计算traversal和插值所需的常量因子，比如edge function中的a，b,c。
clipping在setup之前做，因为裁剪可能会产生更多三角形，为了防止因裁剪产生过多三角形，通常会在clip区域中设置一段保护带（guard-band），如下图中蓝色三角形则不必被裁剪了：

插值
三角形顶点的任何属性a都可以通过重心坐标(u,v)插值出来，下面的式子中Ai代表顶点pi对边与插值点(x,y)组成的三角形的面积。

另外一个结论是edge function的结果等于改变与插值点围成的三角形的面积，那么也就是说uv可以用edge function计算

透视校正插值，参见我的第二篇博客

保守光栅化CR
见下图，绿色是内部保守光栅化，蓝+黄+绿是外部保守光栅化

ALU

ALU是一段用来执行特定实体（顶点 片元等实体）程序的硬件。有时也用SIMD lane表示ALU。如下图，ALU的主要计算单元是floating point （FP）unit和integer unit。dispatch port接受要执行的当前指令的信息，operand collector读取指令所需的寄存器。

ALU也包含move/compare和load/store等能力，并且有一个unit用于计算sin，cos等操作。在某些架构中，计算sin等操作的单元从ALU中独立出来，也就是说一个unit可服务多个ALU，这些单独的unit被成组的放在special unit （SU）中。
为了更好的调度任务，大部分的GPU都将ALU成群的组织在一起，比如上图，每32个ALU一组。它们以锁步的方式执行（SIMD-processing），也就是说全部32个ALU是一个SIMD engine。不同厂商对其命名不同，RTR4中使用Multiprocessor（MP）。

MP中有一个scheduler来分配任务到SIMD engine，同时还有L1 cache，local data storage(LDS),texture units(TX),还有前文提到的SU。

scheduler首先取得任务，然后将任务分派到MP中，将registers file（RF）中的寄存器分配给warp中的thread，同时对这些任务确定优先级。一般来说后期的一些阶段优先级更高，比如片元着色器的优先级高于顶点着色器，这是为了避免拥塞。

注意，对于Piexl shader，warp scheduler分配整个quad(2x2像素大小)的任务，这是因为为了能够计算导数，像素在quad尺度上着色。比如，如果warp的大小为32，那么总共有8个quad用来执行。

在更高尺度上，MP也有许多份，GPU也对这些MP分配任务。

延迟隐藏
由于处理器时钟频率和主内存读取速度以及带宽的差异，导致数据从主内存传输到处理器计算单元的过程存在很大延迟，例如全局内存的访问高达400-600个时钟周期。
为了克服这种延迟，一些技术通过一些辅助手段来隐藏这种延迟，该技术被称为延迟隐藏。当一个线程处于延迟状态时，处理器自动切换到其他处于等待状态的线程进行执行，这样通过使用多处理器能够处理个数的线程数目，内存读取的延迟也能够在一定程度上被隐藏。

GPU要放大这种技术的隐藏作用，有两个方面可以改进。第一个是使用能够容纳更多的等待线程。第二个方面，GPU拥有数量众多的寄存器，它致力于为每一个线程都分配真实的存储器，哪怕是处于等待状态的线程，这正是它隐藏延迟的秘密所在。

占有率定义

w m a x w_{max} wmax​是MP中允许的最大warp的数量。 w a c t i v e w_{active} wactive​是当前活动的warp数量。o度量了计算资源的利用程度。

假定MP中允许的最大warp的数量为32，每个warp有32个thread。一个shader processor有256KB的寄存器，其中一个shader program每个thread使用27个32位浮点寄存器，另一个则使用150个浮点寄存器。这里假定使用的寄存机代表了活动的warp的数量。

这样就得到了两个程序可用的warp数量，对于使用27个寄存器的程序78.85>32，占有率o=1，该情况是理想的，可以隐藏延迟，对于第二个，o=0.43，占有率较低，可能无法隐藏延迟。

当指令与内存读取结果无关的时候，可以选择继续执行当前warp。

占有率低也就意味着当进行内存读取的时候，可能不存在空闲的warp以供转换。

存储体系结构和总线
port（端口）是在两个设备之间发送数据的通道，bus（总线）是多个设备之间发送数据的共享通道，bandwidth是数据在总线或端口上传输的吞吐量。

对于许多GPU来说，在图形加速器上拥有专有的GPU内存是很常见的，而这种内存通常被称为video memory(显存)。访问这个内存通常比让GPU通过总线访问系统内存快得多。比如PC上的PCIe v4速度为31.51GB/s,GTX 1080的显存则为320GB/s。

传统上，纹理和渲染目标存储在显存中，但它也可以存储其他数据。场景中的许多物体在每一帧之间都不会有明显的形状变化。即使是人类角色也通常是用一组不变的网格来渲染的，这些网格在关节处使用GPU顶点混合。对于这种类型的数据，纯粹通过modeling matrices和顶点着色程序进行动画，通常使用静态顶点和索引缓冲区，它们被放置在显存中。这样做可以使GPU快速访问。

对于被CPU每帧更新的顶点数据，被放置在可以通过总线访问的系统内存中。

大多数游戏主机，如所有的xbox和PLAYSTATION 4，都使用统一内存架构(UMA)，这意味着图形加速器可以使用主机内存的任何部分来处理纹理和不同类型的缓冲区。CPU和图形加速器都使用相同的内存，因此也使用相同的总线。这显然不同于使用专用的显存。英特尔还使用了UMA，使CPU内核和GEN9图形架构之间共享内存，英特尔的SoC Gen9图形架构与CPU核和共享内存模型连接的内存架构的简化视图如下所示，注意last-level caches(LLCs)在图形处理器和CPU内核之间共享。

然而，并不是所有的缓存都是共享的。图形处理器有自己的一组L1缓存、L2缓存和L3缓存。LLCs是内存层次结构中的第一个共享资源。对任何计算机或图形架构，cache hierarchy是很重要的。如果访问中存在某种局部性的话，这样做会降低平均内存访问时间。

caching and compression
架构中cache hierarchy的目标是为了利用局部性原理减少延迟率和带宽。大部分的buffers和纹理都以分块的方式存储，这同样有利于局部性原理的应用。

大部分GPU包含专门的硬件单元用于动态的压缩和解压缩render target，这些压缩算法都是有损的。这些算法的核心是tile table，它存储了每个tile的信息。两种系统如下图所示：

左边post-cache compression，该方式的压缩器和解压缩器在cache之后，而右图在cache之前。每个tile table存储了framebuffer中由像素组成的块的信息。tile table可快速地清除rendertarget。

Color Buffering
虽然名字叫做color buffer，但实际上其他类型数据也是可以存储在里面的。color buffer有许多模式：
high color：每像素2B。
True color或RGB color，每像素3或4B。
Deep Color每像素30，36或48位。

对于High color，通常来说每个颜色5位，多出来的一位给绿色，因为人眼对绿色更敏感。该方式占用空间少，但是每个颜色可表示的level较少，可能会导致banding，如下图，同一level的强度相同，正确的感受是低-高，但是人的视觉却误以为交界处的强度变化为低-更低-更高-高:

true color模式每个通道使用1B位，在PC上，有时组合顺序为BGR。24位的颜色在实时渲染中总体上是可以接受的，虽然还会产生banding现象，但比16位的有所减缓。

Triple buffer
双缓冲在交换前后缓冲时，系统不能访问缓冲。可以采用两个back buffer来解决这个问题。额外的buffer被称为等待缓冲（pending buffer）。pending buffer和back buffer都是离屏缓冲。等待缓冲和前后缓冲一起组成了三缓冲循环。如下图底层一栏所示，该方法的优点是可以在交换前后缓冲的时候访问等待缓冲。对于双缓冲，在交换的时候，前缓冲需要保持被用户看到，后缓冲需要保持数据不变，所以在这段时间内系统不能访问缓冲。三缓冲的缺点是增加了延迟，从开始绘制到呈现在屏幕上的时间变长。

Depth Culling，Testing and Buffer
深度管线的目标是检测每个因光栅化图元而输入的深度，将该值与depth buffer中的值进行对比，如果片元通过了深度测试，将该值写入到深度缓冲中。

如下图所示，深度管线从粗糙的光栅化开始，粗糙的光栅化是在tile尺度上执行的，只有那些与图元重叠的tile被输入到下一阶段，即HIZ unit，在该单元执行z-culling。

HIZ首先执行的是coarse depth test（粗糙的深度测试），此处包括两种测试。第一个是z-max culling，其思想是每个tile存储一个最大深度值，该值被存储在cache上，或者是单独的HIZ cache上。

为了检测一个tile内的三角形是否被完全阻挡，我们需要计算三角形在tile内的最小z值 z m i n t r i z_{min}^{tri} zmintri​，如果 z m i n t r i z_{min}^{tri} zmintri​大于存储的zmax，那么该三角形被完全阻挡，后面的步骤也就不需要执行了。

精确计算最小z值消耗较大，下面是几种不同的计算最小z值的算法：
1.通过三角形的三个顶点最小z值计算，该算法精确度不高。
2.使用三角形所在平面的方程计算tile的四个角上的z值，使用它们中最小的值。

可以将上面两种方法结合起来，然后取较大的值。

除了z-max culling之外另外一种则是z-min culling，该方法有两个用处，第一个是减少读取zbuffer次数，加入 z m a x t r i z_{max}^{tri} zmaxtri​小于zmin的话，那么该三角形一定可通过测试，第二个用处是，平常一般采用Less-Than模式，这种情况下z-max裁剪很有效，对其他模式，结合zmin可带来更多提升。

上图中绿色区域是用来更新tile的zmax和zmin值的。如果三角形覆盖整个tile，那么直接在HIZ单元里修改就可以了（左边的绿框）。否则，整个tile的每个sample都需要被读取（右边的绿框），最后只保留最大最小值。Anndersson提出了一些优化该过程的方法。

通过HIZ单元后，接着计算像素或采样点的覆盖率（通过edge function计算）和每个采样点的深度（使用z-interpolation）。接着把这些值传到depth unit，在某些环境下这些值会先到piexl shader，不过由于early-z的原因，depth可能会在piexl shader之前执行。

导数计算
在Mipmap章节已经提到过导数计算，它是由硬件完成的，方式如下：

导数计算是在一个2x2的quad内执行的，这也说明了为什么GPU喜欢按quad来调度，如左上角水平方向上的导数是右上减左上，竖直方向的导数是左下减左上。

GPU纹理存储方式
第一种方式是分块存储，每块里有若干纹素，取的时候整块取出来。
第二种方式是使用swizzled模式

在上式中纹理坐标为uv，下标表示该坐标二进制表示的第i位，T表示单个纹素占有的字节数。

架构
通常来说，并行图形架构首先在application阶段将数据送到GPU，经过调度后，GPU并行的执行geometry（几何处理单元），输出的结果向后传递，依次经过rasterizer unit和pixel processing unit，完成后，将最终结果显示出了。

如果串行执行的部分过多，会影响总体的性能，可用下式度量：

其中s为串行百分比，1-s则为并行百分比，p为通过并行化程序可产生的最大提升。