圆弧的生成算法研究.doc

圆弧的生成算法研究本文由天空乐园大学生旅游网整理分享 摘要本文研究了计算机图形学中圆弧生成的几种算法，有直角坐标算法、DDA算法、中心点法和Bresenham算法，并比较了它们的优缺点。其中前三种算法存在计算速度慢、精度差等的较大的缺点。本文着重介绍了使用广泛Bresenham算法。Bresenham 画圆算法是常用的一种画圆算法,它很大程度上客服了计算速度慢、精度差的缺点，是很好的圆弧生成算法。关键字：圆弧生成；直角坐标算法； DDA算法；中心点法；Bresenham算法；1、 引言 计算机图形学(Computer Graphics，简称CG)是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格形式的科学。简单地说，计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。计算机图形学的研究内容非常广泛，如图形硬件、图形标准、图形交互技术、光栅图形生成算法、曲线曲面造型、实体造型、真实感图形计算与显示算法、非真实感绘制，以及科学计算可视化、计算机动画、自然景物仿真、虚拟现实等。目前，绝大多数计算机图形系统使用的是阴极射线管显示器（CRT），显示器被分成若干大小相等的像素。通过控制使像素或暗或亮，从而使屏幕得到所需要的图形。这样，在显示器上显示的图形就存在误差，比如在显示器上显示一条直线，不可能从一个像素到另一个像素之间直接画一条直线，而是通过一系列的靠近直线的像素表示。怎样快速和精确地生成所需的图形就成为计算机图形学关心的问题。二、基本理论 目前，圆弧的生成算法有很多种，本文主要研究圆弧生成的直角坐标算法、DDA算法、中心点法和Bresenham算法，然后比较这几个算法的优缺点，从而说明Bresenham算法的快速，精确。2.1 直角坐标系算法直角坐标法是圆弧生成算法中一种比较简单的算法。由圆的方程 其中以为圆心坐标，取x为自变量，可知y为： （1）由式（1）可得出圆弧的直角坐标法： （2） 在式（2）这个直角坐标算法中，x以0到R等步长变化，当x越接近R时，圆的斜率越大，计算出来的y却不是间隔均匀的，这样画出的圆弧精度不高；在计算中，由于采用了平方、开方运算和取整运算，画圆时速度慢，算法效率不高，并且存在很大的误差。所以这个算法在实际的应用中很少采用，这里只是做一个简单说明。2.2 DDA（数值微分法）算法(0,0)(R,0)图1 圆心坐标原点由式（1）可知圆弧的参数方程为： （3） 说明：这里只给出圆心坐标在原点情况的图形（图1）。在式（3）中，为半径的旋转角度，对式（3）两边求导得到圆的极坐标方程： （4）由于： （5） 由式（3）和式（4）可得到圆弧的DDA算法 （6）在这个算法中，涉及到乘法运算和取整运算，输出的精度低；由于变化小，圆弧输出效率低。2.3 中心点法2.3.1 中心点法的具体内容 为了简便起见,只考虑中心在原点,半径为R的圆。 对于中心不在原点的圆,可先通过平移变换,转化为中心在原点的圆。考虑到圆的对称性,在具体进行扫描转换时,只需对1/8圆实施即可。如果要显示一个整圆,只要在显示上确定一点( x, y) , 利用对称性原理同时显示圆周上其它7 个对称点, 它们分别是(y,x),(y,-x),(x,-y),(-y,-x),(-y,x),(-x,y),(-x,-y)。如下图2：图2下面讨论从(0,R)到 顺时针确定最佳逼近于该圆弧的像素序列。 假定任一像素点为最接近理想圆弧的点并确定,那么下一像素点只能是正右方的像素点或右下方的像素点。如下图3所示。图3 当前像素与下一个像素的候选者构造函数：。1) 圆上的点；2) 圆内的点；3) 圆外的点。假设为的中点，如果，说明在圆内,离圆弧更近,应选为下一像素点;如果,说明在圆外,离圆弧更近,应选为下一像素点;如果,说明、与圆弧等距离,选任意一点皆可,约定选取点。构造判别式 若，选为下一像素点;再构造下一个判别式： 如图4所示：图4若，选为下一个像素点；在构造下一个判别式： 如图5所示图5由于起始点是,判别式的初始值为 依据的正负,就可以选出下一个要选择的点,同理依据、的正负,可以递推出后续的选择点。在这个算法中,涉及到取整运算和乘法运算,输出的精度低。2.3.2 中心点法的程序代码void MidPointCircle(int r,int color) int x,y,d x=0; y=r; d=5-4r; CirclePoint(x,y,color); while(x=y) if(d=0) d+=8x+12; else d+=8(x-y)+20;y-; x+; CirclePoint(x,y,color); 2.3.3 利用中心点法实现圆弧的绘制如下图图6 使用中心点法绘制的圆弧2.4 Bresenham 算法2.4.1 Bresenham算法的具体内容Bresenham画圆算法是最有效的算法之一。该算法是由Bresenham 提出来的，其基本的方法是利用判别变量来判断选择最近的像素，判别变量的数值仅仅用一些加、减和移位运算就可以计算出来。为了简便起见，考虑圆心在坐标原点，并且从（x=0、y=R）开始的顺时针方向的1/4的圆弧的生成过程。在这种情况下，x 坐标每走一步增加一个像素单位，从x=0 开始到x=R结束；y坐标则根据偏离圆弧的误差符号决定,减一个像素单位或不减.。已知为已经亮的点，要想得到下一个点，有三种可能：右边点、右下方点和下方点，在决定选那个像素点时，采用被选取的点与圆弧的距离的平方为最小。圆弧与当前显示点P 附近显示点R、D 和B 为五种情况如下图所示。图7 显示P 点的下一个点的五种情况圆心到D点的距离平方与圆的半径的平方为差为 （7） 以为决策变量来决定下一个要显示的点。当 0 时说明D 点在圆内，则图1 中1、2 符合，计算点R 和D 点到圆心距离的平方差： （8）1) 当0 时选择D点；当为第1种情况时，为 （9） 同理，可以分析其他四种情况，可以得出以下结论：1) 0，则取D点；2) 0 时，如时，则取D点；如0时，则取B点；3) =0 时，则取D点。本算法不涉及取整运算,乘法也可由加法取代,故算法效率高.2.4.2 Bresenham 算法C语言程序通过上面的计算，可以得出程序框图及其C语言程序。Bresenham 的C语言程序如下(程序框图如图8)：图8 程序框图程序代码：Circle(int Xo, int Yo, int R) d=(x+1)*(x+1)+(y-1)*(y-1)-R*R;dd=2*(d+y)-1;dv=2*(d-x)-1;if（d0） if(dd0) if(dv=0) /*让D 点亮*/else /*让B 点亮*/else /*让D 点亮*/2.4.3 利用Bresenham 算法实现圆弧的绘制下图是绘制的1/8圆弧.图9 Bresenham算法绘制的圆弧三、算法改进3 利用Bresenham 算法实现任意圆弧的绘制 当圆心不在原点时, 通过对Bresenham算法的变换可以实现任意圆弧的绘制。 设坐标系的原点 在屏幕中心, 水平向右为x轴正向,垂直向上为y轴正向,规定以逆时针方向旋转的角度() 为正向。 若圆弧的圆心在点P ( x, y) ,半径为r,通过平移变换把点P平移到原点,再通过旋转使圆弧的起始点与y轴正向重合。利用图形变换的反变换, 把Bresenhm迭代的点先旋转,再平移,即可在任意方向上生成圆弧。算法步骤:1) 用Bresenham算法进行点的迭代,迭代生成的点用表示；2) 进行旋转变换；3) 进行平移变换；4) 绘制；5) 重复1)到4）的步骤。经过改进后的算法多了一步乘法运算和取整运算,算法的时间复杂度并没有改变,圆弧的光栅梯度平滑。 图10到图12是算法改进后生成的圆弧。图10图11图12四、结果分析通过上述对各种圆弧生成算法的研究和比较，可以看出直角坐标算法、DDA算法、中心点法有很大精度差，并且运算的速度慢。Bresenham 圆弧生成算法得出了这种算法避开了乘法和开放运算，生成效率高，误差小。五、总结总体来说，圆弧的生成算法中Bresenham圆弧生成算法有明显的优势，它很好的解决了精度差大、程序代码运行速度慢的缺点，是圆弧生成算法的首选。当然，也可以以此算法为基础研究出更好的圆弧生成算法。六、参考文献1 孙家广, 许隆文. 计算机图形学M. 北京：清华大学出版社, 1986. 2 谭浩强, C程序设计（第二版）M. 北京：清华大学出版社, 1999.3 张荣国, 边秀雪. 圆弧插补的一种改进算法J. 太原重型机械学院学报, 1998, 19(2): 133-136.4 古辉, 古纯效. 一种新型的圆弧插补算法J. 山西机械, 19