第四章多边形填充.ppt

第四章第四章n n有效边表填充算法有效边表填充算法有效边表填充算法有效边表填充算法n n边缘填充算法边缘填充算法边缘填充算法边缘填充算法n n四邻接点种子填充算法四邻接点种子填充算法四邻接点种子填充算法四邻接点种子填充算法n n八邻接点种子填充算法八邻接点种子填充算法八邻接点种子填充算法八邻接点种子填充算法n n扫描线种子填充算法扫描线种子填充算法扫描线种子填充算法扫描线种子填充算法本章学习目标本章学习目标n4.14.1　多边形的扫描转换　多边形的扫描转换 n4.2 4.2 有效边表填充算法有效边表填充算法n4.3 4.3 边缘填充算法边缘填充算法n4.4 4.4 区域填充算法区域填充算法n4.5 4.5 本章小结本章小结n习题习题 4 4本章内容本章内容4.14.1　多边形的扫描转换　多边形的扫描转换 本章将以直线段连接而成的示例多边形为例讲解多边形的填充算法，同时给出图形边界像素的处理原则多边形内部可以使用平面着色模式或光滑着色模式填充无论使用哪种着色模式，都意味着要使用指定颜色为多边形边界内的每一个像素着色  多边形是由折线段组成的封闭图形。

它由有序顶点的点集Pi（i＝0，…，n-1）及有向边的线集Ei（i＝0，…，n-1）定义，n为多边形的顶点数或边数，且Ei＝PiPi+1，i＝0，…，n-1这里Pn＝P0，保证了多边形的闭合多边形可以分为凸、凹多边形以及环 4.1.1 4.1.1 多边形的定义多边形的定义 P0P1P2P3P4P5E0E1E2E3E4E5顺时针逆时针图 4-4 多边形的定义 用多边形的顶点序列来描述特点是直观、占内存少，易于进行几何变换，但由于没有明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换后才能逐条扫描线填充 ⑴⑴顶点表示法顶点表示法⑵⑵点阵表示法点阵表示法 多边形的点阵表示法是用位于多边形内的像素点集来描述，这种表示方法虽然失去了许多重要的集合信息，如顶点、边界等，但便于运用帧缓冲来表示图形，方便直接读取像素来更改多边形的填充色 4.1.2 4.1.2 多边形的表示多边形的表示 ⑶⑶多边形的扫描转换多边形的扫描转换 将多边形的描述从顶点表示法变换到点阵表示法的过程，称为多边形的扫描转换即从多边形的顶点信息出发，求出位于多边形内部的各个像素点信息，并将其颜色值写入帧缓冲的相应单元中。

多边形的顶点表示法 多边形的点阵表示法4.1.3 4.1.3 多边形着色模式多边形着色模式 多边形可以使用平面着色模式（flat shading mode）或光滑着色模式（smooth shading mode）填充平面着色是指多边形所有顶点的颜色都相同，多边形内部具有同顶点一样的颜色光滑着色是指多边形各个顶点的颜色不同，多边形边的颜色是由这条边的两个顶点的颜色插值得到，多边形内部的颜色是由扫描线上共享同一顶点的相邻两条边上的颜色插值得到 光滑着色平面着色实际光强感知光强 马赫带 边界位置的实际光强与感知光强 马赫带（Mach Band）是由灰度接近的矩形块组成在观察明暗变化的边界时，边界处亮度对比度加强，常常在光强阶梯变化的一侧感知到亮度的正向尖峰效果，而在另一侧感知到亮度的负向尖峰效果，使得边界表现得非常明显，这种现象称为马赫带效应马赫带效应不是一种物理现象，而使一种心理现象，夸大了平面着色的渲染效果，使得人眼感觉到的亮度变化比实际的亮度变化要大绘制真实感图形的过程中应尽量避免出现马赫带效应球面的马赫带4.1.4 4.1.4 填充多边形填充多边形 多边形填充的主要算法是扫描线算法。

