第三章 基 本 图 形 的 生 成 本 章 主 要 内 容 直线段的扫描转换算法 圆弧的扫描转换算法 多边形的扫描转换与区域填充 字符 裁剪 反走样 消隐

3.1 直线段的扫描转换算法 直线的扫描转换 三个常用算法 确定最佳逼近于该直线的一组像素 按扫描线顺序，对这些像素进行写操作 数值微分(DDA)算法 中点画线法 Bresenham画线算法

3.1.1 数值微分(DDA)法 基本方法（不是DDA方法） 已知过端点 的直线段L：y = kx+b 则有： x=x+xInc； 而像素 (x, round(y)) 作为当前点的坐标。 评价：①这种方法直观易懂，②但效率太低，因为画每一个点需要一次浮点乘法和一次舍入运算。

3.1.1 数值微分(DDA)法 数值微分(DDA)算法---增 量 算 法 分 析： 1:如果 | k | ≤1，则 ( X i+1 ,Yi + 1) (X i , Yi) 栅格交点表示像素点位置 。 分 析： 1:如果 | k | ≤1，则 yi+1 = kxi+1 + b = kxi + kx + b = yi + kx 当x =1;有：yi+1 = yi+k ……式3-1 当x =-1;有：yi+1 = yi-k ……式3-2 乘法运算

3.1.1 数值微分(DDA)法 2:如果 | k| ＞1，有 当y =1;有：xi+1 = xi + 1/k ……式3-3 增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。如：式3-1、式3-2、式3-3、式3-4那样； DDA算法便是一个增量算法。尊重历史，继往开来 乘法运算

3.1.1 数值微分(DDA)法 #define round(x) ((int)(x+0.5)) 取整运算 #define round(x) ((int)(x+0.5)) void DDALine(int x0,int y0,int x1,int y1,int color)  int dx = x1- x0, dy = y1- y0, steps, k； float xin,yin,x = x0 ,y = y0 ; if(abs(dx)>abs(dy)) steps = abs(dx); else steps = abs(dy); xin = dx/(float)steps; yin = dy/(float)steps; setpixel (round(x), round(y), color); for (k=0;k<steps;k++) x + = xin; y + = yin;  浮点运算

3.1.1 数值微分(DDA)法 关于DDA的评价： 改进措施： DDA方法计算像素位置比直接采用方程式更快； 利用了光栅特性消除了3-1式中的乘法； 浮点增量的连续迭代加中取整误差的积累，导致长线段所计算的像素位置偏离实际线段； 程序DDAline中的取整函数和浮点运算仍然十分耗时； 改进措施： 将增量k、1/k分解成整数和小数部分，使所有计算都改进成整数DDA算法的性能；

3.1.2 中点画线法 采用增量思想的DDA算法，每计算一个象素，只需计算一个加法，是否最优？ 如非最优，如何改进？ 目标：进一步将一个加法改为一个整数加法。 新思路－> DDA算法采用两点式，可否采用其他的直线表示方式？

3.1.2 中点画线法 基本思想 当前象素点为(xp, yp) 。下一个象素点为P1 或P2 。 设M=(xp+1, yp+0.5)，为p1与p2 之中点，Q为理想直线与x=xp+1 垂线的交点。将Q与M的y坐标进 行比较。 当M在Q的下方，则P2 应为 下一个象素点； M在Q的上方，应取P1为下一点。

3.1.2 中点画线法 构造判别式:d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0 当d<0，M在L(Q点)下方，取右上方P2为下一个象素； 当d>0，M在L(Q点)上方，取右方P1为下一个象素； 当d=0，选P1或P2均可，约定取P1为下一个象素；

3.1.2 中点画线法 这样做，每一个像素的计算量是4个加法，两个乘法。 如果也采用增量算法呢？ d 是xp, yp的线性函数，因此可采用增量计算，提高运算效率。

3.1.2 中点画线法 若当前象素处于d0情况，则取正右方象素P1 (xp+1, yp), 要判下一个象素位置，应计算 d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a； 增量为a 若d<0时，则取右上方象素P2 (xp+1, yp+1)。要判断再下一象素，则要计算 d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ；增量为a＋b

3.1.2 中点画线法 至此，至少新算法可以和DDA算法一样好。 能否再做改进？能否实现整数运算？ 画线从(x0, y0)开始，d的初值 d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b =a+0.5b。 可以用2d代替d来摆脱小数，提高效率。 令 d0=2a+b, d1=2a, d2=2a+2b,我们有如下算法 。

