第4章基本光栅图形算法.ppt

Computer Graphics第4章 基本光栅图形算法Computer Computer GraphicsGraphics主要内容光栅图形生成算法是计算机图形学的基础，本章主要包括直线和圆弧的生成算法、多边形的填充以及其他相关的图形基本元素的生成算法直线和圆弧等是图形的基本元素，生成基本元素算法的效率对图形系统的效率有直接关系虽然很多智能绘图机和图形显示器都有自己生成直线和圆弧的功能，但也有很多情况下要自己编写一些设备的驱动程序，在图形软件包中用软件生成直线和圆弧有时也是十分必要的多边形的填充算法是面显示的基础，其思想可用于解决计算机图形学中的消隐、真实感显示等许多问题，本章主要讨论此类图元的绘制问题 Computer Computer GraphicsGraphics主要章节直线生成算法4.1圆弧生成算法4.2多边形的填充4.3区域填充4.4光栅图形的反走样算法4.5Computer Computer GraphicsGraphics4.1直线生成算法Ø数学上的直线 理想的直线是没有宽度的，是由无数个点构成的集合 Ø光栅化的直线 在光栅的有限像素点阵中，确定最佳逼近于该直线的一组像 素，用这些像素表示该直线。

Ø常用算法 DDA方法\正负法\Bresenham算法Ø屏幕坐标系 产生光栅图形，首先要为每个像素指定一个惟一坐标，因此需要在屏幕上建立一个坐标系，每个像素中心的坐标为该像素的坐标,坐标均为整数 图 4.1 像素和坐标的对应关系(a)(b)Computer Computer GraphicsGraphics直线的三种表示v显示 Y=kx+bv隐式 ax+by+c=0 v参数 P(t)=(1-t)P0+tP1 Computer Computer GraphicsGraphics4.1.1生成直线的DDA算法设直线的起点为(xs,ys),终点为（xe,ye）, 并设(xs,ys)和（xe,ye）都是整数（做求整处理）令Δx= xe–xs,Δy= ye–ys则直线的参数方程是(4.1)目标是能快速地求出能很好地表示直线的像素提高速度的方法之一是:乘法用加法实现，用等步长计算直线上的点 设 是第i步得到的直线上的点，则直线上第个i+1点是( , ),其中 (4.2)图4.2 图中黑圆点表示用DDA法生成的直线Computer Computer GraphicsGraphics当 ,即直线斜率小于1时应使x方向每次增加1，y方向最多增加1，此时取 .当 时，直线斜率大于1，取所以图4.2 图中黑圆点表示用DDA法生成的直线用式4.2可求得图4.2中直线 上用三角形表示的点，但显示时要用像素表示，可用舍入的办法得到最靠近三角形的像素，用这些像素表示直线，这个方法称为DDA方法。

DDA算法的缺点:计算量较大， 产生一个像素需要2次加法，2次取整运算 算法还需要除法运算，增加了硬件实现上的困难 生成直线的DDA算法Computer Computer GraphicsGraphics4.1.2正负法基本原理：为讨论方便，假设直线斜率在0和1之间假设 是直线上的一点（ 表示），与P最近的像素为（ ）( 表示 )，那么下一个与直线最近的像素只能是正右方的 或右上方的 两者之一以M表示 和 的中点，Q是直线与垂线 的交点显然，若M在Q的下方，则 离直线近，应取 为下一个像素，否则应取 图4.3 正负法每步迭代涉及的象素和中点示意图Computer Computer GraphicsGraphics正负法算法的具体实现设直线的起点和终点分别为(x0,y0)和(x1,y1),直线方程为:其中 ， ， 分别对应于点 在直线上、上方和下方 要判断M在直线的上方还是下方，只需把M代入，判断它的符号即可构造判别式d<0，Q在M上方，取P P2 2为下一像素d>0，取P P1 1为下一像素，d=0,可在两个点中任取一个，约定取右下方的点。