先确定多边形覆盖的扫描线条数，对每一条扫描线，计算扫描线与多边形边界的交点区间，如果能判断该区间在多边形内部，则将其内的像素绘制为指定的颜色扫描线算法在处理每条扫描线时，需要与多边形的所有边求交，处理效率很低改进的算法是有效边表算法对一条扫描线的填充一般分为以下4个步骤•求交求交：计算扫描线与多边形各边的交点；•排序排序：把扫描线上所有交点按递增顺序进行排序；•配对配对：将第一个交点与第二个交点，第三个交点与第四个交点等等进行配对，每对交点代表扫描线与多边形的一个相交区间•着色着色：把区间内的像素置为填充色4.1.5 4.1.5 填充区域填充区域 区域是指相互连通的一组像素的集合区域通常由一个封闭的边界来定义，处于一个封闭边界线内的所有像素构成一个区域区域内的所有像素着同一填充色，区域的边界色和填充色一般不一致种子填充算法是从区域内的一个种子位置开始，由内向外用填充颜色绘制种子及其相邻像素直到颜色不同的边界像素为止种子填充算法主要分为4邻接点算法和8邻接点算法4.24.2　有效边表填充算法　有效边表填充算法 4.2.1 4.2.1 填充原理填充原理 有效边表填充算法通过维护边表和有效边表，避开了扫描线与多边形所有边求交的复杂运算。

填充原理是按照扫描线从小到大的移动顺序，计算当前扫描线与有效边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，最后用指定颜色填充区间内的所有像素，即完成填充工作有效边表填充算法已成为目前最为有效的多边形填充算法之一 4.2.2 4.2.2 边界像素处理原则边界像素处理原则 填充左下角为（1，1），右上角为（3，3）的正方形时，若将边界上的所有像素全部填充，就得到图示的结果  面积3×3 面积2×2 在多边形填充过程中，常采用“左闭右开”和“下闭上开”的原则对边界像素进行处理 参CDC::FillRect的处理原则：When filling the specified rectangle, FillRect does not include the rectangle’s right and bottom sides.其中CDC使用的设备坐标系与本书自定义的坐标系不同 P6P7P0P5P8P1P4P2边界像素的处理 局部最高点P1、P6和P4，共享顶点的两条边落在扫描线的下方；普通连接点P2，共享顶点的两条边分别落在扫描线两侧；局部最低点P0、P3和P5，共享顶点的两条边落在扫描线的上方。

