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

1、计算机图形学第三章第三章 基本光栅图形算法基本光栅图形算法本章内容1直线的扫描转换2圆的扫描转换3多边形的扫描转换多边形的扫描转换4区域填充区域填充5光栅图形的反走样算法光栅图形的反走样算法22014-2015-1:CG:SCUEC多边形的扫描转换v 什么是多边形的扫描转换？ 把多边形的顶点表示转化为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个像素，并给帧缓冲器内各个对应元素设置相应的灰度和颜色 多边形的扫描转换过程，实际上是给多边形包围的区域着色的过程图图1 1 多边形的顶点表示多边形的顶点表示P0P1P2P3P4 图图2 2 多边形的点阵表示多边形的点阵表示v 多边形的表示

2、方法顶点表示: 用多边形的顶点序列来刻划多边形 该表示方法几何意义强、占内存少 不能明确指出哪些像素在多边形内，不能直接用于面着色点阵表示: 用位于多边形内的象素的集合来刻划多边形 该方法便于利用帧缓冲器表示图形，是面着色所需要的图形表示形式 失去了许多重要的几何信息32014-2015-1:CG:SCUEC为什么研究图形的扫描转换与区域填充？哪个长方形在前，哪个在后？哪个长方形在前，哪个在后？v 与单纯由线条所构成的线画图形相比，采用面着色绘制的光栅图形显得更为生动、直观，真实感更强v 面着色可以使使光栅图形的画面明暗自然,色彩丰富,形象逼真,具有真实感42014-2015-1:CG:SCU

3、EC逐点判断法v 逐点判断是实现多边形扫描转换最简单的方法 逐个像素判别，确定它们是否在多边形内，从而给出位于多边形内的点（像素）的集合#define MAX 100typedef struct int VertexNum; / 多边形顶点个数多边形顶点个数 Point VerticesMAX /多边形顶点数组多边形顶点数组 Polygon / 多边形多边形52014-2015-1:CG:SCUECvoid FillPolygonPbyP(Polygon P) int x, y; for(x = xmin; x = xmax; x+) for(y = xmin; y e, d y k+1, 那

4、那么扫描线么扫描线d与上述边也是相交的，与上述边也是相交的，交点交点横坐标递增序列记为横坐标递增序列记为leieieieixxxx,321123,didididihxxxx 对同一条边，前一条扫描线对同一条边，前一条扫描线e与该边与该边的交点为的交点为xeir，而后一条扫描线，而后一条扫描线d=e+1与该边的交点则为与该边的交点则为xdir= xeir +1/m ，如右图所示。如右图所示。 以上性质称为以上性质称为边的连续性。边的连续性。122014-2015-1:CG:SCUEC存在的问题上述三种形式的连续性都基于一个几何事实：每一条扫描线与多上述三种形式的连续性都基于一个几何事实：每一条扫

5、描线与多边形边形P 的边界的交点个数都是偶数（包括零）。的边界的交点个数都是偶数（包括零）。但是当扫描线与多边形但是当扫描线与多边形P 的边界的交点恰好是的边界的交点恰好是P的顶点时：如果的顶点时：如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数（如把每一奇点简单地计为一个交点，则交点个数可能出现奇数（如下图中的扫描线下图中的扫描线7的情况）；若将每一奇点都简单地计为两个交的情况）；若将每一奇点都简单地计为两个交点，同样会导致反常的结果（如下图中扫描线点，同样会导致反常的结果（如下图中扫描线2的情况）。的情况）。扫描线1扫描线2扫描线7EFGx123459681171012012345

