第3章-基本光栅图形算法

1、概述概述 光栅图形显示器可以看作一个光栅图形显示器可以看作一个像素的矩阵。像素的矩阵。在光栅显示器在光栅显示器上显示的每一种图形，实际上都是具有上显示的每一种图形，实际上都是具有一种或多种颜色一种或多种颜色的的像素集合像素集合。确定。确定最佳逼近图形最佳逼近图形的像素集合，并用指定属性的像素集合，并用指定属性写像素的过程称为图形的扫描转换或光栅化。写像素的过程称为图形的扫描转换或光栅化。 在不考虑线宽时，可用在不考虑线宽时，可用一个像素宽一个像素宽的直线、曲线来显示图的直线、曲线来显示图形轮廓；直线和圆弧是组成图形的基本元素，在产生一幅形轮廓；直线和圆弧是组成图形的基本元素，在产生一幅图形的过

2、程中要多次调用生成这些基本元素的算法，因此图形的过程中要多次调用生成这些基本元素的算法，因此其生成算法的好坏对图形系统的效率至关重要。其生成算法的好坏对图形系统的效率至关重要。 二维图形的光栅化必须确定区域对应的像素集，并用指定二维图形的光栅化必须确定区域对应的像素集，并用指定的属性或图案来显示，即的属性或图案来显示，即区域填充。区域填充。多边形的填充算法是多边形的填充算法是面片显示的基础，在计算机图形学中的消隐、真实感显示面片显示的基础，在计算机图形学中的消隐、真实感显示等许多问题中有广泛应用。等许多问题中有广泛应用。 像素逼近示意图像素逼近示意图可寻址点，即显示器可以可寻址点，即显示器可以

3、找到的点，找到的点，(x, y)整数地址整数地址一个像素占一个像素占有一定面积有一定面积3.2 3.2 直线生成算法直线生成算法 图形图像是由屏幕上不同亮度不同颜色的光点图形图像是由屏幕上不同亮度不同颜色的光点（像素）组成。在光栅显示器的荧光屏上生成一个（像素）组成。在光栅显示器的荧光屏上生成一个对象，实质上是往帧缓存寄存器的相应单元中填入对象，实质上是往帧缓存寄存器的相应单元中填入数据。数据。所以所以 对对直线直线进行进行光栅化光栅化的时候，只能在显示器所给的时候，只能在显示器所给定的有限个像素组成的点阵中确定最佳逼近于该直定的有限个像素组成的点阵中确定最佳逼近于该直线的一组像素，用这些像素

4、表示该直线。线的一组像素，用这些像素表示该直线。所以所以 生成直线的主要工作是：生成直线的主要工作是：快速快速找出距离直线找出距离直线最近最近的网格点，用这些网格点对应的像素表示该直线。的网格点，用这些网格点对应的像素表示该直线。直线生成的基本思路：直线生成的基本思路： 首先，直线是像素集合，那么生成算法的最终目首先，直线是像素集合，那么生成算法的最终目的，就是为了寻找能更准确逼近直线的像素点。的，就是为了寻找能更准确逼近直线的像素点。 所以，要确定直线上每个点，那么，如：所以，要确定直线上每个点，那么，如：m1时，时，从起始点从起始点xs, xs+1, xs+2, xs+3 到到xe的每个点

5、的每个点(xi,yi) ，需要确定其对应的像素值。需要确定其对应的像素值。 所以，每一个所以，每一个(xi, yi)即准确值即准确值，都要寻找对应其的，都要寻找对应其的像素值像素值(xi, yi,r)，即最接近其准确值的整数值，最，即最接近其准确值的整数值，最简单简单取整取整 。 假设假设(xi, yi)已经确定了它的对应整数像素点，则下已经确定了它的对应整数像素点，则下面就要找个规则确定下一个点即面就要找个规则确定下一个点即(xi+1, yi+1)的对应的对应像素点。像素点。 对应于上述情况，即对应于上述情况，即m1的情况，的情况， xi+1 = xi1，即即yi+1需要确定，即需要确定上述

6、说的准则，即给需要确定，即需要确定上述说的准则，即给定一个判定式，由判定式来确定定一个判定式，由判定式来确定yi+1的选择。的选择。 而判定式为了计算方便也可以有更简便的方式来而判定式为了计算方便也可以有更简便的方式来计算，故判定式也可以由递推式来确定。计算，故判定式也可以由递推式来确定。直线生成的基本思路：直线生成的基本思路：3.2.1 基本增量算法基本增量算法（DDA，digital Differential Analyzer） 1、基本思想：基本思想： 舍入法求解最佳逼近；利用微分思想，即每一个点坐舍入法求解最佳逼近；利用微分思想，即每一个点坐标都可以由前一个坐标变化一个增量得到。标都可

7、以由前一个坐标变化一个增量得到。 2、直线的表示：直线的表示： 设直线：设直线：y = mx + b 满足满足 0=my0，即直线斜率小于即直线斜率小于1 1，应使，应使x方向每次增加方向每次增加1 1，y方方向最多增加向最多增加1 1，此时取，此时取t =1/x； 同理，当同理，当yx0直线斜率大于直线斜率大于1 1，取，取t =1/y，所以所以yxt/1 ,/1mintyydyyytxxdxxxiiiiii11iittt14 4、直线的、直线的DDA算法程序算法程序void dda(Graphics g, int x1, int x2, int y1, int y2) int k; flo

