计算机图形学 第五章_Arc

1、Designed by Ruifang ZHAI华中农业大学计算机科学与技术系计计 算算 机机 图图 形形 学学 Computer GraphicsComputer Graphics翟瑞芳翟瑞芳Designed by Ruifang ZHAI华中农业大学计算机科学与技术系解决的问题：解决的问题：绘出圆心在原点，半径为绘出圆心在原点，半径为整数整数R的圆的圆x2+y2=R2。Designed by Ruifang ZHAI华中农业大学计算机科学与技术系(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)八分法画圆八分法画圆Designed by Ruifang

2、ZHAI华中农业大学计算机科学与技术系解决问题：解决问题： 只要扫描转换八分之一圆弧，就可以求出整个圆只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集弧的象素集1/8圆弧圆弧Designed by Ruifang ZHAI华中农业大学计算机科学与技术系 解决方法解决方法中点画圆中点画圆Bresenhem算法算法Designed by Ruifang ZHAI华中农业大学计算机科学与技术系 X2 + Y2 = R2Y = Round（Sqrt(R2 - X2)）在一定范围内，每给定一在一定范围内，每给定一X值，可得一值，可得一Y值。值。当当X取整数时，取整数时，Y须取整。须取整。缺点：浮点运

3、算，开方，缺点：浮点运算，开方，取整，不均匀。取整，不均匀。yx算法原理算法原理：利用其函数方程，直接离散计算。利用其函数方程，直接离散计算。Designed by Ruifang ZHAI华中农业大学计算机科学与技术系圆的圆的极坐标方程极坐标方程为：为： sincosRyRx)sin( )cos()( 11111iiiiiiRroundyRroundx为一固定角度步长Designed by Ruifang ZHAI华中农业大学计算机科学与技术系简单方程产生圆弧的方法计算复杂，简单方程产生圆弧的方法计算复杂，效率极低。效率极低。Designed by Ruifang ZHAI华中农业大学计算机

4、科学与技术系构造函数构造函数F(x,y)=x2+y2-R2。 对于圆上的点，有对于圆上的点，有F(x,y)=0； 对于圆外的点，对于圆外的点， F(x,y)0； 而对于圆内的点，而对于圆内的点，F(x,y)0时，下一点取时，下一点取 Pd(xi +1,yi-1)。构造判别式：构造判别式：222)5 . 0() 1()5 . 0, 1(),(RyxyxFyxFdiiiiMMDesigned by Ruifang ZHAI华中农业大学计算机科学与技术系误差项的递推（误差项的递推（d0） 2222)5 . 0()2( )5 . 0, 2(RyxyxFdiiii32)5 . 0(32) 1()5 .

5、0() 11(12222222iiiiiixdRyxxRyxdd0的情况的情况Designed by Ruifang ZHAI华中农业大学计算机科学与技术系2222)5 . 1()2( )5 . 1, 2(RyxyxFdiiii5)(25)(2)5 . 0() 1(1)5 . 0(2)5 . 0(32) 1() 15 . 0() 11(1222222222iiiiiiiiiiiiyxdyxyxRyyxxRyxd误差项的递推（误差项的递推（d0） d0的情况的情况Designed by Ruifang ZHAI华中农业大学计算机科学与技术系判别式的初始值判别式的初始值RRRRFyxFd25. 1

6、 )5 . 0(1 )5 . 0, 1 ()5 . 0, 1(22000Designed by Ruifang ZHAI华中农业大学计算机科学与技术系改进：改进：用用d-0.25d-0.25代替代替d d，此时有：，此时有：Rddyxdddxddiii125. 05)(225. 0320025. 0025. 0ddddDesigned by Ruifang ZHAI华中农业大学计算机科学与技术系算法步骤：算法步骤：1. 输入圆的半径输入圆的半径R。2. 计算初始值计算初始值d=1.25-R、x=0、y=R。3. 绘制点绘制点(x,y)及其在八分圆中的另外七个对称点。及其在八分圆中的另外七个对称

7、点。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. 当当xy时，重复步骤时，重复步骤3和和4。否则结束。否则结束。Designed by Ruifang ZHAI华中农业大学计算机科学与技术系 MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1.25-r; drawpixel(x,y,color); while(xy) if(

8、d0) d+ = 2*x+3; x+ elsed+ = 2*(x-y) + 5; x+;y-; Designed by Ruifang ZHAI华中农业大学计算机科学与技术系算法步骤算法步骤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)更新为更新为(x+1,y-1)。5.当当

9、x F(xi,yi) 向右向右- 向圆外向圆外Pi在圆外时在圆外时- F(xi,yi)0 - 向下向下- 向圆内向圆内Designed by Ruifang ZHAI华中农业大学计算机科学与技术系即求得即求得Pi点后选择下一个象素点点后选择下一个象素点Pi+1的规则为：的规则为：当当F(xi,yi) 0 取取xi+1 = xi+1，yi+1 = yi;当当F(xi,yi) 0 取取xi+1 = xi， yi+1 = yi - 1;这样用于表示圆弧的点均在圆弧附近，且使这样用于表示圆弧的点均在圆弧附近，且使F(xi,yi) 时正时负，故称正负法。时正时负，故称正负法。 快速计算的关键是快速计算的