P2P P1 1Computer Computer GraphicsGraphics正负法算法的具体实现在d>=0，取右下方像素P1 ，下一个像素应取哪个，应计算 P2P P1 1若d<0，则取右上方像素 P2，并计算 讨论d的初始值，第一个像素应取 (x0,y0)由于(x0,y0)在直线上，故F(x0,y0)=0因此， Computer Computer GraphicsGraphics正负法程序void MidpointLine(int x0,int y0,int x1,int y1){int a, b, delta1, delta2, d,x, y;a=y0-y1;  b=x1-x0;d=2*a+b;     delta1=2*a;      delta2=2*(a+b);      x=x0;  y=y0;     glBegin(GL_POINTS);     glVertex2s(x,y); glEnd();  while(x

设A为CD边的中点，若B在A点上面则应取D点作为(xi+1,yi+1,r),否则应取C点ε(xi+1)=yi+1–(yir+ yir+1)/2  =yi+1–yir–0.5 图4.4 的几何意义ε(x) ε(xi+1)用来判断取C或DComputer Computer GraphicsGraphicsε(xi+1) =yi+1–yir–0.5 yi+1，r= yir+1若ε(xi+1)≥0  B在A点上面yi+1，r= yir ， 若ε(xi+1)< 0 B在A点下面要计算下一个点，需计算ε(xi+2)计算ε(xi+2)的递推公式ε(xi+2)  = yi+2–yi+1, r–0.5            = yi+1+m–yi+1, r–0.5 yi+1，r= yir+1，若ε(xi+1)≥0 yi+1，r= yir ， 若ε(xi+1)< 0Bresenham算法Computer Computer GraphicsGraphicsBresenham算法ε(xi+2)yi+1,r= yir+1，若ε(xi+1)≥0  yi+1,r= yir ， 若ε(xi+1)< 0 设xs和ys均为整数,x1=xs,  y1=ysε(x2)=y2–y1–0.5=m–0.5        (ε(xi+1) =yi+1–yir–0.5)程序m=(double)dy/(double)dx；e = m–0.5；for(i=0;i=0){   y=y+1；   e=e–1;}x=x+1；e=e+m;} 其中dy=ye–ys，dx=xe–xs。

缺点：缺点：有除法和浮点数 Computer Computer GraphicsGraphics4.1.4生成直线算法的进一步改进设0 ≤ m ≤1，每循环一次绘制二个象素当yi+2–yir≤0.25×2时绘pattern1当0.5×2≥yi+2–yir>0.25×2时绘pattern2当0.75×2≥yi+2–yir>0.5×2时绘pattern3当yi+2–yir>0.75×2时绘pattern4xixi+1xi+2xixi+1xi+2xixi+1xi+2xixi+1xi+2图4.6四种绘制模式Computer Computer GraphicsGraphics递推公式Computer Computer GraphicsGraphics一般情况的讨论Ø当直线斜率m的 绝对值很小时，同一像素行上可以连续出现很多个表示直线的像素点，每循环一次有可能同时填充多个像素，Ø某些图形加速卡也具有在一个像素行上平行填充多个像素的功能 图4.7当|m|较小的情况时返回Computer Computer GraphicsGraphics4.2圆弧生成算法本节仅考虑圆心在原点的情况 u正负法uBresenham法u多边形迫近法 4.2.1正负法设圆的圆心在(0,0),半径为R,则圆的方程为 F(x,y)=x2+y2–R2=0 v当点(x,y)在圆内时, F(x,y)<0。

v当点(x,y)在圆外时，F(x,y)>0 （0，0）图4.8 对弧AB上点的取法Computer Computer GraphicsGraphics正负法基本思想Ø第第1 1步：步：x0=0，y0=RØ第第2 2步：步： 求得Pi(xi,yi)后找点Pi+1的原则为：ü当Pi在圆内时(F(xi,yi)≤0)，，要向右走一步得Pi+1，这是向圆外方向走去取xi+1= xi+1, yi+1= yiü当Pi在圆外时(F(xi,yi)>0)，要向下走一步得Pi+1，这是向圆内方向走去，取xi+1= xi, yi+1= yi-1考虑F(xi,yi)的计算Pi+1oComputer Computer GraphicsGraphics计算F(xi+1,yi+1)（分两种情况） Ø当xi+1=xi+1，yi+1=yi时，F(xi+1,yi+1)=xi+12+yi2-R2                 =xi2+yi2-R2+2xi+1                 =F(xi,yi)+2xi+1Ø当xi+1=xi，yi+1=yi-1时， F(xi+,yi+1)=xi2+（yi-1)2-R2              =F(xi,yi)-2yi+1  计算F(xi+1,yi+1)的公式程序vx0=0，y0=R F（xi,yi）=0vF(xi,yi)≤0时，则 xi+1= xi+1, yi+1= yi   F(xi+1,yi+1)=F(xi,yi)+2xi+1vF(xi,yi) >0时，则 xi+1= xi, yi+1= yi-1 F(xi+,yi+1)=F(xi,yi)-2yi+1正负法显示圆弧时可不用除法，而且计算时全为整型数，这很适合于用硬件来实现。

