计算机图形学 圆的扫描转换

1、第三讲 圆的扫描转换1）直接利用圆的方程生成圆）直接利用圆的方程生成圆 下面先以圆心在原点、半径r为整数的圆为例，讨论圆的生成算法。假设圆的方程为： x2 + y2 = r2x2 + y2 = r2y = sqrt(r2 - x2)在一定范围内，每给定一x值，可得一y值。当x取整数时，y须取整。缺点：浮点运算，开方，取整，不均匀。yx )(2R0, x121211iiiixRroundyxx也可应用圆的参数方程画出分布比较均匀的点x = Rcosy = Rsin 但仍要采用浮点运算、乘法运算、取整运算。)sin( )cos()( 11111iiiiiiRroundyRroundx为一固定角度步

2、长(x,y)yy=-xy=x(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)2）八分法画圆）八分法画圆利用圆的对称性：利用圆的对称性：结论：只需对一个八分圆进行扫描转换。结论：只需对一个八分圆进行扫描转换。yy=x图5-10 1/8圆弧xR 当圆心坐标(xc ，yc ) ，半径为整数r时： (x-xc)2+(y-yc)2=r2 可以先对圆心坐标(0 ，0 ) ，半径为r的八分圆进行扫描转换，根据圆的对称性，得到八个对称点，再将这八个点进行平移，即可得到原始圆上的对应点。3 3）画任意圆的方法）画任意圆的方法 void Circle8Points(int x

3、0,int y0, int x,int y,COLORREF c) pDC-SetPixel(x0+x,y0+y,c); pDC-SetPixel(x0-x,y0+y,c); pDC-SetPixel(x0+x,y0-y,c); pDC-SetPixel(x0-x,y0-y,c); pDC-SetPixel(x0+y,y0+x,c); pDC-SetPixel(x0-y,y0+x,c); pDC-SetPixel(x0+y,y0-x,c); pDC-SetPixel(x0-y,y0-x,c); 对于圆心在（对于圆心在（x0,y0)、半径为、半径为r的圆，先对圆心在原的圆，先对圆心在原点，半径为

4、点，半径为r的的8分圆进行扫描转换，每确定一个象素，可分圆进行扫描转换，每确定一个象素，可输出原始圆的输出原始圆的8个点。个点。2 中点画圆法利用圆的对称性，只须讨论1/8圆。第二个8分圆。P为当前点亮象素，那么，下一个点亮的象素可能是P1（xp+1，yp）或P2（xp +1，yp -1)。(|dy|=|x/y|*|dx|)MP1P2P（xp ，yp ）P2构造函数：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)MP1有如下结论： F（M）M在圆内- 取P1 F（

5、M）= 0 -M在圆外- 取P2为此，可采用如下判别式： MP1P2 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. MP1P2M最后一个问题：判别式最后一个问题：判别式d的初始值的初始值rrrrFd25. 1 )5 . 0(1 )5 . 0

6、, 1 (220算法步骤算法步骤：1.输入圆的半径R。2.计算初始值d=1.25-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当x=y时，重复步骤3和4。否则结束。中点画圆法程序代码中点画圆法程序代码 MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1.25-r; drawpixel(x,y,color); while(

7、x=y) if(d0) d=d+2*x+3; x+ elsed= d+2*(x-y) + 5; x+;y-; 为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。 使用e=d-0.25代替d e0=1-r 当e为整数时（e0)(e-0.25)算法优化算法优化算法步骤算法步骤：1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为

8、(x+1,y-1)。5.当x=y时，重复步骤3和4。否则结束。中点画圆法程序代码中点画圆法程序代码 MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1-r; drawpixel(x,y,color); while(x=y) if(d0) d+ = 2*x+3; x+ elsed+ = 2*(x-y) + 5; x+;y-; 上述算法能否再改进呢？上述算法能否再改进呢？注意到注意到d d的增量是的增量是x x, ,y y的线性函数，的线性函数， 每当每当x x递增递增1 1，则，则d d的增量递增的增量递增x x=2=

