《计算机图形学(多边形的扫描转换).ppt》由会员分享，可在线阅读，更多相关《计算机图形学(多边形的扫描转换).ppt（27页珍藏版）》请在三一办公上搜索。
1、第三章 基本光栅图形算法,本章内容,2,2014-2015-1:CG:SCUEC,多边形的扫描转换,什么是多边形的扫描转换？把多边形的顶点表示转化为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个像素，并给帧缓冲器内各个对应元素设置相应的灰度和颜色多边形的扫描转换过程，实际上是给多边形包围的区域着色的过程,多边形的表示方法顶点表示:用多边形的顶点序列来刻划多边形该表示方法几何意义强、占内存少不能明确指出哪些像素在多边形内，不能直接用于面着色点阵表示:用位于多边形内的象素的集合来刻划多边形该方法便于利用帧缓冲器表示图形，是面着色所需要的图形表示形式失去了许多重要的几何信息,3,201
2、4-2015-1:CG:SCUEC,为什么研究图形的扫描转换与区域填充？,与单纯由线条所构成的线画图形相比，采用面着色绘制的光栅图形显得更为生动、直观，真实感更强,面着色可以使使光栅图形的画面明暗自然,色彩丰富,形象逼真,具有真实感,4,2014-2015-1:CG:SCUEC,逐点判断法,逐点判断是实现多边形扫描转换最简单的方法逐个像素判别，确定它们是否在多边形内，从而给出位于多边形内的点（像素）的集合,#define MAX 100typedef struct int VertexNum;/多边形顶点个数 Point VerticesMAX/多边形顶点数组 Polygon/多边形,5,20
3、14-2015-1:CG:SCUEC,void FillPolygonPbyP(Polygon P)int x,y;for(x=xmin;x=xmax;x+)for(y=xmin;y=ymax;y+)if(IsInside(P,x,y)FrameBuffer(x,y)=POLYGON_COLOR;else FrameBuffer(x,y)=BACKGROUND_COLOR;/*end of FillPolygonPbyP()*/,IsInside(P,x,y)：验证点(x,y)是否在多边形P内的布尔函数，当从(x,y)到(+,y)的射线与P的交点个数是奇数时，函数取值true，否则取值Fals
4、e。,FrameBuffer(x,y)：在帧缓存中对应位置存放屏幕上像素(x,y)的颜色值。,POLYGON-COLOR：多边形P的颜色值。,BACKGROUND-COLOR：屏幕的背景色。,逐点判断法,6,2014-2015-1:CG:SCUEC,扫描线算法,扫描线算法按扫描线的顺序计算出扫描线与多边形的相交区间，然后用要求的颜色填充这些区间内的像素。该算法利用了相邻像素间的连续性，避免对像素的逐点判断和反复求交运算，减少了计算量，提高了算法速度。,先求出扫描线与多边形边的交点，利用扫描线的连续性求出多边形与扫描线相交的连续区域，然后利用多边形边的连续性，求出下一条扫描线与多边形的交点，对所
5、有扫描线由上到下依次处理。,区域的连续性、扫描线的连续性、边的连续性,7,2014-2015-1:CG:SCUEC,区域的连续性（21）,设多边形 P 的顶点为Pi=(xi,yi)，i=0,1,2,n，又设 是各顶点Pi的纵坐标 yi 的递减数列,当,屏幕上位于于y=和 y=两条扫描线之间的长方形区域，被多边形 P 的边分割成若干梯形（三角形看作其中一底边长为0的梯形）。,8,2014-2015-1:CG:SCUEC,区域的连续性（22）,如果知道长方形区域内任一梯形内一点关于多边形P的内外关系后，即可确定区域内所有梯形关于P的内外关系。此性质称为区域的连续性。,这些梯形有如下的三个性质：,梯
6、形的两底边分别在y=和y=两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。梯形可分为两类：一类位于多边形P的内部；另一类在多边形P的外部。两类梯形在长方形区域，内相间的排列。即相邻的两梯形必有一个在多边形P内，另一个在P外。,9,2014-2015-1:CG:SCUEC,设多边形P的顶点，将各顶点 的纵坐标 按递减顺序排列,即设当前扫描线，与多边形P的边 的交点记为。设 为 与P的边界各交点横坐标的递增序列，该序列称为交点序列。,扫描线的连续性（21）,10,2014-2015-1:CG:SCUEC,1、交点个数 l 是偶数；2、扫描线上的区间 l1位于多边形P内（下图中的红线段部分），
7、其余区间都在P 外（下图中的虚线段部分），两类区间沿扫描线相间排列。这些性质就称为扫描线的连续性。,扫描线的连续性（22）,交点序列具有以下性质：,11,2014-2015-1:CG:SCUEC,边的连续性,两交点序列元素的个数相等，即l=h,当前扫描线e与多边形的某些边是相交的,设 是该扫描线与这些边各交点横坐标的递增序列。设下一条扫描线为d=e+1，如果yk e,d y k+1,那么扫描线d与上述边也是相交的，交点横坐标递增序列记为,对同一条边，前一条扫描线e与该边的交点为xeir，而后一条扫描线d=e+1与该边的交点则为xdir=xeir+1/m，如右图所示。,以上性质称为边的连续性。,
8、12,2014-2015-1:CG:SCUEC,存在的问题,上述三种形式的连续性都基于一个几何事实：每一条扫描线与多边形P 的边界的交点个数都是偶数（包括零）。但是当扫描线与多边形P 的边界的交点恰好是P的顶点时：如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数（如下图中的扫描线7的情况）；若将每一奇点都简单地计为两个交点，同样会导致反常的结果（如下图中扫描线2的情况）。,13,2014-2015-1:CG:SCUEC,多边形顶点的分类,设多边形P 的顶点为 这些顶点可分为两类：极值点和非极值点。如果，则称顶点 为极值点（如下图中的）；否则称 为非极值点（如下图中的）。,14,2014
9、-2015-1:CG:SCUEC,奇点的处理,为了使交点个数保持为偶数，规定当奇点是P的极值点时，该点按两个交点计算；否则按一个交点计算。,预处理:若Pi是非极值点，则将 两边中位于扫描线y=yi上方的那条边在Pi点处截去一单位长。,非极值点的处理,15,2014-2015-1:CG:SCUEC,算法的实现步骤,对于每一条扫描线，多边形的扫描转换可分为以下4步：求交点：计算扫描线与多边形各边的交点，设交点个数为n。交点排序：把所有的交点按x值递增的顺序进行排列。交点配对：将排序后的第1个与第2个交点，第3个与第4个交点，第n-1个与第n个交点配对，每对交点就代表扫描线与多边形的一个相交区间。区
10、间填色：把相交区间内的像素置成多边形的颜色，相交区间外的像素置成背景色。,16,2014-2015-1:CG:SCUEC,算法的数据结构,与当前扫描线相交的边称为活性边。把活性边与扫描线的交点按x坐标递增的顺序放在一个链表中，该链表就称为活性边表（Active Edge List,AEL）。,设多边形某一条边的方程为，当前扫描线 与该边的交点坐标为，则下一条扫描线 与该边的交点 不需要重新计算，只要加一个增量 即可。因为此时有,其中 为常数，并规定 时，。,17,2014-2015-1:CG:SCUEC,算法的数据结构,18,2014-2015-1:CG:SCUEC,为方便活性边表的建立与更新
11、，还要为每一条扫描线建立一个新边表（New Edge List,NEL），存放在该扫描线上第一次出现的边。也就是说，如果某边的较低端点为，则该边就放在扫描线 的新边表中。,注意：水平边不放到任何扫描线的NEL中，即水平边不参加分类。NEL中的节点结构与AEL相同，只是 x 在这里不再表示边与扫描线的交点，而是表示该边较低端点的 x 坐标值。,算法的数据结构,19,2014-2015-1:CG:SCUEC,算法描述,根据给出的多边形顶点坐标，建立新边表NEL；(AEL初始化)将边的活性边表AEL设置为空(y初始化)取扫描线纵坐标y的初始值为NEL中非空元素的最小序号,20,2014-2015-1
12、:CG:SCUEC,如新边表NEL中的第y类元素非空，则将属于该类的所有边从NEL中取出并插入边的活性边表AEL中，AEL中的各边按照x值(当x的值相等时，按x值)递增方向排序若相对于当前扫描线，边的活性边表AEL非空，则将AEL中的边两两依次配对，即第1，2边为一对，第3，4边为一对，依此类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点(象素)按多边形属性着色将活性边表AEL中满足y=ymax的边删去将活性边表AEL剩下的每一条边的 x 域累加x，即x=x+x将当前的扫描线的纵坐标值 y 累加，即y:=y+1,4.按从下到上的顺序对纵坐标值为y的扫描线(当前扫描
13、线)执行下列步骤，直到新边表NEL和活性边表AEL都为空,算法描述,21,2014-2015-1:CG:SCUEC,P0(2,5),P1(2,10),P2(9,6),P3(16,11),P4(16,4),P5(12,2),P6(7,2),具体例子,22,2014-2015-1:CG:SCUEC,边缘填充算法,假设某像素的颜色是，对该像素做偶数次求补运算后，其颜色还是；做奇数次求补运算后，其颜色变为。在光栅图形中，如某区域已着上值为M 的某种颜色，则上述求补运算的结果是：对区域作偶数次求补运算后，该区域的颜色不变；作奇数次求补运算后，该区域的颜色则变成值为 的颜色。,23,2014-2015-1
14、:CG:SCUEC,以扫描线为中心的边缘填充算法,设x0,x2,xm是扫描线y=e与多边形P的边界交点x坐标序列（不要求递增排列），则该扫描线上位于多边形P内的像素可按如下步骤求得：步骤1：将位于扫描线y=e上的所有像素都着上值 为M的颜色 for x:=xmin to xmax do setpixel(framebuffer,x,e,M)步骤2：将位于扫描线y=e上所有坐标大于xi(i=1,2,m)的像素向右求反for i:=1 to m do for x:=xi to xmax do complement(framebuffer,x,e),24,2014-2015-1:CG:SCUEC,1、将绘图窗口的背景色置为；,以边为中心的边缘填充算法,2、对多边形的每一条非水平边做：从该边上的每个象素开始向右求反；,25,2014-2015-1:CG:SCUEC,边缘填充算法,边缘填充算法的数据结构和程序结构都比扫描线算法简单，原因是求反运算代替了排序算法执行时需对帧缓冲器中的大批元素反复赋值，算法运行效率较低另外，如果区域内原来有其他的颜色，也不能保证最后区域内的颜色是多边形的颜色，所以对单值图像比较有用,26,2014-2015-1:CG:SCUEC,结 束,