Computer Computer GraphicsGraphics4.2.2 Bresenham 生成圆弧的算法 假设圆心(0,0)为原点 考虑AB弧的画法，显示一个整圆时，只要在显示AB上任一点(x,y)时，同时显示在圆周上其它七个对称点 (y,x), (y,-x),(x,-y),(-x,-y),(-y,-x),(-y,x),(-x,y)从A点开始寻找弧AB上要用的点设Pi-1是已选中的一个表示圆弧上的点，下一个点应从Hi或Li中选择设Hi和Li两点的坐标分别为(xhi,yhi)和(xli,yli)考虑应选哪一个 xyLiHiPi-1图4.9 七个对称点图4.10 两个候选点Computer Computer GraphicsGraphics选点的判别式令D(P)=(x2+y2)-R2   di=D(Hi)+D(Li) v当di=0，点Hi和Li距弧AB的距离相等v当di<0时，|D(Hi)|<|D(Li)|，取Hi来显示弧AB；v当di≥0时，|D(Hi)|>|D(Li)|，取Li来显示弧AB 计算di 设已选中的点Pi-1=(xi-1,yi-1)则Hi和Li点的坐标分别为(xi,yi-1)和(xi,yi-1–1)Hi+1和Li+1的坐标分别为(xi+1,yi)和(xi+1,yi –1)。

因为 x0=0,  y0=R,  x1=x0+1，所以d1=D(H1)+D(L1)=(12+y20-R2)+(12+(y0-1)2-R2) =3-2y0=3-2R xyLiHiPi-1Computer Computer GraphicsGraphics选点的判别式di=(x2i+y2i-1-R2)+(x2i+(yi-1-1)2-R2)   =2x2i+2y2i-1-2yi-1-2R2+1                                  (4.20)di+1=(xi+1)2+y2i-R2+(xi+1)2+(yi-1)2-R2      =2x2i+4xi+2y2i-2yi-2R2+3                             (4.21)xi= xi-1+1当di<0时,点Hi被选中, yi=yi-1，由 (4.5)- (4.6) 得 di+1= di+ 4xi+2= di+ 4xi-1+6                         (4.22)当di≥0时,点Li被选中, yi= yi-1-1，由(4.5)- (4.6)得 di+1=di+4xi-4yi-1+6=di+4(xi-1-yi-1)+10              (4.23) 程序vx0=0, y0=R，d1 =3–2*Rv当di<0时 ， di+1=di+ 4xi-1+6 xi= xi-1+1v当di≥0时， di+1=di+4(xi-1-yi-1)+10 xi= xi-1+1，yi= yi-1-1 Bresenham算法在候选的两个像素和中，总是选定离圆弧最近的像素为圆弧的一个近似点，因此，Bresenham算法比正负法决定的像素更合理。

xyLiHiPi-1图4.10 两个候选点Computer Computer GraphicsGraphics4.2.3圆弧的离散生成 Ø前面的算法对于生成完整的圆和四分之一或八分之一圆弧是很方便和快速的，但是如果生成任意的圆弧，前面的算法就不是很方便Ø下面给出的圆弧离散生成算法，可以很容易地生成任意的圆弧Ø该算法的基本思想就是将整个圆弧等分成一段段的短直线，用这些短直线形成的折线来逼近圆弧，为了获得这些短直线，只需按一定的方式计算给定圆弧轨迹上一系列顶点，短直线的绘制可采用直线的生成算法，如果将圆弧分割的足够密，则短直线将足够短，形成的折线将可以和圆弧接近到任意程度，因此在允许的误差范围内，可以用显示折线代替显示圆弧 Computer Computer GraphicsGraphics圆弧的离散生成 设圆的圆心为c(0,0),半径为R假设圆弧的起始角和终止角分别为α0和α1，把圆弧分割为n份，则两个顶点之间的夹角为 α=（ α1 - α0 ）/n  图4.11 用正多边形迫近圆弧法设顶点序列的第i个点为 的幅角为 （如图），则下一个顶点Pi+1的坐标为或者用矩阵表示为只要作四次乘法。