3.1.2 中点画线法 void Midpoint Line (int x0,int y0,int x1, int y1,int color) { int a, b, d1, d2, d, x, y; a=y0-y1, b=x1-x0, d=2*a+b; d1=2*a, d2=2* (a+b); x=x0, y=y0; drawpixel(x, y, color); while (x<x1) { if (d<0) {x++, y++, d+=d2; } else {x++, d+=d1;} drawpixel (x, y, color); } /* while */ } /* mid PointLine */

3.1.2 中点画线法 例：用中点画线法 i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 5 4 2 5

3.1.3 Bresenham算法 基本思想 DDA算法采用点斜式，中点法采用隐式表示。 中点法可以有整数算法。 其他表示可以推出整数算法吗？

3.1.3 Bresenham算法 d2 d1 Yk+3 Yk+2 Yk+1 Yk Yk+1 Y Yk Xk Xk+1 Xk+2 Xk+3

3.1.3 Bresenham算法 决策参数: 可见,如果 pk<0,即d1<d2,yk+1=yk,否则 yk+1=yk+1

3.1.3 Bresenham算法 例:画直线从(20,10)到(30,18),斜率为0.8. △x=10, △y=8;初始决策参数为p0=2△y-△x=6. k pk (xk+1,yk+1) 6 (21,11) 5 (26,15) 1 2 (22,12) (27,16) -2 (23,12) 7 (28,16) 3 14 (24,13) 8 (29,17) 4 10 (25,14) 9 (30,18)

3.2圆弧扫描转换算法 圆弧的扫描转换 四个常用算法 确定最佳逼近于该圆弧的一组象素 按扫描线顺序，对这些象素进行写操作 中点画圆法 Bresenham画圆算法 生成圆弧的正负法 圆的内接正多边形逼近法

圆弧扫描算法 下面仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。 假设圆的方程为： X2 + Y2 = R2

3.2 圆弧扫描算法 X2 + Y2 = R2 Y = Sqrt(R2 - X2) 在一定范围内，每给定一 X值，可得一Y值。 缺点：浮点运算，开方， 取整，不均匀。 y x

中点画圆法 利用圆的对称性，只须讨论1/8圆。第二个8分圆 P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp +1，Yp -1)。 P（Xp ，Yp ） P1 M P2

中点画圆法 构造函数：F（X，Y）=X2 + Y2 - R2 ；则 F（X，Y）= 0 （X，Y）在圆上； 设M为P1、P2间的中点，M=(Xp+1,Yp-0.5) P1 M P2

F（M）< 0 ->M在圆内-> 取P1 F（M）>= 0 ->M在圆外-> 取P2 中点画圆法 有如下结论： F（M）< 0 ->M在圆内-> 取P1 F（M）>= 0 ->M在圆外-> 取P2 为此，可采用如下判别式： P1 M P2

中点画圆法 d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2 - R2 若d<0, 则P1 为下一个象素，那么再下一个象素的判别式为： d2 = F(xp + 2, yp - 0.5) = (xp + 2)2 + (yp - 0.5) 2 - R2 = d + 2xp +3 即d 的增量为 2xp +3. P1 M P2

中点画圆法 若d>=0, 则P2 为下一个象素，那么再下一个象素的判别式为： d1 = F(xp + 2, yp - 1.5) = (xp + 2)2 + (yp - 1.5) 2 - R2 = d + （2xp + 3）+（-2 yp + 2） 即d 的增量为 2 (xp - yp) +5. d的初值: d0 = F(1, R-0.5) = 1 + (R-0.5)2 - R2 = 1.25 - R P1 M P2

