第二章光栅图形学 光栅图形显示器可以看作一个象素的矩阵。在光栅显示器上显示任何一种图形,实际上都是一些具有 种或多种颜色的象素集合。确定最佳逼近图形的象素集合,并用指定属性写象素的过程称为图形的扫描 转换或光栅化。对于一维图形,在不考虑线宽时,用一个象素宽的直、曲线来显示图形。二维图形的光栅 化必须确定区域对应的象素集,并用指定的属性或图案显示之,即区域填充。 任何图形进行光栅化时,必须显示在屏幕的一个窗口里,超出窗口的图形不予显示。确定一个图形的 哪些部分在窗口内,必须显示:哪些部分落在窗口之外,不该显示的过程称为裁剪。裁剪通常在扫描转换 之前进行,从而可以不必对那些不可见的图形进行扫描转换。 对图形进行光栅化时,由于显示器的空间分辨率有限,对于非水平、垂直、±45°直线,因象素逼近误 差,使所画图形产生畸变(台阶、锯齿)的现象称之为走样:用于减少或消除走样的技术称为反走样 ( ant ia l i as ing)。提高显示器的空间分辨率可以减轻走样问题,但这是以提高设备成本为代价的。实际上 当显示器的象素可以用多亮度显示时,可以通过调整图形上各象素的亮度来减轻走样问题 由于存在不透光的物体,因此阻挡了来自某些物体部分的光线到达观察者,这些物体部分成为隐藏部 分。隐藏部分是不可见的,如果不把隐藏的线或面删除,还可能发生对图的错误理解。为了使计算机图形 够真实的反映这一现象,必须把隐藏的部分从图中消除,习惯上称作消除隐藏线和隐藏面,或简称为消 2.1直线段的扫描转换算法 在数学上,理想的直线是没有宽度的,由无数个点构成的集合。当我们对直线进行光栅化时,只能在显 示器所给定的有限个象素组成的矩阵中,确定最佳逼近于该直线的一组象素,并且按扫描线顺序,对这些 象素进行写操作,这就是通常所说的用显示器绘制直线或直线的扫描转换。由于一个图中可以包含成千上 万条直线,所以要求绘制算法应尽可能的快。本节我们介绍一个象素宽直线的三个常用算法:数值微分法 (DDA)、中点画线法和 Bresenham算法 211数值微分(DDA法 已知过端点P(Aony,P(x,y)的直线段L(P),;直线斜率为x0画线过程从x的 左端点x开始,向ⅹ右端点步进,步长=1(个象素),计算相应的y坐标y=kx+B:取象素点(x, round(y) 作为当前点的坐标 计算v yi* kxM+B =k1X:+B+k△X =y+k△x 即:当Ⅹ每递增1,y递增k(即直线斜率): DDA画线算法程序 void DDALine(int Xo, int yo, int Xi, int y, int color) int X: float dx, dy, y, k; dx Xr-Xo, dy=yr-yo k=dyldx, y=yo Line:P0(0,0)--P1(5,2) for(X=XG;X≤X,X++) o drawpixel(x, int(y+0. 5), color) 举例:用DDA方法扫描转换连接两点P0(0,0)和P1(52) x int(y+0.5)y+0.5 000 100.4+0.5 210.8+0.5 012345 311.2+0.5 421.6+0.5 图2.1.1直线段的扫描转换 注意上述分析的算法仅适用于k≤1的情形。在这种情况下,x每 必须把ⅹ,y地位互换,y每增加1,x相应增加1/k。在这个算法中,y与k必须用浮点数表示,而且每一 步都要对y进行四舍五入后取整。这使得它不利于硬件实现 计算机图形学第二章第18页共27页
计算机图形学 第二章 第 18 页 共 27 页 第二章 光栅图形学 光栅图形显示器可以看作一个象素的矩阵。在光栅显示器上显示任何一种图形，实际上都是一些具有 一种或多种颜色的象素集合。确定最佳逼近图形的象素集合，并用指定属性写象素的过程称为图形的扫描 转换或光栅化。对于一维图形，在不考虑线宽时，用一个象素宽的直、曲线来显示图形。二维图形的光栅 化必须确定区域对应的象素集，并用指定的属性或图案显示之，即区域填充。 任何图形进行光栅化时，必须显示在屏幕的一个窗口里，超出窗口的图形不予显示。确定一个图形的 哪些部分在窗口内，必须显示；哪些部分落在窗口之外，不该显示的过程称为裁剪。裁剪通常在扫描转换 之前进行，从而可以不必对那些不可见的图形进行扫描转换。 对图形进行光栅化时，由于显示器的空间分辨率有限，对于非水平、垂直、±45 直线，因象素逼近误 差，使所画图形产生畸变(台阶、锯齿)的现象称之为走样；用于减少或消除走样的技术称为反走样 (antialiasing)。提高显示器的空间分辨率可以减轻走样问题，但这是以提高设备成本为代价的。实际上， 当显示器的象素可以用多亮度显示时，可以通过调整图形上各象素的亮度来减轻走样问题。 由于存在不透光的物体，因此阻挡了来自某些物体部分的光线到达观察者，这些物体部分成为隐藏部 分。隐藏部分是不可见的，如果不把隐藏的线或面删除，还可能发生对图的错误理解。为了使计算机图形 能够真实的反映这一现象，必须把隐藏的部分从图中消除，习惯上称作消除隐藏线和隐藏面，或简称为消 隐。 2.1 直线段的扫描转换算法 在数学上，理想的直线是没有宽度的，由无数个点构成的集合。当我们对直线进行光栅化时，只能在显 示器所给定的有限个象素组成的矩阵中，确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些 象素进行写操作，这就是通常所说的用显示器绘制直线或直线的扫描转换。由于一个图中可以包含成千上 万条直线，所以要求绘制算法应尽可能的快。本节我们介绍一个象素宽直线的三个常用算法：数值微分法 （DDA）、中点画线法和 Bresenham 算法。 2.1.1 数值微分(DDA)法 已知过端点 P0 (x0, y0), P1(x1, y1)的直线段 L(P0, P1),；直线斜率为 画线过程从 x 的 左端点 x0开始，向 x 右端点步进，步长=1(个象素)，计算相应的 y 坐标 y=kx+B；取象素点(x, round(y)) 作为当前点的坐标。 计算 yi+1 = kxi+1+B = k1 xi+B+k x = yi+k x 当 x =1; yi+1 = yi+k 即：当 x 每递增 1，y 递增 k(即直线斜率)； DDA 画线算法程序 void DDALine(int x0,int y0,int x1,int y1,int color) int x； float dx, dy, y, k; dx = x1-x0, dy=y1-y0; k=dy/dx, y=y0; for (x=x0; x x1, x++) drawpixel (x, int(y+0.5), color); y=y+k; 举例：用 DDA 方法扫描转换连接两点 P0（0,0）和 P1（5,2）的直线段。 x int(y+0.5) y+0.5 0 0 0 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 注意上述分析的算法仅适用于 k ≤1 的情形。在这种情况下，x 每增加 1,y 最多增加 1。当 k 1 时， 必须把 x，y 地位互换，y 每增加 1，x 相应增加 1/k。在这个算法中，y 与 k 必须用浮点数表示，而且每一 步都要对 y 进行四舍五入后取整。这使得它不利于硬件实现。 图 2.1.1 直线段的扫描转换
212中点画线法 画直线段的过程中,当前象素点为(X,y),一个象素点有两种可选择点p1(x+1,y)或p2(x+1,y+1)。若 M=(x+1,y+0.5),为p与p2之中点,Q为理想直线与x=xp+1垂线的交点。当M在Q的下方,则P2应为下 个象素点:M在Q的上方,应取P1为下一点。就是中点画线法的基本原理 P2 P 图212中点画线法每步迭代涉及的象素和中点示意图 下面讨论中点画线法的实现。令直线段L(p(xyo),p(X1,y),其方程式F(x,y)=ax+by+c=0。其中 a=yoy,b=X-X,c=xy-Xy;点与L的关系:on:F(xy)=0;up:F(x,y)>0;down:F(x,y)<0:因此,欲判断 中M在Q点的上方还是下方,只要把M代入F(X,y),并判断它的符号。构造判别式 d=F(M)=F(x+1,y+0.5)=a(X+1)+by+0.5)+c 当d<0,M在L(Q点)下方,取P2为下一个象素 当d>0,M在L(Q点)上方,取P为下一个象素 当d=0,选P1或P2均可,约定取P1为下一个象素 注意到d是xpyp的线性函数,可采用增量计算,提高运算效率, 若当前象素处于￠≥0情况,则取正右方象素P1(X+1,yp),要判下一个象素位置,应计算d=F(x+2 y+0.5)=a(x+2)+b(y+0.5)=d+a:增量为a 若d<0时,则取右上方象素P2(x+1,yp+1)。要判断再下一象素,则要计算 d=F(x+2,y+15)=a(X+2)+by+15)+c=d+a+b;增量为a+b 画线从(X,y)开始,d的初值d=F(x+1,y+0.5)=F(X,y)+a+0.5b因F(x,yo)=0,则d=a+0.5b 由于我们使用的只是d的符号,而且d的增量都是整数,只是初始值包含小数。因此,我们可以用2d 代替d来摆脱小数,写出仅包含整数运算的算法。 中点画线算法程序 void Midpoint Line(int Xo, int yo, int XI, int yi, int color) i int a, b, dL,d2, d, x,y, a=yo-y1, b=X -Xo, d=2*a+b: d=2*a,d=2*(a+b) X-Xo, y=yo drawpixel(x, y, color) if(d<0)(X++,y++,d+=da;} else X++, d+di; 1 0 drawpixel (x, y, color) 1/* while */ 图2.1.3用中点画线法对连接两点的直线进行光栅化 3/mid Point Line*/ 举例用中点画线方法扫描转换连接两点P0(0,0)和P1(52)的直线段 a=y0y1=2;b=x1-X0=5;d0=2a+b=1;d1=2*a=4d2=2a+b)=6 xy d 00 10-3 31-1 425 52 问题1:若上述算法往下取二步(Δj=2),则算法和象素的取法将变成怎样? 213 Bresenham算法 Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。该方法类似于中点法,由误差项 符号决定下一个象素取右边点还是右上点 计算机图形学第二章第19页共27页
计算机图形学 第二章 第 19 页 共 27 页 2.1.2 中点画线法 画直线段的过程中，当前象素点为(xp, yp)，一个象素点有两种可选择点 p1(xp+1, yp)或 p2(xp+1, yp+1)。若 M=(xp+1, yp+0.5)，为 p1与 p2之中点，Q 为理想直线与 x=xp+1 垂线的交点。当 M 在 Q 的下方，则 P2 应为下 一个象素点；M 在 Q 的上方，应取 P1 为下一点。就是中点画线法的基本原理。 图 2.1.2 中点画线法每步迭代涉及的象素和中点示意图 下面讨论中点画线法的实现。令直线段 L(p0(x0,y0), p1(x1, y1)), 其方程式 F(x, y)=ax+by+c=0。其中， a=y0-y1, b=x1-x0, c=x0y1-x1y0; 点与 L 的关系：on: F(x,y)=0; up: F(x, y)>0; down: F(x, y)<0; 因此，欲判断 中 M 在 Q 点的上方还是下方，只要把 M 代入 F（x，y），并判断它的符号。构造判别式: d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c 当 d<0，M 在 L(Q 点)下方，取 P2为下一个象素； 当 d>0，M 在 L(Q 点)上方，取 P1为下一个象素； 当 d=0，选 P1或 P2均可，约定取 P1为下一个象素； 注意到 d 是 xp, yp的线性函数，可采用增量计算，提高运算效率。 若当前象素处于 d 0 情况，则取正右方象素 P1（xp+1, yp）,要判下一个象素位置，应计算 d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a； 增量为 a 若 d<0 时，则取右上方象素 P2（xp+1, yp+1）。要判断再下一象素，则要计算 d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ；增量为 a＋b 画线从(x0, y0)开始，d 的初值 d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b 因 F(x0, y0)=0，则 d0=a+0.5b。 由于我们使用的只是 d 的符号，而且 d 的增量都是整数，只是初始值包含小数。因此，我们可以用 2d 代替 d 来摆脱小数，写出仅包含整数运算的算法。 中点画线算法程序 void Midpoint Line (int x0,int y0,int x1, int y1,int color) { int a, b, d1, d2, d, x, y; a=y0-y1, b=x1-x0, d=2*a+b; d1=2*a, d2=2* (a+b); x=x0, y=y0; drawpixel(x, y, color); while (x<x1) { if (d<0) {x++, y++, d+=d2; } else {x++, d+=d1;} drawpixel (x, y, color); } /* while */ } /* mid PointLine */ 举例 用中点画线方法扫描转换连接两点 P0（0,0）和 P1（5,2）的直线段。 a=y0-y1=-2; b=x1-x0=5; d0=2*a+b=1;d1=2*a=-4;d2=2*(a+b)=6 , x y d 0 0 1 1 0 -3 2 1 3 3 1 -1 4 2 5 5 2 15 问题 1：若上述算法往下取二步( i=2)，则算法和象素的取法将变成怎样？ 2.1.3 Bresenham 算法 Bresenham 算法是计算机图形学领域使用最广泛的直线扫描转换算法。该方法类似于中点法，由误差项 符号决定下一个象素取右边点还是右上点。 图 2.1.3 用中点画线法对连接两点的直线进行光栅化
算法原理如下:过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂 直网格线的交点,然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算,使得 对于每一列,只要检査一个误差项的符号,就可以确定该列的所求象素。 如下图所示。设直线方程为)=y+k(x- 其中k=dydx。假设x列的象素已经 确定为X,其行坐标为y。那么下一个象素的列坐标为x+1,而行坐标要么不变为y,要么递增1为y+1 是否增1取决于如图所示误差项d的值。因为直线的起始点在象素中心,所以误差项d的初值d0=0。X 下标每增加1,d的值相应递增直线的斜率值k,即d=d+k。一旦￠l,就把它减去1,这样保证d在0、 1之间。当￠0.5时,直线与X+1列垂直网格交点最接近于当前象素(x,y)的右上方象素(X+1,y +1);而当d<0.5时,更接近于右方象素(x+1,y)。为方便计算,令e=d-0.5,e的初值为-0.5, 增量为k。当e≥0时,取当前象素(X,y)的右上方象素(x+1,y+1):而当e<0时,更接近于右方 象素(X+1,y)。 图21.4 Bresenham算法所用误差项的几何含义 Bresenham画线算法程序: void Bresenhamline(int Xo, int yo, int XI, int yi, int color) I int x, y, dx, dy: float k. e dx =XrXo, dy= yr-yo, k=dy/dx e=-0.5, X=Xo, y=yo for(=0;k≤dx;++) i drawpixel (x, y, color) X=X+1, e=e+k. y++,e=e-1} 举例:用 Bresenham方法扫描转换连接两点P0(0,0)和P1 (5,2)的直线段 10-0.1 21-0.7 31-0.3 42-0.9 52-0.5 上述 bresenham算法在计算直线斜率与误差项时用到小数01 与除法。可以改用整数以避免除法。由于算法中只用到误差项 的符号,因此可作如下替换:e=2*e*ax 改进的 Bresenham画线算法程序: void Inter Bresenhamline(int Xo, int yo, int XI, int yi, int color) dx= X -Xo, dy= yr-yo, e=-dx X-Xo, y=yo, idrawpixel(x, y, color if(e≥0){ 2d×} 计算机图形学第二章第20页共27页
计算机图形学 第二章 第 20 页 共 27 页 算法原理如下：过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂 直网格线的交点，然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算，使得 对于每一列，只要检查一个误差项的符号，就可以确定该列的所求象素。 如下图所示。 设直线方程为 ，其中 k=dy/dx。 假设 x 列的象素已经 确定为 xi，其行坐标为 yi。那么下一个象素的列坐标为 xi＋1，而行坐标要么不变为 yi，要么递增 1 为 yi＋1。 是否增 1 取决于如图所示误差项 d 的值。因为直线的起始点在象素中心，所以误差项 d 的初值 d0＝0。X 下标每增加 1，d 的值相应递增直线的斜率值 k，即 d＝d＋k。一旦 d≥1，就把它减去 1，这样保证 d 在 0、 1 之间。当 d≥0.5 时，直线与 xi＋1 列垂直网格交点最接近于当前象素（xi，yi）的右上方象素（xi＋1，yi ＋1）；而当 d<0.5 时，更接近于右方象素（xi＋1，yi）。为方便计算，令 e＝d－0.5，e 的初值为－0.5， 增量为 k。当 e≥0 时，取当前象素（xi，yi）的右上方象素（xi＋1，yi＋1）；而当 e<0 时，更接近于右方 象素（xi＋1，yi）。 图 2.1.4 Bresenham 算法所用误差项的几何含义 Bresenham 画线算法程序： void Bresenhamline (int x0,int y0,int x1, int y1,int color) { int x, y, dx, dy; float k, e; dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0; for (i=0; i dx; i++) { drawpixel (x, y, color); x=x+1，e=e+k; if (e 0) { y++, e=e-1;} } } 举例：用 Bresenham 方法扫描转换连接两点 P0（0,0）和 P1 （5,2）的直线段。 x y e 0 0 -0.5 1 0 -0.1 2 1 -0.7 3 1 -0.3 4 2 -0.9 5 2 -0.5 上述 bresenham 算法在计算直线斜率与误差项时用到小数 与除法。可以改用整数以避免除法。由于算法中只用到误差项 的符号，因此可作如下替换： 改进的 Bresenham 画线算法程序： void InterBresenhamline (int x0,int y0,int x1, int y1,int color) { dx = x1-x0, dy = y1- y0, e=-dx; x=x0, y=y0; for (i=0; i dx; -e+) {drawpixel (x, y, color); x++, e=e+2*dy; if (e 0) { y++; e=e-2*dx;} } }
22圆弧的扫描转换算法 221圆的特征 圆被定义为到给定中心位置(x,y)距离为r的点集。圆心位于原点的圆有四条对称轴x=0,y=0,x=y 和x=-y。若已知圆弧上一点(x,y),可以得到其关于四条对称轴的其它7个点,这种性质称为八对称性 因此,只要扫描转换八分之一圆弧,就可以求出整个圆弧的象素集 显示圆弧上的八个对称点的算法 void CirclePoints(int x, int y, int color) i drawpixel(x,y, color); drawpixel(y, x, color) drawpixel(-x,y, color); drawpixel(y, x, color); drawpixel(, -y, color); drawpixel(-y, x, color) drawpixel(-x,-y, color); drawpixel(-y, x,color) 222中点画圆法 构造圆函数F(xy)=x2+y2-R2。对于圆上的点,(xy)=0:对于圆外的点(xy)>0 对于圆内的点F(xy)(0。与中点画线法一样,构造判别式 d=F(MO=F(x,+1y,-05=(x,+1)2+(y,-05)2-R 若d<0则应取P1为下一象素,而且再下一象素的判别式为 y2-05)-(x,+2)2+(y,-052-R2-d+2x d≥0若则应取P2为下一象素,而且下一象素的判别式为 F(xy+2y-1.5)=(x,+2)2+( +2(x-y) 我们这里讨论的是按顺时针方向生成第二个八分圆。则第一个象素是(0R),判别式d的初始值为 d0=F(,R-0.5)=1.25-R P=(xph yp 图2.2.1当前象素与下一象素的候选者 MidPointcircle(int r int color) fint x,y: float d X=0:y=r;d=1.25r; circlepoints(x,y, color); fd<o)d+=2*x+3 else (d=2 (x-y)+5: y-1 circlepoints(x, y, color); 为了进一步提高算法的效率,可以将上面的算法中的浮点数改写成整数,将乘法运算改成加法运算,即 仅用整数实现中点画圆法 23多边形的扫描转换与区域填充 在计算机图形学中,多边形有两种重要的表示方法:顶点表示和点阵表示。顶点表示是用多边形的顶点 序列来表示多边形。这种表示直观、几何意义强、占内存少,易于进行几何变换,但由于它没有明确指出 哪些象素在多边形内故不能直接用于面着色。点阵表示是用位于多边形内的象素集合来刻画多边形。这种 表示丢失了许多几何信息,但便于帧缓冲器表示图形,是面着色所需要的图形表示形式。光栅图形的一个 基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换 计算机图形学第二章第21页共27页
计算机图形学 第二章 第 21 页 共 27 页 2.2 圆弧的扫描转换算法 2.2.1 圆的特征 圆被定义为到给定中心位置（xc,yc）距离为 r 的点集。圆心位于原点的圆有四条对称轴 x=0,y=0,x=y 和 x=-y。若已知圆弧上一点（x,y）,可以得到其关于四条对称轴的其它 7 个点，这种性质称为八对称性。 因此，只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集。 显示圆弧上的八个对称点的算法： void CirclePoints(int x,int y,int color) { drawpixel(x,y,color); drawpixel(y,x,color); drawpixel(-x,y,color); drawpixel(y,-x,color); drawpixel(x,-y,color); drawpixel(-y,x,color); drawpixel(-x,-y,color); drawpixel(-y,-x,color); } 2.2.2 中点画圆法 构造圆函数 。 对于圆上的点， ；对于圆外的点 ； 对于圆内的点 。与中点画线法一样，构造判别式 若 则应取 P1 为下一象素，而且再下一象素的判别式为 若 则应取 P2 为下一象素，而且下一象素的判别式为 我们这里讨论的是按顺时针方向生成第二个八分圆。则第一个象素是（0,R），判别式 d 的初始值为 图 2.2.1 当前象素与下一象素的候选者 MidPointCircle(int r int color) { int x,y; float d; x=0; y=r; d=1.25-r; circlepoints (x,y,color); while(x<=y) { if(d<0) d+=2*x+3; else { d+=2*(x-y)+5; y--;} x++; circlepoints (x,y,color); } } 为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即 仅用整数实现中点画圆法。 2.3 多边形的扫描转换与区域填充 在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。顶点表示是用多边形的顶点 序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出 哪些象素在多边形内故不能直接用于面着色。点阵表示是用位于多边形内的象素集合来刻画多边形。这种 表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。光栅图形的一个 基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换
231多边形的扫描转换 多边形分为凸多边形、凹多边形、含内环的多边形 ①凸凸多边形 ②凹多边形③含内环的多边形 任意两顶点间的任意两顶点间的 连线均在多边形连线有不在多边 内 形内的部分 图23.1多边形的种类 2.3.1.1扫描线算法 扫描线多边形区域填充算法是按扫描线顺序,计算扫描线与多边形的相交区间,再用要求的颜色显示这 些区间的象素,即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条 扫描线,多边形的填充过程可以分为四个步骤: (1)求交:计算扫描线与多边形各边的交点 (2)排序:把所有交点按x值递增顺序排序 (3)配对:第一个与第二个,第三个与第四个等等:每对交点代表扫描线与多边形的一个相交区间, (4)填色:把相交区间内的象素置成多边形颜色,把相交区间外的象素置成背景色。 P6(2,7) P4(118 B D P5(55) P1(2,2 P(5,1) 图2.3.2一个多边形与若干扫描线 为了提高效率,在处理一条扫描线时,仅对与它相交的多边形的边进行求交运算。我们把与当前扫描线 相交的边称为活性边,并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中,称此链表为活性边 表(AET) P6P1 P5P6 P4P5 P3P4 子·[207-.5H1.7一728-1081人 B△ x ymax (a)扫描线6的活性边表 P4P5 P3P4 |2|8-018∧ G (b)扫描线6的活性边表 图2.3.3活性边表(AE 计算机图形学第二章第22页共27页
计算机图形学 第二章 第 22 页 共 27 页 2.3.1 多边形的扫描转换 多边形分为凸多边形、凹多边形、含内环的多边形。 ① 凸凸多边形： ② 凹多边形 ③ 含内环的多边形 任意两顶点间的 任意两顶点间的 连线均在多边形 连线有不在多边 内 形内的部分 图 2.3.1 多边形的种类 2.3.1.1 扫描线算法 扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这 些区间的象素，即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条 扫描线，多边形的填充过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按 x 值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间， （4）填色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。 图 2.3.2 一个多边形与若干扫描线 为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。我们把与当前扫描线 相交的边称为活性边，并把它们按与扫描线交点 x 坐标递增的顺序存放在一个链表中，称此链表为活性边 表(AET)。 (a)扫描线 6 的活性边表 (b)扫描线 6 的活性边表 图 2.3.3 活性边表(AET)