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

Presentation on theme: "第4章 基本光栅图形算法."— Presentation transcript:

1 第4章 基本光栅图形算法

2 主要内容 光栅图形生成算法是计算机图形学的基础，本章主要包括直线和圆弧的生成算法、多边形的填充以及其他相关的图形基本元素的生成算法。
直线和圆弧等是图形的基本元素，生成基本元素算法的效率对图形系统的效率有直接关系。虽然很多智能绘图机和图形显示器都有自己生成直线和圆弧的功能，但也有很多情况下要自己编写一些设备的驱动程序，在图形软件包中用软件生成直线和圆弧有时也是十分必要的。 多边形的填充算法是面显示的基础，其思想可用于解决计算机图形学中的消隐、真实感显示等许多问题，本章主要讨论此类图元的绘制问题。

3 主要章节 4.1 直线生成算法 4.2 圆弧生成算法 4.3 多边形的填充 4.4 区域填充 4.5 光栅图形的反走样算法

4 4.1直线生成算法 数学上的直线 光栅化的直线 常用算法 屏幕坐标系
理想的直线是没有宽度的，是由无数个点构成的集合 光栅化的直线 在光栅的有限像素点阵中，确定最佳逼近于该直线的一组像 素，用这些像素表示该直线。 常用算法 DDA方法\正负法\Bresenham算法 屏幕坐标系 产生光栅图形，首先要为每个像素指定一个惟一坐标，因此需要在屏幕上建立一个坐标系，每个像素中心的坐标为该像素的坐标,坐标均为整数 图 4.1 像素和坐标的对应关系 (a) (b)

5 直线的三种表示 显示 Y=kx+b 隐式 ax+by+c=0 参数 P(t)=(1-t)P0+tP1

6 4.1.1生成直线的DDA算法 设直线的起点为(xs,ys),终点为（xe,ye）, 并设(xs,ys)和（xe,ye）都是整数（做求整处理）。 令Δx= xe–xs,Δy= ye–ys。则直线的参数方程是 (4.1) 图4.2 图中黑圆点表示用DDA法生成的直线 目标是能快速地求出能很好地表示直线的像素。 提高速度的方法之一是:乘法用加法实现，用等步长计算直线上的点 。 设 是第i步得到的直线上的点，则直线上第个i+1点是( , ),其中 (4.2)

7 生成直线的DDA算法 当 ,即直线斜率小于1时应使x方向每次增加1，y方向最多增加1，此时取 . 当 时，直线斜率大于1，取 所以
当 时，直线斜率大于1，取 图4.2 图中黑圆点表示用DDA法生成的直线 所以 用式4.2可求得图4.2中直线 上用三角形表示的点，但显示时要用像素表示，可用舍入的办法得到最靠近三角形的像素，用这些像素表示直线，这个方法称为DDA方法。 DDA算法的缺点:计算量较大， 产生一个像素需要2次加法，2次取整运算。 算法还需要除法运算，增加了硬件实现上的困难。

8 4.1.2正负法 基本原理： 为讨论方便，假设直线斜率在0和1之间。
图4.3 正负法每步迭代涉及的象素和中点示意图 为讨论方便，假设直线斜率在0和1之间。 假设 是直线上的一点（ 表示），与P最近的像素为（ ）( 表示 )，那么下一个与直线最近的像素只能是正右方的 或右上方的 两者之一。以M表示 和 的中点，Q是直线与垂线 的交点。 显然，若M在Q的下方，则 离直线近，应取 为下一个像素，否则应取

9 正负法算法的具体实现 设直线的起点和终点分别为(x0,y0)和(x1,y1),直线方程为: 其中 ， ， 分别对应于点 在直线上、上方和下方
其中 ， ， 分别对应于点 在直线上、上方和下方 要判断M在直线的上方还是下方，只需把M代入，判断它的符号即可。构造判别式 P2 P1 d<0，Q在M上方，取P2为下一像素 d>0，取P1为下一像素， d=0,可在两个点中任取一个，约定取右下方的点。

10 正负法算法的具体实现 在d>=0，取右下方像素P1 ，下一个像素应取哪个，应计算 若d<0，则取右上方像素 P2，并计算
讨论d的初始值，第一个像素应取 (x0,y0) 由于(x0,y0)在直线上，故F(x0,y0)=0。因此，

