Tile型三角形多向并行扫描算法的设计

樊 萌，蒋 林，杨博文，郭佳乐，田 璞

(1.西安邮电大学 电子工程学院，陕西 西安 710121；2.西安科技大学 集成电路设计实验室，陕西 西安 710054)

0 引 言

随着图形应用的快速发展，复杂的三维(3D)图形应用需求与日俱增，图形处理器(graphic processing unit，GPU)作为显示系统的核心，以硬件加速的形式实现了3D图形的绘制，在计算机系统中的作用日益增高[1,2]。光栅化是GPU的关键单元[3,4]，是将几何图元转换为片段的重要过程，其扫描填充率的高低直接影响到GPU图形加速的性能。因此，如何设计合理的三角形光栅扫描算法，使得硬件电路设计简单，扫描填充速度快成为了研究的热点。

传统的光栅扫描算法会产生大量无关像素，文献[5]介绍的Zigzag扫描算法与文献[6]介绍的中心线扫描算法都能够减少对大量多余像素的遍历，但是通过中心线算法在对三角形进行处理时，会出现中心线偏离三角形的情况，导致扫描行起始点在三角形外，从而增加无效像素的遍历。文献[7]介绍的中点遍历算法将三角形以中间顶点划分为上下两部分，通过对上下两个方向的扫描，可以解决中心线扫描算法中心线偏离的情况。但是以上算法都只能从一个方向对三角形进行扫描，并行度低，当三角形面积过大时，扫描周期变长，填充效率较低。文献[8]提出的基于块的等半空间三角形光栅化将三角形通过包围盒平分线划分为上半空间和下半空间两部分，并且以像素块为单位,同时从两个方向对三角形进行遍历，一次可以处理两个像素块，提高了扫描效率。但是该算法上半空间和下半空间的交汇点固定为三角形包围盒的平分线，当上半空间和下半空间像素分布相差比较大时，会出现其中一个半空间扫描结束，另一半空间仍有大部分像素还未扫描的情况，导致长时间的等待问题。因此，算法对三角形遍历也不能达到最佳效果。

针对现有光栅扫描算法的不足，在适用于分块式渲染(Tile based rendering，TBR)架构的基础上，提出了一种高效的基于Tile的三角形多向并行扫描算法，并通过专用硬件电路进行设计实现，该算法的设计在避免了对无关像素处理的基础上，与其它光栅扫描算法相比，并行度更高，可以显著提高三角形的遍历速度，对三角形的填充率最大可达到100%，适用于高性能的移动图形处理器。

1 适用于分块式渲染的图形处理器

为了适用于移动GPU低带宽，低功耗需求，基于Tile的GPU架构被广泛用于移动平台[9,10],该架构通常分为TBR架构和分块式延迟渲染(Tile based deferred rende-ring，TBDR)架构。

TBR架构将屏幕划分为若干个很小的Tile，并且对每一个Tile进行光栅化等后续处理[11,12]。与传统的渲染架构相比，该架构可以将整个Tile的帧缓冲区、深度缓冲区和模板缓冲区保存在片上高速缓存中，利用内部存储直接对其进行渲染，从而减少GPU对外部存储的访问和内存带宽的消耗。TBR架构如图1所示。

图1 TBR架构

为了在TBR架构上进一步降低带宽的消耗，提出了TBDR渲染架构。该架构和TBR架构原理相似，都是以Tile为单位对三角面进行绘制。但该架构对每个光栅化生成的像素都进行深度测试操作，提前剔除掉被遮挡的像素，减少不必要渲染的片段，降低了带宽的需求[13]。TBDR架构如图2所示。

图2 TBDR架构

2 光栅化扫描算法分析

2.1 边界函数算法分析

本文提出的三角形扫描算法基于边界函数方程，边界函数算法可以有效地对像素点进行判断，基本思想是通过三角形3条边的线性函数确定出属于三角形内部的像素点，判断过程如下：

假定一个Tile左上方为坐标原点，一个三角形由点A(x1，y1)、B(x2，y2)、C(x3，y3)绕逆时针顺序组成，通过式(1)计算出P(x，y)点相对于三角形3条边的边界方程，并通过Top_left原则[14]判断出该像素点与三角形的位置关系

(1)

对式(1)进行推导变形为

(2)

其中

(3)