8、at x, y, dx, dy; k = Math.abs(x2-x1); if (Math.abs(y2-y1)k) k = Math.abs(y2-y1); /应该走几步应该走几步 dx = (float)(x2-x1)/k; dy = (float)(y2-y1)/k; /变化的增量变化的增量 x = (float)x1; y = (float)y1; for (int i = 0; i k ; i+ ) g.drawLine(int)(x+.5f), (int)(y+.5f), (int)(x+.5f), (int)(y+.5f);x = x+dx;y = y+dy; 图中黑点表示用图

9、中黑点表示用DDA算法生成的直线算法生成的直线完成四舍五入完成四舍五入产生一个像素需要两产生一个像素需要两次加法和两次取整次加法和两次取整3.2.3 3.2.3 Bresnham算法算法1 1、基本原理：、基本原理： 选择的原则是看精确值选择的原则是看精确值y与与yi及及yi+1的距离的距离d1及及d2 的大小而定。的大小而定。 d2d1yyiyi+1xiXi+12 2、直线的表示：、直线的表示： 令令 m=y/x 考虑考虑0m1 ，x方向增加方向增加1, y方向增加方向增加m yi+1=yi+m(xi+1xi)=yi+m 由起点由起点( (xs, ys),),可求得直线上的点可求得直线上的点

