《直线和圆弧的生成算法.docx》由会员分享，可在线阅读，更多相关《直线和圆弧的生成算法.docx（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; i0,对于圆内的点F(x,y)0。与中点画线法一样,构造判别式：d=F(M)=F(xp+1,yp-0.5)=(Xp+1)2+(yp-0.5)2-R2若dQ则应取P2为下一像素，而且下一像素的判别式为：d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R
11、2=d+2(xp-yp)+5我们这里讨论的第一个像素是(0,R),判别式d的初始值为：do=F(1,R-0.5)=1.25-Rp二x)图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+y2-R2所以,沿正右方向,d的增量为2为,+3。假设M是Pi和P2的中点,即yr0. 5)么，当尸(100时,M在圆外,Pa距离圆弧 更近，则应取P?.当尸(M)=0时,Pi 与P?任取一个；
12、我们约定取内。而若d=0,则P2是下一象素，而口下一象素的判别式为 d=F(Xp+2jp- /. 5)=(4+2)2+。 /. 5)2公 =d+(2x0+3)+(- 2j/+2)所以，沿右下方向,判别式d的增量为2Gk)+5。三：用中点画圆算法生成半径为10的圆万i。，10）顺时针地确定乙最，女圆弧的软素用歹第个曾累为已知P1 (0.10)第二个宝东，d=-5.750, P2(lt10)第三个象素,d= 0.750, 第五个徐素，第2 750 第六个毂索，（18. 250, 第匕个象案,d=5. 250, 第八个象素，d=6.25.利用网的对称性通过系列的简单.反射变换得到其它部分的圆瓠P4(3J0)P*4,9)P6(5,9) 出(6.8) Ps(7,7)replay