基本光栅图形算法

1、第三章 基本光栅图形算法,本章内容,2,多边形的扫描转换,什么是多边形的扫描转换？ 把多边形的顶点表示转化为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个像素，并给帧缓冲器内各个对应元素设置相应的灰度和颜色 多边形的扫描转换过程，实际上是给多边形包围的区域着色的过程,多边形的表示方法 顶点表示: 用多边形的顶点序列来刻划多边形 该表示方法几何意义强、占内存少 不能明确指出哪些像素在多边形内，不能直接用于面着色 点阵表示: 用位于多边形内的象素的集合来刻划多边形 该方法便于利用帧缓冲器表示图形，是面着色所需要的图形表示形式 失去了许多重要的几何信息,3,为什么研究图形的扫描转换与区

2、域填充？,与单纯由线条所构成的线画图形相比，采用面着色绘制的光栅图形显得更为生动、直观，真实感更强,面着色可以使使光栅图形的画面明暗自然,色彩丰富,形象逼真,具有真实感,4,逐点判断法,逐点判断是实现多边形扫描转换最简单的方法 逐个像素判别，确定它们是否在多边形内，从而给出位于多边形内的点（像素）的集合,#define MAX 100 typedef struct int VertexNum; / 多边形顶点个数 Point VerticesMAX /多边形顶点数组 Polygon / 多边形,5,void FillPolygonPbyP(Polygon P) int x, y; for(x

3、= 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，否则取值False。,FrameBuffer(x, y)：在帧缓存中对应位置存放屏幕上像素(

4、x, y)的颜色值。,POLYGON-COLOR：多边形P的颜色值。,BACKGROUND-COLOR：屏幕的背景色。,逐点判断法,6,扫描线算法,扫描线算法按扫描线的顺序计算出扫描线与多边形的相交区间，然后用要求的颜色填充这些区间内的像素。该算法利用了相邻像素间的连续性，避免对像素的逐点判断和反复求交运算， 减少了计算量，提高了算法速度。,先求出扫描线与多边形边的交点，利用扫描线的连续性求出多边形与扫描线相交的连续区域，然后利用多边形边的连续性，求出下一条扫描线与多边形的交点，对所有扫描线由上到下依次处理。,区域的连续性、扫描线的连续性、边的连续性,7,区域的连续性（21）,设多边形 P 的

5、顶点为Pi = (xi, yi)，i =0,1,2, , n，又设 是各顶点Pi的纵坐标 yi 的递减数列,当 ,屏幕上位于于y = 和 y = 两条扫描线之间的长方形区域 ， 被多边形 P 的边分割成若干梯形（三角形看作其中一底边长为0的梯形）。,8,区域的连续性（22）,如果知道长方形区域内任一梯形内一点关于多边形P的内外关系后，即可确定区域内所有梯形关于P的内外关系。此性质称为区域的连续性。,这些梯形有如下的三个性质：,梯形的两底边分别在y = 和y = 两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。 梯形可分为两类：一类位于多边形P的内部；另一类在多边形P的外部。 两类梯形在长

6、方形区域 ， 内相间的排列。即相邻的两梯形必有一个在多边形P内，另一个在P外。,9,设多边形P的顶点 ，将各顶点 的纵坐标 按递减顺序排列 , 即 设当前扫描线 ， ， 与多边形P的边 的交点记为 。设 为 与P的边界各交点横坐标的递增序列，该序列称为交点序列。,扫描线的连续性（21）,10,1、交点个数 l 是偶数； 2、扫描线上的区间 l1位于多边形P内（下图中的红线段部分），其余区间都在P 外（下图中的虚线段部分），两类区间沿扫描线相间排列。这些性质就称为扫描线的连续性。,扫描线的连续性（22）,交点序列具有以下性质：,11,边的连续性,两交点序列元素的个数相等，即l=h,当前扫描线e与

7、多边形的某些边是相交的,设 是该扫描线与这些边各交点横坐标的递增序列。设下一条扫描线为d=e+1，如果yk e, d y k+1, 那么扫描线d与上述边也是相交的，交点横坐标递增序列记为,对同一条边，前一条扫描线e与该边的交点为xeir，而后一条扫描线d=e+1与该边的交点则为xdir= xeir +1/m ，如右图所示。,以上性质称为边的连续性。,12,存在的问题,上述三种形式的连续性都基于一个几何事实：每一条扫描线与多边形P 的边界的交点个数都是偶数（包括零）。 但是当扫描线与多边形P 的边界的交点恰好是P的顶点时：如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数（如下图中的扫描线

8、7的情况）；若将每一奇点都简单地计为两个交点，同样会导致反常的结果（如下图中扫描线2的情况）。,13,多边形顶点的分类,设多边形P 的顶点为 这些顶点可分为两类：极值点和非极值点。 如果 ，则称顶点 为极值点（如下图中的 ）；否则称 为非极值点（如下图中的 ）。,14,奇点的处理,为了使交点个数保持为偶数，规定当奇点是P的极值点时，该点 按两个交点计算；否则按一个交点计算。,预处理: 若Pi是非极值点，则将 两边中位于扫描线 y = yi上方的那条边在Pi点处截去一单位长。,非极值点的处理,15,算法的实现步骤,对于每一条扫描线，多边形的扫描转换可分为以下4步： 求交点：计算扫描线与多边形各边

9、的交点，设交点个数为n。 交点排序：把所有的交点按x值递增的顺序进行排列。 交点配对：将排序后的第1个与第2个交点，第3个与第4个交点，第n-1个与第n个交点配对，每对交点就代表扫描线与多边形的一个相交区间。 区间填色：把相交区间内的像素置成多边形的颜色，相交区间外的像素置成背景色。,16,算法的数据结构,与当前扫描线相交的边称为活性边。把活性边与扫描线的交点按x坐标递增的顺序放在一个链表中，该链表就称为活性边表（Active Edge List, AEL ）。,设多边形某一条边的方程为 ，当前扫描线 与该边的交点坐标为 ，则下一条扫描线 与该边的交点 不需要重新计算，只要加一个增量 即可。因

10、为此时有,其中 为常数，并规定 时， 。,17,算法的数据结构,18,为方便活性边表的建立与更新，还要为每一条扫描线建立一个新边表（New Edge List, NEL ），存放在该扫描线上第一次出现的边。也就是说，如果某边的较低端点为 ，则该边就放在扫描线 的新边表中。,注意：水平边不放到任何扫描线的NEL中，即水平边不参加分类。NEL中的节点结构与AEL相同，只是 x 在这里不再表示边与扫描线的交点，而是表示该边较低端点的 x 坐标值。,算法的数据结构,19,算法描述,根据给出的多边形顶点坐标，建立新边表NEL； (AEL初始化)将边的活性边表AEL设置为空 (y初始化)取扫描线纵坐标y的

11、初始值为NEL中非空元素的最小序号,20,如新边表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. 按

12、从下到上的顺序对纵坐标值为y的扫描线(当前扫描线)执行下列步骤，直到新边表NEL和活性边表AEL都为空,算法描述,21,P0(2, 5), P1(2, 10), P2(9, 6), P3(16, 11), P4(16, 4), P5(12, 2), P6(7, 2),具体例子,22,边缘填充算法,假设某像素的颜色是 ，对该像素做偶数次求补运算后，其颜色还是 ；做奇数次求补运算后，其颜色变为 。在光栅图形中，如某区域已着上值为M 的某种颜色，则上述求补运算的结果是：对区域作偶数次求补运算后，该区域的颜色不变；作奇数次求补运算后，该区域的颜色则变成值为 的颜色。,23,以扫描线为中心的边缘填充算法,设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),