计算一个点Computer Computer GraphicsGraphics椭圆弧的离散生成 该椭圆的参数方程为 设顶点序列的第i个顶点为 则 的坐标满足 由此可得椭圆的递推公式 其中Computer Computer GraphicsGraphics4.2.4椭圆生成算法椭圆的方程：F(x,y)=b2x2+a2y2-a2b2=0只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点 椭圆上一点处的法向：二分量相等 法向量 上半部分 下半部分 在当前点处，法向量的y分量 比x分量大, 即 , 而在下一点，不等式改变方向，则说明椭圆弧从上部分转入下部分图4.12 第一象限的椭圆弧Computer Computer GraphicsGraphics上半部分绘制Ø计算di 是当前像素上半部分下半部分根据di的符号来决定下一像素是取正右方的 ， 还是右下方的 。

Ø若di ＜0，中点在椭圆内，取正右方的 新的判别式：Ø当di ≥0，中点在椭圆外，取右下方的 新的判别式：Computer Computer GraphicsGraphics初始条件：                     (x,y)=(0，b)；  d0 =F(1,b-0.5)= b2 +a2(b-0.5)2 -a2b2                          = b2 +a2(-b+0.25)转入下一部分， 下一象素可能是正下方或右下方， 判别式要初始化d0 = F(x+0.5,y-1) = b2(x+0.5)2+a2(y-1)2-a2b2  若di <0,取右下方像素，则 di+1 = F(x+1.5,y-2) = di + b2(2x+2)+a2(-2y+3) 若di >=0,取正下方像素，则 di+1 = F(x+0.5,y-2) = di + a2(-2y+3) 下半部分弧的终止条件为 y = 0上半部分下半部分返回上半部分绘制Computer Computer GraphicsGraphics4.3多边形的填充 前面讨论的是几何线条的图形生成算法，本节开始讨论区域的显示和处理问题，即面着色的问题 主要讨论多边形区域的面着色问题。

面着色算法分为两大类：1、扫描线填色（Scan-Line Filling）算法这类算法建立在多边形边界顶点的矢量形式(几何)数据之上，可用于程序填色，也可用交互填色2、种子填色（Seed Filling）算法这类算法建立在多边形边界或多边形的内点图象(点阵、位图）形式数据之上，并还需提供多边形界内一点的坐标Computer Computer GraphicsGraphics4.3.1多边形的表示方法多边形的表示方法：顶点表示和点阵表示顶点表示：顶点表示：是用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少，但它不能直观地说明哪些像素在多边形内点阵表示：点阵表示：是用位于多边形内的象素的集合来刻划多边形，该方法虽然没有多边形的几何信息，是面着色所需要的图像表示形式 图4.13 多边形的顶点表示 图4.14 多边形的点阵表示 多边形填充就是把多边形的顶点表示转换为点阵表示，即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜色 Computer Computer GraphicsGraphics4.3.2多边形填充的扫描线算法 P0P1P2P3P4P5P6P7图4.15 区域的连续性P8扫描线算法充分利用了相邻象素之间的连贯性，避免了对象素的逐点判断和反复求交的运算1.区域的连贯性 设多边形P的顶点又设 是各顶点Pi的纵坐标yi的递减数列,当 ,屏幕上位于y= 和y= 两条扫描线之间的长方形区域被多边形P的边分割成若干梯形，它们具有下列性质(设 为整数)： (1)梯形的两底边分别在y= 和y= 两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。

(2) 梯形可分为两类：一类位于多边形P的内部；另一类在多边形P的外部3) 两类梯形在长方形区域{ ， }内相间的排列 Computer Computer GraphicsGraphics2.扫描线的连贯性P0P1P2P3P4P5P6P7P8Xe0Xe2Xe3Xe7Xe6Xe4图4.16 扫描线的连续性图中 ---- 表示在多边形外的区间 ── 表示在多边形内的区间设e为一整数 ≥e≥ 若扫描线y=e与多边形P的边Pi-1Pi相交，则记其交点的横坐标为设 (4.32) 是该扫描线与P的边界各交点横坐标的递增序列由区域的连贯性可知，此交点序列具有以下性质： (1) l是偶数2) 在该扫描线上，只有区段 l–1位于多边形P内. 以上性质称为扫描线的连贯性Computer Computer GraphicsGraphics3.边的连贯性P0P1P2P3P4P5P6P7P8Xe0Xe2Xe3Xe7Xe6Xe4图4.17 边的连续性Xd0Xd2Xd3Xd7Xd6Xd4若d为一整数，d=e–1，且yi0≥y≥yin；设位于扫描线y=d上的交点序列为 (4.33) 若 成立时，则由区域的连续性可知序列（4.32）和（4.33）之间有以下关系：(1)两序列元素的个数相等。

