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

计算机图形学 第三章 基本光栅图形算法 本章内容 1 直线的扫描转换 2 圆的扫描转换 3 多边形的扫描转换 4 区域填充 5 光栅图形的反走样算法 * 2009-2010-2:CG:SCUEC 多边形的扫描转换 什么是多边形的扫描转换？ 把多边形的顶点表示转化为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个像素，并给帧缓冲器内各个对应元素设置相应的灰度和颜色 多边形的扫描转换过程，实际上是给多边形包围的区域着色的过程 图1 多边形的顶点表示 P0 P1 P2 P3 P4 图2 多边形的点阵表示 多边形的表示方法 顶点表示: 用多边形的顶点序列来刻划多边形 该表示方法几何意义强、占内存少 不能明确指出哪些像素在多边形内，不能直接用于面着色 点阵表示: 用位于多边形内的象素的集合来刻划多边形 该方法便于利用帧缓冲器表示图形，是面着色所需要的图形表示形式 失去了许多重要的几何信息 * 2009-2010-2:CG:SCUEC 为什么研究图形的扫描转换与区域填充？ 哪个长方形在前，哪个在后？ 哪个长方形在前，哪个在后？ 与单纯由线条所构成的线画图形相比，采用面着色绘制的光栅图形显得更为生动、直观，真实感更强 面着色可以使使光栅图形的画面明暗自然,色彩丰富,形象逼真,具有真实感 * 2009-2010-2:CG:SCUEC 逐点判断法 逐点判断是实现多边形扫描转换最简单的方法 逐个像素判别，确定它们是否在多边形内，从而给出位于多边形内的点（像素）的集合 #define MAX 100 typedef struct { int VertexNum; // 多边形顶点个数 Point Vertices[MAX] //多边形顶点数组 } Polygon // 多边形 * 2009-2010-2: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，否则取值False。 FrameBuffer(x, y)：在帧缓存中对应位置存放屏幕上像素(x, y)的颜色值。 POLYGON-COLOR：多边形P的颜色值。 BACKGROUND-COLOR：屏幕的背景色。 逐点判断法 * 2009-2010-2:CG:SCUEC 扫描线算法 基本思想 扫描线算法按扫描线的顺序计算出扫描线与多边形的相交区间，然后用要求的颜色填充这些区间内的像素。该算法利用了相邻像素间的连续性，避免对像素的逐点判断和反复求交运算， 减少了计算量，提高了算法速度。 先求出扫描线与多边形边的交点，利用扫描线的连续性求出多边形与扫描线相交的连续区域，然后利用多边形边的连续性，求出下一条扫描线与多边形的交点，对所有扫描线由上到下依次处理。 区域的连续性、扫描线的连续性、边的连续性 * 2009-2010-2:CG:SCUEC 区域的连续性（2－1） 设多边形 P 的顶点为Pi = (xi, yi)，i =0,1,2, …, n，又设 是各顶点Pi的纵坐标 yi 的递减数列,当 ,屏幕上位于于y = 和 y = 两条扫描线之间的长方形区域{ ， }被多边形 P 的边分割成若干梯形（三角形看作其中一底边长为0的梯形）。 P0 P1 P2 P3 P4 P5 P6 P7 P8 * 2009-2010-2:CG:SCUEC 区域的连续性（2－2） 如果知道长方形区域内任一梯形内一点关于多边形P的内外关系后，即可确定区域内所有梯形关于P的内外关系。此性质称为区域的连续性。 这些梯形有如下的三个性质： P0 P1 P2 P3 P4 P5 P6 P7 P8 梯形的两底边分别在y = 和y = 两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。 梯形可分为两类：一类位于多边形P的内部；另一类在多