10、关键是F(xi,yi) 的计算，能否采用增的计算，能否采用增量算法？量算法？Designed by Ruifang ZHAI华中农业大学计算机科学与技术系若若F(xi,yi) 已知，计算已知，计算F(xi+1,yi+1) 可分可分两种情况：两种情况：1、F(xi,yi)0- xi+1 = xi+1，yi+1 = yi; - F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2 - = (xi+1)2+ yi2 -R2 = F(xi,yi) +2xi +12、 F(xi,yi)0- xi+1 = xi，yi+1 = yi -1; - F(xi+1,yi+1)= (xi+1 )

11、2 +(yi+1 )2 -R2 - = xi2+(yi 1)2-R2 = F(xi,yi) - 2yi +13、初始值：略初始值：略Designed by Ruifang ZHAI华中农业大学计算机科学与技术系Designed by Ruifang ZHAI华中农业大学计算机科学与技术系1. 椭圆的特征椭圆的特征bax xy y图 5-14 长 半 轴 为 a， 短 半 轴 为 b的 标 准 椭 圆( (x x, ,y y) )( (x x, ,- -y y) )( (- -x x, ,- -y y) )( (- -x x, ,y y) )Designed by Ruifang ZHAI华中农

12、业大学计算机科学与技术系0),(222222bayaxbyxF 对于椭圆上的点，有对于椭圆上的点，有F(x,y)=0F(x,y)=0； 对于椭圆外的点，对于椭圆外的点，F(x,y)0F(x,y)0； 对于椭圆内的点，对于椭圆内的点，F(x,y)0F(x,y)00，取，取P Pd d(x(xi i+1,y+1,yi i-1)-1)p p( (x xi i, ,y yi i) )p pu u( (x xi i+ +1 1, ,y yi i) )p pd d( (x xi i+ +1 1, ,y yi i- -1 1) )M M( (x xi i+ +1 1, ,y yi i- -0 0. .5 5

13、) ) 上上半半部部分分椭椭圆圆弧弧的的绘绘制制原原理理Designed by Ruifang ZHAI华中农业大学计算机科学与技术系误差项的递推误差项的递推 d10：)x(bd )x(bba).(ya)(xb ba).(ya)(xb).,yF(xdiiiiiiii32325015025022122222222222221Designed by Ruifang ZHAI华中农业大学计算机科学与技术系) 22() 32 ( ) 22() 32 () 5 . 0() 1( ) 5 . 1() 2() 5 . 1, 2(221222222222222221iiiiiiiiiiyaxbdyaxbbay

14、axbbayaxbyxFd误差项的递推误差项的递推 d10：Designed by Ruifang ZHAI华中农业大学计算机科学与技术系判别式的初始值判别式的初始值 )25. 0( )5 . 0()5 . 0, 1 (22222220babbababbFdDesigned by Ruifang ZHAI华中农业大学计算机科学与技术系p p( (x xi i, ,y yi i) )p pl l( (x xi i, ,y yi i- -1 1) )p pr r( (x xi i+ +1 1, ,y yi i- -1 1) )M M( (x xi i+ +1 1, ,y yi i- -0 0. .

15、5 5) )5-19 下半部分椭圆弧的绘制原理再来推导椭圆弧下半部分的绘制公式再来推导椭圆弧下半部分的绘制公式Designed by Ruifang ZHAI华中农业大学计算机科学与技术系判别式判别式 2222222) 1() 5 . 0() 1, 5 . 0(bayaxbyxFdiiii 若若d20，取，取Pl(xi,yi-1) 若若d20，取，取Pr(xi+1,yi-1)p p( (x xi i, ,y yi i) )p pl l( (x xi i, ,y yi i- -1 1) )p pr r( (x xi i+ +1 1, ,y yi i- -1 1) )M M( (x xi i+ +

16、1 1, ,y yi i- -0 0. .5 5) )5-19 下半部分椭圆弧的绘制原理Designed by Ruifang ZHAI华中农业大学计算机科学与技术系误差项的递推误差项的递推 d20：)y(ad )y(aba)(ya)(xb ba)(ya)(xb),yF(xdiiiiiiii323215 . 025 . 025 . 0 2222222222222222Designed by Ruifang ZHAI华中农业大学计算机科学与技术系d20： ) 32() 22( ) 32() 22() 1() 5 . 0( ) 2() 5 . 1() 2, 5 . 1(22222222222222

17、2222iiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFd( (b b) ) d d = =0 0的的情情况况P Px xi ix xi i+ +2 2x xi i+ +1 1y yi i- -1 1y yi iy yi i- -2 2Designed by Ruifang ZHAI华中农业大学计算机科学与技术系注意：注意： 上半部分的终止判别上半部分的终止判别 下半部分误差项的初值下半部分误差项的初值 算法步骤：算法步骤：1. 输入椭圆的长半轴输入椭圆的长半轴a和短半轴和短半轴b。2. 计算初始值计算初始值d=b2+a2(-b+0.25)、x=0、y=b。3. 绘制点绘制点(x,y)及其在四分象限上的另外三个对称点。及其在四分象限上的另外三个对称点。Des