直线和圆弧的生成算法

1、第3章直线和圆弧的生成算法3.1直线图形的生成算法数学上的直线是没有宽度、由无数个点构成的集合，显然，光栅显示器只 能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个像素中, 确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作, 这个过程称为用显示器绘制直线或直线的扫描转换。由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽可能地快。本节我们介绍一个像素宽直线绘制的三个常用算法：数值微分法(DDA)、中点画线法和Bresenham算法。3.1.1逐点比较法3.1.2数值微分(DDA)法设过端点Po(xo ,yo)、Pi(xi ,yi)的直线段为L( P

2、o , Pi)，则直线段L的斜 率为21二2 要在显示盎显示L,必须确定最佳逼近厶的象素集合。我们从L的起点Po的横坐标xo向L的终点Pi的横坐标xi步进，取步长=1(个像素)，用L的直线方程y=kx+b计算相应的y坐标，并取像素点(x,round( y)作为当前点 的坐标。因为：y+1= kxi+i+b=kixi+b+k=x=yi+k x所以，当Ax =1; y+i = yi+k。也就是说，当x每递增1, y递增k(即直线斜 率)。根据这个原理，我们可以写出 DDA (Digital Differential Analyzer )画线算 法程序。DDA画线算法程序：void DDALi ne

3、(int x0,i nt yO,i nt x1,i nt y1,i nt color) int x ；float dx, dy, y, k ；dx = x1-x0 ； dy=y1-y0 ；k=dy/dx, ； y=y0 ；for (x=x0 ； x< x1 ； x+) drawpixel (x, i nt(y+0.5), color);y=y+k;注意：我们这里用整型变量color表示像素的颜色和灰度。举例：用DDA方法扫描转换连接两点P0( 0,0)和P1(5,2)的直线段。xin t(y+0.5)y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5

4、图3.1.1直线段的扫描转换注意：上述分析的算法仅适用于|k| < 1的情形。在这种情况下，x每增 加1,y最多增加1。当|k| 1时，必须把x，y地位互换，y每增加1, x相应增加 1/k。在这个算法中，y与k必须用浮点数表示，而且每一步都要对 y进行四舍五 入后取整，这使得它不利于硬件实现。动画演示：数值微分画线算法(DDAP0 (0.0)牝刊(5f2)的直钱限-为洋前鏡索点O 一为终止点O 为起始点replavL.*-J3.1.3中点画线法假定直线斜率k在01之间，当前像素点为(xp,yp)，则下一个像素点 有两种可选择点 Pi( xp+1,yp)或 P2(xp+1,yp+1)。若

5、 Pi 与 P2 的中点(Xp+1,yp+0.5) 称为M， Q为理想直线与x=xp+1垂线的交点。当M在Q的下方时，则取P2应 为下一个像素点；当M在Q的上方时，则取Pi为下一个像素点。这就是中点画 线法的基本原理。图3.1.2中点画线法每步迭代涉及的像素和中点示意图下面讨论中点画线法的实现。过点(xo,yo)、(xi, yi)的直线段L的方程式 为 F(x, y)=ax+by+c= 0，其中,a=yo-yi, b=xi-xo, c=xoyi-xiyo，欲判断中点 M 在 Q 点的上方还是下方，只要把 M代入F (x，y)，并判断它的符号即可。为此，我 们构造判别式：d=F(M)=F(xp+

6、i, yp+o.5)=a(xp+i)+b(yp+o.5)+c当d<o时，M在L(Q点)下方，取P2为下一个像素； 当d>o时，M在L(Q点)上方，取Pi为下一个像素； 当d=o时，选Pi或P2均可，约定取Pi为下一个像素； 注意到d是xp, yp的线性函数，可采用增量计算，提高运算效率。若当前像素处于d_0情况，则取正右方像素Pi(xp+1, yp),要判下一个像素 位置，应计算 di=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a,增量为 a。若d<0时，则取右上方像素P2(xp+i, yp+i)。要判断再下一像素，则要计 算 d2= F(xp+

7、2, yp+i.5)=a(xp+2)+b(yp+i.5)+c=d+a+b，增量为 a+ b。画线从(xo, yo) 开始，d 的初值 do=F(xo+i, yo+o.5)=F(xo, yo)+a+o.5b，因 F(xo, yo)=o，所以 do=a+o.5b。由于我们使用的只是d的符号，而且d的增量都是整数，只是初始值包 含小数。因此，我们可以用2d代替d来摆脱小数，写出仅包含整数运算的算法 程序。中点画线算法程序:void Midpoint Line (int xO,int yO,int x1, int y1,int color) int a, b, d1, d2, d, x, y；a=y0

8、-y1;b=x1-x0 ； d=2*a+b ；d1=2*a； d2=2* (a+b)；x=x0; y=y0;drawpixel(x, y, color);while (x<x1) if (d<0)x+ ; y+;d+=d2; else x+ ；d+=d1;drawpixel (x, y, color); /* while */ /* mid PointLine */举例：用中点画线方法扫描转换连接两点P0 (0,0)和P1 (5,2)的直线段a=y0-y1=-2; b=x1-x0=5; d0=2*a+b=1;d 仁 2*a=-4;d2=2*(a+b)=6 ,1 IA 1012345

9、xyd00110-321331-14255215图3.1.3中点画线法问题1:若上述算法往下取二步，则算法和像素的取法将变成怎样?问题2:与DDA法相比，中点法的优点是什么？动画演示：中点画线算法用申点曲筱方诫扣描矗撫隹找鬲 更R (0)和列G刃的直依段d=F(W =F(xp+l, yp+O. 5) =a(xp+1) +b(yp+O. 5) +cfl.=yOy 12; ljx Ix051 <10=2*44+1)=1: <12=2* (a+b) 6dXJ取正右方鎭盍肯下一个星泰位置 虫0取右上方象素为下个象素林岂x yd012345-3 I -1 “为当前象素点 一为卜一个象秦点o

10、"沟起始点o "为终止点卩21_152 153.1.4 Bresenham 算法Brese nham算法是计算机图形学领域使用最广泛的直线扫描转换算法。仍然 假定直线斜率在01之间，该方法类似于中点法，由一个误差项符号决定下一个 像素点。算法原理如下：过各行各列像素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点 最近的像素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列的所求像素。如图2.1.4所示，设直线方程为yi+i=yi+k(xi+i-xi)+k。假设列坐标像素已 经

11、确定为Xi，其行坐标为yi。那么下一个像素的列坐标为 人+ 1,而行坐标要么 为y,要么递增1为yi+1。是否增1取决于误差项d的值。误差项d的初值do =0, x坐标每增加1,d的值相应递增直线的斜率值 k,即d = d+ k。一旦 d> 1, 就把它减去1,这样保证d在0、1之间。当d>0.5时，直线与垂线x=Xi+ 1交点 最接近于当前像素(Xi, yi)的右上方像素(Xi+ 1, yi + 1);而当d<0.5时，更接近于右方像素(x + 1, yi)。为方便计算，令e= d 0.5, e的初值为0.5,增量为k当e>0时，取当前像素(Xi, yi)的右上方像素

12、(Xi + 1, yi+ 1);而当e<0时，取(Xi, yi)右方像素(xi+ 1, yi)。图3.1.4 Bresenham算法所用误差项的几何含义O Brese nham画线算法程序: void Brese nhamli ne (int x0,i nt y0,i nt x1, int y1,i nt color) int x, y, dx, dy ;float k, e;dx = x1-x0 ； dy = y1- y0 ； k=dy/dx ；e=-0.5;x=x0,; y=y0;for (i=0 ； i<dx ； i+) drawpixel (x, y, color);x=x

13、+1 ； e=e+k;if(c 0) y+ ；e=e-1;举例：用Bresenham方法扫描转换连接两点P0 (0,0)和P1 (5,2)的直线 段。xye00-0.510-0.121-0.7:31-0.342-0.9:52-0.5图 3.1.5 Bresenham算法可以改用2*e*dx 。上述Bresenham算法在计算直线斜率与误差项时用到小数与除法。整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换:改进的Bresenham画线算法程序：void In terBrese nhamli ne (int xO,i nt yO,i nt x1, int y1,i nt color

14、) dx = x1-x0, ； dy = y1- y0,； e=-dx;x=x0 ；y=y0;for (i=0; i<dx; i+)drawpixel (x, y, color);x+ ；e=e+2*dy;0)汁七 c-c-2*dx;动画演示： Bresenham 画线算法:用氐购C紡w方试扣描希筷直產鬲靈P0 (0.0)知存(5亡)袒克藏醍£ -(J u. jj> 口口14 jQW QJlie -： H. ； ' :.S'r； :： ;, - '. M 卜 % 彳x ye0 00.50- 5o 一为当前象素点 一为卜一个象爲点O 一为初始点O 一

15、为终止点3 11 20. 1-0.95 2-0.9-0. 52 I |山3 |67|rephtvL.厂3.2圆弧的扫描转换算法这一节我们来讨论圆弧的扫描转换算法。3.2.1圆的特征圆被定义为到给定中心位置(Xc,yc)距离为r的点集。圆心位于原点的圆 有四条对称轴x=O,y=O,x=y和x=-y。若已知圆弧上一点(x,y),可以得到其关于四条 对称轴的其它7个点，这种性质称为圆的八对称性。因此，只要扫描转换八分之 一圆弧，就可以求出整个圆弧的像素集。显示圆弧上的八个对称点的算法：void CirclePoi nts(i nt x,i nt y,i nt color) drawpixel(x,y

16、,color); drawpixel(y,x,color);drawpixel(-x,y,color); drawpixel(y,-x,color);drawpixel(x,-y,color); drawpixel(-y,x,color);drawpixel(-x,-y,color); drawpixel(-y,-x,color);3.2.2中点画圆法如果我们构造函数F(x,y)=x2+y2-R2,则对于圆上的点有F(x,y)=O，对于圆外 的点有F(x,y)>0，对于圆内的点F(x,y)<0。与中点画线法一样，构造判别式:2 2 2d=F(M)=F(Xp+1,yp-0.5)=(X

17、p+1)2+(yp-0.5)2-R2若d<0,则应取Pi为下一像素，而且再下一像素的判别式为：2 2 2d=F(xp+2,yp-0.5)=(Xp+2) +(yp-0.5) -R =d+2xp+3若d>0则应取P2为下一像素，而且下一像素的判别式为：2 2 2d=F(xp+2,yp-1.5)=(Xp+2) +(yp-1.5) -R =d+2(xp-yp)+5我们这里讨论的第一个像素是(0,R)，判别式d的初始值为：图3.2.1当前像素与下一像素的候选者中点画圆算法：MidPointCircle(int r int color) int x,y;float d;x=0; y=r; d=

18、1.25-r;circlepo ints (x,y,color);while(x<=y) if(d<0)d+=2*x+3;else d+=2*(x-y)+5; y-;x+;circlepo ints (x,y,color);为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数， 将 乘法运算改成加法运算，即仅用整数实现中点画圆法。动画演示：中点画圆算法:圆的对称性假设已知一牛岡七在原点的國 上一点（叫刃根据对称性可得 >!外七6八分呦上的对称点.中点画圆算法判别式的构造考虑中心在厚点，半轻为R的国的第二个八 分园.假定R燮标为咖的象養中.与谏岡弧 毘近的敦索已定、沟卩饭卩,珈几 那么.下一 牛与近的象索只能址F麻#iE右方 的Pl（Xp+1yp）或右下方的P?（xp+1, yp1）两 者构造的数:F(xt y)=x:>+y2-R2所以，沿正右方向,的增量为2时3。假设M是Pi和P?的中点.即M=(xp+L yp-O. 5) 那么,SFOOW, M在跑内这说明Pl