6、67yP1P2P3P4P5P6(2,2)(2,2)(5,1)(5,1)(11,3)(11,3)(2,7)(2,7)(5,5)(5,5)(11,8)(11,8)132014-2015-1:CG:SCUEC多边形顶点的分类设多边形P 的顶点为 这些顶点可分为两类：极值点和非极值点。如果 ，则称顶点 为极值点（如下图中的 ）；否则称 为非极值点（如下图中的 ）。, 1 , 0),(niyxPiii0)(11iiiiyyyyiP123568,P P P P P PiP047,P P PP0P1P2P3P4P5P6P7多边形顶点的分类多边形顶点的分类P8142014-2015-1:CG:SCUEC奇点的

7、处理 为了使交点个数保持为偶数，规定当奇点是P的极值点时，该点按两个交点计算；否则按一个交点计算。 预处理: 若Pi是非极值点，则将 两边中位于扫描线y = yi上方的那条边在Pi点处截去一单位长。11,iiiippppPiyi-1y = yiyi+1Piyi-1y = yiyi+1非极值点的处理非极值点的处理152014-2015-1:CG:SCUEC算法的实现步骤对于每一条扫描线，多边形的扫描转换可分为以下4步： 求交点：计算扫描线与多边形各边的交点，设交点个数为n。 交点排序：把所有的交点按x值递增的顺序进行排列。 交点配对：将排序后的第1个与第2个交点，第3个与第4个交点，第n-1个与

8、第n个交点配对，每对交点就代表扫描线与多边形的一个相交区间。 区间填色：把相交区间内的像素置成多边形的颜色，相交区间外的像素置成背景色。1234162014-2015-1:CG:SCUEC算法的数据结构活性边表与当前扫描线相交的边称为活性边。把活性边与扫描线的交点按x坐标递增的顺序放在一个链表中，该链表就称为活性边表（Active Edge List, AEL ）。 设多边形某一条边的方程为 ，当前扫描线 与该边的交点坐标为 ，则下一条扫描线 与该边的交点 不需要重新计算，只要加一个增量 即可。因为此时有0axbyciyy( ,)iix y1iyy11(,)iixyx111()iiiibcbb

9、xb ycyxaaaaa 其中 为常数，并规定 时， 。/xb a 0a 0 x 172014-2015-1:CG:SCUEC使用增量计算时，还要知道一条边何时不再与下一条扫描线相交，以及时地把该边从活性边表中删除，因此需要记录下与该边相交的最高扫描线号。综上，AEL中的节点应由如下四个域组成： : 边的上端点的y坐标，即与该边相交的最高扫描线号。 x: 边与扫描线的交点的x坐标。 : 从当前扫描线到下一条扫描线间的x坐标的增量，即边的斜率的倒数。Next: 指向下一条边的指针。maxyx算法的数据结构182014-2015-1:CG:SCUEC新边表为方便活性边表的建立与更新，还要为每一条扫

10、描线建立一个新边表（New Edge List, NEL ），存放在该扫描线上第一次出现的边。也就是说，如果某边的较低端点为 ，则该边就放在扫描线 的新边表中。minyminy注意：水平边不放到任何扫描线的NEL中，即水平边不参加分类。NEL中的节点结构与AEL相同，只是 x 在这里不再表示边与扫描线的交点，而是表示该边较低端点的 x 坐标值。 算法的数据结构192014-2015-1:CG:SCUEC算法描述1. 根据给出的多边形顶点坐标，建立新边表NEL； 2. (AEL初始化)将边的活性边表AEL设置为空3. (y初始化)取扫描线纵坐标y的初始值为NEL中非空元素的最小序号202014-

11、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+14. 按从下到上的顺

12、序对纵坐标值为y的扫描线(当前扫描线)执行下列步骤，直到新边表NEL和活性边表AEL都为空算法描述212014-2015-1:CG:SCUECP0(2, 5), P1(2, 10), P2(9, 6), P3(16, 11), P4(16, 4), P5(12, 2), P6(7, 2)具体例子222014-2015-1:CG:SCUEC边缘填充算法基本思想假设某像素的颜色是 ，对该像素做偶数次求补运算后，其颜色还是 ；做奇数次求补运算后，其颜色变为 。在光栅图形中，如某区域已着上值为M 的某种颜色，则上述求补运算的结果是：对区域作偶数次求补运算后，该区域的颜色不变；作奇数次求补运算后，该区域

13、的颜色则变成值为 的颜色。 CCCM232014-2015-1: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)242014-2015-1:CG:SCUEC1、将绘图窗口的背景色置为 ；M以边为中心的边缘填充算法2、对多边