常根据共享顶点的两条边的另一端的y值大于扫描线y值的个数来将交点个数取为0、1和2事实上，有效边表算法能自动处理这三类顶点处理特殊点 P34.2.3 4.2.3 有效边与有效边表有效边与有效边表 1.1.有效边有效边 多边形与当前扫描线相交的边称为有效边（active edge）在处理一条扫描线时仅对有效边进行求交运算，可以避免与多边形的所有边求交，提高了算法效率有效边上的扫描线由起点到终点每次加1，即像素点的y坐标为y＝y+1，x坐标的变化可以按如下方法推导xi，yi）（xi+1，yi+1）11/k有效边交点相关性（x0，y0）（x1，y1）2.2.有效边表有效边表有效边表结点 class CAET{public: CAET (); virtual ~ CAET (); public: double x; int yMax; double k; // ｝ 有效边表类4.2.4 4.2.4 桶表与边表桶表与边表 从有效边表的建立过程可以看出，有效边表给出了扫描线与有效边交点坐标的计算方法，但是并没有给出新边出现的位置坐标。

为了确定在哪条扫描线上插入了新边，就需要构造一个边表（edge table，ET），用以存放扫描线上多边形各条边出现的信息因为水平边的1/k为∞，并且水平边本身就是扫描线，在建立边表时可以不予考虑1.桶表和边表的表示法桶表和边表的表示法（1）桶表是按照扫描线顺序管理边出现情况的一个数据结构首先，构造一个纵向扫描线链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点称为桶（bucket），对应多边形覆盖的每一条扫描线class CBucket {public:CBucket();virtual ~CBucket();public:int ScanLine; //扫描线CAET *p; //桶上的边表指针CBucket *next;};桶类（2）将每条边的信息链入与该边最小y坐标（ymin）相对应的桶处也就是说，若某边的较低端点为ymin，则该边就存放在相应的扫描线桶中（3）对于每一条扫描线，如果新增多条边，则按x|ymin坐标递增的顺序存放在一个链表中，若x|ymin 相等，则按照1/k由小到大排序，这样就形成边表。

边表结点2.2.桶表与桶表与边表示例边表示例示例多边形4.3 4.3 边缘填充算法边缘填充算法4.3.1 4.3.1 填充原理填充原理 边缘填充算法是先求出多边形的每条边与扫描线的交点，然后将交点右侧的所有像素颜色全部取为补色（或反色）按任意顺序处理完多边形的所有边后，就完成了多边形的填充任务边缘填充算法利用了图像处理中的求“补”或求“反”的概念，对于黑白图像，求补就是把RGB(1,1,1)（白色）的像素置为RGB(0,0,0)（黑色），反之亦然；对于彩色图像，求补就是将背景色置为填充色，反之亦然求补的一条基本性质是一个像素求补两次就恢复为原色如果多边形内部的像素被求补偶数次，保持原色，如果被求补奇数次，显示填充色 假定边的顺序为E0、E1、E2、E3、E4、E5和E6这里，边的顺序并不影响填充结果，只是方便编写循环结构而已填充过程如图所示边缘填充算法定义示例多边形P0（x0，y0）P1（x1，y1）E E0 0E1E2E3E4E5E64.3.2 4.3.2 填充过程填充过程 边缘填充算法原理 void CTestView::FillPolygon(CDC *pDC) {COLORREF BClr=RGB(255,255,255);//背景色COLORREF FClr=GetClr;//填充色int ymin,ymax;//边的最小y值与最大y值double x,y,k;//x,y当前点，k斜率的倒数for(int i=0;i<7;i++)//循环多边形所有边{int j=(i+1)%7;k=(P[i].x-P[j].x)/(P[i].y-P[j].y);//计算1/kif(P[i].yGetPixel(m,Round(y))) pDC->SetPixelV(m,Round(y),BClr);else pDC->SetPixelV(m,Round(y),FClr);}x+=k; } }}4.4 4.4 区域填充算法区域填充算法 种子填充算法是从区域内任一个种子像素位置开始，由内向外将填充色扩散到整个多边形区域的填充过程。

种子填充算法突出的优点是能对具有任意复杂闭合边界的区域进行填充 4.4.1 4.4.1 填充原理填充原理 4.4.2 4.4.2 四邻接点与八邻接点四邻接点与八邻接点 四邻接点定义 八邻接点定义4.4.3 4.4.3 四连通域与八连通域四连通域与八连通域 1.四连通域定义四连通域定义 四连通域及其四连通边界 四连通域及其八连通边界 2.八连通域定义八连通域定义 八连通域及其四连通边界 八连通域及其八连通边界  四邻接点算法填充八连通域 八邻接点算法填充八连通域4.4.4 4.4.4 种子填充算法种子填充算法 1.算法定义算法定义 从种子像素点开始，使用四邻接点方式搜索下一像素点的填充算法称为四邻接点填充算法从种子像素点开始，使用八邻接点方式搜索下一像素点的填充算法称为八邻接点填充算法八邻接点填充算法的设计和四邻接点填充算法基本相似，只要把搜索方式由四邻接点修改为八邻接点即可2.算法原理算法原理 种子填充算法一般要求区域边界色和填充色不同，输入参数只有种子坐标位置和填充颜色。

种子填充算法一般需要使用堆栈数据结构来实现算法原理为：先将种子像素入栈，种子像素为栈底像素，如果栈不为空，执行如下3步操作：⑴栈顶像素出栈；⑵按填充颜色绘制出栈像素⑶按左、右、下、上（或左、左上、上、右上、右、右下、下、左下）顺序搜索与出栈像素相邻的四（八）个像素，若该像素的颜色不是边界色并且未置成填充色，则把该像素入栈；否则丢弃该像素四邻接点填充算法八邻接点填充算法四邻接点填充算法void CTestView::FillPolygon(CDC *pDC)//填充多边形{COLORREF BoundaryClr=RGB(0,0,0);//边界色COLORREF PixelClr;//当前像素的颜色pHead=new CStackNode;//建立栈头结点pHead->next=NULL;//栈的头结点总是为空Push(Seed); //种子像素入栈while(NULL!=pHead->next)//如果栈不为空{CP2 PopPoint;Pop(PopPoint); //种子像素出栈pDC->SetPixelV(Round(PopPoint.x), Round(PopPoint.y),SeedClr);PointLeft.x=PopPoint.x-1;//搜索出栈结点的左方像素PointLeft.y=PopPoint.y;PixelClr=pDC->GetPixel(Round(PointLeft.x), Round(PointLeft.y));if(BoundaryClr!=PixelClr && SeedClr!=PixelClr)Push(PointLeft);//左方像素入栈PointTop.x=PopPoint.x;PointTop.y=PopPoint.y+1;//搜索出栈结点的上方像素PixelClr=pDC->GetPixel(Round(PointTop.x), Round(PointTop.y));if(BoundaryClr!=PixelClr && SeedClr!=PixelClr)Push(PointTop);//上方像素入栈PointRight.x=PopPoint.x+1;//搜索出栈结点的右方像素PointRight.y=PopPoint.y;PixelClr=pDC->GetPixel(Round(PointRight.x), Round(PointRight.y));if(BoundaryClr!=PixelClr && SeedClr!=PixelClr)Push(PointRight);//右方像素入栈PointBottom.x=PopPoint.x;PointBottom.y=PopPoint.y-1;//搜索出栈结点的下方像素PixelClr=pDC->GetPixel(Round(PointBottom.x), Round(PointBottom.y));if(BoundaryClr!=PixelClr && SeedClr!=PixelClr)Push(PointBottom);//下方像素入栈}pDC->TextOut(rect.left+50,rect.bottom-20,"填充完毕");delete pHead;pHead = NULL;}4.4.5 4.4.5 扫描线种子填充算法扫描线种子填充算法 算法原理为：先将种子像素入栈，种子像素为栈底像素，如果栈不为空，执行如下4步操作。

1）栈顶像素出栈2）沿扫描线对出栈像素的左右像素进行填充，直至遇到边界像素为止即每出栈一个像素，就对区域内包含该像素的整个连续区间进行填充3）同时记录该区间，将区间最左端像素记为xleft，最右端像素记为xright4）在区间〔xleft，xright〕中检查与当前扫描线相邻的上下两条扫描线的有关像素是否全为边界像素或已填充像素，若存在非边界且未填充的像素，则把未填充区间的最右端像素取作种子像素入栈 扫描线种子填充算法效果图4.5 4.5 本章小结本章小结 本章重点讲授了有效边表填充算法，该算法是后面一直使用的多边形填充算法，由于可以访问多边形内的每一个像素，因此可以使用平面着色模式或结合双线性线性插值算法的光滑着色模式填充物体表面有效边表表示的是扫描线在一条边上的连贯性，边表表示的是新边在扫描线上的插入位置，边表是有效边表的特例，有效边表和边表都使用CAET类表示区域填充算法主要包括四邻接点种子填充算法和八邻接点种子填充算法，由于未考虑像素间的相关性，只是孤立地对单个像素进行测试，效率很低有效的改进方法是扫描线种子填充算法习题习题4 41.试写出图4-43所示多边形的边表和扫描线y＝4的有效边表。

P P0 0P P1 1P P2 2P P3 3P P4 4P P5 5P P6 6图4-43 多边形 示例多边形返回。