直线和圆弧的生成算法

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

2、R）,则直线段L的斜率为”也 要在显示器显示也 必须确定最佳逼近£的氟素集合口我们从 内一两L的起点Po的横坐标X0向L的终点Pi的横坐标xi步进，取步长=1（个像素），用L 的直线方程y=kx+b计算相应的y坐标，并取像素点（x,round（y）作为当前点的坐 标。因为：y+1= kxi+1+b=k1xi+b+ k x=yi+k x所以，当X =1;yi+i = y+ko也就是说，当x每递增1, y递增k(即直线斜率)。根据这个原理，我们可以写出DDA ( Digital Differential Analyzer )画线算法程序。DDA画线算法程序:void DDALine(in

3、t x0,int y0,int x1,int y1,int 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, int(y+0.5), color);y=y+k;注意：我们这里用整型变量color表示像素的颜色和灰度。举例：用DDA方法扫描转换连接两点P0 (0,0)和P1 (5,2)的直线段xint(y+0.5)y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5图3.1.1直线段的

4、扫描转换注意：上述分析的算法仅适用于|k|<1的情形。在这种情况下，x每增加1,y最多增加1。当|k| 1时，必须把x, y地位互换，y每增加1, x相应增加 1/k。在这个算法中，y与k必须用浮点数表示，而且每一步都要对y进行四舍五 入后取整，这使得它不利于硬件实现。动画演示：数值微分画线算法(DDA)用仍用方筑益柏转换盘盘两直 亚3G笈P (5,2)的去俵包O 一为起始点一为当前象亲点o 为终止点522.。| 0. 5Word资料3.1.3 中点画线法假定直线斜率k在01之间，当前像素点为(”,yp),则下一个像素点 有两种可选择点Pi (xp+1,yp)或P2 (xp+1,yp+1

5、 )。若Pi与沁的中点(xp+1,yp+0.5) 称为M, Q为理想直线与x=xp+1垂线的交点。当M在Q的下方时，则取P2应 为下一个像素点；当M在Q的上方时，则取Pi为下一个像素点。这就是中点画 线法的基本原理。图3.1.2中点画线法每步迭代涉及的像素和中点示意图下面讨论中点画线法的实现。过点(xo,y。)、(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(x

6、o+i, yp+0.5)= a(xp+i)+ b(yp+0.5)+ c当d<0时，M在L(Q点)下方，取8为下一个像素；当d>0时，M在L(Q点)上方，取Pi为下一个像素；当d=0时，选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+1, yp+1)0要判断再下一像素，则要计 算 d2=

7、 F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b，增量为 a+ b。画线从(xo,yo) 开始，d 的初值 do=F(xo+1, 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 x0,int y0,int x1, int y1,int color) int a, b, d1, d2, d, x,

8、y ；a=y0-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;d1=2*a=-4;d2=2*(a+b)=6

9、 ,xyd00110-321331-14255215图3.1.3中点画线法问题1:若上述算法往下取二步(i=2),则算法和像素的取法将变成怎样?问题2:与DDA法相比，中点法的优点是什么?动画演示：中点画线算法用中支诙假力俊扣盘抢排连接国直亚9G和制(52)的支修段d=F(M)=F (jp+1, yptJL 5) =a (sp+1 > +b (yp+0.5)+a a=y0-yl=-2: W1-j(O5; d0=2*a+b= 1 ;d1=2*a= ;d2=2*(a+b) =6 a以正石用象系为卜一个家靠位置一水电收右上方发黄力下，个象然他附3.1.4 Bresenham 算法Bresenh

10、am算法是计算机图形学领域使用最广泛的直线扫描转换算法。仍 然假定直线斜率在01之间，该方法类似于中点法，由一个误差项符号决定下 一个像素点。算法原理如下：过各行各列像素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点 最近的像素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列的所求像素。如图2.1.4所示，设直线方程为yi+产yi+k(x+xi)+k。假设列坐标像素已经 确定为x,其行坐标为yio那么下一个像素的列坐标为 x+1,而行坐标要么为V，要么递增1为yi+ 1。是否增1取决于误差项d

11、的值。误差项d的初值d0=0, x坐标每增加1, d的值相应递增直线的斜率值k,即=十七一旦d1,就 把它减去1,这样保证d在0、1之间。当d >0.5时，直线与垂线x=x+1交点 最接近于当前像素仅i, yi)的右上方像素(x+1, y+1);而当d<0.5时，更接近于 右方像素(x+1, y)。为方便计算，令e = d 0.5, e的初值为-0.5,增量为k。 当e0时，取当前像素(x, yi)的右上方像素(x+1, yi+1);而当e<0时，取仅i, yi)右方像素(xi+1, y)。图3.1.4 Bresenham算法所用误差项的几何含义O Bresenham画线算法

