图形学教案sy-7,8,9讲(线预处理算法).pptVIP

区域填充算法 确定待填充的象素，即检查光栅的每一像素是否位于多边形区域内 射线法检验交点数 检验夹角之和 若夹角和为0，则点p在多边形外 设d=e-1,y=d的扫描线与P的边的交点序列为 xdj1， xdj2， xdj3，…，xdjn ………(2) 若多边形P的一条边Pr-1Pr与扫描线y=d，y=e都相交， 则由xdr可推出xer: xer=xdr+1/m m是边Pr-1Pr的斜率 (3)边的连贯性 设边的直线斜率为 k，若 y=yi 时，x=xi，则当y=yi+1时，xi+1=xi+1/k。 若yike,dyik+1，即和扫描线e相交的边与和扫描线d相交的边都一样，则有以下边的连贯性: ?两交点序列元素的个数相等，即m=n； ?点(xeir,e)与(xdjr,d)位于多边形P的同一条边上，即ir=jr。 xeir= xdjr+1/m (3)边的连贯性 当扫描线与多边形P的顶点相交时，则称该交点为奇异点。 (4)奇异点的处理 P0 P1 P2 P4 P5 P7 P8 P3 P6 1 2 对奇异点的处理如下： 首先将奇点分为两类:极值点和非极值点. 对点Pi， 若(yi-1- yi)*(yi+1- yi) ?0 则称Pi为极值点； 否则，称之为非极值点。 P0 P1 P2 P4 P5 P7 P8 P3 P6 1 2 (4)奇异点的处理 对左下角为(1,1),右上角为(3,3)的正方形填充时,若对边界上所有象素都进行填充,就得到面积为3x3的区域,如下图(a);而实际面积只有2x2.显然,这是由于对边界上所有象素未加处理而引起的.为此,在填充时,采用“左闭右开”,“下闭上开”的原则对扫描线进行填充.如下图(b). ? ? ? ? ? ? ? ? ? (a) ? ? ? ? (b) (4)奇异点的处理 ?对非极值点，将按一个交点处理； ?对极值点， 若其是局部最高点，则按0个交点处理； 若其是局部最低点，则按2个交点处理。 (4)奇异点的处理 Pi Pi Pi 对非极值点的处理 对局部最高点的处理 Pi (4)奇异点的处理 算法步骤: (5)扫描线算法的数据结构与实现步骤 1.求交。对每条扫描线(y=y0，y= y0 +1，y= y0+2….)，求与多边形各边的交点； 2.按x坐标递增方式对交点排序； 3.在每一对交点之间，着指定象素值.交点总数为偶数个。 基本思想:对于每一条扫描线和每条多边形边的交点 (x1,y1),将该扫描线上交点右方的所有象素取补.对多边形的每条边做此处理,多边形的顺序随意. 该算法的优点是简单,缺点是对复杂图形,每一象素可能被访问多次,输入输出的量比较大. 3.边缘填充算法 ? ? 扫描线算法：对每条扫描线，首先计算它与扇形区域边界的交点，再把配对交点之间的像素用指定颜色填充。 *三.扫描转换扇形区域 区域（种子）填充是指先将区域内的一点(种子点)赋予给定颜色,然后将颜色扩充到整个区域内的过程(染色过程). 区域:已经表示成点阵形式的象素集合,具有相同颜色. 区域填充(种子填充算法) (1) 区域的两种表示:内点表示、边界表示. 边界表示:给位于边界上的所有象素着色,而区 域内不着色. 内点表示:给区域内所有象素都着上同一种颜色 (特征值),边界上pixel不着色. 区域填充(2) 要求: 区域具有一定的连通性:4连通或8连通 4连通区域:取区域内任意两点,在该区域内(不能通过区域外的点),若从其中一点出发,通过上、下、左、右 四种运动可到达另一点时,则称该区域为4连通区域. 区域填充(3) 4连通运动方向 8连通运动方向 区域填充(4) 允许从4个方向有哪些信誉好的足球投注网站下一个象素的填充算法称为是四向填充算法 允许从8个方向有哪些信誉好的足球投注网站下一个象素的填充算法称为是8向填充算法 区域填充(5) 算法思想： 设G为一内点表示的区域，(x,y)是G内一点，以(x,y)为种子点，先将(x,y)置为newcolor，然后对(x,y)的4(或8)领域进行递归处理，逐步将整个区域G置为newcolor. (1)递归算法 void FloodFill4(int x, int y, int oldColor, int newColor) {if (GetPixel(x,y)==oldColor) { PutPixel(x,y,newColor);