采用Top_left原则对系数dx12、dx23、dx31、dy12、dy23、dy31进行约束，得到式(4)

(4)

当三角形3条边的边界方程值都小于0时，像素点P在三角形内部；当有其中一条边的边界方程值为0，并且同时满足式(4)时，像素点P在三角形内部；若不满足以上两种情况，则像素点P在三角形外部。

2.2 三角形光栅化扫描算法分析

通过对边界函数算法的分析，在适用于分块式渲染的GPU架构基础上，提出一种基于Tile的三角形多向并行扫描算法，在不同大小的Tile内，从三角形的最大顶点(xmax_block，ymax_block)和最小顶点(xmin_block，ymin_block)开始，将三角形分为上下两个半空间，以2×2大小的像素块为单位，分别从下到上和从上到下同时进行左右并行扫描，直到两个方向的扫描相遇时停止。该算法流程如图3所示，当输入三角形的3个顶点坐标位置信息后，先通过简单加法器和乘法器对三角形的边界方程系数进行计算，以及对三角形最大顶点和最小顶点的计算，记为三角形参数计算，然后对三角形同时进行上、下半空间扫描处理，采用边界函数算法判断出像素与三角形的位置关系，并且输出属于三角形内部的像素点，完成对三角形的扫描遍历。

图3 三角形光栅化扫描算法流程

以16×16大小的Tile为例，扫描过程如图4所示。每个框代表一个2×2像素块，其中斜线框表示边缘像素块，灰色框表示边界像素块(边缘像素块的一种)，竖线框表示内部像素块，虚线箭头表示扫描起始块像素坐标，垂直方向箭头表示当前行扫描属于上半空间还是下半空间，这需要在每一次对当前行扫描完成之后通过条件判断后得到，水平方向箭头表示对当前行进行的左右遍历。

图4 三角形光栅化扫描算法

扫描算法的步骤如下：

(1)首先计算对三角形扫描的起始像素块，根据输入的三角形顶点坐标信息，分别确定x，y坐标的最大值和最小值，利用式(5)计算出三角形的两个起始像素块坐标(xmax_block，ymax_block)和(xmin_block，ymin_block)，如图4中虚线箭头所示

(5)

其中，x(y_max)，x(y_min)分别表示当y值最大和最小时x的值。

(2)从两个当前扫描行起始像素块坐标开始同时对上、下半空间进行左右并行扫描，根据边界函数值判断并输出属于三角形内部和边缘像素块，如图4中斜线框和竖线框所示，直到遇到位于三角形之外的像素块时停止，并且记前一个像素块为边界像素块，如图4中灰色框表示。当左右方向扫描都停止时，该行扫描结束。

(3)计算下一行起始扫描像素块，开始进行下一行的扫描，下一行水平扫描线的起始块坐标可以通过当前水平扫描行的边界像素块坐标得到，具体做法如式(6)

start_block_x=left_bound+(right_bound-
left_bound)>>1,start_block_y=current_y±2

(6)

其中，start_block_x为下一行水平扫描线的起始块x坐标，start_block_y为下一行水平扫描行的y坐标，current_y为当前行水平扫描行的y坐标，left_bound、right_bound分别为当前水平扫描行的左边界和右边界。

(4)判断出下一行是停止扫描还是继续扫描，如若是继续扫描，判断出该水平扫描线是属于上半空间还是下半空间，如若是停止扫描，则三角形遍历结束。判断条件如下：

1)当上半空间和下半空间同时完成当前水平扫描行时。若满足top_start_block_y=down_start_block_y，下半空间停止扫描，上半空间完成下一行扫描后三角形遍历结束；若满足top_start_block_y=down_start_block_y+2，停止上半空间和下半空间扫描，三角形遍历结束。

2)当上半空间正在扫描当前行，下半空间开始下一行扫描时，若满足top_current_y+2=down_start_block_y，上半空间完成当前行扫描停止，下半空间完成下一行扫描停止。三角形遍历结束。

3)当下半空间正在扫描当前行，上半空间开始下一行扫描时，若满足top_start_block_y+2=down_current_y，下半空间完成当前行扫描停止，上半空间完成下一行扫描停止。三角形遍历结束。

4)若不满足上述1)，2)，3)条件，从下一行的起始像素块开始，执行步骤(2)。

