西安电子科技大学《计算机图像显示技术》第11讲图形显示软件

计算机图形显示技术主讲徐青西安电子科技大学雷达信号处理国防科技重点实验室1第一页，共五十六页。第十一讲图形软件Bresenham画线算法圆的生成算法Bresenham画圆法中点画圆法区域填充算法扫描线填充算法边界填充算法2第二页，共五十六页。

图形软件

——Bresenham画线算法

AboutBresenhamE.JackBresenham——ProfessorofComputerSciencePh.D.,StanfordUniversity,1964MSIE,StanfordUniversity,1960BSEE,UniversityofNewMexico,1959Retiredfrom27yearsserviceatIBMasaSeniorTechnicalStaffMemberin1987.Havetaught10yearsatWinthrop.Holderoffivepatents.3第三页，共五十六页。图形软件

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

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

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

其中b=y1-k*x16第六页，共五十六页。图形软件

——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+17第七页，共五十六页。图形软件

——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）由于k不一定是整数，因此由(2)式求出的y也不一定是整数。所以要用最靠近y的整数yi来代替y假设直线上第i个像素坐标为(xi,yi)，那么，它的下一个点的像素点的可能位置为(xi+1,yi)或(xi+1,yi+1)。如图：8第八页，共五十六页。图形软件

——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

(3)d2=(yi+1)-y=(yi+1)-k(xi+1)-b(4)，这两个距离的差为：d1-d2=2k(xi+1)-2yi+2b-1(5)9第九页，共五十六页。图形软件

——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）根据（5）式，作如下讨论分析：当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)作为下一个直线像素点10第十页，共五十六页。图形软件

——Bresenham画线算法Bresenham画线算法若直线斜率k∈[0,1]且x2>x1的情况（1a象限）因此，利用（d1-d2）的符号就可以决定下一个像素点的选择然而含有变量xi、yi，不利于计算。为此，我们构造一个新的判别式：pi=x*(d1-d2)=2xiy-2yix+c（6）其中：x=(x2-x1)>0，因此pi与(d1-d2)符号相同；

y=y2-y1；数c=2y+x(2b-1)11第十一页，共五十六页。图形软件

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

假设直线上的初始端点恰好是其像素点的坐标，则将将x1,y1，和b代入式（6）中的xi,yi可到pi的初始值p1=2y-x（9）12第十二页，共五十六页。图形软件

——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时13第十三页，共五十六页。图形软件

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

——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；15第十五页，共五十六页。图形软件

——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；否则end16第十六页，共五十六页。图形软件

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

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

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

——Bresenham画线算法Bresenham画线算法例:分析从(0,0)到(5,3)的直线段19第十九页，共五十六页。图形软件

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

直角坐标法

(xxc)2+(yyc)2=r2由上式导出：

20第二十页，共五十六页。图形软件

——圆的生成算法⒈直角坐标法当但同时xxc从r到r作加1递增时，就可以求出对应的圆周点的y坐标由于有乘方和平方根运算，且都是浮点运算，算法效率不高。，这样求出的圆周上的点是不均匀的，

xxc接近R时，由于圆的斜率趋向于无穷大，使得圆周上有较大的间隙21第二十一页，共五十六页。图形软件

——圆的生成算法⒉

极坐标法假设利用圆周上一点（x,y）处的半径与x轴的夹角为θ,

则圆的极坐标方程为：x=xc+r·cosθ，y=yc+r·sinθ圆周上点的对称性，我们可求出圆上各点，此时自变量θ的取值范围是[0,45]度，以固定角度为步长来变化，可得到沿圆周等距离分布的一系列光点，但运算量大，也不被采用。22第二十二页，共五十六页。图形软件

——圆的生成算法AB极坐标法对称性（x,y）（y,x）（y,-x）（x,-y）（-x,y）（-y,x）（-y,-x）（-x,-y）45°直角坐标法画圆23第二十三页，共五十六页。图形软件

——圆的生成算法Bresenham画圆算法与Bresenham直线生成算法一样，其基本思想：利用判别变量来判断选择最近的像素，判别变量仅用加减和移位就可计算出来为讨论方便，仅考虑圆心在原点，半径为R的第一象限上的一段圆弧取（0，R）为起点，按顺时针方向绘制该1/4圆弧24第二十四页，共五十六页。Bresenham画圆算法

如图所示，从当前点亮像素出发，按顺时针方向生成圆时，最佳逼近该圆的下一个像素只可能为H、D、V三像素之一。

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

图形软件

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

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

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

图形软件

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

图形软件

——圆的生成算法27第二十七页，共五十六页。Bresenham画圆算法

与Bresenham画线算法一样，按照上述不同类型，找出误差度量的递推公式，然后判别它的正、负性即可确定最佳逼近的像素点

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

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

≤0则应选H，否则选D

图形软件

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

Bresenham画圆算法

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

=(x+1)2+y2-R2+(x+1)2+(y-1)2-R2=2D+2y-1对于第1种情况：∵y是x的单调递减函数∴H为下一点亮像素。（如图）另，此时H<0和D<0

H+D=2D+2y-1<0

综上两种情况可得如下结论：

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

图形软件

——圆的生成算法29第二十九页，共五十六页。Bresenham画圆算法

当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

图形软件

——圆的生成算法30第三十页，共五十六页。

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是最佳像素

图形软件

——圆的生成算法31第三十一页，共五十六页。Bresenham画圆算法总结上述分析结果：（如图）当D＞0，若2(D-x)-1＞0，取D，否则取V当D＜0，若2(D+y)-1≤0，取H，否则取D当D=0，取D关键的问题就是计算D

（见D的计算公式）采用增量法，获得D的计算公式

图形软件

——圆的生成算法32第三十二页，共五十六页。Bresenham画圆算法分三种情况：（如图）下一像素为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

图形软件

——圆的生成算法33第三十三页，共五十六页。Bresenham画圆算法下一像素为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

图形软件

——圆的生成算法34第三十四页，共五十六页。Bresenham画圆算法下一像素为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

图形软件

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

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

图形软件

——圆的生成算法36第三十六页，共五十六页。（x，y）H（x+1，y）D（x+1，y-1）V（x，y-1）(0,R)HDV(x,y)12345Figure2Figure3Figure1返回37第三十七页，共五十六页。图形软件

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

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

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

——圆的生成算法中点画圆算法假设用该算法计算出第k个点(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）40第四十页，共五十六页。图形软件

——圆的生成算法中点画圆算法在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-r241第四十一页，共五十六页。图形软件

——圆的生成算法中点画圆算法递归表达式：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–r42第四十二页，共五十六页。图形软件

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

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≥043第四十三页，共五十六页。图形软件

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

——圆的生成算法中点画圆算法步骤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)，且

pk+1=pk+2xk+1+1-2yk+1 其中：2xk+1=2xk+1，2yk+1=2yk-2

45第四十五页，共五十六页。图形软件

——圆的生成算法中点画圆算法4.确定在其它7个8分圆中的对称点5.将每个计算出的像素位置(x,y)移动到中心在(xc,yc)的圆路径上，并画坐标值：

x=xc+xy=yc+y6.重复步骤3到5，直至x≥y46第四十六页，共五十六页。图形软件

——区域填充算法区域填充是指在一个有界区域内填充某些颜色或图案该区域的边界可以是圆、多边形甚至任意曲线，区域内所有像素的颜色相同（称为实心区域），或呈现一定的规律（图案）我们后面讨论的都是实心区域的填充算法47第四十七页，共五十六页。图形软件

——区域填充算法扫描线填充算法扫描线算法是按扫描线顺序，计算扫