直线和圆弧的生成算法

第3章直线和圆弧的生成算法3.1 直线图形的生成算法数学上的直线是没有宽度、由无数个点构成的集合，显然，光栅显示器只 能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个像素中， 确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作， 这个过程称为用显示器绘制直线或直线的扫描转换。由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽可能地快。本节我们介绍一个像素宽直线绘制的三个常用算法：数值微分法(DDA)、中点画线法和Bresenham算法。3.1.1 逐点比较法3.1.2 数值微分(DDA)法设过端点Po(xo , y0)、Pi(xi , yi)的直线段为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 DDALine(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 012345图3.1.1直线段的扫描转换注意：上述分析的算法仅适用于|k| <1的情形。在这种情况下，x每增加1,y最多增加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, 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)+c当d<0时，M在L(Q点)下方，取P2为下一个像素；当d>0时，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。若d<0时，则取右上方像素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 的初值 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, 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 ,xyd00110-321331-14255215012345图3.1.3中点画线法问题1：若上述算法往下取二步(i-2),则算法和像素的取法将变成怎样?问题2:与DDA法相比，中点法的优点是什么？动画演示：中点画线算法用中老离我方眩神榴转罐隹丝鬲立W，J和制(5,8)轮直我段d=F(W=F(xp+lJ yp+O. 5) (xp+1) +b (yp+0. 5)+ca=yO-yl=-2: lrxt-x0=5: d0=2*a+b=l:41-2=4:d2=2*(ab) =6Q-0取正右方焦素为下一个象素位置 水。取右上方象旗为卜 个象病位置3.1.4 Bresenham 算法Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。仍然 假定直线斜率在01之间，该方法类似于中点法，由一个误差项符号决定下一个 像素点。算法原理如下：过各行各列像素中心构造一组虚拟网格线。按直线从起 点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点 最近的像素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列的所求像素。如图2.1.4所示，设直线方程为yi+i=yi+k(xi+i-xi)+k。假设列坐标像素已 经确定为K,其行坐标为yio那么下一个像素的列坐标为xi+1,而行坐标要么 为yi,要么递增1为yi+1。是否增1取决于误差项d的值。误差项d的初值do = 0,x坐标每增加1, d的值相应递增直线的斜率值 k,即 = +匕一旦 d>1, 就把它减去1,这样保证d在0、1之间。当d0.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, y）的右上方像素（xi + 1, yi+1）;而当e<0时，取（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 ;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(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算法在计算直线斜率与误差项时用到小数与除法。可以改用 整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换：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*dy;i1(c 0) "T； C-C-2*dx;动画演示： Bresenham 画线算法:用外血友ffit方法扫播转操挂两支P0 (0.0) %用(5)的直裁版IJ一口 Ur 3Q(JT 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,对于圆外