图形显示软件

1

图形软件

——Bresenham画线算法AboutBresenhamE.JackBresenham

——ProfessorofComputerSciencePh.D.,StanfordUniversity,1964MSIE,StanfordUniversity,1960BSEE,UniversityofNewMexico,1959Retiredfrom27yearsserviceatIBMasaSeniorTechnicalStaffMemberin1987.Havetaught10yearsatWinthrop.Holderoffivepatents.第一页，共四十八页。2图形软件

——Bresenham画线算法Bresenham算法该算法由Bresenham在1965年提出，是目前使用较为广泛的一种扫描转换算法，可用于直线、圆弧等图元的扫描转换。第二页，共四十八页。3图形软件

——Bresenham画线算法Bresenham画线算法基本思想过各行各列像素中心构造一组假想的栅格按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素第三页，共四十八页。4图形软件

——Bresenham画线算法Bresenham画线算法设直线从起点（x1,y1）到终点（x2,y2）设直线方程为：y=kx+b

其中b=y1-k*x1第四页，共四十八页。5图形软件

——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）根据即DDA算法的讨论有：xi+1=xi+1(1)yi+1=yi+k(2)

在1a象限里，当直线光栅化时，x每次都增加1个单元：xi+1=xi+1第五页，共四十八页。6图形软件

——Bresenham画线算法Bresenham画线算法由于k不一定是整数，因此由(2)式求出的y也不一定是整数。所以要用最靠近y的整数yi来代替y假设直线上第i个像素坐标为(xi,yi)，那么，它的下一个点的像素点的可能位置为(xi+1,yi)或(xi+1,yi+1)。如图：第六页，共四十八页。7图形软件

——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）如上图在x=xi+1处，直线上y的值y=k(xi+1)+b该点距离点(xi+1,yi)和点(xi+1,yi+1)的距离分别为d1和d2：d1=y-yi=k(xi+1)+b-yi

d2=yi+1-y=yi+1-k(xi+1)-b

因此，这两个距离的差为：d1-d2=2k(xi+1)-2yi+2b-1(1)第七页，共四十八页。8图形软件

——Bresenham画线算法Bresenham画线算法根据（1）式，作如下讨论分析：当d1-d2>0时，说明直线上的理论点距离(xi+1,yi+1)较近，因此下一个直线像素点应取(xi+1,yi+1)。当d1-d2<0时，说明直线上的理论点距离(xi+1,yi)较近，因此下一个直线像素点应取(xi+1,yi)。当d1-d2=0时，说明直线上的理论点距离上、下两个像素点的距离相等，因此规定取(xi+1,yi+1)作为下一个直线像素点第八页，共四十八页。9图形软件

——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）因此，利用（d1-d2）的符号就可以决定下一个像素点的选择然而含有

变量xi、yi，不利于计算。为此，我们构造一个新的判别式：pi=x*(d1-d2)=2xiy-2yix+c（2）其中：x=(x2-x1)>0，因此pi与(d1-d2)符号相同；

y=y2-y1；c=2y+x(2b-1)第九页，共四十八页。10

图形软件

——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）①以i+1代入式(2)中的i，得：pi+1=x*(d1-d2)=2xi+1y-2yi+1x+c（3）②将式(3)减去式(2)，并由xi+1=xi+1可得：pi+1=pi+2y-2x(yi+1-yi)（4）③

假设直线上的初始端点恰好是其像素点的坐标，则将x1,y1和b代入式（2）中的xi,yi可到pi的初始值p1=2x1y-2y1x+2y+x[2(y1-kx1)-1]=2y-x（5）第十页，共四十八页。11图形软件

——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）利用上面构造的误差判别变量，可得第1a象限内的直线Bresenham算法：p1=2y-x

xi+1=xi+1yi+1=yi+1,pi+1=pi+2(y-x)当pi≥0时

yi+1=yi,pi+1=pi+2y当pi<0时第十一页，共四十八页。12图形软件

