计算机图形学-反走样设计与实现.doc

计算机图形学
反走样设计与实现
学 生 董庆洋
班 级 2012级四班
反走样设计与实现
董庆洋
摘 要：图形图像技术是现代社会信息化的重要技术，而走样却是数字化表示图形图像的必然产物。为了提高图形的显示质量，需要减少或消除走样现象，用于减少或消除这种效果的技术称为反走样。消除或减缓走样现象，给人视觉上产生更舒适光滑的图形，在图形界面已成为人机交互主流方式的今天，具有一定的应用价值.本文介绍了几种常用的反走样方法，主要有:提高分辨率来显示图形对象、区域采样、加权区域采样以及改进的反走样方法：Wu像素反走样。
关键词：走样;反走样;过取样;区域取样;加权区域取样；Wu像素反走样
1。引入走样与反走样
光栅图形显示器是目前使用最广泛的图形显示器，因为它具有以下优点：光栅扫描显示器具有固定的刷新顺序，扫描从屏幕的左上角开始，从左到右，从上到下的顺序进行刷新，从而刷新控制部件得以简化，节约了成本。在光栅显示系统中，构成图形的最小图形元素是像素，这样只要计算屏幕上位于给定区域以内的所有像素,并且赋予一定的颜色，就完成了图形的绘制.光栅显示器中的图形由像素构成,而每一个像素又可呈现出多级灰度或不同的颜色值，颜色丰富，显示出来的图形具有更好的视觉效果。光栅扫描显示器是一个画点设备，与图形的复杂度无关，刷新频率固定,因此不会像随机扫描显示器那样出现闪烁现象，人眼看上去更舒服.但光栅显示器也有它的缺陷，数学意义上的图形是由无线多个连续的、面积为零的点构成，而光栅显示系统中用来表示图形的却是一个个离散的,具有一定面积的像素。用离散的像素来表示连续的图形时会出现失真，也就称为走样。
光栅显示系统为何会出现走样呢？光栅图形显示器上被显示的线段、字符、图形及背景色都按像素点一一存储在帧缓冲存储器中。当我们要画一条直线时，它通常不可能完全精确地从一个可编址的像素点画一条直线到另一个可编址的像素点，只可能用尽可能靠近这条直线路径的像素点集来近似地表示这条直线.显然只有画水平线、垂直线时，像素点集在直线路径上的位置才是准确的，其他情况下的直线均或多或少地存在阶梯状(锯齿状）的现象。光栅图形的走样现象除了上述锯齿状边界外,还有图形细节失真，狭小图形遗失等现象。为了提高图形的显示质量，需要减少或消除走样现象，这种用于减少或消除走样现象的技术称为反走样技术。
2.实现反走样技术的一些方法
2.1 过取样技术
一种简单的反走样方法是以较高的分辨率显示对象，如图1。假设把显示器分辨率提高一倍，直线经过两倍的像素，锯齿也增加一倍,但同时每个阶梯的宽度也减小了一倍,所以显示出的直线段看起来就平直光滑了一些。这种反走样方法是以4倍的存储器代价和扫描转换时间获得的.因此，增加分辨率虽然简单,但是不经济的方法,而且它也只能减轻而不能消除锯齿问题。但是它的思想给我们以后的反走样方法一定的启示。
图1 分辨率提高一倍,阶梯程度减小一倍
一种可行的反走样方法：在较高分辨率下用点取样方法计算,然后对几个像素的属性进行平均得到较低分辨率下的像素属性，这种技术称为过取样（Supersampling），或后滤波（Postfiltering）。该技术是把显示器看成是比实际更细的网格来增加取样率,然后根据这种更细的网格使用取样点来确定每个屏幕像素合适的亮度等级。
2.1.1 提高分辨率方法
过取样方式的一个简单实现是用较高的分辨率进行计算，如图2，在x方向和y 方向上把分辨率提高一倍,使每个像素都对应4个子像素，然后扫描转换求得各子像素的颜色亮度，再对4个像素的颜色亮度进行平均,得到较低分辨率下的像素颜色亮度。由于像素中可供选择的子像素最大数目是4，因此，该例中提供的亮度等级数是5。图中，编号为1和7的像素亮度级别是1，编号为2,3，4，5和6的像素亮度是2。通过这个方法为图中的每个像素设定不同的灰度值，可以使显示出来的直线看起来平滑一些，达到减少走样现象。
图2 简单的过取样方式
2。1。2 基于加权模板的过取样
另一种过取样方式（重叠过取样）。为了得到更好的效果，在对一个像素点进行着色处理时，不仅仅只对其本身的子像素进行采样，同时对其周围的多个像素的子像素进行采样，来计算该点的颜色属性。如图3所示。
由于接近像素区域中心的子像素在决定像素的颜色亮度值中发挥着重要的作用，因此过取样算法中采用了加权平均的方法来计算显示像素的颜色亮度值(基于加权模板的过取样）。图4示出了3×3像素分割常采用的加权模板。中心子像素的权是角子像素的4倍，是其他子像素的2倍，中心子像素的加权系数是1/4，顶部和底部及两侧子像素的加权系数是1/8，而角子像素的加权系数是1/16。
图3 重叠过取样
图4 常用的加权模板
2。1。3 过取样算法的实现
对于过取样，不管用哪一种方法都需要在内存中建立一个比现在大几倍的图，便于对像素取样，取得像素的亮度值。具体实现的算法如下:
void SuperSamplingLine（int xa， int ya， int xb, int yb,boolean Weighted）
｛   int dx = xb-xa+1,
      dy = yb-ya+1，
      x,y,xs，ys，i，j，s，
      w[3][3]=  ｛1,2，1,
                2,4,2，
                1,2,1｝；
   BYTE gray;
Graphics:：TBitmap * big_bmp;
   big_bmp = new Graphics::TBitmap（);
   big_bmp->Width = 3*dx;
   big_bmp—〉Height = 3*dy;
   //设置白底色
   big_bmp-〉Canvas—>Brush->Color = clWhite;
   big_bmp->Canvas—〉FillRect(big_bmp—>Canvas—〉ClipRect);
   big_bmp->Canvas-〉Refresh（)；
   //设置绿笔
   big_bmp—〉Canvas-〉Pen-〉Color = clGreen；
   big_bmp-〉Canvas->MoveTo(1，1)；
   big_bmp—〉Canvas-〉LineTo（3*dx—1,3＊dy—1)；
   for (x=xa；x〈=xb；x++) ｛
      xs = 3＊（x-xa）；
      for (y=ya；y〈=yb;y++) ｛
          ys = 3*（y—ya）；
          s = 0;
       for （i=xs;iCanvas-〉Pixels［i][j]==clGreen） ｛
             if （Weighted）
               s=s+w［i—xs］［j-ys];
             else s++；
           ｝
       if (Weighted)
         gray = （BYTE)（255.0 — s*(255.0/8.0））;
       else
         gray = (BYTE）(255。0-s*(255.0/3.0）);
       Form1—〉Image2-〉Canvas—>Pixels［x][y］=RGB(gray，gray,gray)；
     }
   }
｝
2。2 区域取样
2.2。1 简单的区域取样
在整个像素区域内进行采样的技术称为区域取样，又由于像素的亮度是作为一个整体被确定的,不需要划分子像素，故也被称为前置滤波。
直线段扫描转换算法中均假定像素是数学上的一个点,像素颜色是由对应于像素中心的图形中一点的颜色决定的；并且直线段是数学上抽象的直线段,它的宽度是0.但实际上像素不是一个点，而是一个有限区域。屏幕上所画的直线不是数学意义上的无宽度的理想线段，而是一个宽度至少为一个像素单位的线条。因此，将屏幕上的直线段看成如图5中显示的矩形更为合理。算法中所假定的条件和实际情况之间的差距是造成走样的原因之一.为了减少走样，必须改变直线段的模型，从而得到了简单区域取样的方法,这个方法的具体步骤是：
1）将直线看成具有一定宽度的狭小矩形；

2)当直线与像素相交时,求出两者相交区域的面积；
3）根据相交区域的面积，确定像素的亮度值；相交面积大的像素亮度高,相交面积小的像素亮度低。
图5 有宽度的直线段
这种方法将产生模糊的边界,以此来减轻锯齿效应。在图5中，像素1约有40﹪被线条区域覆盖，因此该像素的亮度就设置为线条亮度的40﹪。同样，像素2的亮度设置为线条亮度的60﹪，而像素3的亮度则设置为线条亮度的90﹪，等等.对于图5中宽度线段的任何一个像素而言,其面积S是介于0--1之间的正数,用它乘以像素的最大光强为Imax,则该像素的光强I=S×Imax.区域取样中，起关键作用的是直线段与像素相交区域的面积。这个面积可根据直线的斜率K和直线的精确起点位置求出。如图6中（a）所示情况为例,如果已知直线的精确起点，则可得到图中的D值，利用D和直线斜率K可以得到相交区域的面积：1／2×D×(D/K）=（D×D)/(2×K).同样，可以计算出（b)中重叠区域的面积。
图6 重叠区域面积的计算
在OpenGL中实现这种算法，现在利用改进后的Bresenham反走样画线算法，如下：
　BresenhamAntialiasingLine(int x1, int y1， int x2， int y2，int I）
　// （x1， y1),（x2， y2）分别是直线的起点和终点
　// I是画线的最大亮度值
　{
　　int x，y，dx，dy,m,w,e；
　　x = x1；
　　y = y1;
　　dx = x2－x1；
　　dy = y2－y1;
　　m = I＊dy/dx;
　　w = I－m;
　　e = I/2；
　　SetPixel(x,y,m/2）;
　　while （x < x2)
　　｛
　　　if (e 〈 w）
　　　{
　　　　　x ++;
　　　　　e += m;
　　　｝
　　　else
　　　｛
　　　　x ++；
　　　　y++;
　　　　e —= m;
　　　}
　　　SetPixel（x，y,e）；
　　｝
　}
为了简化计算，可以利用一种求相交区域近似面积的离散计算方法：
1）将屏幕像素分割成n个更小的子像素，
2)计算中心落在直线段内的子像素的个数m，
3） m/n为线段与像素相交区域面积的近似值。
这种简单的区域采样也称为非加权区域采样，这种方法有两个缺点：①像素的亮度与相交区域的面积成正比,而与相交区域落在象素内的位置无关,这仍然会导致锯齿效应。②直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差.为了克服这样的缺点,可以采用加权区域采样方法，使相交区域对象素亮度的贡献依赖于该区域与象素中心的距离。
2。2.2 加权区域采样
在区域取样中,我们使用覆盖像素的连续的加权函数（Weighting Function）或滤波函数（Filtering Function）来确定像素的亮度。
加权函数W（x，y)是定义在二维显示平面上的函数.对于位置为（x，y）的小区域dA来说，函数值W(x，y)（也称为在(x,y)处的高度）表示小区域dA的权值。将加权函数在整个二维显示图形上积分，得到具有一定体积的滤波器(Filter），该滤波器的体积为1。将加权函数在显示图形上进行积分，得到滤波器的一个子体，该子体的体积介于0到1之间。用它来表示像素的亮度.如图7所示的盒式滤波器：
图7 盒式滤波器的加权区域取样
除了盒式滤波器外,常用的滤波器还有圆锥滤波器和高斯滤波器（如图8所示）。滤波器的底可以具有不同的大小，类似于过取样加权模板的大小，但是为了获得较好的效果，盒式滤波器的底常取作边长为像素单位整数倍的正方形，而圆锥滤波器和高斯滤波器的底则是半径为像素单位整数倍的圆。
图8 常用的滤波函数
这种加权区域采样的特点是：①接近理想直线的象素将被分配更多的灰度值。 ②相邻两个象素的滤波器相交，有利于缩小直线条上相邻象素的灰度差。
2.3 反走样算法的改进
通常的整数画线因为只能在整数坐标上绘图，所以产生难看的锯齿。因此,我们可以用一种非整数坐标改进它，Wu像素反走样就是一种可以处理非整数坐标的方法。Wu像素的绘制原理是:
1）绘制多个像素代替一个像素
2）理论点位置不一定在屏幕像素的正中,这个偏差是我们按偏差的比例来绘制多个像素来代替理论像素的根据。
3）绘制的多个像素灰度和要于原像素相等。
一个WU直线不仅仅是看上去比一个普通直线好,它也产生更好的动画。一个普通的直线从一个位置简单的跳到下一个位置.然而，一条Wu直线非常悠闲的漂到下一个位置，最终的算法相当容易实现，但是在实际应用中显得太慢.因此,还有待于改进。
3。总结
在分析讨论了反走样理论知识的基础上，本论文实现了普通过取样、加权过取样、普通区域取样、加权区域取样、Wu像素反走样算法。即：在高于显示分辨率的较高分辨率下用点取样方法计算，然后对几个象素的属性进行平均得到较低分辨率下的象素属性的技术称为过取样,或后滤波；在整个像素区域内进行采样的技术称为区域取样，这种技术由于像素的亮度是作为一个整体被确定的,不需要划分子像素，故也被称为前置滤波;而加权区域取样技术是基于这两种技术之上：过取样中，我们对所有子像素的亮度进行简单平均或加权平均来确定像素的亮度；在区域取样中，我们使用覆盖像素的连续的加权函数（Weighting Function）或滤波函数（Filtering Function）来确定像素的亮度.对于这几种反走样方法的比较：过取样是在较高分辨率下用点取样方法计算,然后对几个像素的属性进行平均得到较低分辨率下的像素属性.由于是对每个像素进行平均值计算，因此速度明显慢了很多。普通区域取样是将直线看成具有一定宽度的狭小矩形,当直线与像素相交时，求出两者相交区域的面积，然后确定像素的亮度值,达到反走样效果。区域取样的速度要比过取样快得多，不过从效果上来讲,还是过取样的视觉效果更好，更平滑.但由于这些方法画线只能在整数坐标上绘图，会产生难看的锯齿，我们又可以选在非整数坐标上绘图的方法-—Wu像素反走样。因此,在实际应用中要根据需要来选取不同的反走样算法。
参考文献：
［1] 计算机图形学基础/陆枫，何云峰编著 ——2版 -—北京：电子工业出版社；2008.10
高等学校规划教材
[2］ 常进；OpenGL机载图形生成算法研究[D]；上海交通大学；2007年
［3] 罗振东，计算机图示学原理和方法,1993年
［4] 刘建国,张晔；Bresenham曲线但走样算法[J]；计算机与现代化；2005年02期
[5］ 李震霄，何援军;任意宽度直线的绘制与反走样[J]；武汉大学学报（工学版）；2006年04期
［6］ 章立亮,周琼，光栅图形反走样的加权区域采样算法；期刊 宁德师专学报(自然科学版）；2002年 第01期
［7］ 工宁平；光栅显示图形中直线反走样技术算法的改进；期刊-核心期刊 哈尔滨理工大学学报；2008年 第03期
7