计算机图形学4圆及椭圆的扫描转换.ppt

1、第四讲 圆和椭圆的扫描转换,1 基础知识 2 中点画圆法 3 Bresenham画圆法,1）直接利用圆的方程生成圆 下面先以圆心在原点、半径r为整数的圆为例，讨论圆的生成算法。 假设圆的方程为： x2 + y2 = r2,1 基础知识,x2 + y2 = r2 y = sqrt(r2 - x2) 在一定范围内，每给定一 x值，可得一y值。 缺点：浮点运算，开方， 取整，不均匀。,也可应用圆的参数方程画出分布比较均匀的点 x = Rcos y = Rsin 但仍要采用浮点运算、乘法运算、取整运算。,(y,x),(-y,x),(-x,y),(-x,-y),(-y,-x),(y,-x),(x,-y)

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

3、); 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的圆，先对圆心在原点，半径为r的8分圆进行扫描转换，每确定一个象素，可输出原始圆的8个点。,2 中点画圆法,利用圆的对称性，只须讨论1/8圆。第二个8分圆。 P为当前点亮象素，那么，下一个点亮的象素可能是P1（xp+1，yp）或P2（xp +1，yp -1)。,M,P1,P2,P（xp

4、，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),M,P1,有如下结论： F（M）M在圆内- 取P1 F（M）= 0 -M在圆外- 取P2 为此，可采用如下判别式：,M,P1,P2,d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2 - r2 若d0, 则P1 为下一个象素，那么再下一个象素的判别式为： d1 = F(xp + 2, yp - 0.5) = (xp + 2)2

5、 + (yp - 0.5) 2 - r2 = d + 2xp +3 即d 的增量为 2xp +3.,M,P1,P2,M,若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.,M,P1,P2,M,最后一个问题：判别式d的初始值,算法步骤： 1.输入圆的半径R。 2.计算初始值d=1.25-R、x=0、y=R。 3.绘制点(x,y)及其在八分圆中的另外七个对称点。 4.判断

6、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(x=y) if(d0) d=d+2*x+3; x+ elsed= d+2*(x-y) + 5; x+;y-; ,为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，

7、将乘法运算改成加法运算，即仅用整数实现中点画圆法。 使用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)更新为(x+1,y-1)。 5.当x=y时，重复步骤3和4。否则结束。,中点画圆法程序代码,MidpointCircle(int r, int color) int x,y; floa

8、t 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的增量是x,y的线性函数， 每当x递增1，则d的增量递增x=2 每当y递减1，则d的增量递增y=2 x初始值=3；y初始值=-2r+2,x=0; y=r; d=1-r; . if(d0) d+ = 2*x+3; x+ ; else d+ = 2*(x-y) + 5; x+;y-; ,x=0;y=r;d=1-r;deltax=3;delty=-2*r+2

9、; . if(d0) d+ = deltax; x+; deltax+=2 ; else d+ = deltx+delty; x+;y-; deltx+=2; delty+=2 ,MidpointCircle(int r, int color) int x,y; int d; x=0; y=r; d=1-r; deltx =3; delty =-2*r+2; while(xy) drawpixel(x,y,color); if(d0) d+ = deltx; x+; deltx +=2 else d+ = deltx + delty; x+;y-; deltx +=2; delty+=2; ,

10、3 Bresenham画圆法,Bresenham画圆法与中点画圆法有很多共同之处，不同之处主要是判别式的设计。,Bresenham画圆算法,顺时针画第一四分圆，下一步选择哪个点？ 基本思想： 通过比较像素与圆的距离平方来避免开方运算 下一像素有3种可能的选择 mH=|(xi+1)2+yi2-R2| mD=|(xi+1)2+(yi-1)2-R2| mV=|xi2 +(yi-1)2-R2 | 选择像素的原则 使其与实际圆弧的距离平方达到最小,Bresenham画圆算法,圆弧与点(xi,yi)附近光栅网格的相交关系有5种 右下角像素D (xi,yi)与实际圆弧的近似程度 i=(xi+1)2+(yi-

11、1)2-R2 当i0时，D在圆外，,Bresenham画圆算法,当i0，则选D 若d=0，则选H,情形也适用,Bresenham画圆算法,当i0时，D在圆外， 情形，选mv ，mD 中最小者 d=mD - mV =|(xi+1)2+(yi-1)2-R2 | - |xi2+(yi-1)2-R2| =(xi+1)2+(yi-1)2-R2 + xi2+(yi-1)2-R2 =2 (i-xi)-1 若d0，则选V 若d=0，则选D,情形也适用,Bresenham画圆算法,当i=0时，D在圆上， 取D点作为下一个象素,Bresenham画圆算法,当i0，选D 当i0时, 若d 0，选D 若d0，选V 当

