《图形学课件第四讲多变形填充.》由会员分享，可在线阅读，更多相关《图形学课件第四讲多变形填充.（35页珍藏版）》请在金锄头文库上搜索。
1、滁州学院国土信息工程系主讲孙勇Email：sunyong_cug计算机图形学第四章多边形的扫描转换与区域填充4.1多边形扫描转换4.2区域填充4.1多边形的扫描转换与区域填充多边形有两种重要的表示方法：顶点表示和点阵表示。多边形的扫描转换:把多边形的顶点表示转换为点阵表示。区域可采用内点表示和边界表示两种表示形式。区域填充:指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。多边形分为凸多边形、凹多边形、含内环的多边形。4.1.1多边形的扫描转换扫描线算法基本思想：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。对于一条扫描线填充过程
2、可以分为四个步骤：（1）求交（2）排序（3）配对（4）填色判断任意点是否在多边形内l算法思想从该点（xy）向（y）引直线，并计算该线与多边形的交点数n(自左向右算起)if(n%2=0)则（xy）在多边形外else则（xy）在多边形内扫描线与多边形的顶点或边界相交时，必须正确的交点的取舍。只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是012来决定。l实际上将多边形的每条边与所有扫描线都求交点没有必要的。因为可能大多数扫描线与多边形根本不相交。为了提高算法效率，应只处理与多边形相交的那些扫描线，同时，交点的计算可以通过增量法来实现扫描线填色法一个多边形与若干扫描线数据
3、结构活性边表(AET)：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中结点内容x：当前扫描线与边的交点坐标x：从当前扫描线到下一条扫描线间x的增量ymax：该边所交的最高扫描线号ymax新边表（NET）：存放在该扫描线第一次出现的边。若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中上图所示各条扫描线的新边表NET假定当前扫描线与多边形某一条边的交点的x坐标为x，则下一条扫描线与该边的交点不要重计算，只要加一个增量x。设该边的直线方程为：ax+by+c=0；若yyi，x=xi；则当y=yi+1时，其中为常数FDCEAB975312468多
4、边形扫描转换算法过程(伪代码)voidpolyfill(polygoncolor)intcolor多边形polygonfor(各条扫描线i)初始化新边表头指针NETi；把ymin=i的边放进边表NETiy=最低扫描线号；初始化活性边表AET为空；for(各条扫描线i)把新边表NETi中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列；遍历AET表，把配对交点区间(左闭右开)上的象素(xy)，用drawpixel(xycolor)改写象素颜色值；遍历AET表，把ymax=i的结点从AET表中删除，并把ymaxi结点的x值递增x；若允许多边形的边自相交，则用冒泡排序法对AET表重新排序；
5、polyfill边界标志算法基本思想：帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。使用一个布尔量inside来指示当前点是否在多边形内的状态。算法过程voidedgemark_fill(polydefcolor)多边形定义polydef；intcolor对多边形polydef每条边进行直线扫描转换；inside=FALSEfor(每条与多边形polydef相交的扫描线y)for(扫描线上每个象素x)if(象素x被打上边标志)inside=!(inside)if(inside！=FALSE
6、)drawpixel(xycolor)elsedrawpixel(xybackground)用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。2.3.2区域填充算法区域指已经表示成点阵形式的填充图形，它是象素的集合。区域可采用内点表示和边界表示两种表示形式。区域可分为4向连通区域和8向连通区域。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的4向连通区域和8向连通区域四个方向运动八个方向运动四连通区域八
7、连通区域区域填充的递归算法内点表示的4连通区域的递归填充算法:voidFloodFill4(intxintyintoldcolorintnewcolor)if(getpixel(xy)=oldcolor)属于区域内点oldcolordrawpixel(xynewcolor)FloodFill4(xy+1oldcolornewcolor)FloodFill4(xy-1oldcolornewcolor)FloodFill4(x-1yoldcolornewcolor)FloodFill4(x+1yoldcolornewcolor)边界表示的4连通区域的递归填充算法:voidBoundaryFill4
8、(intxintyintboundarycolorintnewcolor)intcolorif(color!=newcolor&color!=boundarycolor)drawpixel(xynewcolor)BoundaryFill4(xy+1boundarycolornewcolor)BoundaryFill4(xy-1boundarycolornewcolor)BoundaryFill4(x-1yboundarycolornewcolor)BoundaryFill4(x+1yboundarycolornewcolor)区域填充的扫描线算法算法步骤：首先填充种子点所在扫描线上的位于给定区
9、域的一个区段然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。(1)初始化：堆栈置空。将种子点（x，y）入栈。(2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。(3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。(4)并确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。上述算法对于每一个待填充区段，只需压栈
10、一次；因此，扫描线填充算法提高了区域填充的效率。2.4字符字符指数字、字母、汉字等符号。计算机中字符由一个数字编码唯一标识。“美国信息交换用标准代码集”简称ASCII码。它是用7位二进制数进行编码表示128个字符汉字编码的国家标准字符集。每个符号由一个区码和一个位码（2字节）共同标识。区分ASCII码与汉字编码，采用字节的最高位来标识点阵字符:每个字符由一个位图表示矢量字符:记录字符的笔画信息点阵字符点阵字库中的位图表示矢量轮廓字符特点：点阵字符：存储量大，易于显示矢量字符：存储量小，美观，变换方便需要光栅化后才能显示。字符属性字体宋体仿宋体楷体黑体隶书字高宋体宋体宋体宋体字宽字倾斜角倾斜倾斜
11、对齐(左对齐、中心对齐、右对齐)字色红色、绿色、蓝色写方式：替换方式。与方式2.5裁剪裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。2.5.1直线段裁剪2.5.2多边形裁剪2.5.1直线段裁剪直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。Cohen-Sutherland裁剪基本思想：对于每条线段P1P2分为三种情况处理分为三种情况处理:（1）若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。（2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。（3）若
12、线段不满足“取”或“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。为快速判断，采用如下编码方法：每个区域赋予4位编码编码线段裁剪若P1P2完全在窗口内code1=0且code2=0则“取”若P1P2明显在窗口外code1&code20，则“弃”在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。计算线段P1(x1y1)P2(x2y2)与窗口边界的交点if(LEFT&code!=0)x=XLy=y1+(y2-y1)(XL-x1)(x2-x1)elseif(RIGHT&code!=0)x=XRy=y1+(y2-y1)(XR-x1)(x2-x1)elseif(BOTTOM&code!=0)y=YBx=x1+(x2-x1)(YB-y1)(y2-y1)elseif(TOP&code!=0)y=YTx=x1+(x2-x1)(YT-y1)(y2-y1)