11 正负法程序 while(x<x1){ void MidpointLine(int x0,int y0,int x1,int y1)
if(d<0){ x++; y++; d += delta2; }else{ x++; d += delta1; } glBegin(GL_POINTS); glVertex2s(x,y); glEnd(); } //End While } //End MidpointLine 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();

12 4.1.3Bresenham算法 令m=△y/△x, 考虑0≤m≤1 (4.4) x方向增加1, y方向增加m
yi+1=yi+m(xi+1–xi)=yi+m (4.5) 由起点(xs,ys),可求得直线上的点(xi，yi), i=1,2,3,…, 其中 x1= xs, y1= ys 用坐标为(xi，round(yi))的象素来表示直线上的点 下面考虑如何快速地求出直线上的点 图 的几何意义 ε(x) 设B点是直线上的点，其坐标为(xi+1,yi+1)，点(xi+1,yi+1,r)只能从C或D点中选。 设A为CD边的中点，若B在A点上面则应取D点作为(xi+1,yi+1,r),否则应取C点。 ε(xi+1)=yi+1–(yir+ yir+1)/2 =yi+1–yir–0.5 ε(xi+1)用来判断取C或D

13 yi+1，r= yir ， 若ε(xi+1)< 0 B在A点下面
Bresenham算法 ε(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)< 0

14 Bresenham算法 ε(xi+2) 设xs和ys均为整数, 程序 其中dy=ye–ys，dx=xe–xs。 缺点：有除法和浮点数
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– (ε(xi+1) =yi+1–yir–0.5) m=(double)dy/(double)dx； e = m–0.5； for(i=0;i<dx;i++) { gl_Point(x,y); if(e>=0){ y=y+1； e=e–1; } x=x+1；e=e+m; 其中dy=ye–ys，dx=xe–xs。 程序 缺点：有除法和浮点数

15 4.1.4生成直线算法的进一步改进 设0 ≤ m ≤1，每循环一次绘制二个象素。 当yi+2–yir≤0.25×2时绘pattern1
xi xi+1 xi+2 图4.6四种绘制模式

16 递推公式

17 一般情况的讨论 当直线斜率m的 绝对值很小时，同一像素行上可以连续出现很多个表示直线的像素点，每循环一次有可能同时填充多个像素，
某些图形加速卡也具有在一个像素行上平行填充多个像素的功能。 图4.7当|m|较小的情况时 返回

18 4.2圆弧生成算法 4.2.1正负法 本节仅考虑圆心在原点的情况 正负法 Bresenham法 多边形迫近法
（0，0） 4.2.1正负法 设圆的圆心在(0,0),半径为R,则圆的方程为 F(x,y)=x2+y2–R2=0 当点(x,y)在圆内时, F(x,y)<0。 当点(x,y)在圆外时，F(x,y)>0。 图4.8 对弧AB上点的取法

19 正负法基本思想 第1步：x0=0，y0=R 第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+1 o

20 F(xi+1,yi+1)=F(xi,yi)+2xi+1 F(xi,yi) >0时，则 xi+1= xi, yi+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)的公式 x0=0，y0=R F（xi,yi）=0 F(xi,yi)≤0时，则 xi+1= xi+1, yi+1= yi F(xi+1,yi+1)=F(xi,yi)+2xi+1 F(xi,yi) >0时，则 xi+1= xi, yi+1= yi-1 F(xi+,yi+1)=F(xi,yi)-2yi+1 正负法显示圆弧时可不用除法，而且计算时全为整型数，这很适合于用硬件来实现。

21 4.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) x y Li Hi Pi-1 图4.9 七个对称点 考虑应选哪一个 图4.10 两个候选点

22 选点的判别式 计算di 令D(P)=(x2+y2)-R2 di=D(Hi)+D(Li) 当di=0，点Hi和Li距弧AB的距离相等。
当di<0时，|D(Hi)|<|D(Li)|，取Hi来显示弧AB； 当di≥0时，|D(Hi)|>|D(Li)|，取Li来显示弧AB。 x y Li Hi Pi-1 计算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

