毕业设计（论文）-反走样技术的研究与实现说明书.doc

杭州师范学院本科毕业论文反走样技术的研究与实现反走样技术的研究与实现说明书论文目 录摘要iAbstract i第一章 引言11.1研究背景11.2 编程实验环境2第二章 反走样概述52.1 过取样技术52.2 区域取样72.3 WU像素反走样122.4点取样142.5象素移相14第三章 反走样算法的改进153.1 多段直线反走样算法153.2 圆反走样算法 18 3.3位图反走样19第四章 总结与展望23 4.1总结234.2进一步改进设想23参考文献25第一章 引 言1.1研究背景光栅图形显示器是目前使用最广泛的图形显示器，因为它具有以下优点：光栅扫描显示器具有固定的刷新顺序，扫描从屏幕的左上角开始，从左到右，从上到下的顺序进行刷新，从而刷新控制部件得以简化，节约了成本。在光栅显示系统中，构成图形的最小图形元素是像素，这样只要计算屏幕上位于给定区域以内的所有像素，并且赋予一定的颜色，就完成了图形的绘制。光栅显示器中的图形由像素构成，而每一个像素又可呈现出多级灰度或不同的颜色值，颜色丰富，显示出来的图形具有更好的视觉效果。光栅扫描显示器是一个画点设备，与图形的复杂度无关，刷新频率固定，因此不会象随机扫描显示器那样出现闪烁现象，人眼看上去更舒服。但光栅显示器也有它的缺陷，图形信号是连续的，而光栅显示系统中用来表示图形的却是一个个离散的像素。用离散的像素来表示连续的图形时会出现失真，也就称为走样，如图1.1所示。图1.1锯齿状边界光栅显示系统为何会出现走样呢？光栅图形显示器是一个画点设备，被显示的线段、字符、图形及背景色都按像素点一一存储在帧缓冲存储器中。当我们要画一条直线时，它通常不可能完全精确地从一个可编址的像素点画一条直线到另一个可编址的像素点，只可能用尽可能靠近这条直线路径的像素点集来近似地表示这条直线。显然只有画水平线、垂直线时，像素点集在直线路径上的位置才是准确的，其他情况下的直线均或多或少地存在阶梯状（锯齿状）的现象。光栅图形的走样现象除了上述锯齿状边界外，还有图形细节失真，狭小图形遗失等现象。 图1.2 图形细节失真在光栅显示器上显示如图1.2(a)所示的细长矩形时，出现了图形细节失真，其结果如图1.2(b)所示，原细长的矩形被显示成了加宽的矩形。图1.3 狭小图形的遗失由于光栅系统中表示图形的最小单位是一个像素，图形中那些比像素更窄的细节丢失了，这就出现了图形细节失真现象。在图1.3中，一些狭小的图形分布在两条扫描线之间，由于它不覆盖任何一个像素中心，故不会被显示出来。当这些狭小的图形进行运动时，覆盖像素中心时被显示出来，不覆盖像素中心时不被显示出来。这样在运动的过程中时隐时现，产生闪烁。为了提高图形的显示质量，需要减少或消除上述走样现象。用于减少或消除这种走样现象的技术，称为反走样（Antialiasing）。研究如何消除或减缓这类走样现象，给人视觉上产生更舒适光滑的图形，在图形界面已成为人机交互主流方式的今天，具有一定的应用价值。 反走样技术能提高图形的显示质量，因此在很多画图软件中也采用了这种技术。优软电脑有限公司设计推出的新一代绘画程序-优软精灵画笔2.0，在原有的各种绘画功能上，添加了一系列全新设计的绘画工具；可以打开外来JPG，TAG，TIFF，GIF，BMP文件；更新三维立体窗口系统；对压力感应笔高效率支持，速度和流畅度达到专业软件水准，让用户的体会更加细腻逼真。它的精妙之处在于具有细笔尖反走样功能，所以使细笔画更细致更漂亮。 反走样技术不仅能提高图形显示质量,而且在反走样汉字方面也有很好的效果。由于汉字的笔画很多,而且大多数非水平非垂直,也会产生较严重的走样现象。图1.4中第1 个字为追踪出的轮廓,第2 个为显示的原始矢量字符。第3 个为反走样处理后的矢量字符。图1.4矢量字体轮廓的反走样由此可见，反走样技术在实际应用中有十分重要的意义。另外, 在处理纹理图形, 以及在动画中闪烁的细小物体图形等问题中反走样技术都得到了广泛运用。1.2 编程实验环境 本文采用的实验环境的是C+ Builder 6。C+ Builder由著名的Borland公司开发，是Windows环境下功能强大的可视化C+开发环境，它全面实现了ANSIC+标准，并提供了自己的扩展，并且兼容PC计算机上的两种最常用的C+编译器，即BorlandC+和VisualC+。Borland C+和VisualC+的程序几乎不用做任何修改，就可以在C+ Builder下编译、运行。下面主要介绍在论文中使用最频繁的、与图形图象处理密切相关的组件及其属性和方法。1.2.1 TColor在计算机图形处理软件中，通常颜色是根据红、绿、蓝三种颜色的饱和度来定义的，这种模型称为RGB模型。任何颜色都是红、绿、蓝三种基本色的不同组合组成，因此每种颜色都可以用红、绿、蓝基本色来表示。Red、Green、Blue用来表示基本色构成的三个分量，他们的取值为0-255，最小值表示没有颜色，最大值255表示最高的饱和度。 TColor类型用于定义一个对象的颜色，很多组件的颜色属性就是TColor类型。同时C+ Builder定义了一些常用的颜色常量，可在程序中直接使用。比如clRed，clGreen等。1.2.2 TCanvas在C+ Builder中提供了一个TCanvas对象，它封装了Windows应用程序在图形输出方面所需要的大多数GDI对象和绘图命令。在这个区域上，程序可实现各种绘图功能，很多图形组件（如TImage、TPaintBox）的画布（Canvas）属性都是一个TCanvas对象。 TCanvas的属性和方法很多，最常用的有：l TCanvas的属性(1)Pixels属性 Canvas的Pixels属性可以用来去顶像素的颜色。可以利用Pixels属性来获得某一点的颜色值，也可以通过它来设置某一点的颜色值，这个属性在反走样算法中起了相当重要的作用。 如要获得坐标（20，20）的颜色值，可以使用下面的代码： TColor Color; Color=Canvas-Pixels2020；如果要将坐标点（10，20）的颜色设置为红色，可以使用如下代码：Canvas-Pixels1020=clRed；(2)画笔属性 TCanvas的画笔（Pen）属性是一个TPen对象。在用画布划线的时候，需要设置画笔的属性。对每一个画笔均可以选择不同的宽度，颜色，线型。我的论文中用到了颜色（Color）属性。 该属性用于控制线的颜色，可以使用预定义的颜色或设置自己的颜色，例如： Canvas-Pen-Color=clBlue； Canvas-Pen-Color=TColor (RGB(125,0,0)；(3)画刷属性 Canvas的画刷（Brush）属性是一个TBrush对象，它封装了标准的Windows刷子对象。画刷可以利用颜色和图案来填充矩形、多边形和圆等。使用画刷的Color属性可以设置画刷的颜色，默认的画刷颜色是clWhite。例如： Canvas-Brush-Color=clRed；这个属性在清屏方法起着主要作用。(4)ClipRect属性 ClipRect属性用于定义一个画图的矩形区域.在定义了一个剪切区域后,即使画的图形大于这个ClipRect,也不会画到这个区域的外面,同时FillRect属性可以用来填充矩形区域的颜色。l TCanvas的方法 (1)画直线 绘制直线涉及到两个方法：MoveTo和LineTo。MoveTo（int startx,int starty）的任务是设置当前画笔的位置到（startx,starty），而不进行任何绘图工作。然后可以调用LineTo（int endx，int endy）来画直线。它从当前画笔的位置画一条直线到点（endx，endy），并将当前的画笔位置改变为（endx，endy）。 （2）画椭圆弧线绘制椭圆弧线的方法比绘制直线方法要复杂一些。下面是最基本的椭圆弧线绘制函数：Arc(int X1, int Y1, int X2, int Y2, int X3, int Y3, int X4, int Y4);Arc方法画一段椭圆弧，椭圆由（X1，Y1），（X2，Y2）两点所确定的矩形所决定。弧的起点是椭圆圆周和椭圆中心与（X3，Y3）连线的交点。弧的终点是椭圆圆周和椭圆中心与（X4，Y4）连线的交点，以逆时针方向画弧。在位图的反走样算法中所画的弧线都是由该函数实现的。 （3）绘制矩形 Rectangle的具体形式如下：Rectangle（int X1, int Y1, int X2, int Y2）; Rectangle方法是在画布上用当前画刷绘制矩形，其中（X1，Y1）是矩形的左上角，（X2，Y2）是矩形的右下角。如果设置Brush的Style模式为bsClear,则可以绘制未填充的矩形。同时在论文中经常会用到清屏这个功能，它就是调用了FillRect方法，它是用指定的画刷填充矩形，并且绘制的矩形没有边框。具体形式如下：FillRect（const windows:TRect &Rect）; 第二章 反走样技术概述在光栅显示器上显示图形时，直线段或图形边界或多或少会呈锯齿状。原因是图形信号是连续的，而在光栅显示系统中，用来表示图形的却是一个个离散的象素。这种用离散量表示连续量引起的失真现象称之为走样(aliasing)，走样是伴随着光栅显示系统而出现的，也是数字化的必然产物。用于减少或消除这种效果的技术称为反走样(antialiasing)。第一章中已经介绍了光栅图形的走样现象除了阶梯状的边界外，还有图形细节失真(图形中的那些比象素更窄的细节变宽)，狭小图形遗失等现象。常用的反走样方法主要有：提高分辨率、区域采样和加权区域采样等。下面将对他们进行介绍。2.1 过取样技术反走样的方法很多，一种简单的反走样方法是以较高的分辨率显示对象，如图2.1。假设把显示器分辨率提高一倍，直线经过两倍的象素，锯齿也增加一倍，但同时每个阶梯的宽度也减小了一倍，所以显示出的直线段看起来就平直光滑了一些。这种反走样方法是以4倍的存储器代价和扫描转换时间获得的。因此，增加分辨率虽然简单，但是不经济的方法，而且它也只能减轻而不能消除锯齿问题。但是它的思想给我们以后的反走样方法一定的启示。 图2.1 提高显示分辨率一种可行的反走样方法：在较高分辨率下用点取样方法计算，然后对几个像素的属性进行平均得到较低分辨率下的像素属性。这种技术称为过取样（Supersampling），或后滤波（Postfiltering）。该技术是把显示器看成是比实际更细的网格来增加取样率，然后根据这种更细的网格使用取样点来确定每个屏幕像素合适的亮度等级。 反走样的另一种方法是根据图形对象在每个像素点上的覆盖程度率来确定像素点的亮度，这种计算覆盖率的反走样技术称为区域取样（Area Sampling），或前滤波（Prefiltering）。2.1.1 提高分辨率方法过取样方式的一个简单实现是用较高的分辨率进行计算，如图2.2，在x方向和y 方向上把分辨率提高一倍，使每个像素都对应4个子像素，然后扫描转换求得各子像素的颜色亮度，在对4个像素的颜色亮度进行平均，得到较低分辨率下的像素颜色亮度。由于像素中可供选择的子像素最大数目是4，因此，该例中提供的亮度等级数是5。如图2.2中，编号为1和7的像素亮度级别是1，编号为2，3，4，5和6的像素亮度是2。通过这个方法为图中的每个像素设定不同的灰度值，可以使显示出来的直线看起来平滑一些，达到减少走样现象。6753412图2.2 简单的过取样方式2.1.2基于加权模板的过取样另一种过取样方式（重叠过取样），如图2.3，假设显示器分辨率为m*n，其中m=4，n=3，首先把显示窗口划分为（2m+1）*（2n+1）个像素，然后通过扫描转换求得各子像素的颜色值，在对为于子像素中心及四周的9个子像素的颜色值进行平均，最后得到显示像素的颜色亮度值。 由于接近像素区域中心的子像素在决定像素的颜色亮度值中发挥着重要的作用，因此过取样算法中采用了加权平均的方法来计算显示像素的颜色亮度值（基于加权模板的过取样）。图2.4示出了3*3像素分割常采用的加权模板。中心子像素的权是角子像素的4倍，是其他子像素的2倍，中心子像素的加权系数是1/4，顶部和底部及两侧子像素的加权系数是1/8，而角子像素的加权系数是1/16。000000000000121242121图2.3 另一种过取样方式图 2.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, w33= 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;ixs+3;i+) for (j=ys;jCanvas-Pixelsij=clGreen) if (Weighted) s=s+wi-xsj-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-Pixelsxy=RGB(gray,gray,gray); 2.2区域取样2.2.1简单的区域取样直线段扫描转换算法均假定像素是数学上的一个点，像素颜色是由对应于像素中心的图形中一点的颜色决定的；并且直线段是数学上抽象的直线段，它的宽度是0。但实际上像素不是一个点，而是一个有限区域。屏幕上所画的直线不是数学意义上的无宽度的理想线段，而是一个宽度至少为一个像素单位的线条。算法中所假定的条件和实际情况之间的差距是造成走样的原因之一。为了减少走样，必须改变直线段的模型，从而得到了简单区域取样的方法，这个方法的具体步骤是：（1）将直线看成具有一定宽度的狭小矩形；（2）当直线与像素相交时，求出两者相交区域的面积；（3）根据相交区域的面积，确定像素的亮度值； 图2.5 具有一定宽度的直线 图2.6 灰度与面积成比例通过将每个像素亮度设置成与线条部分重叠的区域面积成正比，可以完成对直线的区域取样。若一个像素与线条部分重叠，根据重叠区域面积的大小来选择不同的灰度。重叠面积大的像素黑一点，重叠面积小的像素白一点。这种方法将产生模糊的边界，以次来减轻锯齿效应。图2.5是待显示的直线段，图2.6是采用简单区域取样方法绘制的结果。这个方法中，起关键作用的是直线段与像素相交区域面积的计算。那么相交区域如何计算呢？假设一条直线的斜率是m，若规定它的显示宽度是一个像素，那么直线和像素的相交有如下三种情况，如图所示。其中（c）的计算可转化为正方形面积减去两个三角形面积。接下来介绍（a）和（b）两种情况。 （a） （b） （c）图2.7 直线段与像素相交的三种情况在图2.7（a）中，假设三角形x方向上的边长为D，则y方向上的边长为mD，从而三角形的面积为. 在图2.7（b）中，假设梯形左底边长为D，则右底边长为D-m，从而梯形的面积为；所得到的面积介于0，1之间的实数，用它乘以像素的最大灰度值，即可得到像素实际显示的灰度值。上面的计算十分的麻烦，为了简化计算，可以采用下面的离散方法：（见图2.8）（1）将屏幕像素分割成n个更小的子像素；（2）计算中心点落在直线内的子像素的个数，记为k；（3）k/n为线段与像素相交区域的近似值 ；图2.8 n=16，k=3，近似面积为3/16综上所述，非加权区域采样方法具有下面三条性质：（1）直线对一个像素亮度的贡献与两者相交区域的面积成正比，从而和直线与像素中心点的距离成反比。因为直线距像素中心越远，相交区域的面积越小。（2）当直线和一个像素不相交时，它对该像素的亮度没有影响。（3）相同面积的相交区域对像素的亮度贡献相同，而与这个相交区域落在像素内什么位置无关。2.2.2 加权区域取样简单区域取样由于相同面积重叠区域对像素的贡献相同，但是这样仍然会出现走样现象，接下来介绍的加权区域取样对此进行了改善，使得相交区域对像素亮度的贡献依赖于该区域与像素中心的距离。对于相同面积的相交区域，当它距离像素中心近时，它对像素亮度的贡献大，当它距离像素中心远时，对像素亮度贡献小。这种方法更符合人的视觉系统对图象信息的处理方式。 加权区域取样的特点：一是接近理想直线的像素将被分配更多的灰度值；二是相邻两个像素的滤波器相交，所以直线条经过该相交区域时，将对这两个像素都分配给适当的灰度值，这样就缩小了直线条上相邻像素的灰度差。 加权区域取样方法的具体步骤如下：（1）求直线段与过滤器底面的重叠区域S。（2）计算 的值，其中f（x，y）是过滤函数，S是过滤器的底面，且有 =1 。（3）上面得到的值介于0和1之间，用它乘以像素的最大灰度值，即得到该像素显示灰度值。求积分的运算量是很大的，为了方便计算，可以利用加权区域取样的离散计算方法： （1）将屏幕像素均匀分割成n个子像素，Siin=1，则每个子像素的面积为 ，计算每个子像素对原像素亮度的贡献， 将fi=1保存在加权表中。 （2）求出所有中心落在直线段内的子像素的集合F。 （3）计算所有这些子像素对原像素亮度的贡献之和。该值乘以像素的最大灰度值即为像素的显示灰度值。根据上面的讨论，fi是一个经验值，因此我们可以根据经验直接设定fi的值。例如，我们将屏幕像素划分为n=3*3=9个子像素，加权表可取作 2.2.3简单区域取样算法的实现 有些反走样方法把像素当作是数学上的一个点，像素颜色是由对应于像素中心的图形中一点的颜色决定的；而区域取样认为像素不是一个点，而是一个有面积的区域,因此我们在区域取样时要计算直线段与像素相交区域的面积,然后根据相交区域面积来确定像素的亮度值。由于直线与像素相交的形式有三种，那么我们如何来判断直线与像素相交的形式呢？图2.9 区域取样示意图如图2.9所示，设直线段与某像素纵列相交区域下顶点的y坐标为yl，m为该直线的斜率，y5是扫描线y+0.5。如果yl+my5，则说明直线和像素的相交区域是由上中下三个相邻像素中的两个三角形和一个四边形组成，否则相交区域是由上下两个相邻像素中的两个梯形组成。然后计算出相交区域的面积就可以得到每个像素的亮度，从而达到反走样直线，而且反走样的效果也十分的好。综上所述，实现的算法如下： void AreaSamplingLine(int xa, int ya, int xb, int yb)/将直线段的宽度理解为一个像素的宽度 float m,b, / 设直线方程为： y = mx + b l, / 直线段框与某像素纵列相交区域（平行四边形）的纵向边长 yl, / 直线段框与某像素纵列相交区域（平行四边形）下顶点的y坐标 y5, / 扫描线y+0.5 xl, / 直线段框与y-0.5线的交点 xu, / 直线段框与y+0.5线的交点 sl, / 下方像素中的三角形（或梯形）的面积 su; / 上方像素中的三角形面积 boolean is3part; int x; m = (float)(yb-ya)/(xb-xa); / 直线的斜率 b = ya-m*xa; / 截距 l = sqrt(1+m*m); /既是纵向边长，也是平行四边形的面积 xl = (ya-0.5-b+l/2)/m; /xl的初值 xu = (ya+0.5-b-l/2)/m; /xu的初值 yl = m*(xa-0.5) + b - l/2; /yl的初值 PutPixel(xa,ya,127); y5 = ya + 0.5; for ( x=xa+1;x y5) /相交区域由上中下三个相邻像素中的两个三角形和一个四边形组成 is3part = true;/计算下方像素中的三角形面积sl ，并设置像素的亮度 sl = 0.5*(y5-yl)*(xl-x+0.5); PutPixel(x,(int)(y5-0.499),(int)(255-255*sl); /计算上方像素中的三角形面积su，并设置像素的亮度 su = 0.5*(yl+m+l-y5-1)*(x+0.5-xu); PutPixel(x,(int)(y5+1.501),(int)(255-255*su); /中间像素的四边形面积就是平行四边形面积减去sl，su，并设置像素的亮度 PutPixel(x,(int)(y5+0.501),(int)(255-255*(l-su-sl); else /相交区域由上下两个相邻像素中的两个梯形组成 is3part = false; /计算下方像素中梯形的面积，并设置像素亮度 sl = 0.5*(y5-yl+y5-(yl+m); PutPixel(x,(int)(y5-0.499),(int)(255-255*sl); /计算上方像素中梯形的面积就是平行四边形面积减去sl，并设置像素亮度 PutPixel(x,(int)(y5+0.501),(int)(255-255*(l-sl) ); if (is3part) y5+; PutPixel(xb,yb,127); Form1-Image1-Refresh(); 本算法通过计算相交区域面积来设置像素的亮度从而达到反走样直线的效果，实现的速度明显比普通过取样和加权过取样要快的多，平滑直线的视觉效果也非常的好。2.3 WU像素反走样2.3.1 WU反走样普通的Breshenham算法画线很快,但并不是很精细.通常的整数画线因为只能在整数坐标上绘图,所以产生难看的锯齿.介绍的WU像素反走样算法就采用了非整数坐标改进它,效果也十分的好。 一条经过wu反走样的直线要比一条普通的直线要好,产生光滑的边界,。如图2.9所示。 图2.10 普通直线和WU反走样直线的对比在WU反走样算法中，有一个重要的概念就是WU像素。WU像素具有两个属性：1、绘制的所有像素的亮度的总和等于原始的粒子的亮度。2、WU像素的中心亮度被定位在原始粒子的非整数位置。根据WU像素的这两个属性我们就可以实现WU反走样直线。2.3.2 WU反走样直线算法理想的反走样算法将计算每条线覆盖的精确区域，从区域可以得到像素的灰度值，从而达到反走样的效果。WU反走样直线不是这样做，而是跨骑着直线绘制一对像素。一个主循环将沿着直线的长度画一对像素,端点的像素对将被分别计算处理，如图2.10所示。 图2.11 跨骑着直线的像素对 图2.12 亮度设置跨骑直线的像素对中，两个像素的亮度应该都是1,中心点的亮度就是理想直线的亮度。直线上的像素的亮度必须于(1-a)成比例,线下面的像素的亮度必须与(1-b)成比例。也就是说越靠近直线的像素应该越亮。沿着直线长度画这样的像素对,就可以得到一条WU反走样直线。在画完了中间端点后，我们要画起始端点和终结端点，如图2.12所示。可以看到直线的一个端点,用红色的点来表示，蓝色的点表示像素的中心点。你可以看到,顶点不在像素的中心点上，那么如何计算直线端点的两个像素的正确亮度呢？方法就是把直线延长(向后或向前)到最近的整数x坐标(p)，像计算直线上普通的像素对的亮度一样计算这些像素对。然后,因为直线只是覆盖这个像素的很小一部分xgap,直线将降低它的亮度，所以亮度应该乘上xgap。因此,当整条直线向右移动, xgap将变小,使得这个像素对平滑的变暗，按照这个方法可以画出两个端点。上面讲的是abs(xd)abs(yd)的情况，其实abs(xd)abs(yd) if (x1 x2) temp= x1; x1=x2; x2=temp; temp= y1; y1=y2; y2=temp; xd = x2-x1; yd = y2-y1; grad = yd/xd;/绘制起始端点 xend = x1+1; yend = y1 + grad*(xend-x1); xgap = invfrac(x1); ix1 = int(xend); iy1 = int(yend); /起始点像素亮度计算 brightness1 = invfrac(yend) * xgap ; brightness2 = frac(yend) * xgap ; c1 = BYTE (brightness1 * MaxPixelValue); c2 = BYTE (brightness2 * MaxPixelValue);putPixel(ix1,iy1, c1) ;putPixel(ix1,iy1+1, c2);yf = yend+grad ;/绘制中间点的亮度需要/绘制终结端点xend = trunc(x2) ;yend = y2 + grad*(xend-x2);xgap = invfrac(x2);ix2 = int(xend);iy2 = int(yend); /终结点像素亮度计算brightness1 = invfrac(yend) * xgap;brightness2 = frac(yend) * xgap;c1 = BYTE (brightness1 * MaxPixelValue);c2 = BYTE (brightness2 * MaxPixelValue);putPixel(ix2,iy2,c1);putPixel(ix2,iy2+1, c2);/绘制中间像素 for (int i=ix1+1;iabs(yd)的方法，只需要改变x和y的值即可实现； WU反走样算法思路清晰，速度也比较快，而且采用了像素的灰度处理，在反走样两像素宽度的直线效果上还好，因此在计算机图形学中得到了广泛应用。2.4 点取样点取样的原理很简单，就是对被取样的连续信号通过取样脉冲函数一个点一个点进行采样，最后来确定该像素的颜色。但这个取样方法不够科学，最后颜色的设定不一定就能反映像素的真实颜色值。因为点采样技术只考虑到单一的采样点中心，而没有考虑对像素灰度产生影响的多边形区域部分，这样的话仍然会使图形走样，我们可使用像素细分技术。像素细分技术的基本思想是将发生图形混淆的像素细胞分为四个子像素，分别对子像素进行光线跟踪。若子像素仍有图形混淆，则继续细分子像素直到最后确定整个像素亮度为止。这在前面介绍的方法中已经介绍到了，在此不多做介绍。2.5 象素移相在可以对屏幕网格内的子像素位置编址的光栅系统上，可使用像素移相来反走样图形。将电子束移动（微定位）到更接近由物体几何指定的近似位置，可光滑沿线路径或物体边界的阶梯状。加入这种技术的系统，单个像素位置可根据像素直径的小数部分来移动。典型地，电子束根据像素直径的1/4，1/2，3/4移动来画接近于线或物体边真实路径的点。有些系统也允许对单个像素的尺寸进行调整。第三章 反走样算法的改进3.1 多段直线反走样算法3.1.1 概述直线是最基本的图形元素，是构成复杂图形的基础，人们在设计和改进直线生成算法方面已经进行了较深的研究。其中Bresenham算法是最著名的，它在绘制线段的过程当中只涉及整数的加法和符号的判断，是一种简单、高效的算法。但不管是Bresenham算法还是别的直线生成算法都会使直线产生锯齿状边界。在第二章已经介绍并实现了几种反走样算法,但是它们都需要对直线上的每一个像素进行反走样处理，我们研究的多段反走样直线算法利用直线段像素可能存在的多段相似性，大大提高反走样速度，节省了反走样时间。3.1.2算法的设计思想 设平面直线l的方程为y=kx+b，根据斜率为k的取值范围，可将平面直线分为5类： （1）0k1；（2）1k；（3）-k-1；（4）-1k0；（5）k=0，|k|=1，|k|=；根据数字图形的特点，对第（5）类直线不必反走样扫描转换就可简单地生成直线。而对第（2），（3），（4）类直线，只要在反走样扫描转换时通过简单地交换x和y，或改变其增量的符号就可变换到第（1）类的反走样直线。设x0，y0，xn，yn为整数，不妨设x0xn，y0yn，对于以（x0，y0）和（xn，yn）为端点的直线段l，记dy=yn- y0，dx= xn-x0，则斜率k=，因为0k0，所以0dydx。记m为dy，dx的最大公约数，即m=gdc（dx，dy），则存在互质的正整数p和q，使得 k=，0qp。例如，如图3.1所示，（x0，y0）=（0，0），（xn，yn）=（15，12），m=gdc（15，12）=3，p=5，q=4。 设计思想1:反走样直线段l扫描转换生成的像素序列（xi，yi）|i=0，1，2，n可被划分成具有相同形状的m个片段：l1，l2，lm加终点像素，每个片段含p个像素，每个片段的第一个像素精确地落在l上，且在整个像素序列中有且仅有m+1个像素精确地落在l上（如图3.1所示）。图3.1 分段扫描示意图证明、因为对于第(1)类直线，沿x轴正方向单位步长取样且有dx=mp，所以扫描转换生成的像素序列具有mp+1个像素，故可等分为每段p个像素的m个片段l1，l2，lm，再加一个终点像素。记第j段的起点像素（xij，yij）(0j1的线段，根据性质1的分段相似特性, 可在反走样线段l1段后简单地复制或并行地反走样线段l2,l3,，lm。 综上所述，充分利用直线段特性，以普通过取样算法为基础，提出改进算法如下： 1）计算两个数的最大公约数函数 int gdc(int x,int y)int m=x,n=y,temp,r;if(mn) temp=m;m=n;n=temp;r=m%n;while(r!=0) m=n;n=r;r=m%n;return n; 2）斜率在0与1之间的直线void _fastcall TForm1:improveClick(TObject *Sender) int x1=20,y1=20,x2=400,y2=200,dx,dy,m; dx=x2-x1;dy=y2-y1; m=gdc(dx,dy); dx=dx/m;dy=dy/m; for(int i=1;iCanvas-MoveTo(20,20+10); Image1-Canvas-LineTo(400,200+10); 同理，其他斜率的直线可通过转换到斜率在0与1之间的直线来反走样。3.1.4 计算效率分析本算法需要通过计算获取的扫描转换像素个数最多为dx的一半：若m1，则仅需计算dx/m个像素后就会出现dk=0；若计算达到dx的一半时仍未遇到精确落在直线上的像素，则由性质1可知m=1，从而利用性质2进行对称复制。这样的话比普通的反走样直线算法明显具有优势,速度提高了很多。3.2圆反走样算法3.2.1算法思想圆反走样算法只需考虑圆心位于坐标原点的圆弧反走样，对于圆心为任意点的圆弧，可以先将其平移到原点，然后反走样，再平移到原来的位置上。圆心位于原点的圆有四条对称轴x=0，y=0，x=y，x=-y，如图3.2所示。因此只要知道圆弧上的一点（x，y）就可以得到它的七个对称点，也称为圆的八对称性。因此我们只要反走样八分之一圆弧其余的都可以对称得到反走样。圆的每一个八分之一圆弧都是由一段段的水平线段组成，因此圆弧反走样的问题就是反走样一段段小的水平线段的问题。 图3.2圆的八对称性3.2.2算法的实现 算法首先分析圆的特