点光栅化及反走样算法的研究与实现

王媛媛，韩俊刚，蒋 林，张 娜

（西安邮电大学a.电子工程学院；b.计算机学院；c.研究生部，陕西 西安 710061）

点光栅化及反走样算法的研究与实现

王媛媛a，韩俊刚b，蒋 林c，张 娜a

（西安邮电大学a.电子工程学院；b.计算机学院；c.研究生部，陕西 西安 710061）

图形处理器流水线中经典的点生成算法和点反走样算法便于实现，但采样点测试的计算量大并且存在冗余测试，为此提出了多采样扫描转换算法。该算法将多采样集中在边界片元，同时，利用点区别于其他图元的对称特性，减少了采样点的冗余测试，提高了多采样时扫描转换的性能。试验结果表明：文中算法在较小代价下达到了同样的反走样性能。

点图元；光栅化；反走样；图形处理器

0 引言

图形处理器［1］（GPU）不仅是处理大量图形计算的专用处理器，而且还可以在图形处理之外的领域进行通用计算。它采用流水线结实现图形的定位（形状、位置的确定）、着色和光栅化操作。GPU流水线［2］包括：命令处理、几何变换、图元装配、投影变换、齐次化、视窗变换、扫描转换（图元光栅化和反走样）和消隐等单元。图形处理器的硬件架构经过5代发展变革［3－5］，图元光栅化始终是图形处理过程中最重要的处理单元，直接决定着图形的绘制效果和渲染质量。点图元是图元光栅化中最基本的图元之一，其绘制质量和速度直接影响GPU的性能。但由于点在光栅图形显示器的对应图形是由一系列相同亮度的像素组成，因此，绘制点时会出现锯齿状，这种用离散量表示连续量引起的失真称为走样［6］。消除这种走样现象的技术就叫做反走样。本文对点的光栅化和反走样的算法进行了研究，并用软硬件实现，其正确性已在实际应用中得到验证。

1 点光栅化以及反走样原理与逐点生成算法

1.1 未启用反走样下点光栅化

屏幕上所绘制的各种宽度的点所包含的像素集合取决于是否启用了反走样功能。如果反走样功能被禁用（默认情况），带小数点的宽度值将四舍五入为整型值，在屏幕上所绘制的是其正方形像素区域。

图1为未启用反走样时点图元的光栅化，如图1所示，像素的中心点位于图1a中的黑点位置（x，y），点的大小被定义为6.5 pixel，在未启用反走样的情况下，根据点的大小投影到屏幕上的扫描区域如图1a所示。从左下点起，根据从下向上，自左向右的扫描顺序，依次扫描得到如图1b所示的正方形绘制结果［7－8］。

1.2 启用反走样的点光栅化

如果启用了反走样功能，屏幕上绘制的就是一个圆形的像素区域。在启用了反走样功能情况下，用户使用OpenGL命令设置反走样的质量要求，根据反走样质量要求选择不同的采样频率。根据多重采样的方法对点圆求面圆各个像素所覆盖的亚像素，作为像素亮度大小。

首先，根据点的坐标确定出所要绘制的面圆的中心位置c；然后根据点的大小确定出反走样点的半径r，也就是确定采样圆域；再按照点的位置与大小计算出来点的正方形扫描区域，对正方形区域内的每个像素点，按照自下向上，由左到右的扫描顺序，判断每个像素中落在以c为中心，以r为半径的圆内的亚像素点的个数，来确定该像素的颜色强度。

图1 未启用反走样时点图元的光栅化

图2为反走样时点图元的光栅化，按照这种算法，以点的大小为6.25 pixel为例，如图2所示，图2a中的方框为扫描范围；以c为中心，以r为半径的圆域为采样范围。图2b是基于整像素采样的结果，由图2b可以看出：在边沿部分有明显的锯齿状走样现象。图2c为按照多重采样算法的渲染结果，由图2c可以看出：采用这种算法扫描出来的点在边界有明显的过度，很好地满足了反走样效果［7－8］。