中点画圆法 MidpointCircle(int r, int color) { int x,y; float d; x=0; y=r; d=1.25-r; drawpixel(x,y,color); while(x<y){ if(d<0){ d+ = 2*x+3; x++ } else{d+ = 2*(x-y) + 5; x++;y--; } }

中点画圆法 为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。 使用e=d-0.25代替d e0=1-R

Bresenham画圆算法 设圆的半径为r。考虑圆心在（0，0），并从x=0、y=r开始的顺时针方向的1/8圆周的生成过程。在这种情况下，x每步增加1，从x=0开始，到x=y结束。即有： xi+1=xi+1 相应的yi+1则在两种可能中选择： yi+1= yi 或者 yi+1= yi-1 选择的原则是：考察精确值y是靠近yi还是靠近yi+1 。 xi xi+1 x yi y yi-1

Bresenham画圆算法 选择的原则是：考察精确值y是靠近yi还是靠近yi+1 。 xi xi+1 x yi y yi-1 其中，pi为决策参数。如果pi<0则yi+1= yi 或者 yi+1= yi-1

Bresenham画圆算法 圆的Bresenham算法的程序实现如下: circle(xc,yc,radius,c) { int x=0,y,p; y=radius;p=3-2*radius; while(x<y) { plot_circle(xc,yc,x,y,c); If(p<0) p=p+4*x+6; else { p=p+4*(x-y)+10; y-=1; } x+=1; } if(x=y) plot_circle(xc,yc,x,y,c) {int xc,yc,x,y,c; set_pixel(xc+x,yc+y,c); set_pixel(xc-x,yc+y,c); set_pixel(xc+x,yc-y,c); set_pixel(xc+y,yc+x,c); set_pixel(xc-y,yc+x,c); set_pixel(xc+y,yc-xy,c); set_pixel(xc-y,yc-x,c);} 结论：Bresenham算法的主要计算量在于决策参数的计算，而决策函数只做4的乘法和加法；因此， Bresenham算法运行速度很快，而且适宜在硬件上实施。

3.3 多边形的扫描转换与区域填充 多边形有两种重要的表示方法：顶点表示和点阵表示。 区域填充算法可分为两大类:扫描转换填充算法、种子填充算法。

3.3.1.1 扫描线算法 1、简单的射线法 多边形内的区域填充的最本质的问题是要找出位于区域内的全部像素，即包容性检测问题。 基本思路：射线法是由被测点向某方向作射线，计算此射线与多边形所有边的交点个数。若交点个数为奇数，则被测点在多边形之内，否则，在多边形之外。

3.3.1.1 扫描线算法 奇异点的处理 左闭右开（上闭下开）：射线左边的边与射线相交时交点有效，应计数；右边的无效，不计数。 水平边的处理 当射线与水平边重合时，不求交。 思路简单，速度极慢

3.3.1多边形的扫描转换 3.3.1.1 扫描线算法 基本思想： 按扫描线顺序，计算扫描线与多边形的相交区间，用要求的颜色显示这些区间的象素。该算法利用了相邻扫描线之间的相关性。

3.3.1多边形的扫描转换 对于一条扫描线填充过程可分为四个步骤： 求 交 求出每一条扫描线与多边形所有边的交点，建立(x,y)交点表，若为水平边则跳过； 排 序 按x及y增加（或减少)的顺序，对这些交点进行排序； 配 对 对排序后的交点进行两两配对，定义填充区域； 填 色 将每对交点之间的所有像素置成所需要的颜色； 关键是交点的配对，但配对有可能出错，因为存在奇异点问题。

3.3.1.1 扫描线算法 问题一：奇 异 点 第一类：P2、P4、P5、P6；必须计2次交点；相邻两边不时单调向上或向下；

3.3.1多边形的扫描转换 奇 异 点 的 解 决 办 法 第一类：P2、P4、P5、P6；相邻两边不时单调向上或向下；计2次交点； 方法一： 第一类：P2、P4、P5、P6；相邻两边不时单调向上或向下；计2次交点； 第二类：P1、P3；相邻两边单调向上或向下；计1次交点； 方法二： 第一类：P2、P4、P5、P6；必须计2次交点；相邻两边不时单调向上或向下；不做处理； 第二类：P1、P3；只需计1次交点；相邻两边单调向上或向下；将其中一条边的y值抬高一个像素。

3.3.1多边形的扫描转换 问题二：增量计算的应用 xi+1 = xi+ 1/m （m为边的斜率） yi+1 ∆y yi xi xi+1

3.3.1多边形的扫描转换 问题三：如何减少交点计算的工作量 解决办法： 利用相邻扫描线之间的相关性，构造AET（Active Eges Table）表，表中只记录与当前扫描线相交的活动边，而且这些边按照与扫描线y交点的x坐标排序，以便交点匹配和填充。 先构造便表（ET），再构造AET。

3.3.1多边形的扫描转换 边表（NET）： NET由bucket构成，bucket的数目与扫描线线数相同； 存放在该扫描线第一次出现的边。若某边的较低端点为ymin，则该边就放在扫描线ymin的边表中； 结点包括每条边两端点中最大的y坐标值（ymax），y值较小的那个端点的x坐标值（xmin）以及该边的斜率的倒数(1/m)，如下图所示。 1/m ymin ymax 指针

3.3.1多边形的扫描转换

3.3.1多边形的扫描转换 AET表 活性边表(AET)：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中。 结点内容（同NET表） x：当前扫描线与边的交点坐标 1/m：从当前扫描线到下一条扫描线间x的增量 ymax：该边所交的最高扫描线号ymax

3.3.1多边形的扫描转换 多边形的扫描线算法如下： 将y值设置为ET中所列的最小y值，也即第一个非空的bucket; 将AET初始化，使其为空； 重复做以上各步，直至AET和ET都为空为止。 把ET中y的信息与AET合并，同时保准AET中按x值实现排序； 对于扫描线y，在一对交点之间填充所需要的像素颜色； 从AET中删除y>ymax的项；……？ 对于仍留在AET中的每一项，用x+1/m代替x；……？ 检查并保证AET中各项按x值的排序； 使y增1，成为下一条扫描线的坐标。

y x 1 2 3 4 5 6 7 8 9 10 11 P6 P4 P1 P5 P2 P3 8 7 6 5 4 3 2 1 ∧ . -1.5 11 -3 P4P5 P5P6 P3P4 P6P1 P1P2 P2P3 5 -3 2 . 3 ∧ P1P2 P2P3 y=1 2 7 . 8 3 ∧ P6P1 P2P3 y=2 2 7 . 11 8 ∧ P6P1 P3P4 y=3 2 7 . 11 8 ∧ P6P1 P3P4 y=4 5 2 8 . P4P5 11 ∧ P3P4 -1.5 7 P5P6 P6P1 y=5 7 2 8 . P4P5 11 ∧ P3P4 3.5 -1.5 P5P6 P6P1 y=6 9 2 8 . P4P5 11 ∧ P3P4 y=7

3.3.1多边形的扫描转换 优点： 对每个像素只访问一次 与设备无关 缺点： 数据结构复杂 只适合软件实现

3.3.1.2边界标志算法 基本思想： 帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。 然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。 使用一个布尔量inside来指示当前点是否在多边形内的状态。

边界标志算法过程 void edgemark_fill(polydef, color) 多边形定义 polydef； int color; inside = FALSE; for (每条与多边形polydef相交的扫描线y ) for (扫描线上每个象素x ) { if(象素 x 被打上边标志) inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); }

