画直线算法幻灯片.ppt

第二讲 直线的生成,图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程步骤如下： 1、确定有关像素 2、用图形的颜色或其它属性，对像素进行写操作 对一维图形，若不考虑线宽，则用一个像素宽的直线来显示图形二维图形的光栅化，即区域的填充：确定像素集，填色或图案 任何图形的光栅化，必须显示在一个窗口内，否则不予显示即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪本讲内容,直线段扫描转换算法： 数值微分法DDA算法 中点画线法 Bresenham画线算法,直线段的扫描转换算法,直线的扫描转换: 确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作 在介绍三个常用算法前，先介绍一种最容易想到的算法： 直接计算法！,0 直接计算法,假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数 计算出斜率k=(y1-y0)/(x1-x0) , 在Y轴的截距b=y0-k*x0,,,,,,,,,,,(X i+1, kX i+1+b),(X i , Yi),(X i , Yi),,栅格交点表示象素点位置,直接计算法,这样一来，只要给定 x的值，根据解析式立即可以计算出对应的y值，然后输出(x,round(y)). 这种方法直观，但效率太低，因为每一步需要一次浮点乘法、一次浮点加法和一次舍入运算。

X i+1, kX i+1+b),(X i , Yi),(X i , Yi),1 数值微分法（ＤＤＡ）,假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数X i+1 ,Yi + k),(X i , Int(Yi +0.5)),(X i , Yi),数值微分(DDA)法,基本思想 已知过端点P0 (x0, y0), P1(x1, y1)的直线段L y=kx+b 直线斜率为 考虑当x从xixi+1时y的变化规律： 设x=xi+1- xi xi+1= xi+ x,数值微分(DDA)法,计算yi+1= kxi+1+b= k (xi+ x) +b = kxi+b+kx = yi+kx 当x =1; yi+1 = yi+k 即：当x每递增1，y递增k(即直线斜率)； 注意上述分析的算法仅适用于k ≤1的情形在这种情况下，x每增加1,y最多增加1 当 k 1时，必须把x，y地位互换,数值微分(DDA)法,增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法 DDA算法就是一个增量算法。