图2 反走样时点图元的光栅化

2 点光栅化以及反走样改进算法

2.1 点反走样的改进算法－边界点特性

点逐像素生成反走样算法便于实现多采样［9］，但采样点测试的计算量大并且存在冗余测试。为了解决这个问题，新算法建立图元的边界盒，将所有的覆盖测试限于边界盒中。由于在图元的边界处进行扫描转换时产生锯齿，而在图元内部的片元不会产生这种走样，所以本文的多采样只在图元的边界处附近进行采样，为此提出“边界片元”［10］的概念。本文整合“边界片元”的特性，提出了“反走样边界点”的概念，由“反走样边界点”来确定3种不同片元，这种根据像素位于不同象限，用两个点来确定“边界片元“的方法节省了判定时间和运算效率。规则1～规则4阐述了对不同片元的判定和处理方法。

规则1：算法针对像素位于象限的不同，确定像素两个“反走样边界点”。“反走样边界点”定义为一个像素中离圆心最近的点和离圆心最远的点。当像素位于Ⅰ、Ⅲ象限时边界点为像素的左下角和右上角，当像素位于Ⅱ、Ⅳ象限时边界点为像素的右下角和左上角。新算法根据边界点在圆内和圆外的不同情况来确定此像素是外部片元、“边界片元”或者内部片元。内部片元指与图元重叠面积等于1片元面积的片元；“边界片元”指与图元重叠面积大于0的非内部片元；外部片元指与图元重叠面积等于0的片元，如图3所示。

规则2：片元的“反走样边界点”都在图元内部，则此片元是内部片元；片元的“反走样边界点”一个在图元内部，一个在图元外部，则此片元是“边界片元”；片元的“反走样边界点”都在图元外部，则此片元是外部片元。

规则3：内部片元所有属性按片元属性赋值，alpha值为1；外部片元不定义此片元；“边界片元”按照多采样的方式进行反走样处理。

规则4：每个像素的子像素按照从下到上，从左到右的顺序扫描，某子像素距离圆心的距离平方是：

原算法每个子像素都需要代入式（1），此种情况下浪费乘法器效率。若子像素递进大小为q，则考虑x递增q后，距离平方记为SDX1：

同理递减以及y方向亦可获得。

对于每个像素2×q×x，q×q，2×q×y值固定，即每个子像素的x、y增量都相同，每个像素只需5次乘法。Y轴增加量y_delta＝2×q×y＋q×q，X轴增加量x_delta＝2×q×x＋q×q。

根据以上规则，可将算法定义如下：

算法1，以第1象限的1／4圆为例：

输入，点大小、点属性

输出，构成点的各个像素和它的属性

步骤1：点的坐标确定出所要绘制的点圆的中心位置c，然后根据点的大小确定出反走样点的半径r，也就是确定采样圆域。

步骤2：按照点的位置与大小计算出来点的正方形扫描区，将点圆的中心和扫描区平移置坐标原点。

步骤3：从扫描区域的右上角开始按“反走样边界点”，水平从右到左对1／4点圆进行扫描，直到扫描到内部片元截止。对外部片元不处理，对边界片元按规则4进行各个子像素的扫描。当扫描到内部片元时，此内部片元到Y轴的剩余片元都按内部片元处理。

步骤4：片元垂直坐标位于零点时，扫完此行截止。

图3 图元分类表示

2.2 点反走样的改进算法－点图元对称性质

3种基本图元点、直线、三角形中，点相对直线、三角形来说有很好的对称性质，所以点的对称生成要比直线、三角形更有效。本文探讨不同坐标、不同半径情况下点的绘制，点坐标不同时点分布图见图4。通过比较，提出更节省资源的点绘制方法。