2)点( )与( )位于多边形P的同一边上，即以上性质称为边的连贯性Computer Computer GraphicsGraphics4.奇点的处理当扫描线与多边形P的边界的交点是P的顶点时，则称该交点为奇点 多边形P的顶点可分为两类：极值点和非极值点如果 则称顶点Pi为极值点；否则称Pi为非极值点 如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数若 将每一奇点都简单地计为两个交点，同样会导致反常的结果为了使交点个数保持为偶数，规定当奇点是P的极值点时，该点按两个交点计算；否则按一个交点计算 预处理: 若Pi是非极值点，则将 两边中位于扫描线y=yi上方的那条边在Pi点处截去一单位长 Computer Computer GraphicsGraphics5 . 扫描线算法的数据结构与实现步骤 取 ，求扫描线y=d上的交点序列 ,根据多边形边的连贯性和扫描线的连贯性，按从下到上的顺序求得各条扫描线的交点序列数据结构边的分类表ET和边的活化链表AELET和AEL中的多边形的边由四个域组成： ymax 边的上端点的y坐标； x 在ET中为边的下端点的x坐标，在 AEL中是边与扫描线交点的x坐标 Δx 边的斜率的倒数 next 指向下一条边的指针。

分类表ET按边下端点的纵坐标y对边进行分类同一类中，各边按x值递增的顺序排列成行[P0 P1 P2 P3 P4 P5 P6]=[(2,5) (2,10) (9,6) (16,11) (16,4) (12,2) (7,2)] Computer Computer GraphicsGraphics扫描线算法的数据结构与实现步骤 边的活化链表AEL由与当前扫描线相交的所有多边形的边组成 Computer Computer GraphicsGraphics扫描线算法的数据结构与实现步骤 -5/357AELe0e54212AEL在y=2扫描线上的状态-5/355AELe0e54214AEL在y=3扫描线上的状态-5/353AELe0e54216AEL在y=4扫描线上的状态Computer Computer GraphicsGraphics扫描线算法步骤1: (y初始化)取扫描线纵坐标y的初始值为ET中非空元素的最小序号步骤2：(AEL初始化)将边的活化链表AEL设置为空步骤3：按从下到上的顺序对纵坐标值为y的扫描线(当前扫描线)执行下列步骤，直到边的分类表ET和边的活化链表AEL都变成空为止。

(1) 如边分类表ET中的第y类元素非空，则将属于该类的所有边从ET中取出并插入边的活化链表AEL中，AEL中的各边按照x值(当x的值相等时，按Δx值)递增方向排序 (2) 若相对于当前扫描线，边的活化链表AEL非空，则将AEL中的边两两依次配对，每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点(象素)按多边形属性着色 (3) 将边的活化链表AEL中满足y=ymax的边删去 (4) 将边的活化链表AEL剩下的每一条边的x域累加Δx，即x:=x+Δx (5) 将当前的扫描线的纵坐标值y累加，即y:=y+1Computer Computer GraphicsGraphics4.3.3边缘填充算法 建立ET和AEL时需对多边形的边进行排序,用求余的方法，可免去对边排序假定A为一正数，数M的余是指A–M，记为 =M，对M作偶数次求余运算，其结果是M 边缘填充算法很容易实现，对多边形P的每一非水平边 （i=0,1,…,n）上的各像素做向右求反运算即可，见图4.21，其中(a)为给定的多边形；(b)为对区域赋初值；(c)，(d)，(e)和(f)表示逐边向右求反。