在上述扫描遍历方式中，为了得到三角形内部的像素块，需要采用式(2)对每一个像素块进行边界方程计算，从而导致大量的乘法操作使得算法计算量大，实现效率低下。因此，在实际电路设计中，为了简化电路设计，加快硬件处理速度，对式(2)再进行推导得到式(7)，从而根据当前像素边界方程值可直接计算一个2×2像素块内相邻子像素点的边界方程值

E(x±Δx,y)=E(x,y)±dy×Δx
E(x,y+Δy)=E(x,y)∓dx×Δy
E(x±Δx,y±Δy)=E(x,y)+dy×Δx∓dx×Δy
E(x-Δx,y±Δy)=E(x,y)-dy×Δx∓dx×Δy

(7)

此时，在一个2×2像素块内，相邻像素点的步进为1，则Δx和Δy取值为1。

实现该算法的伪代码如下：

calculate the starting block pixel coorinates(x,y) and edge function values(e1,e2,e3).

determine if the next line scan is the top half space or the down half space.

if(topen==1)//traversing top

while(leften==1 and righten==1)

{

if(e1<0 and e2<0 and e3<0)

rendering this point;

leftx=leftx-2;rightx= rightx+2;

else

y=y+2;

}

if(downen==1) //traversing down, and the same as the top

…

y=y-2;

3 光栅化扫描硬件实现

根据对光栅化扫描遍历算法的分析，将其硬件电路实现分为4个模块：三角形参数建立模块，上半空间扫描模块，下半空间扫描模块和判断模块，硬件结构如图5所示。

三角形参数建立模块主要完成对边界方程系数dx12,dy12,dx23,dy23,dx31,dy31,c12,c23,c31以及三角形最大顶点和最小顶点的计算，并将其结果送入上半空间扫描模块和下半空间扫描模块。

上半空间扫描模块和下半空间扫描模块分为起始像素块边界函数计算模块和扫描模块。起始像素块边界函数计算模块根据三角形参数建立模块的输出数据或者扫描模块的输出数据计算出第一行或者下一水平扫描行的起始像素块的边界函数值，并将结果送入扫描模块，以判定像素块相对于三角形的位置。扫描模块对当前水平扫描行进行左右并行扫描，并且根据式(7)计算出扫描像素点的边界函数值，完成对三角形上半空间和下半空间的遍历，输出三角形内有效像素点，同时将扫描行状态送入判断模块。

判断模块决定三角形的下一行水平扫描线是进行上半空间扫描还是下半空间扫描，或者是停止扫描，并将判断结果送入上一模块。

4 性能分析与FPGA实现

4.1 性能分析

考虑到对于不同的三角形会有不同的绘制效果，为了验证该算法的适用性，在16×16大小的Tile内对等腰三角形、直角三角形、任意锐角三角形、钝角三角形以及特殊狭长三角形进行了功能验证，并将电路仿真结果对三角形进行填充，如图6所示。

图5 光栅化扫描硬件结构

图6 不同三角形的绘制结果

通过对图6的分析，该算法可以正确完成对三角形的扫描遍历过程。对于图6(e)和图6(f)中的狭长三角形来说，该算法具有一定的局限性。从图中可以看出，对狭长三角形的填充会有误差，造成三角形失真，当三角形两条狭长边在横坐标或者纵坐标跨度越小时，绘制的三角形更接近于一条直线，三角形失真越严重。这是因为当两条狭长边越接近于一条直线时，两条边内的像素往往只占半个1×1像素块，无法得到精确的绘制。要解决这个问题，需要将一个1×1像素块再进行划分，假设对1×1像素块再进行2×2像素划分，则绘制的像素个数会成为原来的4倍，这样虽然会得到更精准的狭长三角形，但牺牲了填充率，对于一般三角形而言，会显著降低对三角形的绘制速率，延长三角形的绘制时间，因而降低在图形绘制中光栅化的实现效率，并且，在一般高分辨率图像显示中，这种误差并不影响人们的视觉体验。因此，为了提高三角形的填充率，本文选择该算法完成对三角形的扫描遍历。

衡量光栅化效率最重要的性能指标是平均每个周期能够产生多少个有效像素，一般而言，假设三角形3个顶点坐标为A(x1，y1)、B(x2，y2)、C(x3，y3)，则该三角形包含的有效像素个数可以近似为

count_pixel=area

(8)

