画直线算法专业知识讲座市公开课金奖市赛课一等奖课件

第二讲直线生成图形扫描转换（光栅化）：确定一个像素集合，用于显示一个图形过程。步骤以下：1、确定相关像素2、用图形颜色或其它属性，对像素进行写操作。对一维图形，若不考虑线宽，则用一个像素宽直线来显示图形。二维图形光栅化，即区域填充：确定像素集，填色或图案。任何图形光栅化，必须显示在一个窗口内，不然不予显示。即确定一个图形哪些部分在窗口内，哪些在窗口外，即裁剪。 第1页本讲内容直线段扫描转换算法：数值微分法DDA算法中点画线法Bresenham画线算法第2页直线段扫描转换算法直线扫描转换:确定最正确迫近于该直线一组象素，而且按扫描线次序，对这些象素进行写操作。在介绍三个惯用算法前，先介绍一个最轻易想到算法：直接计算法！第3页0直接计算法

假定直线起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。计算出斜率k=(y1-y0)/(x1-x0),在Y轴截距b=y0-k*x0

(Xi+1,kXi+1+b)(Xi,Yi)(Xi,Yi)栅格交点表示象素点位置。。。。第4页

直接计算法

这么一来，只要给定x值，依据解析式马上能够计算出对应y值，然后输出(x,round(y)).

这种方法直观，但效率太低，因为每一步需要一次浮点乘法、一次浮点加法和一次舍入运算。(Xi+1,kXi+1+b)(Xi,Yi)(Xi,Yi)。。。。第5页1数值微分法（ＤＤＡ）

假定直线起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。

(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)。。。。第6页数值微分(DDA)法基本思想已知过端点P0(x0,y0),P1(x1,y1)直线段Ly=kx+b直线斜率为考虑当x从xixi+1时y改变规律：设x=xi+1-xixi+1=xi+x第7页数值微分(DDA)法计算yi+1=kxi+1+b=k (xi+x)+b =kxi+b+kx =yi+kx当x=1; yi+1=yi+k即：当x每递增1，y递增k(即直线斜率)；注意上述分析算法仅适合用于k

≤1情形。在这种情况下，x每增加1,y最多增加1。当k

1时，必须把x，y地位交换第8页数值微分(DDA)法增量算法：在一个迭代算法中，假如每一步x、y值是用前一步值加上一个增量来取得，则称为增量算法。DDA算法就是一个增量算法。第9页数值微分(DDA)法voidDDALine(intx0,inty0,intx1,inty1,intcolor)

intx； floatdx,dy,y,k; dx,=x1-x0,dy=y1-y0; k=dy/dx,y=y0; for(x=x0;xx1,x++)

drawpixel(x,int(y+0.5),color); y=y+k;

第10页数值微分(DDA)法例：画直线段P0(0,0)--P1(5,2)k=0.4xyint(y+0.5) 0 0 0 0.4 0 0.81 3 1.21 4 1.6 2 5 2.0 2 第11页数值微分(DDA)法缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。第12页2中点画线法原理：假定直线斜率0<K<1，且已确定点亮象素点P（Xp

,Yp

）,则下一个与直线最靠近像素只能是P1点或P2点。设M为中点，Q为交点现需确定下一个点亮象素。第13页中点画线法当M在Q下方->P2离直线更近更近->取P2。M在Q上方->P1离直线更近更近->取P1M与Q重合，P1、P2任取一点。问题：怎样判断M与Q点关系？第14页中点画线法由常识知：若y=kx+b;F(x,y)=y-kx-b;则有第15页中点画线法假设直线方程为：ax+by+c=0(y=(-a/b)x-c/b)经过两点不能唯一确定a,b,c,取a=y0-y1,b=x1-x0,c=x0y1-x1y0F(x,y)=ax+by+c=b(y-(-a/b)x-c/b);则有∴欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检验它符号。第16页中点画线法结构判别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d<0，M在直线(Q点)下方，取右上方P2；当d>0，M在直线(Q点)上方，取右方P1；当d=0，选P1或P2均可，约定取P1；能否采取增量算法呢？第17页中点画线法若d0---->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第18页中点画线法若d<0------>M在直线下方->取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第19页中点画线法画线从(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来摆脱小数，提升效率。第20页中点画线法voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,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*/}/*midPointLine*/第21页中点画线法例：用中点画线法P0(0,0)P1(5,2)a=y0-y1=-2b=x1-x0=5d0=2a+b=1d1=2a=-4d2=2(a+b)=6i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 4 2 5