9、2 每当每当y y递减递减1 1，则，则d d的增量递增的增量递增y y=2=2 x x初始值初始值=3=3；y y初始值初始值=-2=-2r r+2+2x=0; y=r; d=1-r; .if(d0) d+ = 2*x+3; x+ ;elsed+ = 2*(x-y) + 5; x+;y-; x=0;y=r;d=1-r;d1=3;d2=-2*r+2; .if(d0) d+ = d1; x+;d1+=2 ;elsed+ = d1+d2; x+;y-; d1+=2;d2+=2 MidpointCircle(int r, int color) int x,y; int d; x=0; y=r; d=

10、1-r;d1=3;d2=-2*r+2; while(x=y) drawpixel(x,y,color); if(d0) d+ = d1; x+;d1+=2 else d+ = d1+d2; x+;y-; d1+=2;d2+=2; 3 Bresenham画圆法 Bresenham画圆法与中点画圆法有很多共同之处，不同之处主要是判别式的设计。详见课本169页。本讲小结本讲小结 了解直接用圆的方程计算确定圆上了解直接用圆的方程计算确定圆上的像素的方法及其不足。的像素的方法及其不足。 掌握通过一个八分圆的扫描转换，掌握通过一个八分圆的扫描转换，画出任意圆周的方法。画出任意圆周的方法。 理解中点画圆法的

11、基本思想，掌握理解中点画圆法的基本思想，掌握中点画圆算法及其特点。中点画圆算法及其特点。 能够应用中点画圆法，编程实现画能够应用中点画圆法，编程实现画圆的功能。圆的功能。掌握掌握画圆算法及其特点。画圆算法及其特点。能够应用能够应用画圆法，编程画圆法，编程实现画圆的功能。实现画圆的功能。 光栅系统的光栅系统的Bresenham画线算法可通过设画线算法可通过设定在每一取样步寻找最接近圆周像素的决策参定在每一取样步寻找最接近圆周像素的决策参数而移植为画圆算法。数而移植为画圆算法。 然而，圆方程是非线性的，因此，计算像然而，圆方程是非线性的，因此，计算像素与圆的距离必须进行平方根运算。素与圆的距离必须

12、进行平方根运算。 Bresenham画圆算法则通过比较像素与圆画圆算法则通过比较像素与圆的距离的平方而避免了平方根运算。的距离的平方而避免了平方根运算。 与与Bresenham直线生成算法一样，其基本直线生成算法一样，其基本思想：利用判别变量来判断选择最近的像素，思想：利用判别变量来判断选择最近的像素，判别变量仅用加减和移位就可计算出来判别变量仅用加减和移位就可计算出来 。同样，只考虑同样，只考虑1/8圆，圆，x从到从到R/ 结束。结束。 如果得到第如果得到第k步的步的像素点像素点(xk,yk)， 则下一个像素只可则下一个像素只可能是能是 A(xk+1,yk) 或或B(xk+1,yk-1),

13、如图。如图。2)1, 1(0)1, 1(), 1(), 10)1, 1(), 1(kkkkkkkkkkkkyxyxfyxfyxyxfyxf选择时当选择（时当显然满足：) 1, 1(), 1(kkkkkyxfyxfd定义判别参数：222),(ryxyxf定义：222222) 1() 1() 1(ryxryxdkkkkk以最高点为初始点，计算判别量初值再根据判别量的正负确定递推关系递推关系的确定需根据图分别不同情况进行讨论（去掉绝对值符号，并进行化简）( , )x ykk圆弧上可选点情况), 1(kkyx ) 1, 1(kkyx 初始值的计算) 1, 1 (), 1 (0rfrfdn利用增量计算方法加速判别参数的计算010)(40641kkkkkkkkdyxddxdd注：比较其与中点画圆算法的判别参数。222222) 1(11rrrr221rr23BresenhamBresenham画圆算法代码画圆算法代码void CircleBres(int radius) int x=0,y=radius,p=3-2*radi