图4.21边缘填充算法的过程 和扫描线算法比较，边缘填充算法结构都简单但是需对帧缓冲器中的大批元素反复赋值，故速度不比前者快，另外如果区域内原来有其他的颜色，也不能保证最后区域内的颜色是多边形的颜色，对单值图像比较有用Computer Computer GraphicsGraphics4.3.4边界标志算法 边缘填充算法: 程序和数据结构较简单，但涉及了对帧缓冲器中大量元素的多次赋值而影响了算法的运行效率边界标志法: 先画边界后填色，使对帧缓冲器中的每个元素的赋值次数不超过2次基本思想是：先用一种特殊的颜色在帧缓冲器中将多边形的边界(水平边的部分边界除外)勾画出来然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需的颜色 图4.22边界标志算法的运行过程Computer Computer GraphicsGraphics边界标志法具体实现图4.22边界标志算法的运行过程步骤1：以值为boundary-color 的特殊颜色勾画多边形P的边界设多边形顶点为Pi= (xi, yi),0≤i≤n， xi, yi均为整数；置Pn+1=P0每一条扫描线上着上这种特殊颜色的点的个数必定是偶数(包括零)。

步骤2：设interior_point 是一布尔变量对每一条扫描线从左到右进行搜索，如果当前是像素位于多边形P内，则interior_point=true，需要填上值为polygon_color的颜色；否则该像素在多边 形 P外 ， 需 要 填 上 值 为background_color的颜色 返回Computer Computer GraphicsGraphics4.4区域的填充4.4.1区域的基本概念区域填充是指先将区域内的一点(常称种子点)赋予给定颜色，然后将这种颜色扩展到整个区域内的过程 区域是指已经表示成点阵形式的象素集合 光栅图形中，区域可采用内点表示和边界表示等两种形式进行描述 内点表示法:把位于给定区域内的所有象素一一列举出来的方法 以内点表示法为基础的区域填充算法称为泛填充算法 边界表示法: 把位于给定区域的边界上的象素一一列举出来的方法.它 将区域边界上的象素都着上同一种颜色(常称为边界色) 图4.23分别用内点和边界表示的区域Computer Computer GraphicsGraphics区域的连通性-----4连通的区域: 取区域内任意两点，在该区域内若从其中一点出发通过上、下、左、右四种运动可到达另一点。

8连通区域: 取区域内任意两点，若从其中任一点出发，在该区域内通过沿水平方向、垂直方向和对角线方向的八种运动可到达另一点4连通或8连通 图4.25四个方向的运动图4.26八个方向的运动4连通区域也可理解成8连通区域，但是两者的边界不尽相同如果图中标有·号的象素组成的区域作为4连通区域，则其边界由图中的标有△号的象素组成如果将该区域作为8连通的区域，则其边界由图中标有△号和×号的两种象素组成 图4.27内点表示的八连通区域图4.28边界表示的八连通区域图4.29四连通和八连通区域的不同边界Computer Computer GraphicsGraphics4.4.2简单的种子填充算法void  flood_fill_8(int  x,  int  y,  COLORREF old_color, COLORREF new_color){if (getpixel(framebuffer,x,y)==old_color){setpixel(framebuffer,x,y,new_color);flood_fill_8(x,y+1,old_color,new_color);flood_fill_8(x,y-1,old_color,new_color);flood_fill_8(x-1,y,old_color,new_color);flood_fill_8(x+1,y,old_color,new_color);flood_fill_8(x+1,y+1,old_color,new_color);flood_fill_8(x+1,y-1,old_color,new_color);flood_fill_8(x-1,y+1,old_color,new_color);flood_fill_8(x-1,y-1,old_color,new_color);}} G: 内点表示的区域，(x, y)是G内一点，old–color是G的原色。

填充算法：先测试象素(x, y)的颜色若它的值不等于old–color，则该象素在区域G外，不能取为种子点，停止填充；否则置该象素的颜色为new–color然后将该点周围的四个点（四连通）或八个点（八连通）作为新的种子点进行同样的处理，通过这种扩散完成对整个区域的填充 Computer Computer GraphicsGraphics4.4.3扫描线种子填充算法Ø算法的基本思想算法的基本思想：首先填充当前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来反复进行这个过程，直到所保存的各区段都填充完毕 图4.30扫描线种子填充算法的执行过程图4.30中的例子是用上述算法得到的结果图中标上×号的方格是边界点，其颜色值为boundary_color标有符号·的方格代表给定的种子点标有斜线的方格表示区域内的像素已填充了new_color新颜色方格内的数字表示相应像素作为种子点进入堆栈的先后顺序图（a）表示对种子点所在扫描线区间进行填充的情况和堆栈的状态b）表示对下一条扫描区间进行填充的情况和堆栈的状态c），（d）类似返回Computer Computer GraphicsGraphicsØ算法步骤算法步骤：1 1））将算法设置的堆栈置为空。