规则5：点的中心坐标分为X轴、Y轴两个方向，若X轴坐标在整数点位置上，点所占像素以圆心的X坐标轴为轴左右对称（如图4a所示）；同理若Y轴位于整数点位置上，点所占像素以圆心的Y坐标轴为轴上下对称（如图4a所示）；若X轴坐标在像素中点位置上（坐标分数为5），点所占像素以圆心所占像素为竖轴左右对称（如图4b所示）；同理若Y轴在像素中点位置上，点所占像素以圆心所占像素以横轴上下对称（如图4b所示）；其余情况下不存在像素对称画法。

根据规则3中点所占像素的对称性，可将算法分情况改进为：

情况1：X轴、Y轴坐标均在整数点位置，点圆关于圆心对称，仅需画1／4圆，其他3／4圆关于相应轴复制；扫描范围为｝，此像素按X轴和Y轴均对称复制3次。按下面存储

PutPixel（x，y，color.a.）；

PutPixel（x_another，y，color.a.）；PutPixel（x，y_another，color.a.）；

PutPixel（x_another，y_another，color.a.）。

图4 点坐标不同时点分布图

情况2：一个点中心坐标位于整数点，一个位于像素中点，扫描范围为｛ixLeft＝＜x＜xCenter，iyBottom＝＜y＜yCenter｝，仅需画1／4圆，位于像素中点的1／2行（列）像素关于Y轴左右（X轴上下）复制，其他像素按情况1所述方法复制到另外3个坐标系。

情况3：点中心坐标的一个坐标位于整数点，一个既不位于整数点也不位于像素中点，则需画1／2圆，扫描范围为｛ixLeft＝＜x＜xCenter，iyBottom＝＜y＜iyTop｝或｛ixLeft＝＜x＜ixRight，iyBottom＝＜y＜yCenter｝，像素关于X轴或Y轴对称复制。

情况4：点中心坐标的一个坐标位于像素中点，一个既不位于整数点也不位于像素中点，则需画1／2圆，扫描范围为｛ixLeft＝＜x＜xCenter，iyBottom＝＜y＜iyTop｝或｛ixLeft＝＜x＜ixRight，iyBottom＝＜y＜yCenter｝，除位于中点的一行或一列像素不复制外，其他像素关于X轴或Y轴对称复制。

情况5：两个坐标位置均不位于整数点也不位于像素中点，则扫描范围为｛ixLeft＝＜x＜ixRight，iyBottom＝＜y＜iyTop｝，不需复制，逐点扫描。

2.3 算法比较

传统的多采样方法将采样点逐个代入边界条件中进行采样测试，完全没有考虑图元对片元的覆盖情况。当图元与片元的重叠面积很小时，这种方法的计算效率很低，且这种情况随着采样点数目的增加会变得更为严重。本文算法区分各个片元，对3种不同片元采用不同的处理方法，仅对图元的边界片元进行多采样，可以有效地减少冗余测试，对外部片元采用不存储的策略，节省了存储器效率。

传统逐点生成算法是将每个采样点的坐标值代入点圆的参数方程中，根据求得的结果判断图元是否覆盖该采样点。本文算法将乘法运算用迭代来实现节省乘法器效率，同时利用不同片元的特性来减少单个片元的运算次数。表1中所示设定每个片元采样率为4×4，对两种算法中不同片元进行了运算比较，从中可以看出3种不同片元中运算次数均有减少。

表1 3种片元运算次数比较

本文算法利用圆的对称性，将圆的对称情况分为5种，针对5种情况有不同的处理，可以减少采样点数，提高算法效率。同时根据每扫描行仅需判断一个内部片元的特性来减少采样点个数。外部片元与需判断的内部片元的有效子像素个数为2，每个边界片元有效子像素为4×4。表2对5种不同情况下的点进行了有效子像素数目测试，从表2中可以看出：5种不同情况下有效子像素减少率分别为90.4%、87.7%、75.7%、77.9%和51.8%，减少的趋势是很大的，采样效率明显得到提高。

表2 采样测试的子像素数目比较

3 点光栅化以及反走样的软硬件实现

3.1 点光栅化与反走样的软件实现