23 选点的判别式 程序 di=(x2i+y2i-1-R2)+(x2i+(yi-1-1)2-R2)
Li Hi Pi-1 图4.10 两个候选点 di=(x2i+y2i-1-R2)+(x2i+(yi-1-1)2-R2) =2x2i+2y2i-1-2yi-1-2R (4.20) di+1=(xi+1)2+y2i-R2+(xi+1)2+(yi-1)2-R2 =2x2i+4xi+2y2i-2yi-2R (4.21) xi= xi-1+1 当di<0时,点Hi被选中, yi=yi-1，由 (4.5)- (4.6) 得 di+1= di+ 4xi+2= di+ 4xi (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) (4.23) 程序 x0=0, y0=R，d1 =3–2*R 当di<0时 ， di+1=di+ 4xi xi= xi-1+1 当di≥0时， di+1=di+4(xi-1-yi-1)+10 xi= xi-1+1，yi= yi-1-1 Bresenham算法在候选的两个像素和中，总是选定离圆弧最近的像素为圆弧的一个近似点， 因此，Bresenham算法比正负法决定的像素更合理。

24 4.2.3圆弧的离散生成 前面的算法对于生成完整的圆和四分之一或八分之一圆弧是很方便和快速的，但是如果生成任意的圆弧，前面的算法就不是很方便
下面给出的圆弧离散生成算法，可以很容易地生成任意的圆弧 该算法的基本思想 就是将整个圆弧等分成一段段的短直线，用这些短直线形成的折线来逼近圆弧， 为了获得这些短直线，只需按一定的方式计算给定圆弧轨迹上一系列顶点，短直线的绘制可采用直线的生成算法， 如果将圆弧分割的足够密，则短直线将足够短，形成的折线将可以和圆弧接近到任意程度，因此在允许的误差范围内，可以用显示折线代替显示圆弧。

25 圆弧的离散生成 图4.11 用正多边形迫近圆弧法 设圆的圆心为c(0,0),半径为R。假设圆弧的起始角和终止角分别为α0和α1，把圆弧分割为n份，则两个顶点之间的夹角为 α=（ α1 - α0 ）/n 。 设顶点序列的第i个点为 的幅角为 （如图），则下一个顶点Pi+1的坐标为 或者用矩阵表示为 计算一个点 只要作四次乘法。

26 椭圆弧的离散生成 由此可得椭圆的递推公式 该椭圆的参数方程为 设顶点序列的第i个顶点为 其中 则 的坐标满足

27 4.2.4椭圆生成算法 椭圆的方程： F(x,y)=b2x2+a2y2-a2b2=0
二分量相等 法向量 上半部分 下半部分 椭圆的方程： F(x,y)=b2x2+a2y2-a2b2=0 只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。 椭圆上一点处的法向： 在当前点处，法向量的y分量 比x分量大, 即 , 而在下一点，不等式改变方 向，则说明椭圆弧从上部分转入下部分 图4.12 第一象限的椭圆弧

28 上半部分绘制 计算di 是当前像素 根据di的符号来决定下一像素是取正右方的 ， 还是右下方的 。 若di ＜0，中点在椭圆内，取正右方的
下半部分 计算di 是当前像素 根据di的符号来决定下一像素是取正右方的 ， 还是右下方的 。 若di ＜0，中点在椭圆内，取正右方的 新的判别式： 当di ≥0，中点在椭圆外，取右下方的 新的判别式：