——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）从算法可以看出，第i+1步的判别变量pi+1仅与第i步的判别变量pi、直线的两个端点分量差x、y有关，只用整数相加和乘2运算，没有四舍五入处理，而乘2可利用左移一位来实现因此该算法速度快且易于硬件实现第十二页，共四十八页。13图形软件

——Bresenham画线算法Bresenham画线算法描述若直线斜率k∈[0,1]且x2>x1的情况（1a象限）1、输入两端点(x1,y1),(x2,y2)，并以第一点作为起始点2、分别计算x=x2-x1;y=y2-y1；计算误差初值p1=2y-x；i=1；3、求直线的下一点位置：

xi+1=xi+1；

ifpi≥

0

则yi+1=yi+1；否则yi+1=yi；第十三页，共四十八页。14图形软件

——Bresenham画线算法Bresenham画线算法描述若直线斜率k∈[0,1]且x2>x1的情况（1a象限）4、画点（xi+1,yi+1）；5、求下一个误差pi+1；

ifpi≥0

则pi+1=pi+2y-2x；否则pi+1=pi+2y

；6、i=i+1；ifi<x+1则转3；否则end第十四页，共四十八页。15图形软件

——Bresenham画线算法Bresenham画线算法现在讨论如何让该算法实现任何方向线段的绘制如图所示，线段的方向可分为8种，从原点出发射向8个区当直线斜率的绝对值大于1时，让y坐标每次增加1，再用

Bresenham的误差判别式确定x坐标是否需要增加1。第十五页，共四十八页。16图形软件

——Bresenham画线算法Bresenham画线算法如果能充分利用x－y平面各种八分和四分区域间的对称性就可减少运算量。象限取值1a、2ayi+1=yi或yi+13a、4ayi+1=yi或yi-11b、2bxi+1=xi或xi+13b、4bxi+1=xi或xi-1第十六页，共四十八页。17图形软件

——Bresenham画线算法Bresenham画线算法（FLASH演示）例:分析从(0,0)到(5,2)的直线段原始直线Bresenham画出直线第十七页，共四十八页。18图形软件

——圆的生成算法给出圆心坐标(xc,yc)和半径r，逐点画出一个圆周的公式有下列两种：1.直角坐标法由上式导出：

第十八页，共四十八页。⒈直角坐标法当xxc从r到r作加1递增时，就可以求出对应的圆周点的y坐标但由于有乘方和平方根运算，且都是浮点运算，算法效率不高。同时，这样求出的圆周上的点是不均匀的xxc接近R时，由于圆的斜率趋向于无穷大，使得圆周上有较大的间隙19图形软件

——圆的生成算法第十九页，共四十八页。20图形软件

——圆的生成算法⒉

极坐标法假设圆周上一点(x,y)处的半径与x轴的夹角为θ,则圆的极坐标方程为：x=xc+r·cosθy=yc+r

·sinθ利用圆周上点的对称性，我们可求出圆上各点，此时自变量θ的取值范围是[0,45]度，以固定角度为步长来变化，可得到沿圆周等距离分布的一系列光点，但运算量大，也不被采用。AB极坐标法对称性（x,y）（y,x）（y,-x）（x,-y）（-x,y）（-y,x）（-y,-x）（-x,-y）45°第二十页，共四十八页。21图形软件

——圆的生成算法Bresenham画圆算法与Bresenham直线生成算法一样，其基本思想：利用判别变量来判断选择最近的像素，判别变量仅用加减和移位就可计算出来为讨论方便，仅考虑圆心在原点，半径为R的第一象限上的一段圆弧取（0，R）为起点，按顺时针方向绘制该1/4圆弧第二十一页，共四十八页。22Bresenham画圆算法如图所示，从当前点亮像素出发，按顺时针方向生成圆时，最佳逼近该圆的下一个像素只可能为H、D、V三像素之一。