采用MFC软件平台，利用流水线方式，实现点扫描与反走样。图5为软件实现结果图，分别为OpenGL实现点扫描（见图5a）、OpenGL实现点反走样（见图5b）、算法实现点扫描（见图5c），算法实现点反走样（速度快）（见图5d）、算法实现点反走样（速度慢）（见图5e）；结果表明本文算法与OpenGL实现算法实现效果相同。

图5 软件实现结果图

3.2 点光栅化与反走样的硬件实现

图6为硬件电路的整体设计，如图6所示，硬件电路模块可划分为如下模块：数据接收模块、光栅化模块、反走样模块、RAM写控制模块、双口RAM模块。其中，数据接收模块用于从外部接收点的所有相关信息，将除了坐标信息和alpha信息以外的其他信息存储于内部RAM中；并判断是否反走样将坐标信息和alpha传给反走样模块或光栅化模块。光栅化模块，未启用反走样的情况下根据点的坐标大小确定扫描范围，按照从左到右，从下到上扫描，产生各个像素的坐标。反走样模块包括反走样数据处理模块和覆盖率模块。扫描模块主要确定扫描范围，且根据覆盖率产生各个新的alpha值，并将像素信息输出；覆盖率模块根据speed信号判断覆盖率计算划分子像素个数，统计在圆内子像素个数占总的子像素的比率即可。RAM写控制模块，通过此模块控制3个模块有序的向RAM内写数据。双口RAM模块，用于存储点的各个像素信息。

图6 硬件电路的整体设计

4 结论

本文首先对现有一些绘制点的算法进行了分析及总结，然后基于减少冗余点测试和点的对称性提出了新的点绘制算法，此算法对各个片元和各种不同的点采用了不同的处理方法，在较小的代价下实现了点的扫描和反走样，且本算法适合于硬件实现。FPGA验证结果表明：本设计能够实时准确地完成点的光栅化。综合结果显示：该设计很适合集成到移动设备的GPU系统中。进一步工作是对各个片元进行自适应多采样处理，通过增减各级处理单元来平衡流水线中各级并行度，进一步提高系统的性能。

［1］ 韩俊刚，蒋林，杜慧敏，等.一种图形加速器和着色器的体系结构［J］.计算机辅助设计与图形学学报，2010（3）：363－372.

［2］ Angel E.Interactive Computer Graphics：A Top-Down Approach Using OpenGL［M］.5 ed.Boston：Addison Wesley，2008.

［3］ Harris M.Mapping Computational Concepts to GPUs［C］／／Los Angeles：Annual Conference Series，ACM SIGGRAPH. 2005.

［4］ 张浩，李利军，林岚，等.GPU的通用计算应用研究［J］.计算机与数字工程，2005，33（12）：60－61.

［5］ 丁鹏，陈利学，龚捷，等.GPU通用计算研究［J］.计算机与现代化，2010（1）：12－15.

［6］ Zhang J X，Luo L，Jiang F.Rendering Optimization to Rich Media Scenes on Mobile Devices［J］.Journal of Computer-Aided Design＆Computer Graphics，2010，22（8）：1272－1278.

［7］ Dave S，Mason W，Jackie N，et al.Opengl编程指南［M］.北京：机械工业出版社，2008：26－35.

［8］ Richard S，Wright J，Benjamin L.OpenGL超级宝典［M］.4版.北京：人民邮电出版社，2005：8.

［9］ Schwarz M，Stamminger M.Multisampled Antialiasing of Per-pixel Geometry［C］.Proceedings of Eurographics.2009：21－24.

［10］ 韩俊刚，殷诚信，曹小鹏.自适应多采样扫描转换算法［J］.计算机辅助设计与图形学学报，2012，24（4）：451－458.

TP302

A

1672－6871（2014）04－0043－06

国家自然科学基金重点项目（61136002）

王媛媛（1986－），女，河南洛阳人，硕士生；韩俊刚（1943－），男，吉林长春人，教授，博士生导师，主要研究方向为专用集成电路设计和图形学.

2012－06－03