12、i=0时， 选D,Bresenham画圆算法,判别式的递推关系 当取H(xi+1,yi)时 i+1=(xi+1+1)2+(yi-1)2-R2= i+2(xi+1)+1 当取V(xi,yi-1)时 i+1=(xi+1)2+(yi-1-1)2-R2= i-2(yi-1)+1 当取D(xi+1,yi-1)时 i+1=(xi+1+1)2+(yi-1-1)2-R2= i+2(xi+1)-2(yi-1)+2,Bresenham_Circle(int r,int color) int x,y,delta,delta1, delta2,direction; x=0;y=r;delta=2*(1-r); whi

13、le(y=0) drawpixel(x,y,color); if(delta0) delta1=2*(delta+y)-1; if(delta1=0) direction=1; else direction=2; ,else if (delta0) delta2=2*(delta-x)-1; if (delta=0) direction=2; else direction=3; else direction=2; switch(direction) case 1: x+; delta+=2*x+1; break; case 2: x+;y-; delta+=2*(x-y+1); break;

14、case 3: y-; delta+=(-2*y+1); break; ,本讲小结,1 基础知识 2 中点画圆法 3 Bresenham画圆法,了解直接用圆的方程计算确定圆上的像素的方法及其不足。 掌握通过一个八分圆的扫描转换，画出任意圆周的方法。,理解中点画圆法的基本思想，掌握中点画圆算法及其特点。 能够应用中点画圆法，编程实现画圆的功能。,掌握Bresenham画圆算法及其特点。,实验三,实验目的：理解和掌握圆的扫描转换的中点画圆算法。 实验名称：圆的中点画圆算法 实验步骤：（写出实际实现的程序和结果） 实验总结。,椭圆的扫描转换,F(x,y)=b2x2+a2y2-a2b2=0 椭圆的对称

15、性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。 椭圆上一点处的法向： N(x,y) = (F) x i + (F) y j = 2b2 x i + 2a2 y j,在上半部分,法向量的y分量大 在下半部分,法向量的x分量大,上半部分,下半部分,法向量 两分量相等,M1,M2,在当前中点处，法向量（ 2b2 (Xp+1) ，2a2 (Yp-0.5)的y分量比x分 量大, 即： b2 (Xp+1) a2 (Yp-0.5), 而在下一中点，不等式改变方 向，则说明椭圆弧从上部分转入下部分,椭圆的中点画法,与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一

16、个判别式的值，由判别式的符号确定更近的点 先讨论椭圆弧的上部分 设(Xp，Yp)已确定，则下一待选像素的中点是(Xp+1,Yp-0.5) d1=F(Xp+1,Yp-0.5) = b2(Xp+1)2+a2(Yp-0.5)2-a2b2,根据d1的符号来决定下一像素是取正右方的那个，还是右上方的那个。 若d10，中点在椭圆内，取正右方象素，判别式更新为： d1=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3) d1的增量为b2(2Xp+3) 当d10，中点在椭圆外，取右下方象素，更新判别式： d1=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2) d1的增量为b2(2Xp+3)+a2(-2Yp+2),d1的初始条件：椭圆弧起点为(0，b)； 第一个中点为(1,b-0.5) 初始判别式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25) 转入下一部分，下一象素可能是正下方或右下方，此时判别式要初始化。 d2 = F(Xp+0.5,Yp-1) = b2(Xp+0.5)2+a2(Yp-1)2-a2b2 若d2=0,取正下方像素，则d2 = F(Xp+0.5,Yp-2) = d2 + a2(-2Yp+3) 下