H、D、V中距圆周边界距离最小者，即为所求的像素点。

图形软件

——圆的生成算法第二十二页，共四十八页。23Bresenham画圆算法H、D、V三点到圆心的距离平方与圆的半径平方差，即为H、D、V到圆弧距离的一种度量：

H=(x+1)2+y2-R2；D=(x+1)2+(y-1)2-R2；

V=x2+(y-1)2-R2；为了根据这些度量值可确定最佳像素点，首先，将H、D、V与理想圆弧的关系进行分类

图形软件

——圆的生成算法第二十三页，共四十八页。24Bresenham画圆算法如图存在以下五种情况：1）H、D、V全在圆内2）H在圆外，D、V在圆内3）D在圆上，H在圆外，V在圆内4）H、D在圆外，V在圆内5）H、D、V全在圆外

图形软件

——圆的生成算法HDV(x,y)12345第二十四页，共四十八页。25Bresenham画圆算法与Bresenham画线算法一样，按照上述不同类型，找出误差度量的递推公式，然后判别它的正、负性即可确定最佳逼近的像素点

当D<0,只可能为1或2的情况。为了确定是H还是D，可用如下判别式：

δHD=|H|-|D|δHD

≤0则应选H，否则选D

图形软件

——圆的生成算法第二十五页，共四十八页。26

Bresenham画圆算法

对于第2种情况：δHD=H+D

=(x+1)2+y2-R2+(x+1)2+(y-1)2-R2=2D+2y-1因为H>0，D<0，若D离圆周近的话则2D+2y-1>0，否则2D+2y-1≤0。对于第1种情况：∵y是x的单调递减函数∴H为下一点亮像素。另，此时H<0和D<0

H+D=2D+2y-1<0综上两种情况可得如下结论：

在D＜0时，若2（D+y)-1≤0，则取H，否则取D

图形软件

——圆的生成算法第二十六页，共四十八页。27Bresenham画圆算法当D＞0,只可能有4、5两种情况。且最佳像素点为D或V，可用如下判别式：

δDV=|D|-|V|当δDV≤0则应选D，否则选V。对于第4种情况：δDV=D+V（D＞0，V＜0）

=(x+1)2+(y-1)2-R2+(x)2+(y-1)2-R2=2(D-x)–1若2(D-x)–1＞0，则选V，否则选D。

图形软件

——圆的生成算法第二十七页，共四十八页。28

Bresenham画圆算法对于第5种情况：D，V都在圆外，显然V为所选像素。注意：∵D＞0，

V＞0

∴D+V=2(D-x)-1＞0综上两种情况可得如下结论：

在D＞0时，若2（D-x)-1≤0，则取D，否则取V当D=0此时D是最佳像素

图形软件

——圆的生成算法第二十八页，共四十八页。Bresenham画圆算法总结上述分析结果：当D＞0，若2(D-x)-1＞0，取D，否则取V当D＜0，若2(D+y)-1≤0，取H，否则取D当D=0，取D关键的问题就是计算DD=(x+1)2+(y-1)2-R2；采用增量法，获得D的计算公式

图形软件

——圆的生成算法第二十九页，共四十八页。30Bresenham画圆算法分三种情况：下一像素为H时H=(x’,y’)=(x+1,y)

Dk+1=((x+1)+1)2+(y-1)2-R2=(x+1)2+(y-1)2-R2+2(x+1)+1=Dk+2(x+1)+1

图形软件

——圆的生成算法第三十页，共四十八页。31Bresenham画圆算法下一像素为D时D=(x’,y’)=(x+1,y-1)Dk+1=((x+1)+1)2+((y-1)-1)2-R2=(x+1)2+(y-1)2-R2+2(x+1)-2(y-1)+1=Dk+2(x+1)-2(y-1)+2

图形软件

