1、Bresenham画线圆算法2.1.2 Bresenham算法Bresenham算法是计算机图形学典型的直线光栅化算法。从另一个角度看直线光栅化显示算法的原理由直线的斜率确定选择在x方向或y方向上每次递增（减）1个单位，另一变量的递增（减）量为0或1，它取决于实际直线与最近光栅网格点的距离，这个距离的最大误差为0.5。1)Bresenham的基本原理假定直线斜率k在01之间。此时，只需考虑x方向每次递增1个单位，决定y方向每次递增0或1。设 直线当前点为(xi,y) 直线当前光栅点为(xi,yi)则 下一个直线的点应为(xi+1,y+k) 下一个直线的光栅点 或为右光栅点(xi+1,yi)（y
2、方向递增量0） 或为右上光栅点(xi+1,yi+1)（y方向递增量1）记直线与它垂直方向最近的下光栅点的误差为d，有：d=(y+k)yi，且 0d1 当d0.5：下一个象素应取右光栅点(xi+1,yi) 当d0.5：下一个象素应取右上光栅点(xi+1,yi+1)如果直线的（起）端点在整数点上，误差项d的初值：d00，x坐标每增加1，d的值相应递增直线的斜率值k，即：dd + k。一旦d1，就把它减去1，保证d的相对性，且在0-1之间。令e=d-0.5，关于d的判别式和初值可简化成： e的初值e0= -0.5，增量亦为k; e0时，取当前象素(xi,yi)的右上方象素(xi+1,yi+1)； e
3、=0时，可任取上、下光栅点显示。Bresenham算法的构思巧妙：它引入动态误差e，当x方向每次递增1个单位，可根据e的符号决定y方向每次递增 0 或 1。 e0，y方向递增1 x方向每次递增1个单位，e = e + k因为e是相对量，所以当e0时，表明e的计值将进入下一个参考点（上升一个光栅点），此时须：e = e - 12)Bresenham算法的实施Rogers 版通过(0,0)的所求直线的斜率大于0.5，它与x=1直线的交点离y=1直线较近，离y=0直线较远，因此取光栅点(1,1)比(1,0)更逼近直线；如果斜率小于0.5，则反之；当斜率等于0.5，没有确定的选择标准，但本算法选择(1
4、,1)（程序）/Bresenhams line resterization algorithm for the first octal./The line end points are (xs,ys) and (xe,ye) assumed not equal./ Round is the integer function./ x,y, x, y are the integer, Error is the real./initialize variablesx=xsy=ysx = xe -xsy = ye -ys/initialize e to compensate for a nonzero
5、 interceptError =y/x-0.5/begin the main loopfor i=1 to x WritePixel (x, y, value) if (Error 0) then y=y+1 Error = Error -1 end if x=x+1 Error = Error +y/xnext ifinish3)整数Bresenham算法上述Bresenham算法在计算直线斜率和误差项时要用到浮点运算和除法，采用整数算术运算和避免除法可以加快算法的速度。由于上述Bresenham算法中只用到误差项（初值Error =y/x-0.5）的符号因此只需作如下的简单变换： NEr
6、ror = 2*Error*x即可得到整数算法，这使本算法便于硬件（固件）实现。（程序）/Bresenhams integer line resterization algorithm for the first octal./The line end points are (xs,ys) and (xe,ye) assumed not equal. All variables are assumed integer./initialize variablesx=xsy=ysx = xe -xsy = ye -ys/initialize e to compensate for a nonzer
7、o interceptNError =2*y-x /Error =y/x-0.5/begin the main loopfor i=1 to x WritePixel (x, y) if (NError =0) then y=y+1 NError = NError 2*x /Error = Error -1 end if x=x+1 NError = NError +2*y /Error = Error +y/xnext ifinish4)一般Bresenham算法要使第一个八卦的Bresenham算法适用于一般直线，只需对以下2点作出改造：当直线的斜率|k|1时，改成y的增量总是1，再用Br
8、esenham误差判别式确定x变量是否需要增加1；x或y的增量可能是“+1”或“-1”，视直线所在的象限决定。（程序）/Bresenhams integer line resterization algorithm for all quadrnts/The line end points are (xs,ys) and (xe,ye) assumed not equal. All variables are assumed integer./initialize variablesx=xsy=ysx = abs(xe -xs) /x = xe -xsy = abs(ye -ys) /y = y
9、e -yssx = isign(xe -xs)sy = isign(ye -ys)/Swap x and y depending on the slope of the line.if yx then Swap(x,y) Flag=1else Flag=0end if/initialize the error term to compensate for a nonezero interceptNError =2*y-x/begin the main loopfor i=1 to x WritePixel(x, y , value) if (Nerror=0) then if (Flag) t
10、hen /yx，Y=Y+1 x=x+sx else y=y+sy end if / End of Flag NError = NError 2*x end if / End of Nerror if (Flag) then /yx，X=X+1 y=y+sy else x=x+sx end if NError = NError +2*ynext ifinish例子o 2.2.2 中点圆算法原理设d是点p(x,y)到圆心的距离，有：d= F(x,y)=x2+y2-R2按照Bresenham算法符号变量的思想，以圆的下2个可选象素中点的函数值d的符号决定选择2个可选象素T和B中哪一个更接近圆而作为圆
11、的显示点？ dM= F(xM,yM)= F(xp+1,yp-0.5)=(xp+1)2+( yp-05)2-R2如果dM0，表示下一中点M在圆外，用B点逼近，得 dMB= F(xMB,yMB)= F(xp+2,yp-1.5)=(xp+2)2+( yp-1.5)2-R2 dMB= dMB - dM=2xp-2yp +5结论根据中点d的值，决定显示的光栅点（T或B）新的d（ dMT或dMB ）更新d初值由x0=0，y0=R得xM0=0+1，yM0 = R-0.5dM0= F(xM0,yM0)= F(1,R-0.5)= 12+( R-05)2-R2=1.25-R实施/中点圆算法（假设圆的中心在原点）v
12、oid MidPointCircle(int radius,int value) int x=0; int y= radius; double d=1.25- radius; CirclePoints(x, y, value); While (yx) CirclePoints(x, y,value); if (d0) /选择T d+=2.0*x+3.0; else /选择B d+=2.0*(x-y)+5.0; y-; x+; CirclePoints(x, y,value); /End of while2.2.3 中点圆整数算法 原理中点圆算法的半径是整数，而用于该算法符号判别的变量d（初值d
13、=1.25- radius）采用浮点运算，会花费较多的时间。为了将其改造成整数计算，定义新变量： D =d - 0.25那么判别式d0等价于D-0.25。在D为整数情况下，D-0.25和Dx) CirclePoints(x, y,value); if (d=x) CirclePoints(x, y,value); if (dx) if (d0) /选择T d=d+dt; else /选择B d=d+db; db+=2; y-; dt+=2; db+=2; x+; CirclePoints(x, y,value); /当R5时，将会在x=3,y=4和x=4,y=3显示两次！ /End of while /Finish 例子o