3.3.1.2边界标志算法 用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同， 但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。

3.3.2区域填充算法 区域指已经表示成点阵形式的填充图形，它是象素的集合。 区域可采用内点表示（内定义区域interior-defined） 和边界表示（边界定义区域boundary-defined）。 区域可分为4向连通区域和8向连通区域。 区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的

3.3.2区域填充算法 4向连通区域和8向连通区域 四个方向运动 八个方向运动 四连通区域 八连通区域

1、漫水法（flood-fill algorithm) 3.3.2.1区域填充的递归算法 简单的种子填充算法 1、漫水法（flood-fill algorithm) 基本方法：首先在区域内侧是一点（x，y）的像素值，看其是否具有原始给定的值，也即决定该点是否在区域内未被填充过。如果是，则改变其颜色或亮度值。然后再在其四个方向或八个方向上扩展，继续测试，通过递归调用，实现四连通或八连通的区域填充。 适用于内定义区域。

3.3.2.1区域填充的递归算法 简单的种子填充算法 2、边界填充算法 基本方法：测试（x，y）的像素是否在区域内又未被访问过，①与边界值比较，以检测此像素是否为该区域的一部分；②与新值比较，以决定该像素是否已被访问过。测试的前提是：在初始状态，区域内没有一个像素已设置为新值。但，允许新值等于边界值。适用于内定义区域。

3.3.2.1区域填充的递归算法 2、边界填充算法 基本流程 种子像素压入堆栈； 当堆栈非空时， 从堆栈中推出一个像素，并将该像素置成所要的值； 对于每个与当前像素邻接的四连通或八连通像素，进行上述两部分内容的测试； 若所测试的像素在区域内又未被填充过，则将该像素压入堆栈。

3.3.2.1区域填充的递归算法 2、边界填充算法 算法的缺点 深度递归，栈有可能溢出； 使栈极小化的一种算法是：在任意不间断的扫描线区段中，只取一个种子像素，称为扫描线种子填充算法。

3.3.2.1区域填充的递归算法 内点表示的4连通区域的递归填充算法: void FloodFill4(int x,int y,int oldcolor,int newcolor) { if(getpixel(x,y)==oldcolor) //属于区域内点oldcolor { drawpixel(x,y,newcolor); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); FloodFill4(x-1,y,oldcolor,newcolor); FloodFill4(x+1,y,oldcolor,newcolor); }

3.3.2.1区域填充的递归算法 边界表示的4连通区域的递归填充算法: void BoundaryFill4(int x,int y,int boundarycolor,int newcolor) { int color; if(color!=newcolor && color!=boundarycolor) { drawpixel(x,y,newcolor); BoundaryFill4 (x,y+1, boundarycolor,newcolor); BoundaryFill4 (x,y-1, boundarycolor,newcolor); BoundaryFill4 (x-1,y, boundarycolor,newcolor); BoundaryFill4 (x+1,y, boundarycolor,newcolor); }