12、程序： void Bresenhamline (int x0,int y0,int x1, int y1,int 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+1 ； e=e+k;if (e 0) y+； e=e-1;举例：用Bresenham方法扫描转换连接两点P0 (0,0)和P1 (5,2)的直线段xye00-0.510-0.121-0.731-0

13、.342-0.952-0.5图 3.1.5 Bresenham 算法上述Bresenham算法在计算直线斜率与误差项时用到小数与除法。可以改 用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换： 2*e*dx。改进的Bresenham画线算法程序:void InterBresenhamline (int x0,int y0,int x1, int y1,int color) 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*

14、dy;if (e 0) y+; e=e-2*dx;动画演示： Bresenham 画线算法:用方眩扣相转稳屈曩愚鱼P0。.切备W (5)的直我期*d 0, 5, d+k, k-dv/dx»'户QHlr取与前兼索加在匕以朱春为下 个以意-为当前象素点一为，一个象素点O 为初始点o -为终止点1 0-U.5-0. JU " -o. 5 -o. 52 5 3-0.73 1-0. 731 20, 1-055 2-0.9-0. 5rep1 ay3.2 圆弧的扫描转换算法这一节我们来讨论圆弧的扫描转换算法。3.2.1 圆的特征圆被定义为到给定中心位置(xc,yc)距离为r的点集

15、。圆心位于原点的圆有 四条对称轴x=0,y=0,x=y和x=-y。若已知圆弧上一点(x,y),可以得到其关于四条对 称轴的其它7个点，这种性质称为圆的八对称性。因此，只要扫描转换八分之一 圆弧，就可以求出整个圆弧的像素集。显示圆弧上的八个对称点的算法：void CirclePoints(int x,int y,int 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);

16、drawpixel(-x,-y,color); drawpixel(-y,-x,color);3.2.2 中点画圆法如果我们构造函数F(x,y)=x2+y2-R2,则对于圆上的点有F(x,y)=0 ,对于圆外的点有F(x,y)>0,对于圆内的点F(x,y)<0 。与中点画线法一样,构造判别式：d= F(M)= F(xp+1,yp-0.5)=( xp+1)2+(yp-0.5)2- R2若d<0,则应取Pi为下一像素，而且再下一像素的判别式为：d= F(xp+2,yp-0.5)=( xp+2)2+(yp-0.5)2- R2=d+2xp+3若d冷，则应取P2为下一像素，而且下 一像

17、素的判别式为：d= F(xp+2,yp-1.5)=( xp+2)2+(yp-1.5)2- R2=d+2( xp- yp)+5我们这里讨论的第一个像素是(0,R),判别式d的初始值为：do=F(1,R-0.5)=1.25- R图3.2.1当前像素与下一像素的候选者中点画圆算法：MidPointCircle(int r int color) int x,y;float d;x=0; y=r; d=1.25-r;circlepoints (x,y,color);while(x<=y) if(d<0) d+=2*x+3;else d+=2*(x-y)+5; y-;x+;circlepoin

18、ts (x,y,color);为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。动画演示：中点画圆算法:圆的对称性假设已知小同心在原点的圜 上 点a, 丫）根据对称性可得 另外L个八分网上的对榔直.二:中点画圆算法判别式的构造考虑中心在原点，举独为R的四的第二个A 分圆.假定需坐标为心的赛素中.与该圈强 最近的禄素已定,为巴加那么，下一 1、。%冏瓢心近的象素只能是口豫常正右方 的Pl&p+If Vr）或右下方的P（Yp+l,昨一D两 者之一.构造函数：所以，沿正右方向,d的增量为2小十；，此时FM4时,M在囱外,总距离眦瓠 更近”则应取P九曾FOO=。时，Pi 与巴任取个：我们约定联IF检设M是内和匕的中点,即5) 那么.当FOOS时.M在做内,这说明巴 鹿总同菰更近.应取因作为下 奥素.构琏判别式为：介丹“尸四¥,+1,丁0.5)(片十1尸十(广。5)二炉若d<0,则应取P1为下一象素，而且再下一个象嚷的判别式为rf=>X/>+2f >-O.5)=(A)>+2)-+(匕“().5尸-/?工=+2勾43而若d”0,则P2是卜一象素，而且下一象素的判别式为二代加+2g".5尸(而十力十0/，3)二代 =J+(2x-+3)+(- 2)+