将种子点（x, y）压入堆栈2 2））如果栈为空算法结束；否则取栈顶元素（x, y）作为种子点3 3））从种子点（x, y）开始，沿纵坐标为y的当前扫描线向左右两个方向逐个像素用新的颜色值进行填充，直到边界为止设区间两边界的横坐标分别为 和 4 4））在与当前扫描线相邻的上下两条扫描线上，以区间 为搜索范围，求出需要填充的各小区间，把各小区间中最右边的点并作为种子点压入堆栈，转到步骤2 4.4.3扫描线种子填充算法Computer Computer GraphicsGraphics4.5光栅图形的反走样算法 4.5.1 光栅图形的走样现象 表现：u图形的边界一般都呈阶梯形 如图（4.31），（4.32）图4.31阶梯形边界图图4.32阶梯形线段（a） 待显示的细小图形 （b） 显示结果图4.33 细节失真（a）待显示的狭小矩形（b） 显示结果图4.34 狭小图形的遗失u图形的细节失真、狭小图形遗失如图（4.33),(4.34) 当在光栅显示器上显示如图4.33所示的细长的矩形时，原细长的矩形被显示成了加宽的矩形一些狭小的多边形分布在两条扫描线之间，由于它们不覆盖任何一个像素中心，所以没有被显示出来，造成狭小图形的遗失。

如图4.34Computer Computer GraphicsGraphics4.5.2 提高分辨率的反走样算法提高分辨率的方法1. 采用硬件: 采用高分辨率的光栅图形显示器，花费的代价大2. 采用软件: 花费的代价小，也容易实现用软件提高分辨率的方法是：高分辨率计算，低分辨率显示 高分辨率计算：将低分辨的图形显示象素划分为许多子象素，如2×2划分，3×3划分等，然后按通常的算法计算出各个子象素的颜色值或灰度值低分辨率显示：将一象素内的各个子象素的颜色值或灰度值的平均值作为该象素的颜色值或灰度值求平均值时可取算术平均，也可取加权平均 图4.35是两种典型的加权平均方法图4.35 加权表Computer Computer GraphicsGraphics4.5.3 线段反走样算法线段的反混淆算法的基本思想可归纳如下： (1) 把线段看作是有宽度的狭长的矩形如图4.28 (2) 线段具有一定的面积，当线段通过某象素时，可以求出两者面积的交 (3) 根据每一象素与线段相交部分的面积值决定该象素的颜色值或灰度值用反混淆算法显示的线段称为反混淆/走样线段反混淆线段是将位于原相邻阶梯之间的象素置为过渡颜色或灰度，使得颜色或者灰度过渡自然，变化柔和，阶梯被淡化后，线形就显得平直了。

反混淆算法极大地改善了显示时线段的线形质量由于要计算面积，使得计算量大大增加，速度也由此而减慢，所以它不适合于动态的交互式图形显示 图4.36 有宽度的线段Computer Computer GraphicsGraphics4.5.4多边形反走样算法多边形的混淆现象主要表现在边界上，可采用反走样线段的思想来改善 计算象素与多边形交的面积很费时间Pitteway和Watkinson将画线段的Bresenham算法发展成多边形的反走样算法假定多边形一边的方程为 y = mx,    0≤m≤1Bresenham算法: 每一步要算出ε(xi)以确定表示直线的象素(xi, yi)由ε(xi)的几何意义知，ε(xi)越大，象素和多边形相交的面积越大 图4.37 多边形位于线段的右边ε(xi+1) =yi+1–yir–0.5  yi+1，r= yir+1，若ε(xi+1)≥0  yi+1，r= yir ，   若ε(xi+1)< 0               ε(xi)的几何意义Computer Computer GraphicsGraphics计算ε(xi+2)的递推公式ε(xi+2)= yi+2–yi+1, r–0.5             = yi+1+m–yi+1, r–0.5 ε(xi+1) =yi+1–yir–0.5  yi+1，r= yir+1，若ε(xi+1)≥0  yi+1，r= yir ，   若ε(xi+1)< 0 m–1≤ε(xi)

在（4.1.3）节的程序中用d=e+1–m代替e，则可得反走样的多边形边的绘制程序。