第22页斜率不在[0,1]直线处理设起点和终点分别为(x0,y0)和(x1,y1)若k>1则(y0,x0)和(y1,x1)所确定直线斜率k€[0,1]，适合用于前面讨论情形。对(y0,x0)和(y1,x1)所确定直线进行扫描转换，每确定一组(x,y)，输出(y,x)。(x0,y0)(y1,x1)(x1,y1)(y0,x0)第23页斜率不在[0,1]直线处理若-1<k<0先对(x0,-y0)和(x1,-y1)所确定直线进行扫描转换，每确定一组(x,y)，输出(x,-y)。(x0,y0)(x1,-y1)(x1,y1)(x0,-y0)第24页斜率不在[0,1]直线处理若k<-1对(-y0,x0)和(-y1,x1)所确定直线进行扫描转换，每确定一组(x,y)，输出(y,-x)。(x0,y0)(x1,-y1)(x1,y1)(x,-y0)(-y0,x0)(-y1,x1)第25页3Bresenham算法(教材上介绍)假定直线段0≤k≤1基本原理：Bresenham算法原理第26页误差项d计算d初=0，每走一步：d=d+k一旦y方向上走了一步，d=d-1第27页算法步骤：1.输入直线两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、d=0、x=x0、y=y0。3.绘制点(x,y)。4.d更新为d+k，判断d值。若d>0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；不然(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。不然结束。第28页改进1：令e=d-0.5e初=-0.5，每走一步有e=e+k。if(e>0)thene=e-1第29页算法步骤为：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符号。若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；不然(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。不然结束。第30页改进2：用2e△x来替换ee初=-△x，每走一步有e=e+2△y。if(e>0)thene=e-2△xe=e+ke=e+△y/△x△xe=△xe+△ye=-0.52e=-1第31页算法步骤：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符号。若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2△x；不然(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。不然结束。第32页Bresenham画线算法BresenhamLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{intx,y,dx,dy,e;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;if(e>=0){e=e-2*dx;y++;}}}第33页举例：用Bresenham方法扫描转换连接

两点P0（0,0）和P1（5,2）直线段。

xyee0=-5;dx=5;dy=200-1103(-7)21-3311(-9)42-5

52-1Bresenham算法第34页Bresenham画线算法

在直线生成算法中Bresenham算法是最有效算法之一。令k=Δy/Δx，就0≤k≤1情况来说明Bresenham算法。由DDA算法可知：yi+1=yi+k(1)因为k不一定是整数，由此式求出yi也不一定是整数，所以要用坐标为（xi,yir）象素来表示直线上点，其中yir表示最靠近yi整数。第35页

设图中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点。xiXi+1Yi,rYi+1,rCDBAε(x)几何意义为能确定B在A点上面或下面，令ε(xi+1)=yi+1-yir-0.5(2)若B在A下面，则有ε(xi+1)<0，反之，则ε(xi+1)>0。由图可知yi+1,r=yir+1，若ε(xi+1)≥0(3)yi+1,r=yir，若ε(xi+1)≤0第36页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+1)≤0ε(xi+2)=ε(xi+1)+k-1,当ε(xi+1)≥0ε(xi+2)=ε(xi+1)+k,当ε(xi+1)≤0由式（1）和式（2）可得到ε(x1)=y0+1–y0r-0.5=y1–y0-0.5=k-0.5(5)第37页程序以下：

BresenhamLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{intx,y,dx,dy;floatk,e;dx=x1-x0;dy=y1-y0;k=dy/dx;e=k-0.5;x=x0;y=y0;drawpixel(x,y,color);for(i=1;i<=dx;i++){x++;if(e>0){e=e-1;y++;}drawpixel(x,y,color);e=e+k;}}第38页程序以下：

BresenhamLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{intx,y,dx,dy;floatk,e;