29 上半部分绘制 初始条件： (x,y)=(0，b)； d0 =F(1,b-0.5)= b2 +a2(b-0.5)2 -a2b2
下半部分 初始条件： (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 返回

30 4.3多边形的填充 前面讨论的是几何线条的图形生成算法，本节开始讨论区域的显示和处理问题，即面着色的问题 主要讨论多边形区域的面着色问题。
面着色算法分为两大类： 1、扫描线填色（Scan-Line Filling）算法。这类算法建立在多边形边界顶点的矢量形式(几何)数据之上，可用于程序填色，也可用交互填色。 2、种子填色（Seed Filling）算法。这类算法建立在多边形边界或多边形的内点图象(点阵、位图）形式数据之上，并还需提供多边形界内一点的坐标。

31 4.3.1多边形的表示方法 多边形的表示方法：顶点表示和点阵表示。
顶点表示：是用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少，但它不能直观地说明哪些像素在多边形内。 点阵表示：是用位于多边形内的象素的集合来刻划多边形，该方法虽然没有多边形的几何信息，是面着色所需要的图像表示形式。 图4.13 多边形的顶点表示 图4.14 多边形的点阵表示 多边形填充就是把多边形的顶点表示转换为点阵表示，即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。

32 4.3.2多边形填充的扫描线算法 扫描线算法充分利用了相邻象素之间的连贯性，避免了对象素的逐点判断和反复求交的运算 区域的连贯性
P0 P1 P2 P3 P4 P5 P6 P7 图4.15 区域的连续性 P8 区域的连贯性 设多边形P的顶点 又设 是各顶点Pi的纵坐标yi的 递减数列,当 ,屏幕上位 于y= 和y= 两条扫描线之间的长方形区域被多边形P的边分割成若干梯形，它们具有下列性质(设 为整数)： (1)梯形的两底边分别在y= 和y= 两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。 (2) 梯形可分为两类：一类位于多边形P的内部；另一类在多边形P的外部。 (3) 两类梯形在长方形区域{ ， }内相间的排列。

33 2.扫描线的连贯性 设e为一整数 ≥e≥ 。若扫描线y=e与多边形P的边Pi-1Pi相交，则记其交点的横坐标为 设 (4.32)
Xe0 Xe2 Xe3 Xe7 Xe6 Xe4 图4.16 扫描线的连续性 图中 表示在多边形外的区间 ── 表示在多边形内的区间 设e为一整数 ≥e≥ 。若扫描线y=e与多边形P的边Pi-1Pi相交，则记其交点的横坐标为 设 (4.32) 是该扫描线与P的边界各交点横坐标的递增序列。由区域的连贯性可知，此交点序列具有以下性质： (1) l是偶数。 (2) 在该扫描线上，只有区段 l–1位于多边形P内. 以上性质称为扫描线的连贯性

34 3.边的连贯性 若d为一整数，d=e–1，且yi0≥y≥yin；设位于扫描线y=d上的交点序列为
P0 P1 P2 P3 P4 P5 P6 P7 P8 Xe0 Xe2 Xe3 Xe7 Xe6 Xe4 图4.17 边的连续性 Xd0 Xd2 Xd3 Xd7 Xd6 Xd4 若d为一整数，d=e–1，且yi0≥y≥yin；设位于扫描线y=d上的交点序列为 (4.33) 若 成立时，则由区域的连续性可知序列（4.32）和（4.33）之间有以下关系： 两序列元素的个数相等。 点( )与( )位于多边形P的同一边上，即 以上性质称为边的连贯性

35 4.奇点的处理 当扫描线与多边形P的边界的交点是P的顶点时，则称该交点为奇点。
多边形P的顶点可分为两类：极值点和非极值点。如果 则称顶点Pi为极值点；否则称Pi为非极值点。 如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数。若 将每一奇点都简单地计为两个交点，同样会导致反常的结果。 为了使交点个数保持为偶数，规定 当奇点是P的极值点时，该点按两 个交点计算；否则按一个交点计算。 预处理: 若Pi是非极值点，则将 两边中位于扫描线 y=yi上方的那条边在Pi点处截去 一单位长

36 5 . 扫描线算法的数据结构与实现步骤 取 ，求扫描线y=d上的交点序列 ,根据多边形边的连贯性和扫描线的连贯性，按从下到上的顺序求得各条扫描线的交点序列 数据结构 边的分类表ET和边的活化链表AEL ET和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)]

37 扫描线算法的数据结构与实现步骤 边的活化链表AEL由与当前扫描线相交的所有多边形的边组成

38 扫描线算法的数据结构与实现步骤 -5/3 5 7 AEL e0 e5 4 2 12 AEL在y=2扫描线上的状态 -5/3 5 AEL e0
14 AEL在y=3扫描线上的状态 -5/3 5 3 AEL e0 e5 4 2 16 AEL在y=4扫描线上的状态

39 扫描线算法 步骤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

