多边形扫描转换课件

,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,YTU,单击此处编辑母版标题,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,YTU,*,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,YTU,5.4 多边形的扫描转换与区域填充,5.4.1 多边形的扫描转换,5.4.2 边缘填充算法,5.4.3 区域填充,5.4.4 其他相关概念,YTU,5.4 多边形的扫描转换与区域填充5.4.1 多边形的扫描转,1,5.4.1 多边形的扫描转换,多边形的表示方法 flash 演示,多边形顶点表示,多边形点阵表示,YTU,5.4.1 多边形的扫描转换多边形的表示方法 flash,2,多边形的扫描转换,像素逐点判断法,x-扫描线算法,改进的有效边表算法,边缘填充算法,栅栏填充算法,边界标志算法,扫描线,YTU,多边形的扫描转换像素逐点判断法扫描线YTU,3,1.像素逐点判断法,检查光栅的每一像素是否位于多边形内,YTU,1.像素逐点判断法检查光栅的每一像素是否位于多边形内YTU,4,改进:包围盒技术,包围盒:包含该多边形的最小矩形,只有包围盒内的那些点需要检查,YTU,改进:包围盒技术包围盒:包含该多边形的最小矩形 YTU,5,多边形的空间连贯性,扫描线上的相邻像素几乎都有相同的特性,YTU,多边形的空间连贯性扫描线上的相邻像素几乎都有相同的特性 YT,6,2.x-扫描线算法,图5-23 x-扫描线算法填充多边形,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,y,max,=12,y,min,=1,算法步骤：,y,min,和y,max,填充每条扫描线,求交(all),排序,交点配对,填色,YTU,2.x-扫描线算法图5-23 x-扫描线算法填充多边形xy,7,X-扫描线算法可填充凸的、凹的和带孔的多边形区域,YTU,X-扫描线算法可填充凸的、凹的和带孔的多边形区域YTU,8,存在问题：交点的取舍,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,图5-24 与多边形顶点相交的交点的处理,p5,p0,p1,p2,p3,p4,p6,*奇点：,当扫描线与多边形P的边界的交点是P的顶点时，则称该交点为奇点,YTU,存在问题：交点的取舍xy213456789111234567,9,图5-25 与扫描线相交的多边形顶点的交点数,0,1,1,1,1,0,2,2,2,0,极值点,偶数化处理,下闭上开的原则,1,Flash演示,x-扫描线算法,YTU,图5-25 与扫描线相交的多边形顶点的交点数01111022,10,X扫描线算法的缺点,算法步骤：,y,min,和y,max,填充每条扫描线,求交(all),每条扫描线需要和多边形,的,所有边,求交,排序,交点配对,填色,图5-23 x-扫描线算法填充多边形,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,YTU,X扫描线算法的缺点算法步骤：图5-23 x-扫描线算法,11,3.改进的有效边表算法(Y连贯性算法),x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,填充每条扫描线,求交,排序,交点配对,填色,YTU,3.改进的有效边表算法(Y连贯性算法)xy213456789,12,多边形边的连贯性、扫描线的连贯性,p5,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,p0,p1,p2,p3,p4,p6,x,i+1,=,x,i,+1/k,y,i+1,=y,i,+1,1,1/k,(x,i,y,i,),(x,i+1,y,i+1,),p4,p5,3,4,YTU,多边形边的连贯性、扫描线的连贯性p5xy2134567891,13,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,改进的有效边表算法 改进原理:求交,利用扫描线的连贯性 和多边形边的连贯性 获得交点坐标,每条条扫描线仅对有效边 求交,有效边,活性边Active Edge,与当前扫描线相交的边,YTU,xy2134567891112345678910111210,14,数据结构,有效边(Active Edge),有效边表,(Active Edge Table),边表(Edge Table),YTU,数据结构有效边(Active Edge)YTU,15,x,y,max,1/,k,next,当前扫描线与边的交点,边的最大扫描线值,斜率,链表指针,y3,2.4,7,1/3,4.5,5,3/4,7.0,5,1/2,9.0,9,1/2,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,e1,e2,e3,e4,e1,e2,e3,e4,递增,有效边表,xymax1/knext当前扫描线与边的交点边的最大扫描线值,16,改进的有效边表算法,填充每条扫描线,求交 构造有效边表 AET,排序,交点配对,填色,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,YTU,改进的有效边表算法填充每条扫描线xy213456789111,17,有效边表中包含了扫描线与边的交点信息,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,e1,e2,e3,e4,e5,e6,e7,y=6,1.4,7,-1/3,10.5,12,1/2,e3,e6,x,y,max,1/k,next,当前扫描线与边的交点,y=6时的 有效边表,YTU,有效边表中包含了扫描线与边的交点信息xy2134567891,18,如何构造每条扫描线的AET?,x,y,max,1/k,next,p5,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,p0,p1,p2,p3,p4,p6,YTU,如何构造每条扫描线的AET?xymax1/knextp5xy,19,flash,X扫描线算法与AET,x,2,1,3,4,5,6,7,8,9,11,10,12,y,1,2,3,4,5,6,7,8,9,10,11,12,e1,e2,e3,e4,e5,e6,e7,YTU,flash X扫描线算法与AETx21345678911,20,边表(Edge Table),最大扫描线数:12,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,e1,e2,e3,e4,e5,e6,e7,1,2,3,4,5,6,7,8,9,10,11,12,e1,e7,e2,e3,e4,e5,e6,水平边除外,桶,纵向链表,YTU,边表(Edge Table)最大扫描线数:12xy213,21,1,e3,e4,e5,e6,12,2/5,7,12,-1,x|y,min,y,max,1/k,next,7,9,5,e2,1,2,3,4,5,6,7,8,9,10,11,12,e1,e7,边表节点,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,e1,e2,e3,e4,e5,e6,e7,YTU,1e3e4e5e6122/5712-1x|yminymax1,22,x|y,min,y,max,1/k,next,边低端点处的x值,边表节点,x,y,max,1/k,next,当前扫描线与边的交点,有效边表节点,YTU,x|yminymax1/knext边低端点处的x值边表节点x,23,边表中不包含水平边,2,YTU,边表中不包含水平边2YTU,24,边表中不包含水平边,YTU,边表中不包含水平边YTU,25,当扫描线与多边形的顶点相交时,交点计为1,时的问题,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,e1,e2,e3,e4,e5,e6,e7,y=7,1,7,-1/3,1,12,2/5,11,9,1/2,e3,e2,e6,y=7时的有效边表,当扫描线与多边形的顶点相交时,交点计为1 时的问题xy2,26,解决顶点交点计为1时的情形,图5-28 将多边形的某些边,缩短,以,分离,那些应计为,1个交点,的顶点,（a)原图,（b)缩短y,max,的边,（c)缩短y,min,的边,扫描线y,扫描线y+1,扫描线y-1,YTU,解决顶点交点计为1时的情形图5-28 将多边形的某些边缩短（,27,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,e1,e2,e3,e4,e5,e6,e7,分离顶点,y=7,1,12,2/5,11,9,1/2,e2,e6,y=7时的有效边表,xy2134567891112345678910111210,28,图5.27(c)边表 P126,分离,计为,1个交点,的顶点,x|y,min,y,max,1/k,next,YTU,图5.27(c)边表 P126分离计为1个交点的顶点x|,29,例:改进的AET算法,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,P,4,P,1,P,0,P,2,P,3,P,5,P,6,Flash演示,YTU,例:改进的AET算法xy21345678911123456,30,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,P,1,P,0,P,2,P,3,P,4,P,5,P,6,YTU,xy2134567891112345678910111210,31,y=5,1.7,6,-1/3,6,5,3/4,10,9,1/2,6,5,-1/2,y=1,3,6,-1/3,3,5,3/4,8,9,1/2,8,5,-1/2,y=2,2.7,6,-1/3,3.8,5,3/4,8.5,9,1/2,7.5,5,-1/2,y=3,2.3,6,-1/3,4.5,5,3/4,9,9,1/2,7,5,-1/2,y=4,2,6,-1/3,5.3,5,3/4,9.5,9,1/2,6.5,5,-1/2,y=6,1.3,6,-1/3,10.5,9,1/2,y=7,1,12,2/5,11,9,1/2,y=8,1.4,12,2/5,7,12,-1,11.5,9,1/2,7,9,5,y=9,1.8,12,2/5,6,12,-1,12,9,1/2,12,9,5,y=10,2.2,12,2/5,5,12,-1,y=51.76-1/3653/41091/265-1/2y=,32,改进的有效边表算法详细步骤,1.初始化:构造边表,ET,AET,表置空；,2.获得初始有效边表,将第一个不空的ET表中的边与AET表合并,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,e1,e2,e3,e4,e5,e6,e7,YTU,改进的有效边表算法详细步骤1.初始化:构造边表ET,AET,33,e3,e4,e5,e6,x|y,min,y,max,1/,k,next,1,2,3,4,5,3,6,-1/3,3,5,3/4,8,5,-1/2,8,9,1/2,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,e1,e2,e3,e4,e5,e6,e7,3,6,-1/3,3,5,3/4,8,5,-1/2,8,9,1/2,y=1,AET,x,y,max,1/,k,next,ET,e3e4e5e6x|yminymax1/knext12345,34,由AET表中取出交点对进行填充,填充之后将y=y,max,的边删除,b)形成下一条扫描线的AET表,3.按,从下到上,的顺序对纵坐标值为y的,扫描线,执行下列步骤,a),b),，,直到边表ET和有效边表AET都变成空为止,由AET表中取出交点对进行填充3.按从下到上的顺序对纵坐标值,35,x,y,2,1,3,4,5,6,7,8,9,11,1,2,3,4,5,6,7,8,9,10,11,12,10,12,e1,e2,e3,e4,e5,e6,e7,1,1/k,(x,i,y,i,),(x,i+1,y,i+1,),p4,p5,3,4,计算并修改AET表,yi+1=yi+1,xi+1=xi+1/,k,同时合并ET表中,y=yi+1,桶中的边，按次序(x值从大到小)插入到AET表中,b),形成下一条扫描线的AET表；,xy2134567891112345678910111210,36,注意,请按照题目中关于顶点的分离要求构造边表!,默认:不分离,YTU,注意请按照题目中关于顶点的分离要求构造边表!YTU,37,作业与练习,课堂练习1:P149 5.10,课堂练习2:AET,作业,5.11 p149,YTU,作业与练习课堂练习1:P149 5.10YTU,38,