——圆的生成算法第三十一页，共四十八页。32Bresenham画圆算法下一像素为V时V=(x’,y’)=(x,y-1)Dk+1=(x+1)2+((y-1)-1)2-R2=(x+1)2+(y-1)2-R2-2(y-1)+1=D

k-2(y-1)+1

图形软件

——圆的生成算法第三十二页，共四十八页。33Bresenham画圆算法有了上述D的递推计算公式，还需计算出D的初值∵

圆弧的起点为（0，R）∴D的初值为：D=(0+1)2+(R-1)2-R2=2(1-R)

图形软件

——圆的生成算法第三十三页，共四十八页。34图形软件

——圆的生成算法中点画圆算法与Bresenham画圆算法一样，以单位间隔取样并在每个步长中确定离指定圆最近的像素位置对于给定半径r和圆心（xc，yc），可先给出计算中心在原点（0,0）的像素位置的算法，然后通过平移使每个计算出的（x，y）移动到其适当的屏幕位置利用圆的对称性，只须讨论1/8圆第三十四页，共四十八页。35图形软件

——圆的生成算法中点画圆算法为了应用中点圆算法，定义一个圆函数：

fcircle(x,y)=x2+y2-r2则任何点(x,y)的相对位置可由对圆函数符合的检测来决定: <0(x,y)位于圆边界内fcircle(x,y)=0(x,y)位于圆边界上 >0(x,y)位于圆边界外第三十五页，共四十八页。36图形软件

——圆的生成算法中点画圆算法假设用该算法计算出第k个点P(xk,yk)，下一步需要决定像素位置是A(xk+1,yk)，B(xk+1,yk-1)其中xk+1=xk+1A，B的中点M(xk+1,yk-0.5)MABP（Xk

，Yk

）第三十六页，共四十八页。37图形软件

——圆的生成算法中点画圆算法在M处决策参数：pk=fcircle(xk+1,yk-0.5)=xk+12+(yk-0.5)2-r2则:当pk<0，这个中点M在圆内，扫描线yk上的像素(xk+1,yk)更接近于圆边界，则下一点应取右边的点A(xk+1,yk)否则，中点M位于圆外或在边界上，我们选择扫描线yk-1上的像素B(xk+1,yk-1)pk+1=(xk+1+1)2+(yk+1-0.5)2-r237MABP（Xk

，Yk

）第三十七页，共四十八页。38图形软件

——圆的生成算法中点画圆算法递归表达式：pk+1=pk+2xk+1+(y2k+1-y2k)-(yk+1-yk)+1

其中:yk+1是yk(pk<0)或是yk-1(pk≥0)，这取决于pk的符号圆在起始位置(x0,y0)=(0,r)处求值就可得到初始决策参数：

p0=fcircle(1,r-0.5)=5/4–r第三十八页，共四十八页。39图形软件

——圆的生成算法中点画圆算法中点圆算法的算法表示：

p0=5/4–r xk+1=xk+1 yk+1=yk，pk+1=pk+2xk+1+1当pk<0 yk+1=yk-1，pk+1=pk+2xk+1+1-2yk+1当pk≥039MABP（Xk

，Yk

）第三十九页，共四十八页。40图形软件

——圆的生成算法中点画圆算法对于2xk+1和2yk+1本身又是一个增量表达式2xk+1增量始终为2而2yk+1增量为0(当pk<0)或-2(当pk≥0)，在起始位置(x0,y0)=(0,r)，2xk+1和2yk+1的初始值分别为0和2r第四十页，共四十八页。41图形软件

——圆的生成算法中点画圆算法步骤1.输入圆半径r和圆心(xc,yc),并得到圆心在原点的圆周上的第一点为:(x0,y0)=(0,r)2.计算决策参数的初始值：

p0=5/4–r3.在每个xk位置处，从k=0开始，完成下列检测：假如pk<0，中心在(0,0)的圆的下一个点为(xk+1,yk)，且

pk+1=pk+2xk+1+1 否则，圆的下一个点为(xk+1,yk-1)，且