10、(xi, yi), i=1,2,3, 其中其中 x1= xs, y1= ys。 用坐标为用坐标为(xi，int(yi0.5)的像素来表示直线上的点。的像素来表示直线上的点。ssyxxmy)(这样的程序这样的程序有何不足？有何不足？3、Bresenham算法的具体实现算法的具体实现用坐标为用坐标为(xi, yi,r)的像素来表示直线上的点，则的像素来表示直线上的点，则第第i+1个点只能在个点只能在C和和D中选取中选取。误差项误差项 (xi+1)= yi+1yi,r0.5yi,ryi,r+1ABOxixi+1DC图图3.4 (x)的几何意义的几何意义d1=BCd2=DBd1-d2=(yi+1yi,

11、r)-( yi,r+1-yi+1) =2yi+1yi,r(yi,r+1) = 2yi+12yi,r1d1d2令令可看作是可看作是B和和中点中点A的比较的比较令：令：此时记此时记( xi，yi,r)表示逼近直线的像素。表示逼近直线的像素。 设设A为为CD边的中点边的中点当当( (xi+1)0时时，yi+1, ,r= yi,r+1，选选D点，即下个点（点，即下个点（ xi1, yi1 ）对应的像素（对应的像素（ xi1, yi+1,r ）为）为( xi+1, yi,r+1 )yi,ryi,r+1ABxixi+1DCd1d2yi,ryi,r+1Axixi+1DCd1d2当当( (xi+1)0时时，y

12、i+1, ,r= yi,r，选选C点，即下个点（点，即下个点（ xi1, yi1 ）对应的像素（对应的像素（ xi1, yi+1,r ）为）为( xi+1, yi,r )(xi+2)= yi+2yi+1, r0.5 = yi+1+myi+1, r0.5 10.51, ()0,10.5 ()0,11iyymxi riyymxi rii当当0)(,)(0)(, 1)(1111iiiixmxxmx当当综上，可得综上，可得(xi+2)的递推公式的递推公式(xi+2)的初始值：的初始值： (x2)=y2-y1-0.5=m-0.5如何求下下个点呢？即如何求如何求下下个点呢？即如何求 （xi+2, yi+2

13、）所对应的像素？）所对应的像素？同理，应确定一个同理，应确定一个，以判断该在下面的两个像素中哪个入选，以判断该在下面的两个像素中哪个入选(xi+1)= yi+1yi,r0.5(xi+1)0时，时，yi+1,r= yi,r+1(xi+1)0时，时，yi+1,r= yi,r假设直线段起始点：假设直线段起始点： x1= xs, y1,r= y1= ys4、Bresenham 算法源代码算法源代码m=(double)dy/(double)dx;e = m0.5；for(i=0;i=0) y=y+1； e=e1; x=x+1；e=e+m; /其中其中dy=yeys，dx=xexs。 缺点：有除法和浮点数

14、缺点：有除法和浮点数 Bresenham算法的优点算法的优点： 1、不必计算直线之斜率，因、不必计算直线之斜率，因此不做除法；此不做除法； 2、不用浮点数，只用整数；、不用浮点数，只用整数； 3、只做整数加减法和乘、只做整数加减法和乘2运运算，而乘算，而乘2运算可以用硬件移运算可以用硬件移位实现。位实现。Bresenham算法速度很快，并算法速度很快，并适于用硬件实现。适于用硬件实现。 4、Bresenham 算法源代码（改进）算法源代码（改进）void bresenham(Graphiscs g, int xs, int ys, int xe, int ye) int dx = xe-xs;

15、 int dy = ye-ys; int e = 2*dy-dx； int x = xs; int y = ys; for(int i=0; i=0) y = y+1； e = e2*dx; x=x+1；e=e+2*dy; 3.3 圆弧生成算法圆弧生成算法 1 1、基本原理：、基本原理： 假设已选取假设已选取Pi-1为第为第i-1个像素个像素 则如果则如果Pi-1在圆内，就要向圆外在圆内，就要向圆外方向走一步；方向走一步； 若若已已在圆外就要向圆内走一步。在圆外就要向圆内走一步。xypiPi+1Pi-1BA(0,0)图图3.9 对圆弧对圆弧AB用用 正负法取点正负法取点3.3.1 正负法正负法

16、总之，尽量贴近圆的轮廓线总之，尽量贴近圆的轮廓线2、正负法的具体实现、正负法的具体实现1）圆的表示：设圆的圆心为）圆的表示：设圆的圆心为(0, 0)，半，半径为径为R，则圆的方程为：，则圆的方程为： F(x, y)=x2+y2R2=0 ypiPi+1Pi-1BA(0,0)图图：对圆弧对圆弧AB用正负法取点用正负法取点v如何判断一个点和圆的内外关系如何判断一个点和圆的内外关系v当点当点(x, y)在圆内时在圆内时，F(x, y)0。2 2）实现步骤）实现步骤 第第1步：步：x0=0，y0=R 第第2步：步： 求得求得Pi(xi,yi)后找点后找点Pi+1的原则为：的原则为：ypiBA(0,0)当

17、当Pi在圆内在圆内时时（F(xi,yi)0），要向右走一步得要向右走一步得Pi+1，这是向圆外方这是向圆外方向走去。取向走去。取xi+1= xi+1, yi+1= yiPi+1 当当Pi在圆外在圆外时时（F(xi,yi)0）， 要向下走一要向下走一步得步得Pi+1，这是向圆内方这是向圆内方向走去，取向走去，取xi+1= xi, yi+1= yi-1Pi+1用来表示圆弧的点均在圆弧附近且用来表示圆弧的点均在圆弧附近且 F(xi, yi)时正时负时正时负 Pi假设已经得到点（假设已经得到点（xi, yi），则容易算出），则容易算出F(xi, yi)，即确定了下，即确定了下一个点（一个点（xi+1,

18、 yi+1），则如何计算），则如何计算F(xi+1, yi+1)，以确定下下个，以确定下下个点（点（xi+2, yi+2）？）？分为两种情况：分为两种情况：0, 12,0, 12,11iiiiiiiiiiiiyxFyyxFyxFxyxFyxF右走一步后：右走一步后：xi+1=xi+1，yi+1=yi，此时，此时：F(xi+1, yi+1)=xi+12+yi2-R2 = xi2+yi2-R2+2xi+1 = F(xi, yi)+2xi+1下走一步后下走一步后：xi+1=xi，yi+1=yi-1， 此时此时：F(xi+, yi+1)=xi2+（yi-1)2-R2 = F(xi, yi)-2yi+1

19、 确定了确定了F(xi+1, yi+1)之后，即可决定下一个点之后，即可决定下一个点(xi+2, yi+2)，选择道理同上。，选择道理同上。void pnarc(Graphics g, int radius) int x, y, f; x=0; y=0+radius; f=0; while(y0) g.drawLine(x, y, x, y); if(f0) f=f-2*y+1; y-; else f=f+2*x+1; x+; if(y=0) g.drawLine(x, y, x, y);3.3.2 Bresenham 生成圆弧的算法生成圆弧的算法假设圆心假设圆心(0, 0)为原点，考为原点，

20、考虑虑AB弧的画法，显示一个弧的画法，显示一个整圆时，只要在显示整圆时，只要在显示AB上上任一点任一点(x, y)时，同时显示时，同时显示在圆周上其它七个对称点在圆周上其它七个对称点 (y, x), (y, -x), (x, -y), (-x, -y),(-y, -x), (-y, x), (-x, y)7 7个对称点个对称点1 1、基本原理、基本原理 考虑考虑AB弧段弧段，x每步增加每步增加1，从从 x=0开始开始，到到x=y结束。结束。即有：即有： xi+1=xi+1 相应的相应的yi+1则在两种可能中则在两种可能中 选择选择 yi+1=yi ( (Hi点点) )或者或者 yi+1=yi-

21、1(Li点点)所以：所以： 选择的原则是确定这两个点哪一个选择的原则是确定这两个点哪一个 更接近于更接近于圆弧。圆弧。Pi-1HiLi即：设即：设Pi-1是已选中的一个表示圆弧上的点，下一是已选中的一个表示圆弧上的点，下一个点应从个点应从Hi或或Li中选择。设中选择。设Hi和和Li两点的坐标分别两点的坐标分别为为(xhi, yhi)和和(xli, yli)3.3.2 3.3.2 Bresenham生成圆弧的算法生成圆弧的算法设设R为弧为弧AB的半径，记点的半径，记点P到原点的距离的平方与圆的半径的平到原点的距离的平方与圆的半径的平方之差为方之差为D(P)，即：，即：222)()(RyxPD假定

22、假定 为圆弧上的点，则为圆弧上的点，则 ， 。令。令 1iP()0iD H()0iD L 2222221111()()(1)(1)(1)iiiiiiidD HD LxyRxyR|()| |()|iiD HD L当当 时，时， ， 比比 距圆弧近，应取距圆弧近，应取 来显示弧来显示弧AB ；0idiHiLiH当当 时，时， ，应取，应取 来显示弧来显示弧AB ；|()| |()|iiD HD L0idiL当当 时，可在两者中任取一点，这里规定取时，可在两者中任取一点，这里规定取 。0idiLBresenham算法在候选的两个像素中，总是选离圆弧最近的像素为算法在候选的两个像素中，总是选离圆弧最近

23、的像素为圆弧的一个近似点，因此，它比正负法决定的像素更合理。圆弧的一个近似点，因此，它比正负法决定的像素更合理。 点的选取方法点的选取方法设点设点 坐标为坐标为 ，则，则 和和 点的坐标分别为点的坐标分别为 和和 , , 和和 的坐标分别为的坐标分别为 和和 。已。已知知 ， ， 。则：。则： 1iP),(11iiyxiHiL),(1iiyx) 1,(1iiyx1iH1iL),(1iiyx) 1,(1iiyx00 x 0Ry 101 xx) 1(1 ()1 ()()(22022202111RyRyLDHDdRy23230) 1()(22122212RyxRyxdiiiii1222221212R

24、yyxiii) 1() 1() 1(2222221RyxRyxdiiiii322242222Ryyxxiiii(3.12)(3.13)(3.14)的递推公式的递推公式id3.3.2 3.3.2 Bresenham生成圆弧的算法生成圆弧的算法 di = 2x2i+2y 2i-1-2yi-1-2R2+1 di+1 = 2x2i+4xi+2y2i-2yi-2R2+3 di决定的是决定的是(xi, yi)，即，即Hi和和Li哪个被选中哪个被选中 di+1则决定的是则决定的是(xi+1, yi+1)，即，即Hi+1和和Li+1哪个被选中哪个被选中当当di0时时, ,点点Hi被选中被选中, xi= xi-

25、1+1， yi=yi-1，由由 (3.13)和和(3.14)得得 di+1= di+ 4xi+2= di+ 4xi-1+6 当当di0时时, ,点点Li被选中被选中, xi= xi-1+1，yi= yi-1-1，由由(3.20)和和(3.21)得得 di+1=di+4xi-4yi-1+6=di+4(xi-1-yi-1)+103.3.2 Bresenham3.3.2 Bresenham算法算法算法的程算法的程序实现序实现void bresenham_arc(Graphics g,int radius) int x,y,d; x = 0; y = radius; d = 3-2*radius; w

26、hile (x y) g.drawLine(x, y, x, y); if (d0) d=d+4*x+6; else d=d+4*(x-y)+10; y-; x+; if (x = y) g.drawLine(x,y,x,y); 3、总结、总结 Bresenham算法在候选的两个像素中，总是算法在候选的两个像素中，总是选定选定离圆弧最近的像素离圆弧最近的像素为圆弧的一个近似点，因此，为圆弧的一个近似点，因此，Bresenham算法比正负法决定的像素更合理。算法比正负法决定的像素更合理。3.3.3 圆弧的多边形逼近法圆弧的多边形逼近法1 1、基本思想：、基本思想：将整个圆弧等分成一段段的短直线，

27、将整个圆弧等分成一段段的短直线，用用这些短直线形成的折线来这些短直线形成的折线来逼近逼近圆弧。圆弧。为了获得这些短为了获得这些短直线，只需按一定的方式计算给定圆弧轨迹上一系列直线，只需按一定的方式计算给定圆弧轨迹上一系列顶点，顶点，短直线的绘制可采用直线的生成算法短直线的绘制可采用直线的生成算法，如果将，如果将圆弧分割的足够密，则短直线将足够短，形成的折线圆弧分割的足够密，则短直线将足够短，形成的折线将可以和圆弧接近到任意程度，因此在将可以和圆弧接近到任意程度，因此在允许的误差范允许的误差范围内围内，可以用显示折线代替显示圆弧。，可以用显示折线代替显示圆弧。2 2、圆弧的多边形逼近法、圆弧的多

28、边形逼近法设圆的圆心为设圆的圆心为c(0,0)，半径为半径为R。假设圆弧的起始角和终止角分假设圆弧的起始角和终止角分别为别为0和和1，把圆弧分割为把圆弧分割为n份份，则两个顶点之间的夹角为，则两个顶点之间的夹角为 =（ 1 - 0 ）/n 。 设内接正多边形的一个顶点为设内接正多边形的一个顶点为Pi(xi, yi)，cPi的幅角为的幅角为i，则则 xi=Rcosi yi=Rsini 顶点顶点Pi+1的坐标为的坐标为 xi+1=Rcos(i+) = xicos-yisin yi+1=Rsin(i+) = xisin+yicos 用正多边形迫近圆弧法用正多边形迫近圆弧法由此决定了一系列顶点，两个由

29、此决定了一系列顶点，两个定点确定一条直线，定点确定一条直线，n条直线逼条直线逼近了个整个圆。近了个整个圆。表示为矩阵形式，则内接正多边形的递推公式表示为矩阵形式，则内接正多边形的递推公式iiiiyxyxcossinsincos 11计算一个点（计算一个点（xi+1, yi+1）只要作四次乘法。）只要作四次乘法。xi+1=Rcos(i+) = xicos-yisin yi+1=Rsin(i+) = xisin+yicos ABCDOABCDEOOABCDEF907260v正四边形正四边形v正五边形正五边形v正六边形正六边形drawArc(int x, int y, int width, int

30、height, int startAngle, int arcAngle)前四个参数与画椭圆一样，确定了圆弧所在的圆或椭圆的前四个参数与画椭圆一样，确定了圆弧所在的圆或椭圆的位置及大小；位置及大小；第第5个参数表示该弧开始位置的角度；个参数表示该弧开始位置的角度；第第6个参数表示该弧转过的角度。个参数表示该弧转过的角度。注意：角度的参照系统规定水平向右的角度为注意：角度的参照系统规定水平向右的角度为0，逆时针，逆时针方向为正角度值，顺时针方向为负角度值。方向为正角度值，顺时针方向为负角度值。补充：中点画圆法利用圆的对称性，只须讨论利用圆的对称性，只须讨论1/8圆。圆。 P为当前点亮像素，那么，

31、下一个点亮的像素为当前点亮像素，那么，下一个点亮的像素可能是可能是P1(Xp+1, Yp)或或P2(Xp +1, Yp +1)。MP1P2P(Xp ,Yp )构造函数：构造函数：F(X，Y)=X2 + Y2 - R2 ；则；则 F(X，Y)= 0 （X，Y）在圆上；）在圆上； F(X，Y) 0 （X，Y）在圆外。）在圆外。设设M为为P1、P2间的中点，间的中点，M=(Xp+1,Yp-0.5)MP1P2补充：中点画圆法有如下结论有如下结论： F(M)= 0 说明说明M在圆外，则取在圆外，则取P2 为此，可采用如下判别式：为此，可采用如下判别式： d = F(M) = F(xp + 1, yp -

32、 0.5) =(xp + 1)2 + (yp - 0.5) 2 - R2 补充：中点画圆法 d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2 - R2 若若d=0，则，则P2 为下一个像素，那么再下一个为下一个像素，那么再下一个像素的判别式为：像素的判别式为： d1 = F(xp + 2, yp - 1.5) = (xp + 2)2 + (yp - 1.5) 2 - R2 = d + (2xp + 3)+(-2 yp + 2) 即即d 的增量为的增量为 2 (xp - yp) +5。MP1P2补充：中点画圆法d的初值的初值: d0

33、 = F(1, R-0.5) = 1 + (R-0.5)2 - R2 = 1.25 - R补充：中点画圆法补充：中点画圆法 MidpointCircle(int r) int x,y; float d; x=0; y=r; d=1.25-r; while(xy) drawline(x, y, x, y); if(d0) d+= 2*x+3; x+ else d+ = 2*(x-y) + 5; x+;y-; 为了进一步提高算法的效率，可以将上面的为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。

34、成加法运算，即仅用整数实现中点画圆法。 使用使用e=d-0.25代替代替d e0=1-R补充：中点画圆法在上半部分，法向量的在上半部分，法向量的y分量大分量大在下半部分，法向量的在下半部分，法向量的x分量大分量大上半部分上半部分下半部分下半部分法向量法向量两分量相等两分量相等M1M2在当前中点处，法向量（在当前中点处，法向量（ 2b2 (Xp+1) ，2a2 (Yp-0.5)的的y分量比分量比x分量大，即：分量大，即：b2 (Xp+1) a2 (Yp-0.5)；而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分。下部分。补充：中点

35、法画椭圆 讨论二维区域的填充问题，即面着色的问题，也讨论二维区域的填充问题，即面着色的问题，也就是为指定的平面区域填上所需要的颜色。就是为指定的平面区域填上所需要的颜色。 窗口窗口1 1、表示方法：、表示方法：顶点顶点表示和表示和点阵点阵表示表示（1 1）顶点表示）顶点表示是用多边形的顶点的序是用多边形的顶点的序列来描述多边形，该表示几何意义强、列来描述多边形，该表示几何意义强、占内存少，但它不能直观地说明哪些占内存少，但它不能直观地说明哪些像素在多边形内。像素在多边形内。（2 2）点阵表示）点阵表示是用位于多边形内的是用位于多边形内的像素的集合来刻划多边形，该方法虽像素的集合来刻划多边形，该

36、方法虽然没有多边形的几何信息，是面着色然没有多边形的几何信息，是面着色所需要的图像表示形式。所需要的图像表示形式。多边形的扫描转换就是把多边形的顶点表示转换为点阵表示，即从多边形多边形的扫描转换就是把多边形的顶点表示转换为点阵表示，即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。应元素设置相应的灰度或颜色。实际上就是多边形内的区域的着色过程。实际上就是多边形内的区域的着色过程。图：多边形顶点表示图：多边形顶点表示图：多边形点阵表示图：多边形点阵表示 3.4.1 多边形的表示方法

37、多边形的表示方法3.4.2 多边形填充的扫描线算法多边形填充的扫描线算法1、特点特点：充分利用了扫描线和边的连续性，避免对像素的逐：充分利用了扫描线和边的连续性，避免对像素的逐点判断和反复求交运算，减少了计算量，提高了算法速度。点判断和反复求交运算，减少了计算量，提高了算法速度。基本概念：基本概念：（1 1）扫描线的连续性：扫描线即电子枪由左向右扫过的一）扫描线的连续性：扫描线即电子枪由左向右扫过的一 行，或用坐标的观点来说即行，或用坐标的观点来说即y=i 这样的一条线。这样的一条线。（2 2）边的连续性）边的连续性（3 3）奇点：扫描线与多边形）奇点：扫描线与多边形P P的交点是的交点是P

38、P的顶点，该交点称的顶点，该交点称 为奇点。为奇点。 设多边形设多边形P的顶点的顶点 又设又设 是各顶是各顶点点Pi的纵坐标的纵坐标yi的递减数列的递减数列, ,当当 时时, ,屏幕上位屏幕上位于于和和 两条扫描线之间的长方形区域被多边形两条扫描线之间的长方形区域被多边形P的边分割成若干梯形。的边分割成若干梯形。, 1 , 0),(niyxPiii01nyyy1,01kkyyknkyy1kyy（1 1）扫描线的连续性）扫描线的连续性设设e为一整数为一整数 e 。若扫描线。若扫描线y=e与多边形与多边形P的边的边Pi-1Pi相交，则记其交相交，则记其交点的横点的横坐标为坐标为 。令：。令： 是该

39、扫描线与是该扫描线与P 的边界各的边界各交点横坐标的递增序列，记为交点横坐标的递增序列，记为序列序列1。0ynyeixleieieieixxxx,321由区域的连贯性可知，此交点序列具有以下由区域的连贯性可知，此交点序列具有以下性质：性质：(1) l是偶数。是偶数。(2) 在该扫描线上，只有区段在该扫描线上，只有区段 位于多边形位于多边形P内内. . 1, 5 , 3 , 1),(1lkxxkkeiei654321467320,eeeeeexxxxxxP P内内P P内内P P内内（2）边的连续性）边的连续性1,kkye dy),(dxrdi若若d为一整数，为一整数，d=e1，且，且yi0yy

40、in；设位于扫描线；设位于扫描线 y=d 上的交点序列上的交点序列为为 ，记为序列记为序列2。kdidididixxxx,321若若多边形多边形P的边的边Pi-1Pi与扫描线与扫描线y=e, y=d 都相交，即：都相交，即：则序列则序列1和和 序列序列2有以下关系：有以下关系：a：两个序列元素个数相等，即：两个序列元素个数相等，即l=hb：点：点 和和 位于多边形的同一个边上，于是有位于多边形的同一个边上，于是有 ),(exreirdrermxx/1其中其中mr为边为边Pr-1Pr的斜率的斜率 递推式递推式1edy63y24（3）奇点的处理）奇点的处理 极值点和非极值点。如果极值点和非极值点。

41、如果 ，称顶点，称顶点Pi为极为极值点值点(P1,P2,P3,P5, P6,P8)；否则称；否则称Pi为非极值点为非极值点(P0,P4,P7)。6yy 0)(11iiiiyyyyv处理时遇到的问题处理时遇到的问题如果把每一奇点简单地计为一个交点，则交点个数可能出现如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数，如上图中的奇数，如上图中的 扫描线的情况；但若将每一奇点都简扫描线的情况；但若将每一奇点都简单地计为两个交点，同样会导致反常的结果，如上图中单地计为两个交点，同样会导致反常的结果，如上图中 扫描线的情况。扫描线的情况。 7yy v若扫描线与多边形相交于若扫描线与多边形相交于多边

42、形的顶点，则该交点多边形的顶点，则该交点（顶点）称为（顶点）称为奇点奇点。v多边形多边形P的顶点可分为两类的顶点可分为两类6yy 7yy （3 3）奇点的处理）奇点的处理11,iiiipppp 为了使交点个数保持为偶数，规定当奇点是为了使交点个数保持为偶数，规定当奇点是P 的极值点时，的极值点时，该点按两个交点计算；否则按一个交点计算。该点按两个交点计算；否则按一个交点计算。 实际算法实际算法预处理：若预处理：若Pi是非极值点，则将是非极值点，则将 两边中两边中位于扫描线位于扫描线y=yi上方的那条边在上方的那条边在Pi 点处截去一单位长。点处截去一单位长。 2 2、扫描线算法的实现、扫描线算

43、法的实现 对于对于每一条扫描线，每一条扫描线，多边形的填充过程可分为以下多边形的填充过程可分为以下4步：步：1423把所有的交点按把所有的交点按x值递增的顺序进行排列；值递增的顺序进行排列；计算扫描线与多边形各边的交点，设交点个数为计算扫描线与多边形各边的交点，设交点个数为n； 将排序后的第将排序后的第1个与第个与第2个交点，第个交点，第3个与第个与第4个交点，个交点，第第n-1个与第个与第n个交点配对，每对交点就代表扫描个交点配对，每对交点就代表扫描线与多边形的一个相交区间；线与多边形的一个相交区间； 4把相交区间内的像素置成多边形的颜色，相交区间外把相交区间内的像素置成多边形的颜色，相交区

44、间外的像素置成背景色。的像素置成背景色。2、扫描线算法的实现、扫描线算法的实现3、扫描线算法的数据结构、扫描线算法的数据结构AEL 活性边活性边：与当前扫描线相交的边。：与当前扫描线相交的边。 边的活性边表边的活性边表AEL由与由与当前扫描线相交的所有多边形的当前扫描线相交的所有多边形的边边组成。它记录了多边形边沿扫描线的交点序列。组成。它记录了多边形边沿扫描线的交点序列。 若当前扫描线与该边的交点坐标为若当前扫描线与该边的交点坐标为(xi, yi)，则下一条扫描则下一条扫描线与该边的交点线与该边的交点(xi+1, yi+1)不需要重新计算，只要加一个增量不需要重新计算，只要加一个增量即可。即

45、可。 111()iiiibc bbxb ycyxaaa aa rdrermxx/13 3、扫描线算法的数据结构、扫描线算法的数据结构a a：数据结构：数据结构 AEL中的节点由四个域组成：中的节点由四个域组成： ymax：边的上端点的边的上端点的y坐标；坐标； x：边与扫描线交点的边与扫描线交点的x坐标坐标 x：边的斜率的倒数；边的斜率的倒数； Next：指向下一条边的指针。指向下一条边的指针。告诉处理到哪条扫描线时，就告诉处理到哪条扫描线时，就可以结束这条边了可以结束这条边了记录当前扫描线与某条边的交记录当前扫描线与某条边的交点点x值值dy/dx，扫描线加，扫描线加1时，即时，即y=y+1时

46、时x=x+1/m活活性性边边表表-5/357AELe0e54212AELAEL在在y=2扫描线上的状态扫描线上的状态-5/355AELe0e54214AELAEL在在y=3y=3扫描线上的状态扫描线上的状态2ymaxx1/mAEL中的各边按照中的各边按照x值值(当当x的值相等时，按的值相等时，按x值值)递增方向排序。递增方向排序。3、扫描线算法的数据结构、扫描线算法的数据结构NEL 新边表新边表NEL存放在该扫描线上第一次出现的边。存放在该扫描线上第一次出现的边。按边下端点的纵坐标按边下端点的纵坐标y对边进行分类。也就是说，对边进行分类。也就是说，如果某边的较低端点为如果某边的较低端点为ymi

47、n，则该边就放在扫描，则该边就放在扫描线线ymin的新边表中。的新边表中。同一类中，各边按同一类中，各边按x值递增值递增的顺序排列成行。的顺序排列成行。对于右图中的多边形：对于右图中的多边形： P0P1P2P3P4P5 P6= (2,5) (2,10) (9,6) (16,11) (16,4) (12,2) (7,2) 注意：注意：其中其中P0和和P4点是非极值点，我们在做点是非极值点，我们在做y边的分类之前已经做过对边边的分类之前已经做过对边e1和和e4进行进行预处理预处理：分别在：分别在P0和和P4处截掉一个单处截掉一个单位以保证扫描线位以保证扫描线y=yi只与只与Pi-1Pi、PiPi+

48、1两边的一边相交，只求得一个交点。两边的一边相交，只求得一个交点。同时由于同时由于e6是水平边，不参加分类。是水平边，不参加分类。y12564 4、扫描线算法的步骤：、扫描线算法的步骤： 步骤步骤1 1:(:(AEL初始化初始化) )将活性边表将活性边表AEL设置为空设置为空。 步骤步骤2 2:(:(y初始化初始化) )取扫描线取扫描线纵坐标纵坐标y的初始值为的初始值为NEL中非空中非空元素的元素的最小序号最小序号 步骤步骤3 3：按：按从下到上的顺序从下到上的顺序对纵坐标值为对纵坐标值为y的扫描线的扫描线( (当前当前扫描线扫描线) )执行执行下列步骤下列步骤，直到新边表，直到新边表NEL和

49、活性边表和活性边表AEL都都变成空为止变成空为止。5 5、扫描线算法的具体步骤：、扫描线算法的具体步骤： 如新边表如新边表NEL中的第中的第y类元素非空，则将类元素非空，则将属于该类的所属于该类的所有边从有边从NEL中中取出并插入活性边表取出并插入活性边表AEL中中，AEL中的各边中的各边按照按照x值值( (当当x的值相等时，按的值相等时，按x值值) )递增方向排序。递增方向排序。-5/357AELe0e54212AELAEL在在y=2扫描线上的状态扫描线上的状态2v从从NEL中选择当前扫中选择当前扫描线的边表，方便活描线的边表，方便活性边表的建立和更新性边表的建立和更新5 5、扫描线算法的具

50、体步骤：、扫描线算法的具体步骤： 若相对于当前扫描线，其活性边表若相对于当前扫描线，其活性边表AEL非空，则将非空，则将AEL中的边两两依次配对，即第中的边两两依次配对，即第1，2边为一对，第边为一对，第3，4边为一边为一对，依此类推。对，依此类推。 每一对边与当前扫描线的交点所构成的区段位于多边每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点形内，依次对这些区段上的点( (像素像素) )按多边形属性着色。按多边形属性着色。利用了扫描线利用了扫描线的连续性的连续性-5/357AELe0e54212AELAEL在在y=2扫描线上的状态扫描线上的状态5 5、扫描线算法的具体

51、步骤：、扫描线算法的具体步骤：将表将表AEL中满足中满足y=ymax的边删去。的边删去。 (表明一条边已经结束表明一条边已经结束)将边的将边的AEL剩下的每一条边的剩下的每一条边的x域累加域累加x，即，即x:=x+x。 (下一条扫描线与边的交点下一条扫描线与边的交点x，利用了边的连续性，利用了边的连续性)将当前的扫描线的纵坐标值将当前的扫描线的纵坐标值y累加，即累加，即y:=y+1 ( ( 求下一条扫描线求下一条扫描线) )-5/357AELe0e54212AELAEL在在y=2扫描线上的状态扫描线上的状态-5/355AELe0e54214AEL在在y=3扫描线上的状态扫描线上的状态e0:m=

52、-5/3,所以所以x变为变为75/35e5:m=2,所以所以x变为变为12+214y=y+1,即即y=2+1=3-5/355AELe0e54214AEL在在y=3扫描线上的状态扫描线上的状态-5/353AELe0e54216AEL在在y=4扫描线上的状态扫描线上的状态-5/352AELe0e49216AEL在在y=5扫描线上的状态扫描线上的状态54因为对于因为对于e5，y的的max已经到了，已经到了，故去掉故去掉e5，而，而从从NEL表中加入表中加入e43.4.3 边缘填充算法边缘填充算法1 1、特点：采用对图像进行逐位求反的方法，免去对边排序、特点：采用对图像进行逐位求反的方法，免去对边排序

53、 的工作量。的工作量。2、预备知识：预备知识：对颜色对颜色M作偶数次求反运算，其结果还是作偶数次求反运算，其结果还是M，而对，而对M作奇数次作奇数次求反运算的结果是求反运算的结果是M的反的反M 。在光栅图形中，如某区域已着在光栅图形中，如某区域已着上值为上值为M的某种颜色，则上述求反运算得到的结果是：对区的某种颜色，则上述求反运算得到的结果是：对区域作偶数次求反运算后，该区域的颜色不变；作奇数次求反域作偶数次求反运算后，该区域的颜色不变；作奇数次求反运算后，该区域的颜色则变成值为反运算后，该区域的颜色则变成值为反M的颜色。的颜色。3、边缘填充算法的实现、边缘填充算法的实现 实现：对多边形实现：

54、对多边形P的每一非水平边上的各像素做向右求反运算的每一非水平边上的各像素做向右求反运算 即可，见下图，其中即可，见下图，其中(a)为给定的多边形；为给定的多边形；(b)为对区域赋初值；为对区域赋初值；(c)，(d)，(e)和和(f)表示逐边向右求反。表示逐边向右求反。 3.4.4 边界标志算法边界标志算法1 1、基本原理：首先、基本原理：首先用一种用一种特殊的颜色特殊的颜色在帧缓冲器中将多边形在帧缓冲器中将多边形的的边界边界（水平边的部分边界除外）（水平边的部分边界除外）勾画勾画出来。出来。然后然后再把位于再把位于多多边形内边形内的各个的各个像素着上所需的颜色。像素着上所需的颜色。 2、算法具

55、体实现步骤：算法具体实现步骤：步骤步骤1 1：以值为以值为boundary-color 的特殊颜色的特殊颜色勾画勾画多边形多边形P的的边边界界。设多边形顶点为。设多边形顶点为Pi= (xi, yi),0in， xi, yi均为整数；置均为整数；置Pn+1=P0。每一条扫描线上着上这种特殊颜色的点的个数必定每一条扫描线上着上这种特殊颜色的点的个数必定是偶数是偶数( (包括零包括零) )。3 3、边界标志算法实例、边界标志算法实例标志边界并处理奇点标志边界并处理奇点P2(9,6)P0(2,5)P1(2,11)P3(15,9)P4(15,3)P5(12,1)P6(7,1)for(i=0;i0)x=p

56、i.x;else x=pi+1.x; ymax=(Math.max(pi.y,pi+1.y); ymin=(Math.min(pi.y,pi+1.y); for (y=ymin+1;y=ymax ;y+ ) x=(int)(x+dx+.5); if(pixelsy*w+x=blue) pixelsy*w+x+1=blue; else pixelsy*w+x=blue; / for(i=0;i=n;i+)v确定某条边的确定某条边的上下上下端点端点v水平边不考虑水平边不考虑v多边形的边数多边形的边数v边界颜色边界颜色蓝色蓝色vP0P1的底端点的底端点yminvP0P1的上端点的上端点ymaxXXX

57、XXXvP1P2的底端点的底端点yminXXXXXXXXXXXXXXXXXXXXvImageProducer ip = new MemoryImageSource(w,h,pixels,0,w); v/通过通过MemoryImageSource将数组中的像素产生一个图像，将数组中的像素产生一个图像，w,h分别表其宽度和高度分别表其宽度和高度vimage = createImage(ip);3.4.4 边界标志算法边界标志算法1 1、基本原理：首先、基本原理：首先用一种用一种特殊的颜色特殊的颜色在帧缓冲器中将多边形在帧缓冲器中将多边形的的边界边界（水平边的部分边界除外）（水平边的部分边界除外）勾

58、画勾画出来。出来。然后然后再把位于再把位于多多边形内边形内的各个的各个像素着上所需的颜色。像素着上所需的颜色。 2、算法具体实现步骤：算法具体实现步骤：步骤步骤1 1：以值为以值为boundary-color 的特殊颜色的特殊颜色勾画勾画多边形多边形P的的边边界界。设多边形顶点为。设多边形顶点为Pi= (xi, yi),0in， xi, yi均为整数；置均为整数；置Pn+1=P0。每一条扫描线上着上这种特殊颜色的点的个数必定每一条扫描线上着上这种特殊颜色的点的个数必定是偶数是偶数( (包括零包括零) )。步骤步骤2 2：设设in_flag是一布尔变量。对每一条扫描线从左到右是一布尔变量。对每一

59、条扫描线从左到右进行搜索，如果当前是进行搜索，如果当前是像素像素位于位于多边形多边形P内内，则，则in_flag=true，需要需要填上填上值为值为polygon_color的颜色；否则该的颜色；否则该像素像素在在多边形多边形P外外，需要填上值为需要填上值为background_color的颜色。的颜色。 3、边界标志算法实例、边界标志算法实例P2(9,6)P0(2,5)P1(2,11)P3(15,9)P4(15,3)P5(12,1)P6(7,1)XXXXXXXXXXXXXXXXXXXXXXXXXX/maxx、maxy、minx、miny是获得的多边是获得的多边 形最小矩形包围盒边界值形最小矩

60、形包围盒边界值for(y = miny - 1 ; y= maxy ;y+) in_flag = 0; /多边形内部标志变量多边形内部标志变量 for( x = minx - 1; xmaxx; x+) l = pixelsy*w+x; /多边形边界颜色多边形边界颜色blue if (l = blue) if (in_flag = 0) in_flag = 1; else in_flag = 0; if (in_flag=1) pixelsy*w+x=blue; /在多边形内部填充蓝色在多边形内部填充蓝色 vminy, minxvmaxxvmaxyv获得当前像素获得当前像素颜色以判断是否颜色以判断是否