数值微分(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;  ,数值微分(DDA)法,例：画直线段P0(0,0)--P1(5,2) k=0.4 x y int(y+0.5) 0 0 0 0.4 0 0.8 1 3 1.2 1 4 1.6 2 5 2.0 2,数值微分(DDA)法,缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现2 中点画线法,原理：,假定直线斜率0K1，且已确定点亮象素点P（Xp ,Yp ）,则下一个与直线最接近的像素只能是P1点或P2点设M为中点，Q为交点 现需确定下一个点亮的象素中点画线法,当M在Q的下方- P2离直线更近更近-取P2 。

M在Q的上方- P1离直线更近更近-取P1 M与Q重合， P1、P2任取一点 问题：如何判断M与Q点的关系？,中点画线法,由常识知：若y=kx+b; F(x,y)=y-kx-b;则有,中点画线法,假设直线方程为：ax+by+c=0 (y=(-a/b)x-c/b) 通过两点不能唯一确定a,b,c, 取 a=y0-y1, b=x1-x0, c=x0y1-x1y0 F(x,y)=ax+by+c=b(y-(-a/b)x-c/b); 则有 ∴欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号中点画线法,构造判别式：d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 当d0，M在直线(Q点)上方，取右方P1； 当d=0，选P1或P2均可，约定取P1； 能否采用增量算法呢？,中点画线法,若d0 --M在直线上方-取P1; 此时再下一个象素的判别式为 d1=F(xp+2, yp+0.5) =a(xp+2)+b(yp+0.5)+c = a(xp +1)+b(yp +0.5)+c +a =d+a； 增量为a,中点画线法,若dM在直线下方-取P2; 此时再下一个象素的判别式为 d2= F(xp+2, yp+1.5) =a(xp+2)+b(yp+1.5)+c = a(xp +1)+b(yp +0.5)+c +a +b =d+a+b ； 增量为a＋b,中点画线法,画线从(x0, y0)开始，d的初值 d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a+0.5b = a+0.5b 由于只用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 (xx1) { if (d0) {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=2a+b=1 d1=2a=-4 d2=2(a+b)=6 i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 4 2 5,斜率不在[0,1]的直线的处理,设起点和终点分别为(x0,y0)和(x1,y1) 若k1 则(y0,x0)和(y1,x1)所确定的 直线斜率k€ [0,1]， 适用于前面讨论的情形。

对(y0,x0)和(y1,x1)所确定的 直线进行扫描转换， 每确定一组(x,y)，输出(y,x)斜率不在[0,1]的直线的处理,若-1k0 先对(x0,-y0)和(x1,-y1)所确定的 直线进行扫描转换， 每确定一组(x,y)，输出(x,-y)x0,y0),(x1,-y1),,,,,(x1,y1),,,,,(x0,-y0),斜率不在[0,1]的直线的处理,若k-1 对(-y0,x0)和(-y1,x1)所确定的 直线进行扫描转换， 每确定一组(x,y)， 输出(y,-x)x0,y0),(x1,-y1),,,,,,(x1,y1),,,,,(x,-y0),,,,(-y0,x0),(-y1,x1),3 Bresenham算法(教材上介绍的),假定直线段的0≤k≤1 基本原理：,Bresenham算法原理,误差项d的计算 d初=0， 每走一步：d=d+k 一旦y方向上走了一步，d=d-1,,算法步骤： 1.输入直线的两端点P0(x0,y0)和P1(x1,y1) 2.计算初始值△x、△y、d=0、x=x0、y=y0 3.绘制点(x,y) 4.d更新为d+k，判断d的值若d0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。

5.当直线没有画完时，重复步骤3和4否则结束改进1：令e=d-0.5,e初=-0.5， 每走一步有e=e+k if (e0) then e=e-1,算法步骤为： 1.输入直线的两端点P0(x0,y0)和P1(x1,y1) 2.计算初始值△x、△y、e=-0.5、x=x0、y=y0 3.绘制点(x,y) 4.e更新为e+k，判断e的符号若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y) 5.当直线没有画完时，重复步骤3和4否则结束改进2：用2e△x来替换e e初=-△x， 每走一步有e=e+2△y if (e0) then e=e-2△x,e=e+k e=e+△y/△x △x e= △x e+ △y e=-0.5 2e=-1,算法步骤： 1.输入直线的两端点P0(x0,y0)和P1(x1,y1) 2.计算初始值△x、△y、e=-△x、x=x0、y=y0 3.绘制点(x,y) 4.e更新为e+2△y，判断e的符号若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2△x；否则(x,y)更新为(x+1,y) 5.当直线没有画完时，重复步骤3和4。

否则结束Bresenham画线算法,BresenhamLine(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; { int x,y,dx,dy,e; dx = x1-x0; dy = y1-y0; e = -dx; x=x0; y=y0; for( i=0; i= 0) {e = e - 2*dx; y++; } } },举例：用Bresenham方法扫描转换连接 两点P0（0,0）和P1（5,2）的直线段x y e e0=-5; dx=5;dy=2 0 0 -1 1 0 3 (-7 ) 2 1 -3 3 1 1(-9) 4 2 -5 5 2 -1,Bresenham算法,Bresenham画线算法,在直线生成的算法中Bresenham算法是最有效的算法之一令 k=Δy/Δx，就0≤k≤1的情况来说明Bresenham算法由DDA算法可知： yi+1=yi+k (1) 由于k不一定是整数，由此式求出的yi也不一定是整数，因此要用坐标为（xi,yir）的象素来表示直线上的点，其中yir表示最靠近yi的整数设图中xi列上已用（xi,yir）作为表示直线的点，又设B点是直线上的点，其坐标为（xi+1,yi+1），显然下一个表示直线的点（ xi+1,yi+1,r）只能从图中的C或者D点中去选。

设A为CD边的中点 若B在A点上面则应取D点作为（ xi+1,yi+1,r），否则应取C点xi,Xi+1,Yi,r,Yi+1,r,C,D,B,,A,,,ε(x)的几何意义,为能确定B在A点上面或下面，令 ε(xi+1)=yi+1-yir-0.5 (2) 若B在A的下面，则有ε(xi+1)0 由图可知 yi+1,r=yir+1，若ε(xi+1)≥0 (3) yi+1,r=yir， 若ε(xi+1)≤0,Bresenham画线算法,由式（2）和式（3）可得到 ε(xi+2)=yi+2 - yi+1,r - 0.5 =yi+1 + k - yi+1,r - 0.5 （4） =yi+1 - yir -0.5 + k - 1,当ε(xi+1)≥0 =yi+1 - yir -0.5 + k, 当ε(xi。