《直线和圆弧的生成算法》由会员分享，可在线阅读，更多相关《直线和圆弧的生成算法（14页珍藏版）》请在金锄头文库上搜索。
1、第3章直线和圆弧的生成算法3.1 直线图形的生成算法数学上的直线是没有宽度、由无数个点构成的集合，显然，光栅显示器只 能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个像素中， 确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作， 这个过程称为用显示器绘制直线或直线的扫描转换。由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽可能地快。本节我们介绍一个像素宽直线绘制的三个常用算法：数值微分法(DDA)、中点画线法和Bresenham算法。3.1.1 逐点比较法3.1.2 数值微分(DDA)法设过端点Po(xo , y0)、Pi(xi , yi)的直线段
2、为L( Po , Pi),则直线段L的斜率为此=21二电。要在显示器显示L,必须确定最佳逼近的象素集合。我们从 演一坛L的起点Po的横坐标xo向L的终点Pi的横坐标xi步进，取步长=1(个像素)，用L的直线方程y=kx+b计算相应的y坐标，并取像素点(x,round( y)作为当前点的坐标。因为：y+1= kxi+i+b=kixi+b+Hx=yi+k x所以，当Ax =1; yi+i = yi+ko也就是说，当x每递增1, y递增k(即直线斜 率)。根据这个原理，我们可以写出 DDA (Digital Differential Analyzer)画线算 法程序。DDA画线算法程序：void D
3、DALine(int 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.5241卜1
4、012345图3.1.1直线段的扫描转换注意：上述分析的算法仅适用于|k| 1时,必须把x, y地位互换,y每增加1, x相应增加 1/k。在这个算法中，y与k必须用浮点数表示，而且每一步都要对 y进行四舍五 入后取整，这使得它不利于硬件实现。动画演示：数值微分画线算法(DDA用血?方位制搐转挽遵接前点PO 9G和川(5.2)的直俵里一为当前象素点o 一为终止点O 为起始点3.1.3 中点画线法假定直线斜率k在01之间，当前像素点为(xp,yp),则下一个像素点 有两种可选择点 Pi(xp+1,yp)或 P2(xp+1,yp+1)。若 Pi 与 P2 的中点(Xp+1,yp+0.5) 称为M,
5、 Q为理想直线与x=xp+1垂线的交点。当M在Q的下方时，则取P2应 为下一个像素点；当M在Q的上方时，则取Pi为下一个像素点。这就是中点画 线法的基本原理。1知图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+i, yp+0.5)=a(xp+i)+b(yp+0.5
6、)+c当d0时，M在L(Q点)上方，取Pi为下一个像素；当d=0时，选Pi或P2均可，约定取Pi为下一个像素； 注意到d是xp, yp的线性函数，可采用增量计算，提高运算效率。若当前像素处于d2情况，则取正右方像素Pi(xp+i, yp),要判下一个像素 位置，应计算 di=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a,增量为 a。若d0时，则取右上方像素P2(xp+i, yp+i)。要判断再下一像素，则要计 算 d2= F(xp+2, yp+i.5)=a(xp+2)+b(yp+i.5)+c=d+a+b ,增量为 a+b。画线从(xo, yo) 开始，d 的初值
7、do=F(xo+i, yo+O.5)=F(xo, yo)+a+O.5b,因 F(xo, yo)=O,所以 do=a+0.5bo由于我们使用的只是d的符号，而且d的增量都是整数，只是初始值包含小数。因此，我们可以用2d代替d来摆脱小数，写出仅包含整数运算的算法 程序。中点画线算法程序：void Midpoint Line (int x0,int y0,int x1, int y1,int color) int a, b, d1, d2, d, x, 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,
8、 color);while (xx1) if (d1, 就把它减去1,这样保证d在0、1之间。当d0.5时，直线与垂线x=xi+ 1交点 最接近于当前像素(xi, yi)的右上方像素(xi+1, yi+1);而当d0时，取当前像素（Xi, y）的右上方像素（xi + 1, yi+1）;而当e0时，取（Xi, yi）右方像素（xi+1, yi） o图3.1.4 Bresenham算法所用误差项的几何含义O Bresenham画线算法程序：void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy ;fl
9、oat k, e;dx = x1-x0 ； dy = y1- y0 ； k=dy/dx ；e=-0.5; x=x0,; y=y0;for (i=0 ； idx ； i+) drawpixel (x, y, color);x=x+1 ； e=e+k;if(c 0) y+； e=e-1;举例：用Bresenham方法扫描转换连接两点P0 (0,0)和P1 (5,2)的直线 段。xye00-0.510-0.121-0.7131-0.342-0.952-0.5图 3.1.5 Bresenham算法上述Bresenham算法在计算直线斜率与误差项时用到小数与除法。可以改用 整数以避免除法。由于算法中只用
10、到误差项的符号，因此可作如下替换：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; idx; i+)drawpixel (x, y, color);x+ ； e=e+2*dy;i1(c 0) T； C-C-2*dx;动画演示： Bresenham 画线算法:用外血友ffit方法扫播转操挂两支P0 (0.0) %用(5)的直裁版IJ一口 Ur 3Q(JT
11、HR-C1W Q A)”，/，己 .。一o 一为当前象素点 一为卜一个象素点O 一为初始点O 一为终止点rephtv3.2 圆弧的扫描转换算法这一节我们来讨论圆弧的扫描转换算法。3.2.1 圆的特征圆被定义为到给定中心位置(xc,yc)距离为r的点集。圆心位于原点的圆 有四条对称轴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);drawpixel(-x,-y,color); drawpixel(-y,-x,color);3.2.2 中点画圆法如果我们构造函数F(x,y)=x2+y2-R2,则对于圆上的点有F(x,y)=0,对于圆外
