计算机图形学222的知识

2.2圆的生成算法2.2.1基础知识

给出圆心坐标(xc,yc)r，逐点画出一个圆周的公式有下列两种：⒈直角坐标法

(xxc)2+(yyc)2=r2由上式导出：

当xxc从r到r作加1递增时，就可以求出对应的圆周点的y坐标。但是这样求出的圆周上的点是不均匀的，xxc越大，对应生成圆周点之间的圆周距离也就越长。因此，所生成的圆不美观。12.2圆的生成算法2.2.1基础知识(续）

⒉极坐标法

x=xc+r·cosθ，y=yc+r·sinθ

当θ从0到π作递增时，由此式便可求出圆周上均匀分布的360个点的(x,y)坐标。利用圆周坐标的对称性，此算法还可以简化。将圆周分为8个象限(图2.3)，只要将第1a象限中的圆周光栅点求出，其余7部分圆周就可以通过对称法则计算出来。

图2.3圆心在(0,0)点圆周生成时的对称变换22.2圆的生成算法2.2.2圆的Bresenham算法

设圆的半径为r。先考虑圆心在(0,0)，并从x=0、y=r开始的顺时针方向的1/8圆周的生成过程。在这种情况下，x每步增加1，从x=0开始，到x=y结束。即有

xi+1=xi+1

yi+1=yi或者yi+1=yi1选择的原则是考察精确值y是靠近yi还是靠近yi1(图2.4)，计算式为y2=r2(xi+1)2d1=yi2y2=yi2r2+(xi+1)2d2=y2(yi1)2=r2(xi+1)2(yi1)2图2.4y的位置

32.2圆的生成算法令pi=d1d2，并代入d1、d2，则有

pi=2(xi+1)2+yi2+(yi1)22r2(2.6)pi称为误差。如果pi<0则yi+1=yi，否则yi+1=yi1。pi的递归式为

pi+1=pi+4xi

+6+2(yi2+1yi2)2(yi+1yi)(2.7)pi的初值由式(2.6)代入xi=0，yi=r而得

p1=32r(2.8)根据上面的推导，圆周生成算法思想如下：⒈求误差初值，p1=32r，i=1，画点(0,r)；⒉求下一个光栅位置，其中xi+1=xi+1，如果pi<0则yi+1=yi，否则yi+1=yi1；⒊画点(xi+1,yi+1)；⒋计算下一个误差，如果pi<0则pi+1=pi+4xi+6，否则pi+1=pi+4(xiyi)+10；⒌i=i+1，如果x=y则结束，否则返回步骤2。42.2圆的生成算法

圆的Bresenham算法的程序实现如下：

circle(xc,yc,radius,c)intxc,yc,radius,c;{intx,y,p;x=0;y=radius;p=32*radius；

while(x<y){plot_circle_points(xc,yc,x,y,c);if(p<0)p=p+4*x+6;else{p=p+4*(xy)+10;y=1;}x+=1;}

52.2圆的生成算法if(x==y)plot_circle_points(xc,yc,x,y,c);}plot_circle_points(xc,yc,x,y,c)intxc,yc,x,y,c;{set_pixel(xc+x,yc+y,c);set_pixel(xcx,yc+y,c);set_pixel(xc+x,ycy,c);set_pixel(xcx,ycy,c);set_pixel(xc+y,yc+x,c);

set_pixel(xcy,yc+x,c);set_pixel(xc+y,ycx,c);set_pixel(xcy,ycx,c);}62.3区域填充算法2.3.1基础知识

区域填充即给出一个区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色。

多边形的表示方法顶点表示点阵表示7图2.5扫描线与多边形相交

图2.6光栅化后直线变成离散点

多边形填色一个首要的问题，是判断一个像素是在多边形内还是多边形外。数学上提供的方法是“扫描交点的奇偶数判断法”。(扫描线与边界相交奇数次后进入该多边形，相交偶数次后走出该多边形。）

2.3区域填充算法2.3.1基础知识(续）

82.3区域填充算法填色算法分为两大类：

⒈扫描线填色(Scan-LineFilling)算法。这类算法建立在多边形边界的矢量形式数据之上，可用于程序填色，也可用于交互填色。⒉种子填色(SeedFilling)算法。这类算法建立在多边形边界的图像形式数据之上，并还需提供多边形边界内一点的坐标。所以，它一般只能用于人机交互填色，而难以用于程序填色。92.3区域填充算法2.3.2扫描线填色算法

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

需要解决或改进的问题：⒈左、右顶点处理。左顶点2：y1<y2<y3

右顶点2：y1>y2>y3其中y1、y2、y3是3个相邻的顶点的y坐标。当扫描线与多边形的每个顶点相交时，会同时产生2个交点。这时，填色就会因扫描交点的奇偶计数出错而出现错误。图2.7多边形的顶点

对所有左、右顶点作如下处理：左、右顶点的入边(以该顶点为终点的那条边，即1–2边)之终点删去。对于左顶点，入边端点(x1,y1)、(x2,y2)修改为(x1,y1)、(,y21)；对于右顶点，入边端点(x1,y1)、(x2,y2)修改为(x1,y1)、(,y2+1)；112.3区域填充算法2.3.2扫描线填色算法(续）

⒉

水平边处理。水平边(y1=y2)与水平扫描线重合无法求交点。因此，将水平边画出后删去，不参加求交点及求交点以后的操作。

⒊扫描线与边的求交点方法采用递归算法。以(x1,y1)、(x2,y2)为端点的边与第i+1条扫描线的交点为此式表示交点不为(x1,y1)。否则，交点为(x1,y1)。⒋

减少求交计算量，采用活性边表。对于一根扫描线而言，与之相交的边只占多边形全部边的一部分,每根扫描线与多边形所有边求交的操作是一种浪费，需要加以改进。122.3区域填充算法

活性边表(ActiveListofSide)的采用将多边形的边分成两个子集：与当前扫描线相交的边的集合，以及与当前扫描线不相交的边的集合。对后者不必进行求交运算，这样就提高了算法的效率。图2.8活性边表及其指针的表示

132.3区域填充算法在上述线性表上加入两个指针first和last，形成活性边表。活性边表中每个元素的内容包括以下四项：边的maxy值；与当前扫描线相交的点的x坐标值；边的y方向当前总长y2-y1；边的斜率的倒数1/m。活性边表在每根扫描线扫描之后刷新。调整first和last指针之间的参加求交运算的边元素的值；调整first和last指针，以便使新边进入激活范围。活性边表构成方法如下：将经过左、右顶点处理并剔除水平边后的多边形各边按照maxy值排序，存入一个线性表中。14程序结构见课本32页。扫描线填色算法优、缺点：优点：对于每个象素只访问一次，输入输出的要求可降为最少；缺点：对于各种表的维持和排序的耗费大。扫描线（y=4）：623057.540.5

ymaxxΔy1/m扫描线（y=3）：322-25740.5

p3p4

p2p3012345678

7654321p1p2p3p4p5p4p5p2p315边填充算法（区域扫描转换算法）基本思想：对每条扫描线和多边形边的交点，将该扫描线上交点右方的所有像素取补。（对每条边作处理的顺序随意）p1p2p3p4p5算法优、缺点：优点：简单，适用于具有祯缓存的图形系统；缺点：每个象素可能被访问多次，输入输出的量大。16栅栏填充算法对于每条扫描线与多边形边的交点，将交点与栅栏之间的像素取补。栅栏线优点：减少了访问次数172.3区域填充算法

种子填色又称边界填色(BoundaryFilling)。它的功能是，给出多边形光栅化后的边界位