其中，area为三角形的面积[15]。当产生该三角形内的有效像素所花费的时钟周期个数为T时，平均每个周期产生的有效像素个数为

pixel=count_pixel/T

(9)

三角形的扫描填充率为

rate=area/T

(10)

为了测试本文提出扫描算法的实际处理速率，根据本文所设计电路的实验结果，对不同种类三角形实际填充的像素个数以及完成对三角形遍历所使用的时钟数进行统计，计算出三角形的扫描填充率。结果见表1。

从表1可以看出，本文所设计的算法对直角三角形和等腰三角形的填充率可以达到100%，对钝角三角形和任意锐角三角形的填充率也达到80%以上。对狭长三角形的填充率却只有30.16%，这是因为当三角形足够窄时，对三角形的绘制更趋近于一条直线，一行只需遍历一个像素甚至半个像素，无法发挥算法的并行优势。但对于大部分三角形来说，该算法能够有效地提高三角形的填充率。

表1 不同三角形的遍历结果

为了能够更好地说明提出的扫描算法的高效性，将三角形处理过程中一个时钟节拍所能够处理的像素数目进行统计，与文献[5]、文献[1]提出的双扫描技术以及文献[8]提出的扫描算法进行比较，结果见表2。

表2 不同算法在一个时钟节拍处理的像素数目比较

文献[5]介绍的Zigzag扫描算法以像素点为单位，从起始像素点开始对三角形进行水平扫描，直到遇到无效像素点，使y坐标步进一个单位接着对下一行扫描，如此重复至最后一行结束；文献[1]提出的双扫描技术基于bresenham线扫描算法，以像素点为单位，在单扫描技术的基础上，使用两条扫描线，以y轴中间顶点坐标为界，从上下两端对三角形处理，直到三角形分界线时结束；文献[8]提出的基于块的等半空间三角形光栅化扫描算法是以像素块为单位，将三角形通过包围盒平分线分为上下两个半空间，并从上半空间和下半空间同时向平分线扫描，直到包围盒平分线时停止。在遍历的过程中，3种算法在水平方向上皆是单向的。因此，从表2可以看出，本文提出的扫描算法最大的优势是可以在同一时刻处理更多的像素，处理速度更快，并行度更高。与文献[8]相比，该算法可以解决三角形上下半空间长时间的等待问题，并且将像素的处理效率提高2倍。

4.2 FPGA实现

在真实的图形绘制中，一个Tile内可能会处理多个三角形，本文对各种不同单个三角形完成功能验证后，对一个16×16的Tile内的多个三角形同样进行验证，并且采用Xilinx公司的ISE开发环境进行综合，使用Xilinx公司的ZYNQ系列芯片XC7Z045-2-FFG900对硬件电路进行FPGA测试，通过Chipscope抓取需要直接观测的信号。为了验证FPGA测试的正确性，将抓取到的信号坐标通过Matlab仿真软件进行填充，所得到的结果如图7所示。由于该结果是将小分辨的图像放大得到的，因此，锯齿效果明显，但是这并不影响扫描算法对三角形内部像素填充的正确性。

图7 FPGA测试结果

由图7可以看出，本文所设计的电路能够正确完成对三角形的扫描遍历功能，并且由图可以发现，当不同的三角形共用一条边时，依然能够正确完成对三角形的绘制。因此，FPGA测试结果正确。

在基于Xilinx V6-760 FPGA上对电路进行综合后，资源占用情况与文献[1]的两种算法对比见表3。可以看出，相比于文献[1]的两种算法，本文所设计的硬件电路Slice Registers资源使用率分别减少了59.6%和25.3%，Slice LUTs资源使用率分别减少了36.1%和12.0%，降低了对资源的使用，更易于硬件的实现。

表3 硬件电路资源使用对比情况

5 结束语

在基于分块式渲染架构的基础上，通过对现有光栅化扫描算法的深入分析，针对这些算法所存在的不足和问题，本文提出了更高效的三角形双向并行扫描算法，并通过专用硬件加速设计光栅化单元。经过实验分析，与其它现有扫描算法相比，具有更高的并行性，可以在Tile内对三角形一次处理16个像素，使得扫描填充率最大可以达到100%。通过在Xilinx公司的ZC706开发板上进行验证，可实现三角形的扫描遍历功能，适用于高性能图形处理器。