40 4.3.3边缘填充算法 建立ET和AEL时需对多边形的边进行排序,用求余的方法，可免去对边排序
假定A为一正数，数M的余是指A–M，记为 。 =M，对M作偶数次求余运算，其结果是M 图4.21边缘填充算法的过程 边缘填充算法很容易实现，对多边形P的每一非水平边 （i=0,1,…,n） 上的各像素做向右求反运算即可，见图4.21，其中(a)为给定的多边形；(b)为对区域赋初值；(c)，(d)，(e)和(f)表示逐边向右求反。 和扫描线算法比较，边缘填充算法结构都简单但是需对帧缓冲器中的大批元素反复赋值，故速度不比前者快，另外如果区域内原来有其他的颜色，也不能保证最后区域内的颜色是多边形的颜色，对单值图像比较有用。

41 4.3.4边界标志算法 边缘填充算法: 程序和数据结构较简单，但涉及了对帧缓冲器中大量元素的多次赋值而影响了算法的运行效率。
边界标志法: 先画边界后填色，使对帧缓冲器中的每个元素的赋值次数不超过2次。 图4.22边界标志算法的运行过程 基本思想是：先用一种特殊的颜色在帧缓冲器中将多边形的边界(水平边的部分边界除外)勾画出来。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需的颜色

42 边界标志法具体实现 步骤1：以值为boundary-color 的特殊颜色勾画多边形P的边界。设多边形顶点为Pi= (xi, yi),0≤i≤n， xi, yi均为整数；置Pn+1=P0。每一条扫描线上着上这种特殊颜色的点的个数必定是偶数(包括零)。 图4.22边界标志算法的运行过程 步骤2：设interior_point 是一布尔变量。对每一条扫描线从左到右进行搜索，如果当前是像素位于多边形P内，则interior_point=true，需要填上值为polygon_color的颜色；否则该像素在多边形P外，需要填上值为background_color的颜色 返回

43 4.4区域的填充 4.4.1区域的基本概念 区域填充是指先将区域内的一点(常称种子点)赋予给定颜色，然后将这种颜色扩展到整个区域内的过程。
区域是指已经表示成点阵形式的象素集合。 光栅图形中，区域可采用内点表示和边界表示等两种形式进行描述。 内点表示法:把位于给定区域内的所有象素一一列举出来的方法 以内点表示法为基础的区域填充算法称为泛填充算法。 图4.23分别用内点和边界表示的区域 边界表示法: 把位于给定区域的边界上的象素一一列举出来的方法.它 将区域边界上的象素都着上同一种颜色(常称为边界色)。

44 区域的连通性----- 4连通或8连通 4连通的区域: 取区域内任意两点，在该区域内若从其中一点出发通过上、下、左、右四种运动可到达另一点。
图4.25四个方向的运动 图4.26八个方向的运动 4连通的区域: 取区域内任意两点，在该区域内若从其中一点出发通过上、下、左、右四种运动可到达另一点。 8连通区域: 取区域内任意两点，若从其中任一点出发，在该区域内通过沿水平方向、垂直方向和对角线方向的八种运动可到达另一点。 图4.27内点表示的八连通区域 图4.28边界表示的八连通区域 图4.29四连通和八连通区域的不同边界 4连通区域也可理解成8连通区域，但是两者的边界不尽相同。如果图中标有·号的象素组成的区域作为4连通区域，则其边界由图中的标有△号的象素组成。如果将该区域作为8连通的区域，则其边界由图中标有△号和×号的两种象素组成。

45 4.4.2简单的种子填充算法 G: 内点表示的区域，(x, y)是G内一点，old–color是G的原色。
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。然后将该点周围的四个点（四连通）或八个点（八连通）作为新的种子点进行同样的处理，通过这种扩散完成对整个区域的填充

46 4.4.3扫描线种子填充算法 算法的基本思想：首先填充当前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来。反复进行这个过程，直到所保存的各区段都填充完毕。 图4.30扫描线种子填充算法的执行过程 图4.30中的例子是用上述算法得到的结果。图中标上×号的方格是边界点，其颜色值为boundary_color。标有符号·的方格代表给定的种子点。标有斜线的方格表示区域内的像素已填充了new_color新颜色。方格内的数字表示相应像素作为种子点进入堆栈的先后顺序。图（a）表示对种子点所在扫描线区间进行填充的情况和堆栈的状态。（b）表示对下一条扫描区间进行填充的情况和堆栈的状态。（c），（d）类似。 返回

