假定当前扫描线与多边形某一条边的交点的x坐标为x,则下一条扫描线与该边的交点不要重计算,只要加 个增量△x。设该边的直线方程为:ax+by+c=0 若y=y,x=xi:则当y=yin时, 1(by1 b △x 其中 为常数 另外使用增量法计算时,我们需要知道一条边何时不再与下一条扫描线相交,以便及时把它从活性边表 中删除出去。综上所述,活性边表的结点应为对应边保存如下内容:第1项存当前扫描线与边的交点坐标x 值:第2项存从当前扫描线到下一条扫描线间ⅹ的增量Δx:第3项存该边所交的最高扫描线号y 为了方便活性边表的建立与更新,我们为每一条扫描线建立一个新边表(NET),存放在该扫描线第一次出 现的边。也就是说,若某边的较低端点为y細,则该边就放在扫描线y的新边表中。 76543210 P4P5 P5P6 28·5+1.57 )|8A [2|07A 532-[51313∧ 图2.3.4上图所示各条扫描线的新边表NET 算法过程 void polyfill (polygon, color) int color;多边形 polygon for(各条扫描线i) 初始化新边表头指针NET 把ymn=i的边放进边表NET[i] y=最低扫描线号: 初始化活性边表AET为空; for(各条扫描线i) 把新边表NET[订]中的边结点用插入排序法插入AET表,使之按x坐标递增顺序排列 遍历AET表,把配对交点区间(左闭右开)上的象素(x,y),用 drawpixel(x,y, color)改写象素颜 色值 遍历AET表,把y==i的结点从AET表中删除,并把ymx>i结点的x值递增x 若允许多边形的边自相交,则用冒泡排序法对AET表重新排序 1 /* polyfill * 扫描线与多边形顶点相交时,必须正确的交点的取舍 扫描线与多边形相交的边分处扫描线的两侧,则计一个交点,如点P,P6 扫描线与多边形相交的边分处扫描线同侧,且y<y,y<ym,则计2个交点(填色),如P2。若y>yi y,则计0个交点(不填色),如P1 扫描线与多边形边界重合(当要区分边界和边界内区域时需特殊处理),则计1个交点。 具体实现时,只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2 来决定。 计算机图形学第二章第23页共27页
计算机图形学 第二章 第 23 页 共 27 页 假定当前扫描线与多边形某一条边的交点的 x 坐标为 x，则下一条扫描线与该边的交点不要重计算，只要加 一个增量△x。设该边的直线方程为：ax+by+c=0； 若 y＝yi，x=x i；则当 y = y i+1时， 其中 为常数， 另外使用增量法计算时，我们需要知道一条边何时不再与下一条扫描线相交，以便及时把它从活性边表 中删除出去。综上所述，活性边表的结点应为对应边保存如下内容：第 1 项存当前扫描线与边的交点坐标 x 值；第 2 项存从当前扫描线到下一条扫描线间 x 的增量 x；第 3 项存该边所交的最高扫描线号 ymax。 为了方便活性边表的建立与更新，我们为每一条扫描线建立一个新边表（NET）,存放在该扫描线第一次出 现的边。也就是说，若某边的较低端点为 ymin，则该边就放在扫描线 ymin的新边表中。 图 2.3.4 上图所示各条扫描线的新边表 NET 算法过程 void polyfill (polygon, color) int color;多边形 polygon; { for (各条扫描线 i ) { 初始化新边表头指针 NET [i]； 把 y min = i 的边放进边表 NET [i]; } y = 最低扫描线号； 初始化活性边表 AET 为空； for (各条扫描线 i ) { 把新边表 NET[i]中的边结点用插入排序法插入 AET 表，使之按 x 坐标递增顺序排列； 遍历 AET 表，把配对交点区间(左闭右开)上的象素(x, y)，用 drawpixel (x, y, color) 改写象素颜 色值； 遍历 AET 表，把 y max= i 的结点从 AET 表中删除，并把 y max > i 结点的 x 值递增 x； 若允许多边形的边自相交，则用冒泡排序法对 AET 表重新排序； } } /* polyfill */ 扫描线与多边形顶点相交时，必须正确的交点的取舍。 · 扫描线与多边形相交的边分处扫描线的两侧，则计一个交点，如点 P5，P6。 · 扫描线与多边形相交的边分处扫描线同侧，且 yi<yi-1，yi<yi+1，则计 2 个交点(填色)，如 P2。 若 yi>yi-1， yi>yi+1，则计 0 个交点(不填色)，如 P1。 · 扫描线与多边形边界重合 (当要区分边界和边界内区域时需特殊处理)，则计 1 个交点。 具体实现时，只需检查顶点的两条边的另外两个端点的 y 值。按这两个 y 值中大于交点 y 值的个数是 0,1,2 来决定
P4/P3 图2.3.5扫描线与多边形相交,特殊情况的处理 2.3.1.2边界标志算法 边界标志算法的基本思想是:在帧缓冲器中对多边形的每条边进行直线扫描转换,亦即对多边形边界所 经过的象素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。对 每条与多边形相交的扫描线依从左到右的顺序,逐个访问该扫描线上的象素。使用一个布尔量 inside来指 示当前点是否在多边形内的状态。 Inside的初值为假,每当当前访问的象素为被打上边标志的点,就把 inside取反。对未打标志的象素, inside不变。若访问当前象素时, inside为真,说明该象素在多边形内 则把该象素置为填充颜色 边界标志算法 void edgemark fill(pol ydef, color 多边形定义 polytef: int cold 对多边形 polytef每条边进行直线扫描转换 inside False for(每条与多边形 polytef相交的扫描线y) for(扫描线上每个象素x) if(象素x被打上边标志) inside=!( inside) if(inside!= FALSE) drawpixel (x, y, color) else drawpixel (x, y, background) 图2.3.6正方形内切n个圆的边界标志算法 用软件实现时,扫描线算法与边界标志算法的执行速度几乎相同,但由于边界标志算法不必建立维护边 表以及对它进行排序,所以边界标志算法更适合硬件实现,这时它的执行速度比有序边表算法快一至两个 数量级 2.3.2区域填充算法 这里讨论的区域指已经表示成点阵形式的填充图形,它是象素的集合。区域可采用内点表示和边界表示 两种表示形式。在内点表示中,区域内的所有象素着同一颜色。在边界表示中,区域的边界点着同一颜色 区域填充指先将区域的一点赋予指定的颜色,然后将该颜色扩展到整个区域的过程 区域填充算法要求区域是连通的,因为只有在连通区域中,才可能将种子点的颜色扩展到区域内的其它 点。区域可分为4向连通区域和8向连通区域。4向连通区域指的是从区域上一点出发,可通过四个方向, 即上、下、左、右移动的组合,在不越出区域的前提下,到达区域内的任意象素:8向连通区域指的是从区 域内每一象素出发,可通过八个方向,即上、下、左、右、左上、右上、左下、右下这八个方向的移动的 ●●● 组合来到达 四个方向运动八个方向运动 四连通区域 八连通区域 ●●●● 图2.3.7四连通区域和八连通区域 ●●● 计算机图形学第二章第24页共27页
计算机图形学 第二章 第 24 页 共 27 页 图 2.3.5 扫描线与多边形相交，特殊情况的处理 2.3.1.2 边界标志算法 边界标志算法的基本思想是：在帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所 经过的象素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。对 每条与多边形相交的扫描线依从左到右的顺序，逐个访问该扫描线上的象素。使用一个布尔量 inside 来指 示当前点是否在多边形内的状态。Inside 的初值为假，每当当前访问的象素为被打上边标志的点，就把 inside 取反。对未打标志的象素，inside 不变。若访问当前象素时，inside 为真，说明该象素在多边形内， 则把该象素置为填充颜色。 边界标志算法： void edgemark_fill(polydef, color) 多边形定义 polydef； int color; { 对多边形 polydef 每条边进行直线扫描转换； inside = FALSE; for (每条与多边形 polydef 相交的扫描线 y ) for (扫描线上每个象素 x ) { if(象素 x 被打上边标志)inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); } } 图 2.3.6 正方形内切 n 个圆的边界标志算法 用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不必建立维护边 表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个 数量级。 2.3.2 区域填充算法 这里讨论的区域指已经表示成点阵形式的填充图形，它是象素的集合。区域可采用内点表示和边界表示 两种表示形式。在内点表示中，区域内的所有象素着同一颜色。在边界表示中，区域的边界点着同一颜色。 区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。 区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种子点的颜色扩展到区域内的其它 点。区域可分为 4 向连通区域和 8 向连通区域。4 向连通区域指的是从区域上一点出发，可通过四个方向， 即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意象素；8 向连通区域指的是从区 域内每一象素出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的 组合来到达。 四个方向运动 八个方向运动 四连通区域 八连通区域 图 2.3.7 四连通区域和八连通区域
●表示内点○表示边界点 图2.3.8区域的内点表示和边界表示 2.3.2.1区域填充的递归算法 以上讨论的多边形填充算法是按扫描线顺序进行的。种子填充算法假设在多边形内有一象素已知,由此 出发利用连通性找到区域内的所有象素 设(xy)为内点表示的4连通区域内的一点, oldcolor为区域的原色,要将整个区域填充为新的颜色 newcolor。内点表示的4连通区域的递归填充算法 void FloodFill4(int x, int y, int oldcolor int newcolor) f(getpixel(x, y)==oldcolor i drawpixel(x,y, newcolor) FloodFill4(x, y+1, oldcolor, newcolor) FloodFill4(x, y-1, oldcolor, newcolor) FloodFil4(X-1,y, oldcolor, newcolor) FloodFill4(+1, y, oldcolor, newcolor) 边界表示的4连通区域的递归填充算法 void BoundaryFill4(nt x, int y int boundarycolor, int newcolor) f int color if(colorl=newcolor & colorl=boundarycolor) i drawpixel(x,y, newcolor) Boundary Fill4(x, y+1, boundarycolor, newcolor) Boundary Fill4 (x, y-1, boundarycolor, newcolor) oundary Fill4 (X-1,y, boundarycolor, newcolor Boundary Fill4 (X+1,y, boundarycolor, newcolor) 对于内点表示和边界表示的8连通区域的填充,只要将上述相应代码中递归填充相邻的4个象素增加到递 归填充8个象素即可 2.3.22区域填充的扫描线算法 区域填充的递归算法原理和程序都很简单,但由于多次递归,费时、费内存,效率不高。为了减少递归 次数,提高效率可以采用采用扫描线算法。算法的基本过程如下:当给定种子点(X,y)时,首先填充种子点 所在扫描线上的位于给定区域的一个区段,然后确定与这一区段相连通的上、下两条扫描线上位于给定区 域内的区段,并依次保存下来。反复这个过程,直到填充结束 区域填充的扫描线算法可由下列四个步骤实现: (1)初始化:堆栈置空。将种子点(x,y)入栈 (2)出栈:若栈空则结束。否则取栈顶元素(X,y),以y作为当前扫描线。 (③)填充并确定种子点所在区段:从种子点(X,y)出发,沿当前扫描线向左、右两个方向填充,直到边界 分别标记区段的左、右端点坐标为x和xr (4)并确定新的种子点:在区间[,xr中检査与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非 边界、未填充的象素,则把每一区间的最右象素作为种子点压入堆栈,返回第(2)步 typedef struct∥记录种子点 int y: I Seed void ScanLineFill4(int x, int y, COLORREF oldcolor, COLORREF newcolor) int xl. xr, i bool spanNeedFill 计算机图形学第二章第25页共27页
计算机图形学 第二章 第 25 页 共 27 页 图 2.3.8 区域的内点表示和边界表示 2.3.2.1 区域填充的递归算法 以上讨论的多边形填充算法是按扫描线顺序进行的。种子填充算法假设在多边形内有一象素已知，由此 出发利用连通性找到区域内的所有象素。 设（x,y）为内点表示的 4 连通区域内的一点，oldcolor 为区域的原色，要将整个区域填充为新的颜色 newcolor。内点表示的 4 连通区域的递归填充算法: void FloodFill4(int x,int y,int oldcolor,int newcolor) { if(getpixel(x,y)==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); } } 边界表示的 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); } } 对于内点表示和边界表示的 8 连通区域的填充，只要将上述相应代码中递归填充相邻的 4 个象素增加到递 归填充 8 个象素即可。 2.3.2.2 区域填充的扫描线算法 区域填充的递归算法原理和程序都很简单，但由于多次递归，费时、费内存，效率不高。为了减少递归 次数，提高效率可以采用采用扫描线算法。算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点 所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区 域内的区段，并依次保存下来。反复这个过程，直到填充结束。 区域填充的扫描线算法可由下列四个步骤实现： (1)初始化：堆栈置空。将种子点（x，y）入栈。 (2)出栈：若栈空则结束。否则取栈顶元素（x，y），以 y 作为当前扫描线。 (3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。 分别标记区段的左、右端点坐标为 xl 和 xr。 (4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线 y 上、下相邻的两条扫描线上的象素。若存在非 边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。 typedef struct{ //记录种子点 intx; int y； } Seed; void ScanLineFill4(int x,int y,COLORREF oldcolor,COLORREF newcolor) { int xl,xr,i; bool spanNeedFill;
Seed pt setstackemptyo pt.x =X, pt.y=y stackpush(pt);∥将前面生成的区段压入堆栈 while(lisstackemptyo) i pt= stackpopO y=pt. y: X=pt.X while( getpixel(xy)=≡ oldcolor)∥向右填充 i drawpixel(x, y, newcolor); Xr=x-1 x=pt.x-1 whle( gepiⅸxel(xy)=≡ oldcolor)∥向左填充 drawpixel(x,y, newcolor x|=x+1 ∥0理上面一条扫描线 x=XI: while(X<x I spanNeedFill=FALSE while(getpixel(x, y)==oldcolor) i spanNeedFil=TRUE if(spanNeedFill I pt. XX-1: pt. y=y stackpush(pt); spanNeedFil=FALSE; while(getpixel(x, y)l=oldcolor & x<xr)X++ H/End of while(isxr) ∥处理下面一条扫描线,代码与处理上面一条扫描线类似 x=XI: 2; while(X<xr HEnd of while(isxr) H/End of while(lisstackempty o) 上述算法对于每一个待填充区段,只需压栈一次:而在递归算法中,每个象素都需要压栈。因此,扫描 线填充算法提高了区域填充的效率。 24字符 字符指数字、字母、汉字等符号。计算机中字符由一个数字编码唯一标识。国际上最流行的字符集是“美 国信息交换用标准代码集”简称ASCⅠI码。它是用7位二进制数进行编码表示128个字符,包括字母、标点、 运算符以及一些特殊符号。我国除采用 ASCII码外,还另外制定了汉字编码的国家标准字符集GB2312-80。 该字符集分为94个区,94个位,每个符号由一个区码和一个位码共同标识。区码和位码各用一个字节表示 为了能够区分 ASCII码与汉字编码,采用字节的最高位来标识:最高位为0表示 ASCII码:最高位为1表 示表示汉字编码 为了在显示器等输出设备上输出字符,系统中必须装备有相应的字库。字库中存储了每个字符的形状信 息,字库分为矢量和点阵型两种 241点阵字符 在点阵字符库中,每个字符由一个位图表示。该位为1表示字符的笔画经过此位,对应于此位的象素应 置为字符颜色。该位为0表示字符的笔画不经过此位,对应于此位的象素应置为背景颜色。在实际应用中 计算机图形学第二章第26页共27页
计算机图形学 第二章 第 26 页 共 27 页 Seed pt; setstackempty(); pt.x =x; pt.y=y; stackpush(pt); //将前面生成的区段压入堆栈 while(!isstackempty()) { pt = stackpop(); y=pt.y; x=pt.x; while(getpixel(x,y)==oldcolor) //向右填充 { drawpixel(x,y,newcolor); x++; } xr = x-1; x = pt.x-1; while(getpixel(x,y)==oldcolor) //向左填充 { drawpixel(x,y,newcolor); x--; } xl = x+1; //处理上面一条扫描线 x = xl; y = y+1; while(x<xr) { spanNeedFill=FALSE; while(getpixel(x,y)==oldcolor) { spanNeedFill=TRUE; x++; } if(spanNeedFill) { pt.x=x-1;pt.y=y; stackpush(pt); spanNeedFill=FALSE; } while(getpixel(x,y)!=oldcolor && x<xr) x++; }//End of while(i<xr) //处理下面一条扫描线，代码与处理上面一条扫描线类似 x = xl; y = y-2; while(x<xr) { .... }//End of while(i<xr) }//End of while(!isstackempty()) } 上述算法对于每一个待填充区段，只需压栈一次；而在递归算法中，每个象素都需要压栈。因此，扫描 线填充算法提高了区域填充的效率。 2.4 字符 字符指数字、字母、汉字等符号。计算机中字符由一个数字编码唯一标识。国际上最流行的字符集是“美 国信息交换用标准代码集”简称 ASCII 码。它是用 7 位二进制数进行编码表示 128 个字符，包括字母、标点、 运算符以及一些特殊符号。我国除采用 ASCII 码外，还另外制定了汉字编码的国家标准字符集 GB2312－80。 该字符集分为 94 个区，94 个位，每个符号由一个区码和一个位码共同标识。区码和位码各用一个字节表示。 为了能够区分 ASCII 码与汉字编码，采用字节的最高位来标识：最高位为 0 表示 ASCII 码；最高位为 1 表 示表示汉字编码。 为了在显示器等输出设备上输出字符，系统中必须装备有相应的字库。字库中存储了每个字符的形状信 息，字库分为矢量和点阵型两种。 2.4.1 点阵字符 在点阵字符库中，每个字符由一个位图表示。该位为 1 表示字符的笔画经过此位，对应于此位的象素应 置为字符颜色。该位为 0 表示字符的笔画不经过此位，对应于此位的象素应置为背景颜色。在实际应用中