计算机图形学2.2-2.3.

1、2.2.1 基础知识基础知识 给出圆心坐标给出圆心坐标( (x xc c, , y yc c) )和半径和半径r r，逐点画出一个圆周的公式有下逐点画出一个圆周的公式有下列两种：列两种： 直角坐标法直角坐标法( (x x x xc c) )2 2 + ( + (y y y yc c) )2 2 = = r r2 2由上式导出：由上式导出：cc22()yyrxx 当当x x x xc c从从 r r到到r r作加作加1 1递增时，就可递增时，就可以求出对应的圆周点的以求出对应的圆周点的y y坐标。坐标。 但是这样求出的圆周上的点是不均但是这样求出的圆周上的点是不均匀的，匀的， x x x xc

2、c越大，对应生成圆周点之间越大，对应生成圆周点之间的圆周距离也就越长。因此，所生成的的圆周距离也就越长。因此，所生成的圆不美观。圆不美观。2.2.1 基础知识基础知识( (续）续） 极坐标法极坐标法x x = = x xc c + + r r coscos，y y = = y yc c + + r r sin sin当当从从0 0到到作递增时，由此式便可求出圆周上均匀分布的作递增时，由此式便可求出圆周上均匀分布的360360个个点的点的( (x x, , y y) )坐标。坐标。 利用圆周坐标的对称性，此利用圆周坐标的对称性，此算法还可以简化。将圆周分为算法还可以简化。将圆周分为8 8个象限个

3、象限( (图图2.3)2.3)，只要将第，只要将第1 1a a象象限中的圆周光栅点求出，其余限中的圆周光栅点求出，其余7 7部分圆周就可以通过对称法则部分圆周就可以通过对称法则计算出来。计算出来。图2.3 圆心在(0, 0)点圆周生成时的对称变换2.2.2 圆的圆的Bresenham算法算法 设圆的半径为设圆的半径为r r。先考虑圆心在先考虑圆心在(0, 0)(0, 0)，并从，并从x x=0=0、y y= =r r开始的开始的顺时针方向的顺时针方向的1/81/8圆周的生成过程。在这种情况下，圆周的生成过程。在这种情况下，x x每步增加每步增加1 1，从从x x=0=0开始，到开始，到x x=

4、 =y y结束。即有结束。即有x xi i+1+1 = = xixi + 1 + 1y yi i+1+1 = = yiyi或者或者y yi i+1+1 = = yiyi 1 1 选择的原则是考察精确值选择的原则是考察精确值y y是靠近是靠近y yi i还是还是靠近靠近y yi i 1(1(图图2.4)2.4)，计算式为计算式为y y2 2 = = r r2 2 ( (x xi i+1)+1)2 2d d1 1 = = y yi i2 2 y y2 2 = = y yi i2 2 r r2 2+(+(x xi i+1)+1)2 2d d2 2 = = y y2 2 ( (y yi i 1)1)2

5、 2 = = r r2 2 ( (x xi i+1)+1)2 2 ( (y yi i 1)1)2 2图2.4 y的位置 令令p pi i= =d d1 1 d d2 2，并代入并代入d d1 1、d d2 2，则有则有 p pi i = 2( = 2(x xi i+1)+1)2 2 + + y yi i2 2 + ( + (y yi i 1)1)2 2 2 2r r2 2 (2.6)(2.6)p pi i称为误差。如果称为误差。如果p pi i00则则y yi i+1+1= =y yi i，否则否则y yi i+1+1= =y yi i 1 1。p pi i的递归式为的递归式为 p pi i+

6、1+1 = = p pi i + 4 + 4x xi i +6+2(+6+2(y yi i2 2+1+1 y yi i2 2) ) 2(2(y yi i+1+1 y yi i) ) (2.7) (2.7)p pi i的初值由式的初值由式(2.6)(2.6)代入代入x xi i=0=0，y yi i= =r r而得而得 p1 = 3p1 = 3 2r2r (2.8)(2.8)根据上面的推导，圆周生成根据上面的推导，圆周生成算法思想算法思想如下：如下： 求误差初值，求误差初值，p p1 1=3=3 2 2r r，i i=1=1，画点画点(0, (0, r r) )； 求下一个光栅位置，其中求下一个

7、光栅位置，其中x xi i+1+1= =x xi i+1+1，如果如果p pi i00则则y yi i+1+1= =y yi i，否则否则y yi i+1+1= =y yi i 1 1； 画点画点( (x xi i+1+1, , y yi i+1+1) )； 计算下一个误差，如果计算下一个误差，如果p pi i00则则p pi i+1+1= =p pi i+4+4x xi i+6+6，否则否则p pi i+1+1= =p pi i+4(+4(x xi i y yi i)+10)+10； i i= =i i+1+1，如果如果x x= =y y则结束，否则返回步骤则结束，否则返回步骤2 2。圆的圆

8、的BresenhamBresenham算法的程序实现如下：算法的程序实现如下：circle(circle(xcxc, , ycyc, radius, c), radius, c)int xcint xc, , ycyc, radius, c;, radius, c; intint x, y, p; x, y, p; x=0;x=0; y=radius;y=radius; p=3p=3 2 2* *radiusradius；while(xy)while(xy)plot_circle_points(plot_circle_points(xcxc, ,ycyc,x,y,c);,x,y,c);if(p

9、0) p=p+4if(p0) p=p+4* *x+6;x+6;elseelsep=p+4p=p+4* *(x(x y)+10;y)+10;y y =1;=1; x+=1;x+=1; if(x=y)if(x=y)plot_circle_points(plot_circle_points(xcxc, ,ycyc,x,y,c);,x,y,c); plot_circle_points(plot_circle_points(xcxc, , ycyc, x, y, c), x, y, c)int xcint xc, , ycyc, x, y, c;, x, y, c; set_pixel(set_pixe

10、l(xcxc+x, +x, ycyc+y, c);+y, c);set_pixel(set_pixel(xcxc x, x, ycyc+y, c);+y, c);set_pixel(set_pixel(xcxc+x, +x, ycyc y, c);y, c);set_pixel(set_pixel(xcxc x, x, ycyc y, c);y, c);set_pixel(set_pixel(xcxc+y, +y, ycyc+x, c);+x, c);set_pixel(set_pixel(xcxc y, y, ycyc+x, c);+x, c);set_pixel(set_pixel(xcx

11、c+y, +y, ycyc x, c);x, c);set_pixel(set_pixel(xcxc y, y, ycyc x, c);x, c); 2.3.1 基础知识基础知识 区域填充区域填充即给出一个区域的边界，要求对边界范围内的所有像素即给出一个区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色。单元赋予指定的颜色代码。区域填充中最常用的是多边形填色。多边形的表示方法多边形的表示方法顶点表示顶点表示点阵表示点阵表示图2.5 扫描线与多边形相交 图2.6 光栅化后直线变成离散点 多边形填色一个首要的问题，是判断一个像素是在多边形内还是多多边形填色

12、一个首要的问题，是判断一个像素是在多边形内还是多边形外。数学上提供的方法是边形外。数学上提供的方法是“扫描交点的扫描交点的奇偶数判断法奇偶数判断法”。( (扫描线扫描线与边界相交奇数次后进入该多边形，相交偶数次后走出该多边形。）与边界相交奇数次后进入该多边形，相交偶数次后走出该多边形。） 2.3.1 基础知识基础知识( (续）续） 填色算法分为两大类：填色算法分为两大类： 扫描线填色扫描线填色( (Scan-Line Filling)Scan-Line Filling)算法。算法。这类算法建立这类算法建立在多边形边界的矢量形式数据之上，可用于程序填色，也可在多边形边界的矢量形式数据之上，可用于

13、程序填色，也可用于交互填色。用于交互填色。 种子填色种子填色( (Seed Filling)Seed Filling)算法。算法。这类算法建立在多边这类算法建立在多边形边界的图像形式数据之上，并还需提供多边形边界内一点形边界的图像形式数据之上，并还需提供多边形边界内一点的坐标。所以，它一般只能用于人机交互填色，而难以用于的坐标。所以，它一般只能用于人机交互填色，而难以用于程序填色。程序填色。2.3.2 扫描线填色算法扫描线填色算法 算法的基本思想：算法的基本思想：多边形以多边形以n n、x_arrayx_array、y_arrayy_array的形式给出，其中，的形式给出，其中，x_array

14、x_array、y_arrayy_array中存放着多边形的中存放着多边形的n n个顶点的个顶点的x x，y y坐标。坐标。 用水平扫描线从上到下扫描由点用水平扫描线从上到下扫描由点线段构成的多段定义成的多边形。每线段构成的多段定义成的多边形。每根扫描线与多边形各边产生一系列交根扫描线与多边形各边产生一系列交点。这些交点按照点。这些交点按照x x坐标进行分类，将坐标进行分类，将分类后的交点成对取出，作为两个端分类后的交点成对取出，作为两个端点，以所需要填的色彩画水平直线。点，以所需要填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。多边形被扫描完毕后，填色也就完成。2.3.2 扫描线填色算

15、法扫描线填色算法( (续）续） 需要解决或改进的问题： 左、右顶点处理左、右顶点处理。左顶点左顶点2 2：y y1 1 y y2 2 y y2 2 y y3 3其中其中y y1 1、y y2 2、y y3 3是是3 3个相邻的顶点的个相邻的顶点的y y坐标。坐标。 当扫描线与多边形的每个顶点相交时，当扫描线与多边形的每个顶点相交时，会同时产生会同时产生2 2个交点。这时，填色就会因扫描个交点。这时，填色就会因扫描交点的奇偶计数出错而出现错误。交点的奇偶计数出错而出现错误。图2.7 多边形的顶点 对所有左、右顶点作如下处理：对所有左、右顶点作如下处理：v左、右顶点的入边左、右顶点的入边( (以该

16、顶点为终点的那条边，即以该顶点为终点的那条边，即1212边边) )之终点删去。之终点删去。对于左顶点，入边端点对于左顶点，入边端点( (x1, y1)x1, y1)、(x2, y2)(x2, y2)修改为修改为( (x1, y1)x1, y1)、( (, y2, y2 1)1)；对于右顶点，入边端点对于右顶点，入边端点( (x1, y1)x1, y1)、(x2, y2)(x2, y2)修改为修改为( (x1, y1)x1, y1)、( (, y2+1), y2+1)；21xm21xm2.3.2 扫描线填色算法扫描线填色算法( (续）续） 水平边处理水平边处理。水平边水平边(y1=y2)与水平扫

17、描线重合无法求交点。因此，将与水平扫描线重合无法求交点。因此，将水平边画出后删去，不参加求交点及求交点以后的操作。水平边画出后删去，不参加求交点及求交点以后的操作。 扫描线与边的求交点方法采用递归算法扫描线与边的求交点方法采用递归算法。以以( (x1, y1)x1, y1)、(x2, y2)(x2, y2)为端点的边与第为端点的边与第i+1i+1条扫描线的交点为条扫描线的交点为1211211iiiiyyxxxxyy此式表示交点不为此式表示交点不为( (x1, y1)x1, y1)。否则，交点为否则，交点为( (x1, y1)x1, y1)。 减少求交计算量，采用活性边表。减少求交计算量，采用活

18、性边表。对于一根扫描线而言，与之相对于一根扫描线而言，与之相交的边只占多边形全部边的一部分交的边只占多边形全部边的一部分, ,每根扫描线与多边形所有边求交的操作每根扫描线与多边形所有边求交的操作是一种浪费，需要加以改进。是一种浪费，需要加以改进。 活性边表活性边表( (Active List of Side)Active List of Side)的采用将多边形的边分成的采用将多边形的边分成两个子集：与当前扫描线相交的边的集合，以及与当前扫描线两个子集：与当前扫描线相交的边的集合，以及与当前扫描线不相交的边的集合。对后者不必进行求交运算，这样就提高了不相交的边的集合。对后者不必进行求交运算，这

19、样就提高了算法的效率。算法的效率。图2.8 活性边表及其指针的表示 v在上述线性表上加入两个指针在上述线性表上加入两个指针first和和last，形成活性边表。形成活性边表。v活性边表中每个元素的内容包括以下四项：活性边表中每个元素的内容包括以下四项：边的边的maxy值；值；与当前扫描线相交的点的与当前扫描线相交的点的x坐标值；坐标值；边的边的y方向当前总长方向当前总长y2-y1；边的斜率的倒数边的斜率的倒数1/m。v活性边表在每根扫描线扫描之后刷新。活性边表在每根扫描线扫描之后刷新。调整调整first和和last指针之间的参加求交运算的边元素的值；指针之间的参加求交运算的边元素的值；调整调整

20、first和和last指针，以便使新边进入激活范围。指针，以便使新边进入激活范围。活性边表构成方法如下：活性边表构成方法如下：v将经过左、右顶点处理并剔除水平边后的多边形各边按照将经过左、右顶点处理并剔除水平边后的多边形各边按照maxymaxy值排序，值排序，存入一个线性表中。存入一个线性表中。程序结构见课本32页。扫描线填色算法优、缺点：扫描线填色算法优、缺点：优点优点：对于每个象素只访问一次，输入输出的要求可降为最少；：对于每个象素只访问一次，输入输出的要求可降为最少；缺点缺点：对于各种表的维持和排序的耗费大。：对于各种表的维持和排序的耗费大。扫描线（y=4）： 6 2 3 0 5 7.5

21、 4 0.5 ymax x y 1/m扫描线（y=3）： 3 2 2 -2 5 7 4 0.5 p3p4 p2p3 0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1p1p2p3p4p5p4p5p2p3边填充算法（区域扫描转换算法）边填充算法（区域扫描转换算法）基本思想：对每条扫描线和多边形边的交点，将该扫描线上交点右方基本思想：对每条扫描线和多边形边的交点，将该扫描线上交点右方的所有像素取补。（对每条边作处理的顺序随意）的所有像素取补。（对每条边作处理的顺序随意）p1p2p3p4p5算法优、缺点：算法优、缺点：优点优点：简单，适用于具有祯缓存的图形系统；：简单，适用于具有祯缓存的

22、图形系统；缺点缺点：每个象素可能被访问多次，输入输出的量大。：每个象素可能被访问多次，输入输出的量大。栅栏填充算法栅栏填充算法对于每条扫描线与多边形边的交点，将交点与栅栏之间的像素取补。对于每条扫描线与多边形边的交点，将交点与栅栏之间的像素取补。栅栏线栅栏线优点优点：减少了访问次数：减少了访问次数种子填色又称边界填色种子填色又称边界填色( (Boundary Filling)Boundary Filling)。它的功能是，它的功能是，给出多边形光栅化后的边界位置及边界色代码给出多边形光栅化后的边界位置及边界色代码boundary_colorboundary_color，以及多边形内的一点以及多边形内的一点( (x, y)x, y)位置，要求将颜色位置，要求将颜色fill_colorfill_color填满填满多边形。多边形。2.3.3 2.3.3 种子填色算法种子填色算法 算法要求区域是连通的算法要求区域是连通的连通性连通性 4连通、8连通4连通：连通：从区域内任意一点出发，可通过从区域内任意一点出发，可通过上