计算机图形学课件 Chpt4

第四章填充图元的生成扫描转换矩形扫描转换多边形扫描转换扇形区域区域填充以图像填充区域字符的表示与输出1一般步骤确定那些像素位于填充图元的内部确定以什么颜色填充这些像素2扫描转换矩形（1/2）方法：voidFillRectangle(Rectangle*rect,intcolor) {intx,y;

for(y=rect->ymin;y<=rect->ymax;y++) for(x=rect->xmin;x<=rect->xmax;x++) PutPixel(x,y,color); }/*endofFillRectangle() */3扫描转换矩形（2/2）问题：矩形是简单的多边形，那么为什么要单独处理矩形？共享边界如何处理？原则：左闭右开，下闭上开属于谁？4扫描转换多边形(1/19)多边形的表示方法顶点表示点阵表示扫描转换多边形：将顶点表示形式转换成点阵表示形式5扫描转换多边形(2/19)逐点判断算法方法voidFillPolygonPbyP(Polygon*P,intpolygonColor){intx,y;

for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xmax;x++) if(IsInside(P,x,y)) PutPixel(x,y,polygonColor); else PutPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP() */6扫描转换多边形(3/19)问题：如何判别点(x,y)关于多边形区域P的内外关系？射线法步骤：从待判别点v发出射线求交点个数kK的奇偶性决定了点与多边形的内外关系奇异情况处理7扫描转换多边形(4/19)累计角度法步骤从v点向多边形P顶点发出射线，形成有向角计算有相交的和，得出结论奇异情况处理例子：五角星离散计算方法：编码方法8扫描转换多边形(5/19)算法优点：简单算法缺点：计算量太大，速度慢扫描线算法目标：利用像素之间的连贯性，提高算法效率处理对象：非自交多边形9扫描转换多边形(6/19)基本原理一条扫描线与多边形的边有偶数个交点步骤：求交排序填充演示：MorphInk10扫描转换多边形(7/19)边的连贯性第一类交点：新出现的边与扫描线的交点第二类交点：位于同一条变上的后继交点11扫描转换多边形(8/19)交点的取整规则要求：使生成的像素全部位于多边形之内用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用假定非水平变与扫描线y=e相交，交点的合作标为x,规则如下12扫描转换多边形(9/19)X为小数(a)交点位于左边之上，相右取整(b)交点位于右边之上，相左取整13扫描转换多边形(10/19))2.(x,e)落在像素之上(a)(x,e)位于左边之上，属于多边形(b)(x,e)位于右边之上，不属于多边形14扫描转换多边形(11/19)3.交点位多边形的顶点(a)算作1个交点(b)算作1个交点(c)算作2个交点(d)算作0个交点15扫描转换多边形(12/19)特殊情况处理水平边:扔掉！尖角：凡混淆16扫描转换多边形(13/19)数据结构边边的分类表E按照变得下端点y坐标对非水平边进行分类的指针数组活化边表AEL纪录与当前扫描线相交的边（交点）typedefstruct{intymax; floatx,deltax; Edge*nextEdge; }Edge;

17扫描转换多边形(14/19)18扫描转换多边形(15/19)算法1、建立ET；2、将扫描线纵坐标y的初值置为ET中非空元素的最小序号，如在上图中，y=1；3、置AEL为空；4、执行下列步骤直至ET和AEL都为空．4.1、如ET中的第y类非空，则将其中的所有边取出并插入AEL中；4.2、如果有新边插入AEL，则对AEL中各边排序；4.3、对AEL中的边两两配对，（1和2为一对，3和4为一对，…），将每对边中x坐标按规则取整，获得有效的填充区段，再填充．4.4、将当前扫描线纵坐标y值递值1；4.5、将AEL中满足y=ymax边删去（因为每条边被看作下闭上开的）；4.6、对AEL中剩下的每一条边的x递增deltax，即x=x+deltax．思考题19扫描转换多边形(16/19)边缘填充算法原理：以求余运算代替扫描线算法中的排序运算求余(A=0xFFFFFFFF)算法1：（以扫描线为中心的边缘填充算法）1、将当前扫描线上的所有象素着上值为的颜色；2、求余：

for(i=0;i<=m;i++)

在当前扫描线上，从x坐标为交点向右求余；

20扫描转换多边形(17/19)21扫描转换多边形(18/19)算法2：（以边为中心的边缘填充算法）1、将绘图窗口的背景色置为；2、对多边形的每一条非水平边做： 从该边上的每个象素开始向右求余；

22扫描转换多边形(19/19)23扫描转换扇形区域(1/5)扇形区域的描述原理：同扫描转换多边形问题：如何确定扫描线与直线段和圆弧段的相交顺序方法：分类按点和点所处象限的不同，需要将扇形区域分成4×4=16种情况

24扫描转换扇形区域(2/5)假设点落在第一象限,扇形区域的扫描转换分四种情况1、落在第一象限25扫描转换扇形区域(3/5)2、落在第二象限，此时又分为两种情况当时当时26扫描转换扇形区域(4/5)3、落在第三象限4、落在第四象限27扫描转换扇形区域(5/5)遗留问题：当落在其它区域时?其它方法：多边形迫近方法28区域填充(1/10)区域：点阵表示的图形，像素集合表示方法：内点表示、边界表示内点表示枚举处区域内部的所有像素内部的所有像素着同一个颜色边界像素像素着与内部像素不同的颜色边界表示枚举出边界上所有的像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色29区域填充(2/10)区域填充将指定的颜色从种子点扩展到整个取得过程例子：PaintBrush例子：PhotoShop30区域填充(3/10)连通性：4连通、8连通4连通：8连通31区域填充(4/10)4连通与8连通区域的区别连通性对边界的要求32区域填充(5/10)递归填充算法内点表示的4连通区域voidFloodFill4(intx,inty,intoldColor,intnewColor){if(GetPixel(x,y)==oldColor){PutPixel(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);}}/*endofFloodFill4() */

33区域填充(6/10)34区域填充(7/10)边界表示的4连通区域voidBoundaryFill4(intx,inty,intoldColor,intnewColor){ intcolor;

color=GetPixel(x,y); if((color!=boundaryColor)&&(color!=newColor)) { PutPixel(x,y,newColor); BoundaryFill4(x,y+1,oldColor,newColor); BoundaryFill4(x,y-1,oldColor,newColor); BoundaryFill4(x-1,y,oldColor,newColor); BoundaryFill4(x+1,y,oldColor,newColor); }}/*endofBoundaryFill4() */

35区域填充(8/10)内点表示与边界表示的8连通区域？递归填充算法的特点算法、程序简单递归层次太多，效率极低例子：判断填充方法例子：PaintBrush例子：PhotoShop36区域填充(9/10)扫描线算法目标：减少递归层次步骤1、填充并确定种子区段；2、初始化：将种子区段压入堆栈；3、出栈：如果堆栈为空，则算法结束；否则取栈顶元素（y,xLeft,xRight），以纵坐标为y的扫描线为当前扫描线，[xLeft,xRight]为搜索区间；4、填充并确定新的区段。37区域填充(10/10)38以图像填充区域（1/3）基本