计算机图形学(多边形的扫描转换).ppt

第三章基本光栅图形算法,本章内容,2,2014-2015-1:CG:SCUEC,多边形的扫描转换,什么是多边形的扫描转换？把多边形的顶点表示转化为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个像素，并给帧缓冲器内各个对应元素设置相应的灰度和颜色多边形的扫描转换过程，实际上是给多边形包围的区域着色的过程,多边形的表示方法顶点表示:用多边形的顶点序列来刻划多边形该表示方法几何意义强、占内存少不能明确指出哪些像素在多边形内，不能直接用于面着色点阵表示:用位于多边形内的象素的集合来刻划多边形该方法便于利用帧缓冲器表示图形，是面着色所需要的图形表示形式失去了许多重要的几何信息,3,2014-2015-1:CG:SCUEC,为什么研究图形的扫描转换与区域填充？,与单纯由线条所构成的线画图形相比，采用面着色绘制的光栅图形显得更为生动、直观，真实感更强,面着色可以使使光栅图形的画面明暗自然,色彩丰富,形象逼真,具有真实感,4,2014-2015-1:CG:SCUEC,逐点判断法,逐点判断是实现多边形扫描转换最简单的方法逐个像素判别，确定它们是否在多边形内，从而给出位于多边形内的点（像素）的集合,#defineMAX100typedefstructintVertexNum;/多边形顶点个数PointVerticesMAX/多边形顶点数组Polygon/多边形,5,2014-2015-1:CG:SCUEC,voidFillPolygonPbyP(PolygonP)intx,y;for(x=xmin;xyk+1,那么扫描线d与上述边也是相交的，交点横坐标递增序列记为,对同一条边，前一条扫描线e与该边的交点为xeir，而后一条扫描线d=e+1与该边的交点则为xdir=xeir+1/m，如右图所示。,以上性质称为边的连续性。,12,2014-2015-1:CG:SCUEC,存在的问题,上述三种形式的连续性都基于一个几何事实：每一条扫描线与多边形P的边界的交点个数都是偶数（包括零）。但是当扫描线与多边形P的边界的交点恰好是P的顶点时：如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数（如下图中的扫描线7的情况）；若将每一奇点都简单地计为两个交点，同样会导致反常的结果（如下图中扫描线2的情况）。,13,2014-2015-1:CG:SCUEC,多边形顶点的分类,设多边形P的顶点为这些顶点可分为两类：极值点和非极值点。如果，则称顶点为极值点（如下图中的）；否则称为非极值点（如下图中的）。,14,2014-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个交点配对，每对交点就代表扫描线与多边形的一个相交区间。区间填色：把相交区间内的像素置成多边形的颜色，相交区间外的像素置成背景色。,16,2014-2015-1:CG:SCUEC,算法的数据结构,与当前扫描线相交的边称为活性边。把活性边与扫描线的交点按x坐标递增的顺序放在一个链表中，该链表就称为活性边表（ActiveEdgeList,AEL）。,设多边形某一条边的方程为，当前扫描线与该边的交点坐标为，则下一条扫描线与该边的交点不需要重新计算，只要加一个增量即可。因为此时有,其中为常数，并规定时，。,17,2014-2015-1:CG:SCUEC,算法的数据结构,18,2014-2015-1:CG:SCUEC,为方便活性边表的建立与更新，还要为每一条扫描线建立一个新边表（NewEdgeList,NEL），存放在该扫描线上第一次出现的边。也就是说，如果某边的较低端点为，则该边就放在扫描线的新边表中。,注意：水平边不放到任何扫描线的NEL中，即水平边不参加分类。NEL中的节点结构与AEL相同，只是x在这里不再表示边与扫描线的交点，而是表示该边较低端点的x坐标值。,算法的数据结构,19,2014-2015-1:CG:SCUEC,算法描述,根据给出的多边形顶点坐标，建立新边表NEL；(AEL初始化)将边的活性边表AEL设置为空(y初始化)取扫描线纵坐标y的初始值为NEL中非空元素的最小序号,20,2014-2015-1: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的扫描线(当前扫描线)执行下列步骤，直到新边表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:CG:SCUEC,以扫描线为中心的边缘填充算法,设x0,x2,xm是扫描线y=e与多边形P的边界交点x坐标序列（不要求递增排列），则该扫描线上位于多边形P内的像素可按如下步骤求得：步骤1：将位于扫描线y=e上的所有像素都着上值为M的颜色forx:=xmintoxmaxdosetpixel(framebuffer,x,e,M)步骤2：将位于扫描线y=e上所有坐标大于xi(i=1,2,m)的像素向右求反fori:=1tomdoforx:=xitoxmaxdocomplement(framebuffer,x,e),24,2014-2015-1:CG:SCUEC,1、将绘图窗口的背景色置为；,以边为中心的边缘填充算法,2、对多边形的每一条非水平边做：从该边上的每个象素开始向右求反；,25,2014-2015-1:CG:SCUEC