《图形学教案sy-7,8,9讲(扫描线预处理算法)》由会员分享，可在线阅读，更多相关《图形学教案sy-7,8,9讲(扫描线预处理算法)（53页珍藏版）》请在金锄头文库上搜索。
1、圆的内接正多边形迫近法(1)内接正n边形顶点图4-6圆的多边形迫近圆的内接正多边形迫近法(2)圆的内接正多边形迫近法(3)v使用增量计算确定多边形顶点（可取最高点为初始点）：同理:圆的内接正多边形迫近法(4)上述递推公式可用矩阵形式表示为：可以证明：该递推公式关于误差稳定。圆的内接正多边形迫近法(5)n改进的增量计算：使用两个初始点该递推公式关于误差稳定1.直线线宽的处理在产生一定宽度的线条时,只需用一个“刷子” 来替代单象素直线段中扫描生成的单象素即可.线画图元的属性控制(1)线刷子 原理:假设直线斜率在-1,+1之间,如图(a)所示.这时可把刷 子置成垂直方向图(b).首先将刷子的中点对准
2、直线的一个 端点,从该点开始,让刷子中点沿直线的轨迹往直线的另 一端点平移即可“刷出”具有一定宽度的直线.如图(c).m1m2(a)(b)(c)线画图元的属性控制缺点:(1)线的始末断总是水平或垂直的.(2)线的粗细不一样.水平和垂直线最粗,45斜线最 细.(3) 当线宽为偶数个时,绘制的线条宽度不精确.线画图元的属性控制(2)方形刷子方形刷子是一个宽度为指定线宽的正方形.将 正方形的中心对准直线作平移运动即可.该方法将会重复的写象素.为避免重复,可采用与 活化边表类似的技术.m1方形刷子 线画图元的属性控制(3)区域填充法先算出直线的四个角点的坐标,将其顺序 连接成一个四边形,再用区域填充的
3、方法将四边 形填充.线画图元的属性控制2.圆弧线宽的处理圆弧线宽的处理与直线类似.3.线型的处理如虚线、实线、点划线等不同线的处理.线画图元的属性控制一.扫描转换矩形二.多边形的扫描转换二维填充图元的生成区域填充算法 确定待填充的象素，即检查光栅的每一像素是 否位于多边形区域内 解决的主要问题是什么？ 图案填充还有一个什么象素填什么颜色的问题 曲线围成的区域，可用多边形逼近 矩形的扫描转换v可利用矩形的简单性提高扫描转换的效率 。问题：共享边界的绘制？解决：象素中心定位于矩形的左、下边界时绘制象素点。“下闭上开”、“左闭右开”原则！二.多边形的扫描转换v多边形的表示方法：n多边形的扫描转换：n
4、从顶点表示转换为点阵表示形式，以便于光栅 显示的实现。n顶点表示点阵表示多边形扫描转换算法分类v以点为中心的填充算法：逐点判别算法v以扫描线为中心的填充算法：扫描线算法 (多边形有序边表填充算法)边缘填充算法v种子填充算法：从区域内部一点开始填充直至边界。递归填充算法扫描线算法*1.逐点判别的填充算法算法流程：v逐个判别绘图窗口中的象素点是否在多边形 区域内v 点在多边形内的判别： 射线法 累计角度法 编码法 绘制多边形内的点点在多边形内的判别（1）射线法注意：避免射线穿过顶点原则:若交点为偶数个,则点在多边形之外;若交点为奇数个,则点在多边形之内;射线法检验交点数ABCDE PABCDEP交
5、点数=偶数（包括0）点在多边形之外交点数=奇数点在多边形之内zx左闭右开点在多边形内的判别（2）累计角度法检验夹角之和若夹角和为0，则点p在多边形外 若夹角和为360，则点p在多边形内ABCDEPABCDEP点在多边形内的判别（3）编码方法：是累计角度法的离散计算方法。n预处理：对测试点落在多边形边界上的情 形做单独处理。n以测试点为原点建立局部坐标系，并顺序 编码各象限（如图）n多边形顶点编码与其所在象限的编码相同n多边形边界线段的编码定义为其顶点编码之差n计算多边形边界线段编码之和n和为0则测试点落在多边形外n和为4则测试点落在多边形内0123ACB点在多边形内的判别（4）编码法注意事项：
6、为保证边界线段编码的唯一性规定：编码值在 -2，2之间（对应 ） 故令线段编码作如右处理：33-4=-1;-3-3+4=1边界线段编码为 时也需做特殊处理：0123插入线段中点，并令线段编 码等于两个子线段编码之和 （该过程可递归执行）逐点判别方法的特点v程序简单，实现方便v效率低下2.扫描线算法v扫描线:光栅扫描显示器的一行象素点叫 一条扫描线(1)区域的连贯性设多边形P的顶点是Pi=(xi,yi),i=0,1,2,n,又设yi0,yi1,yin是各顶点Pi的纵坐标yi的 递减数列即yikyik+1,0 k n-1屏幕上位于yik和yik+1两条扫描线之间的长方形 区域被P 的边分割成若干梯
7、形(三角形可看作其 中一底边长为零的梯形),这些梯形具有下列性 质:梯形的两底边分别在y=yik和y=yik+1扫描线上,腰边在P的 边上或在屏幕的边界上; 这些梯形分为两类:一类在P内,一类在P外; 两类相间排列.依照上述性质,可根据长 方形区域内的任一点q的 内外关系,确定所有梯形 的内外关系:若q在内,则q 所在区域位于P内,与该区 域相邻的区域位于P外,依 次类推.(1)区域的连贯性qP0P1P2P4P5P7P8P3P6y=yik y=yik+1设e为一整数，yi0eyin，y=e 的扫描线与多边形的边Pi-1Pi的交点横坐标记为xei假设y=e 扫描线与多边形各边交点横坐标的递增序列
8、为:xei1, xei2 , xei3 ,. , xeim (1) (2)扫描线的连贯性则由区域的连贯性,可知交点序列有如下性质: m是偶数,即共有偶数个交点; 在该扫描线上,只有区段( xeik, xeik+1) (k=1，3， m-1)位于多边形P内，其余区段都在P外 .扫描线的连贯性 边的连贯性扫描线的连贯性是多边形区域连贯性在一 条扫描线上的反映.P0P1P2P4P5P7P8P3P6P0P1P2P4P5P7P8P3P6y=ey=d设d=e-1,y=d的扫描线与P的边的交点序列为xdj1， xdj2， xdj3，xdjn (2)若多边形P的一条边Pr-1Pr与扫描线y=d，y=e都相交，
9、则由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)奇异点的处理P0P1P2P4P5P7P8P3P61 2对奇异点的处理如下：首先将奇点分为两类:极
10、值点和非极值点.对点Pi， 若(yi-1- yi)*(yi+1- yi) 0则称Pi为极值点；否则，称之为非极值点。P0P1P2P4P5P7P8P3P61 2(4)奇异点的处理对左下角为(1,1),右上角为(3,3)的正方形填充时,若对边界上所 有象素都进行填充,就得到面积为3x3的区域,如下图(a);而实际面 积只有2x2.显然,这是由于对边界上所有象素未加处理而引起的.为 此,在填充时,采用“左闭右开”,“下闭上开”的原则对扫描线进行填充. 如下图(b). (a) (b)(4)奇异点的处理对非极值点，将按一个交点处理； 对极值点，若其是局部最高点，则按0个交点处理；若其是局部最低点，则按2
11、个交点处理。(4)奇异点的处理PiPiPi对非极值点的处理对局部最高点的处理Pi(4)奇异点的处理算法步骤:(5)扫描线算法的数据结构与实现步骤1.求交。对每条扫描线(y=y0，y= y0 +1，y= y0+2.)，求 与多边形各边的交点； 2.按x坐标递增方式对交点排序； 3.在每一对交点之间，着指定象素值.交点总数为偶数个 。基本思想:对于每一条扫描线和每条多边形边的交点 (x1,y1),将该扫描线上交点右方的所有象素取补.对 多边形的每条边做此处理,多边形的顺序随意.v该算法的优点是简单,缺点是对复杂图形,每一象素 可能被访问多次,输入输出的量比较大.3.边缘填充算法扫描线算法：对每条扫
12、描线，首先计 算它与扇形区域边界的交点，再把配对 交点之间的像素用指定颜色填充。*三.扫描转换扇形区域区域（种子）填充是指先将区域内的一点(种 子点)赋予给定颜色,然后将颜色扩充到整个区域 内的过程(染色过程).v区域:已经表示成点阵形式的象素集合,具有相同 颜色.区域填充(种子填充算法) (1)v区域的两种表示:内点表示、边界表示.v 边界表示:给位于边界上的所有象素着色,而区 域内不着色.v 内点表示:给区域内所有象素都着上同一种颜色(特征值),边界上pixel不着色. 区域填充(2)要求:区域具有一定的连通性:4连通或8连通4连通区域:取区域内任意两点,在该区域内(不能 通过区域外的点)
13、,若从其中一点出发,通过上、 下、左、右 四种运动可到达另一点时,则称该 区域为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 new
14、Color)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); 算法12345678910111213 14151617 1819202122举例：算法: (1)填充并确定种子点所在的区段；(2)将种子区段压栈;(3)若堆栈非空,栈顶区段出栈;否则算法 结束;
15、(4)填充并确定新的区段, 将其区段信息压栈.5.以图象填充区域*(2)扫描线算法1.点阵字符在点阵字符库中,每个字符都定义成一个 称为字符掩膜的矩阵.矩阵中的每个元素 都是一位二进制数.该位为1,表示字符经 过此位,对应于该位的象素应置为字符颜 色;为0,不经过.字符的表示和输出点阵字符1111110011001101100110111110011001101100111111111000000000000001111110011001101100110111110011001101100111111110000000100000002.矢量字符矢量型字符库采用矢量代码序列表示字 符的各个笔画.3.字型技术字符的表示和输出(2)矢量字符-1落笔抬笔
