《计算机图形学》课程教学资源：第二章光栅图形学.doc_大学文库

第二章光栅图形学光栅图形显示器可以看作一个象素的矩阵。在光栅显示器上显示任何一种图形,实际上都是一些具有种或多种颜色的象素集合。确定最佳逼近图形的象素集合,并用指定属性写象素的过程称为图形的扫描转换或光栅化。对于一维图形,在不考虑线宽时,用一个象素宽的直、曲线来显示图形。二维图形的光栅化必须确定区域对应的象素集,并用指定的属性或图案显示之,即区域填充。任何图形进行光栅化时,必须显示在屏幕的一个窗口里,超出窗口的图形不予显示。确定一个图形的哪些部分在窗口内,必须显示:哪些部分落在窗口之外,不该显示的过程称为裁剪。裁剪通常在扫描转换之前进行,从而可以不必对那些不可见的图形进行扫描转换。对图形进行光栅化时,由于显示器的空间分辨率有限,对于非水平、垂直、±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在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 在 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 用中点画线法对连接两点的直线进行光栅化

计算机图形学第二章第 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 多边形的扫描转换与区域填充在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。顶点表示是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些象素在多边形内故不能直接用于面着色。点阵表示是用位于多边形内的象素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换

假定当前扫描线与多边形某一条边的交点的x坐标为x,则下一条扫描线与该边的交点不要重计算,只要加个增量△x。设该边的直线方程为:ax+by+c=0 若y=y,x=xi:则当y=yin时, 1(by1 b △x 其中为常数另外使用增量法计算时,我们需要知道一条边何时不再与下一条扫描线相交,以便及时把它从活性边表中删除出去。综上所述,活性边表的结点应为对应边保存如下内容:第1项存当前扫描线与边的交点坐标x 值:第2项存从当前扫描线到下一条扫描线间ⅹ的增量Δx:第3项存该边所交的最高扫描线号y 为了方便活性边表的建立与更新,我们为每一条扫描线建立一个新边表(NET),存放在该扫描线第一次出现的边。也就是说,若某边的较低端点为y細,则该边就放在扫描线y的新边表中。 76543210 P4P5 P5P6 28·5+1.57 )|8A [2|07A 532-[51313∧ 图2.3.4上图所示各条扫描线的新边表NET 算法过程 void polyfill (polygon, color) int color;多边形 polygon for(各条扫描线i) 初始化新边表头指针NET 把ymn=i的边放进边表NET[i] y=最低扫描线号: 初始化活性边表AET为空; for(各条扫描线i) 把新边表NET[订]中的边结点用插入排序法插入AET表,使之按x坐标递增顺序排列遍历AET表,把配对交点区间(左闭右开)上的象素(x,y),用 drawpixel(x,y, color)改写象素颜色值遍历AET表,把y==i的结点从AET表中删除,并把ymx>i结点的x值递增x 若允许多边形的边自相交,则用冒泡排序法对AET表重新排序 1 /* polyfill * 扫描线与多边形顶点相交时,必须正确的交点的取舍扫描线与多边形相交的边分处扫描线的两侧,则计一个交点,如点P,P6 扫描线与多边形相交的边分处扫描线同侧,且yyi y,则计0个交点(不填色),如P1 扫描线与多边形边界重合(当要区分边界和边界内区域时需特殊处理),则计1个交点。具体实现时,只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2 来决定。计算机图形学第二章第23页共27页

计算机图形学第二章第 23 页共 27 页假定当前扫描线与多边形某一条边的交点的 x 坐标为 x，则下一条扫描线与该边的交点不要重计算，只要加一个增量△x。设该边的直线方程为：ax+by+c=0；若 y＝yi，x=x i；则当 y = y i+1时，其中为常数，另外使用增量法计算时，我们需要知道一条边何时不再与下一条扫描线相交，以便及时把它从活性边表中删除出去。综上所述，活性边表的结点应为对应边保存如下内容：第 1 项存当前扫描线与边的交点坐标 x 值；第 2 项存从当前扫描线到下一条扫描线间 x 的增量 x；第 3 项存该边所交的最高扫描线号 ymax。为了方便活性边表的建立与更新，我们为每一条扫描线建立一个新边表（NET）,存放在该扫描线第一次出现的边。也就是说，若某边的较低端点为 ymin，则该边就放在扫描线 ymin的新边表中。图 2.3.4 上图所示各条扫描线的新边表 NET 算法过程 void polyfill (polygon, color) int color;多边形 polygon; { for (各条扫描线 i ) { 初始化新边表头指针 NET [i]；把 y min = i 的边放进边表 NET [i]; } y = 最低扫描线号；初始化活性边表 AET 为空； for (各条扫描线 i ) { 把新边表 NET[i]中的边结点用插入排序法插入 AET 表，使之按 x 坐标递增顺序排列；遍历 AET 表，把配对交点区间(左闭右开)上的象素(x, y)，用 drawpixel (x, y, color) 改写象素颜色值；遍历 AET 表，把 y max= i 的结点从 AET 表中删除，并把 y max > i 结点的 x 值递增 x；若允许多边形的边自相交，则用冒泡排序法对 AET 表重新排序； } } /* polyfill */ 扫描线与多边形顶点相交时，必须正确的交点的取舍。 · 扫描线与多边形相交的边分处扫描线的两侧，则计一个交点，如点 P5，P6。 · 扫描线与多边形相交的边分处扫描线同侧，且 yiyi-1， yi>yi+1，则计 0 个交点(不填色)，如 P1。 · 扫描线与多边形边界重合 (当要区分边界和边界内区域时需特殊处理)，则计 1 个交点。具体实现时，只需检查顶点的两条边的另外两个端点的 y 值。按这两个 y 值中大于交点 y 值的个数是 0,1,2 来决定

P4/P3 图2.3.5扫描线与多边形相交,特殊情况的处理 2.3.1.2边界标志算法边界标志算法的基本思想是:在帧缓冲器中对多边形的每条边进行直线扫描转换,亦即对多边形边界所经过的象素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。对每条与多边形相交的扫描线依从左到右的顺序,逐个访问该扫描线上的象素。使用一个布尔量 inside来指示当前点是否在多边形内的状态。 Inside的初值为假,每当当前访问的象素为被打上边标志的点,就把 inside取反。对未打标志的象素, inside不变。若访问当前象素时, inside为真,说明该象素在多边形内则把该象素置为填充颜色边界标志算法 void edgemark fill(pol ydef, color 多边形定义 polytef: int cold 对多边形 polytef每条边进行直线扫描转换 inside False for(每条与多边形 polytef相交的扫描线y) for(扫描线上每个象素x) if(象素x被打上边标志) inside=!( inside) if(inside!= FALSE) drawpixel (x, y, color) else drawpixel (x, y, background) 图2.3.6正方形内切n个圆的边界标志算法用软件实现时,扫描线算法与边界标志算法的执行速度几乎相同,但由于边界标志算法不必建立维护边表以及对它进行排序,所以边界标志算法更适合硬件实现,这时它的执行速度比有序边表算法快一至两个数量级 2.3.2区域填充算法这里讨论的区域指已经表示成点阵形式的填充图形,它是象素的集合。区域可采用内点表示和边界表示两种表示形式。在内点表示中,区域内的所有象素着同一颜色。在边界表示中,区域的边界点着同一颜色区域填充指先将区域的一点赋予指定的颜色,然后将该颜色扩展到整个区域的过程区域填充算法要求区域是连通的,因为只有在连通区域中,才可能将种子点的颜色扩展到区域内的其它点。区域可分为4向连通区域和8向连通区域。4向连通区域指的是从区域上一点出发,可通过四个方向, 即上、下、左、右移动的组合,在不越出区域的前提下,到达区域内的任意象素:8向连通区域指的是从区域内每一象素出发,可通过八个方向,即上、下、左、右、左上、右上、左下、右下这八个方向的移动的 ●●● 组合来到达四个方向运动八个方向运动四连通区域八连通区域 ●●●● 图2.3.7四连通区域和八连通区域 ●●● 计算机图形学第二章第24页共27页

计算机图形学第二章第 24 页共 27 页图 2.3.5 扫描线与多边形相交，特殊情况的处理 2.3.1.2 边界标志算法边界标志算法的基本思想是：在帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。对每条与多边形相交的扫描线依从左到右的顺序，逐个访问该扫描线上的象素。使用一个布尔量 inside 来指示当前点是否在多边形内的状态。Inside 的初值为假，每当当前访问的象素为被打上边标志的点，就把 inside 取反。对未打标志的象素，inside 不变。若访问当前象素时，inside 为真，说明该象素在多边形内，则把该象素置为填充颜色。边界标志算法： void edgemark_fill(polydef, color) 多边形定义 polydef； int color; { 对多边形 polydef 每条边进行直线扫描转换； inside = FALSE; for (每条与多边形 polydef 相交的扫描线 y ) for (扫描线上每个象素 x ) { if(象素 x 被打上边标志)inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); } } 图 2.3.6 正方形内切 n 个圆的边界标志算法用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。 2.3.2 区域填充算法这里讨论的区域指已经表示成点阵形式的填充图形，它是象素的集合。区域可采用内点表示和边界表示两种表示形式。在内点表示中，区域内的所有象素着同一颜色。在边界表示中，区域的边界点着同一颜色。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种子点的颜色扩展到区域内的其它点。区域可分为 4 向连通区域和 8 向连通区域。4 向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意象素；8 向连通区域指的是从区域内每一象素出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。四个方向运动八个方向运动四连通区域八连通区域图 2.3.7 四连通区域和八连通区域

●表示内点○表示边界点图2.3.8区域的内点表示和边界表示 2.3.2.1区域填充的递归算法以上讨论的多边形填充算法是按扫描线顺序进行的。种子填充算法假设在多边形内有一象素已知,由此出发利用连通性找到区域内的所有象素设(xy)为内点表示的4连通区域内的一点, oldcolor为区域的原色,要将整个区域填充为新的颜色 newcolor。内点表示的4连通区域的递归填充算法 void FloodFill4(int x, int y, int oldcolor int newcolor) f(getpixel(x, y)==oldcolor i drawpixel(x,y, newcolor) FloodFill4(x, y+1, oldcolor, newcolor) FloodFill4(x, y-1, oldcolor, newcolor) FloodFil4(X-1,y, oldcolor, newcolor) FloodFill4(+1, y, oldcolor, newcolor) 边界表示的4连通区域的递归填充算法 void BoundaryFill4(nt x, int y int boundarycolor, int newcolor) f int color if(colorl=newcolor & colorl=boundarycolor) i drawpixel(x,y, newcolor) Boundary Fill4(x, y+1, boundarycolor, newcolor) Boundary Fill4 (x, y-1, boundarycolor, newcolor) oundary Fill4 (X-1,y, boundarycolor, newcolor Boundary Fill4 (X+1,y, boundarycolor, newcolor) 对于内点表示和边界表示的8连通区域的填充,只要将上述相应代码中递归填充相邻的4个象素增加到递归填充8个象素即可 2.3.22区域填充的扫描线算法区域填充的递归算法原理和程序都很简单,但由于多次递归,费时、费内存,效率不高。为了减少递归次数,提高效率可以采用采用扫描线算法。算法的基本过程如下:当给定种子点(X,y)时,首先填充种子点所在扫描线上的位于给定区域的一个区段,然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段,并依次保存下来。反复这个过程,直到填充结束区域填充的扫描线算法可由下列四个步骤实现: (1)初始化:堆栈置空。将种子点(x,y)入栈 (2)出栈:若栈空则结束。否则取栈顶元素(X,y),以y作为当前扫描线。 (③)填充并确定种子点所在区段:从种子点(X,y)出发,沿当前扫描线向左、右两个方向填充,直到边界分别标记区段的左、右端点坐标为x和xr (4)并确定新的种子点:在区间[,xr中检査与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素,则把每一区间的最右象素作为种子点压入堆栈,返回第(2)步 typedef struct∥记录种子点 int y: I Seed void ScanLineFill4(int x, int y, COLORREF oldcolor, COLORREF newcolor) int xl. xr, i bool spanNeedFill 计算机图形学第二章第25页共27页

计算机图形学第二章第 25 页共 27 页图 2.3.8 区域的内点表示和边界表示 2.3.2.1 区域填充的递归算法以上讨论的多边形填充算法是按扫描线顺序进行的。种子填充算法假设在多边形内有一象素已知，由此出发利用连通性找到区域内的所有象素。设（x,y）为内点表示的 4 连通区域内的一点，oldcolor 为区域的原色，要将整个区域填充为新的颜色 newcolor。内点表示的 4 连通区域的递归填充算法: void FloodFill4(int x,int y,int oldcolor,int newcolor) { if(getpixel(x,y)==oldcolor) { drawpixel(x,y,newcolor); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); FloodFill4(x-1,y,oldcolor,newcolor); FloodFill4(x+1,y,oldcolor,newcolor); } } 边界表示的 4 连通区域的递归填充算法: void BoundaryFill4(int x,int y,int boundarycolor,int newcolor) { int color; if(color!=newcolor && color!=boundarycolor) { drawpixel(x,y,newcolor); BoundaryFill4 (x,y+1, boundarycolor,newcolor); BoundaryFill4 (x,y-1, boundarycolor,newcolor); BoundaryFill4 (x-1,y, boundarycolor,newcolor); BoundaryFill4 (x+1,y, boundarycolor,newcolor); } } 对于内点表示和边界表示的 8 连通区域的填充，只要将上述相应代码中递归填充相邻的 4 个象素增加到递归填充 8 个象素即可。 2.3.2.2 区域填充的扫描线算法区域填充的递归算法原理和程序都很简单，但由于多次递归，费时、费内存，效率不高。为了减少递归次数，提高效率可以采用采用扫描线算法。算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。区域填充的扫描线算法可由下列四个步骤实现： (1)初始化：堆栈置空。将种子点（x，y）入栈。 (2)出栈：若栈空则结束。否则取栈顶元素（x，y），以 y 作为当前扫描线。 (3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为 xl 和 xr。 (4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线 y 上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。 typedef struct{ //记录种子点 intx; int y； } Seed; void ScanLineFill4(int x,int y,COLORREF oldcolor,COLORREF newcolor) { int xl,xr,i; bool spanNeedFill;

Seed pt setstackemptyo pt.x =X, pt.y=y stackpush(pt);∥将前面生成的区段压入堆栈 while(lisstackemptyo) i pt= stackpopO y=pt. y: X=pt.X while( getpixel(xy)=≡ oldcolor)∥向右填充 i drawpixel(x, y, newcolor); Xr=x-1 x=pt.x-1 whle( gepiⅸxel(xy)=≡ oldcolor)∥向左填充 drawpixel(x,y, newcolor x|=x+1 ∥0理上面一条扫描线 x=XI: while(X<x I spanNeedFill=FALSE while(getpixel(x, y)==oldcolor) i spanNeedFil=TRUE if(spanNeedFill I pt. XX-1: pt. y=y stackpush(pt); spanNeedFil=FALSE; while(getpixel(x, y)l=oldcolor & x<xr)X++ H/End of while(isxr) ∥处理下面一条扫描线,代码与处理上面一条扫描线类似 x=XI: 2; while(X<xr HEnd of while(isxr) H/End of while(lisstackempty o) 上述算法对于每一个待填充区段,只需压栈一次:而在递归算法中,每个象素都需要压栈。因此,扫描线填充算法提高了区域填充的效率。 24字符字符指数字、字母、汉字等符号。计算机中字符由一个数字编码唯一标识。国际上最流行的字符集是“美国信息交换用标准代码集”简称ASCⅠI码。它是用7位二进制数进行编码表示128个字符,包括字母、标点、运算符以及一些特殊符号。我国除采用 ASCII码外,还另外制定了汉字编码的国家标准字符集GB2312-80。该字符集分为94个区,94个位,每个符号由一个区码和一个位码共同标识。区码和位码各用一个字节表示为了能够区分 ASCII码与汉字编码,采用字节的最高位来标识:最高位为0表示 ASCII码:最高位为1表示表示汉字编码为了在显示器等输出设备上输出字符,系统中必须装备有相应的字库。字库中存储了每个字符的形状信息,字库分为矢量和点阵型两种 241点阵字符在点阵字符库中,每个字符由一个位图表示。该位为1表示字符的笔画经过此位,对应于此位的象素应置为字符颜色。该位为0表示字符的笔画不经过此位,对应于此位的象素应置为背景颜色。在实际应用中计算机图形学第二章第26页共27页

计算机图形学第二章第 26 页共 27 页 Seed pt; setstackempty(); pt.x =x; pt.y=y; stackpush(pt); //将前面生成的区段压入堆栈 while(!isstackempty()) { pt = stackpop(); y=pt.y; x=pt.x; while(getpixel(x,y)==oldcolor) //向右填充 { drawpixel(x,y,newcolor); x++; } xr = x-1; x = pt.x-1; while(getpixel(x,y)==oldcolor) //向左填充 { drawpixel(x,y,newcolor); x--; } xl = x+1; //处理上面一条扫描线 x = xl; y = y+1; while(x<xr) { spanNeedFill=FALSE; while(getpixel(x,y)==oldcolor) { spanNeedFill=TRUE; x++; } if(spanNeedFill) { pt.x=x-1;pt.y=y; stackpush(pt); spanNeedFill=FALSE; } while(getpixel(x,y)!=oldcolor && x<xr) x++; }//End of while(i<xr) //处理下面一条扫描线，代码与处理上面一条扫描线类似 x = xl; y = y-2; while(x<xr) { .... }//End of while(i<xr) }//End of while(!isstackempty()) } 上述算法对于每一个待填充区段，只需压栈一次；而在递归算法中，每个象素都需要压栈。因此，扫描线填充算法提高了区域填充的效率。 2.4 字符字符指数字、字母、汉字等符号。计算机中字符由一个数字编码唯一标识。国际上最流行的字符集是“美国信息交换用标准代码集”简称 ASCII 码。它是用 7 位二进制数进行编码表示 128 个字符，包括字母、标点、运算符以及一些特殊符号。我国除采用 ASCII 码外，还另外制定了汉字编码的国家标准字符集 GB2312－80。该字符集分为 94 个区，94 个位，每个符号由一个区码和一个位码共同标识。区码和位码各用一个字节表示。为了能够区分 ASCII 码与汉字编码，采用字节的最高位来标识：最高位为 0 表示 ASCII 码；最高位为 1 表示表示汉字编码。为了在显示器等输出设备上输出字符，系统中必须装备有相应的字库。字库中存储了每个字符的形状信息，字库分为矢量和点阵型两种。 2.4.1 点阵字符在点阵字符库中，每个字符由一个位图表示。该位为 1 表示字符的笔画经过此位，对应于此位的象素应置为字符颜色。该位为 0 表示字符的笔画不经过此位，对应于此位的象素应置为背景颜色。在实际应用中

有多种字体(如宋体、楷体等),每种字体又有多种大小型号,因此字库的存储空间是很庞大的。解决这个问题一般采用压缩技术。如:黑白段压缩:部件压缩:轮廓字形压缩等。其中,轮廓字形法压缩比大, 且能保证字符质量,是当今国际上最流行的一种方法。轮廓字形法采用直线或二/三次 bezier曲线的集合来描述一个字符的轮廓线。轮廓线构成一个或若干个封闭的平面区域。轮廓线定义加上一些指示横宽、竖宽、基点、基线等等控制信息就构成了字符的压缩数据点阵字符的显示分为两步。首先从字库中将它的位图检索出来。然后将检索到的位图写到帧缓冲器中 0 01100 011001 0 100110 1111100 100000000 (a)点阵字符(b)点阵字库中的位图表示(c)矢量轮廓字符图2.4.1字符的种类 24.2矢量字符矢量字符记录字符的笔画信息而不是整个位图,具有存储空间小,美观、变换方便等优点。对于字符的旋转、缩放等变换,点阵字符的变换需要对表示字符位图中的每一象素进行:而矢量字符的变换只要对其笔画端点进行变换就可以了。矢量字符的显示也分为两步。首先从字库中将它的字符信息。然后取出端点坐标,对其进行适当的几何变换,再根据各端点的标志显示出字符 24.3字符属性字体宋体仿宋体楷体黑体隶书字高宋体宋体宋体宋体字宽因子(扩展/压缩)大海大海大海大海字倾斜角倾斜倾斜对齐(左对齐、中心对齐、右对齐) 字色写方式:替换方式时,对应字符掩模中空白区被置成背景色。与方式时,这部分区域颜色不受影响。 25裁剪在使用计算机处理图形信息时,计算机内部存储的图形往往比较大,而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之内,哪些落在显示区之外,以便只显示落在显示区内的那部分图这个选择过程称为裁剪。最简单的裁剪方法是把各种图形扫描转换为点之后,再判断各点是否在窗内但那样太费时,一般不可取。这是因为有些图形组成部分全部在窗口外,可以完全排除,不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。 (a)裁剪前 (b)裁剪后图2.5.1多边形裁剪 251直线段裁剪计算机图形学第二章第27页共27页

计算机图形学第二章第 27 页共 27 页有多种字体（如宋体、楷体等），每种字体又有多种大小型号，因此字库的存储空间是很庞大的。解决这个问题一般采用压缩技术。如：黑白段压缩；部件压缩；轮廓字形压缩等。其中，轮廓字形法压缩比大，且能保证字符质量，是当今国际上最流行的一种方法。轮廓字形法采用直线或二/三次 bezier 曲线的集合来描述一个字符的轮廓线。轮廓线构成一个或若干个封闭的平面区域。轮廓线定义加上一些指示横宽、竖宽、基点、基线等等控制信息就构成了字符的压缩数据。点阵字符的显示分为两步。首先从字库中将它的位图检索出来。然后将检索到的位图写到帧缓冲器中。 (a)点阵字符 (b)点阵字库中的位图表示 (c) 矢量轮廓字符图 2.4.1 字符的种类 2.4.2 矢量字符矢量字符记录字符的笔画信息而不是整个位图，具有存储空间小，美观、变换方便等优点。对于字符的旋转、缩放等变换，点阵字符的变换需要对表示字符位图中的每一象素进行；而矢量字符的变换只要对其笔画端点进行变换就可以了。矢量字符的显示也分为两步。首先从字库中将它的字符信息。然后取出端点坐标，对其进行适当的几何变换，再根据各端点的标志显示出字符。 2.4.3 字符属性 ·字体宋体仿宋体楷体黑体隶书 ·字高宋体宋体宋体宋体 ·字宽因子(扩展/压缩) 大海大海大海大海 ·字倾斜角倾斜倾斜 ·对齐 (左对齐、中心对齐、右对齐) ·字色 ·写方式：替换方式时，对应字符掩模中空白区被置成背景色。与方式时，这部分区域颜色不受影响。 2.5 裁剪在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗内。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。 (a)裁剪前 (b) 裁剪后图 2.5.1 多边形裁剪 2.5.1 直线段裁剪

《计算机图形学》课程教学资源：第二章 光栅图形学

《计算机图形学》课程教学资源：第二章光栅图形学