47 4.4.3扫描线种子填充算法 算法步骤： 1）将算法设置的堆栈置为空。将种子点（x, y）压入堆栈。
3）从种子点（x, y）开始，沿纵坐标为y的当前扫描线向左右两个方向逐个像素用新的颜色值进行填充，直到边界为止。设区间两边界的横坐标分别为 和 。 4）在与当前扫描线相邻的上下两条扫描线上，以区间 为搜索范围，求出需要填充的各小区间，把各小区间中最右边的点并作为种子点压入堆栈，转到步骤2。

48 4.5光栅图形的反走样算法 4.5.1 光栅图形的走样现象 表现： 图形的边界一般都呈阶梯形 如图（4.31），（4.32）
图4.31阶梯形边界图 图4.32阶梯形线段 表现： 图形的边界一般都呈阶梯形 如图（4.31），（4.32） 图形的细节失真、狭小图形遗失 如图（4.33),(4.34) （a） 待显示的细小图形 （b） 显示结果 图4.33 细节失真 当在光栅显示器上显示如图4.33所示的细长的矩形时，原细长的矩形被显示成了加宽的矩形。一些狭小的多边形分布在两条扫描线之间，由于它们不覆盖任何一个像素中心，所以没有被显示出来，造成狭小图形的遗失。如图4.34 （a）待显示的狭小矩形 （b） 显示结果 图4.34 狭小图形的遗失

49 4.5.2 提高分辨率的反走样算法 提高分辨率的方法 1. 采用硬件: 采用高分辨率的光栅图形显示器，花费的代价大。
2. 采用软件: 花费的代价小，也容易实现。 用软件提高分辨率的方法是：高分辨率计算，低分辨率显示。 图4.35 加权表 高分辨率计算：将低分辨的图形显示象素划分为许多子象素，如2×2划分，3×3划分等，然后按通常的算法计算出各个子象素的颜色值或灰度值。 低分辨率显示：将一象素内的各个子象素的颜色值或灰度值的平均值作为该象素的颜色值或灰度值。求平均值时可取算术平均，也可取加权平均。 图4.35是两种典型的加权平均方法。

50 4.5.3 线段反走样算法 线段的反混淆算法的基本思想可归纳如下： (1) 把线段看作是有宽度的狭长的矩形如图4.28
(2) 线段具有一定的面积，当线段通过某象素时，可以求出两者面积的交 (3) 根据每一象素与线段相交部分的面积值决定该象素的颜色值或灰度值 图4.36 有宽度的线段 用反混淆算法显示的线段称为反混淆/走样线段。反混淆线段是将位于原相邻阶梯之间的象素置为过渡颜色或灰度，使得颜色或者灰度过渡自然，变化柔和，阶梯被淡化后，线形就显得平直了。 反混淆算法极大地改善了显示时线段的线形质量。由于要计算面积，使得计算量大大增加，速度也由此而减慢，所以它不适合于动态的交互式图形显示。

51 4.5.4多边形反走样算法 多边形的混淆现象主要表现在边界上，可采用反走样线段的思想来改善 计算象素与多边形交的面积很费时间
Pitteway和Watkinson将画线段的Bresenham算法发展成多边形的反走样算法 假定多边形一边的方程为 y = mx, 0≤m≤1 Bresenham算法: 每一步要算出ε(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)的几何意义

52 计算ε(xi+2)的递推公式 ε(xi+1) =yi+1–yir–0.5 yi+1，r= yir ， 若ε(xi+1)< 0
m–1≤ε(xi)<m, i=2, 3,…… 令 di=ε(xi)+1–m di满足0≤di<1 ε(xi+2)= yi+2–yi+1, r–0.5 = yi+1+m–yi+1, r–0.5 由于 能反映 的大小，故可直接用于确定像素 的灰度值。在（4.1.3）节的程序中用d=e+1–m代替e，则可得反走样的多边形边的绘制程序。