lesson03-直线生成算法市公开课特等奖市赛课微课一等奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,LESSON 03,基本图形生成算法,第1页,基本图形生成算法,总体目标：,掌握二维图形学基本思想，了解二维图形生成基本原理,掌握直线段,生成算法,、,反走样算法,。,掌握,圆弧生成及线形处理,掌握字符生成,基本思想,第2页,基本概念,光栅显示器上显示图形，称之为,光栅图形,。,确定最正确迫近图形象素集合，并用指定颜色和灰度设置象素过程称为,图形扫描转换或光栅化。,二维图形光栅化必须确定区域对应象素集，将各个象素设置成指定颜色和灰度，也称之为,区域填充。,在光栅图形中，非水平和垂直直线用象素集合表示时，会呈锯齿状，这种现象称之为,走样,(aliasing)；用于降低或消除走样技术称为,反走样,(antialiasing)。,第3页,2.1 直线生成 算法概述,在计算机产生图形中，用到大量直线，画好直线是非常有意义，其普通准则是：,线条应该显得笔直：由连续点组成直线要显示在离散网格平面上，一定会有不经过网格点，如左下列图。在这种情况下，必须选择靠近直线网格点来迫近这条直线。若选择好，线就显得较直；不然就会较弯曲，如右下列图。,第4页,2.1 直线生成 算法概述,直线端点位置应该准确：画出线段假如不准确，往往会使两条线之间不能很好镶接，如右图。,直线浓度应该均匀：线段浓度与单位线段中所显示点数成正比。要保持线段浓度均匀端点应该等距分布。只有严格平行和成45线才能做到。,第5页,2.1 直线生成 算法概述,直线浓度应该与线段长度和斜率无关：要取得均匀线段浓度，应该保持每单位长度点数是个常数。普通，采取线段近似长度，以及生成直线算法，使在线段近似长度范围内保持线段浓度均匀。,显示线段速度应快：生成直线可用软件和硬件来实现，普通情况下，硬件要比软件实现得快。,第6页,2.1 直线生成 算法概述,直线惯用生成算法,数值微分(DDA：,Digital Differential Analyzer,)法,中点画线法,Bresenham算法,第7页,2.1.1 直线DDA 算法,直线微分方程表示为：dx/dy=x/y设直线斜率小于等于1，起点坐标为(x,a,y,a,)，终点坐标为(x,b,y,b,)，则方程求解步骤分为：x,0,=x,a,+0.5，x,n,=x,n-1,+1y,0,=y,a,+0.5，y,n,=y,n-1,+y/x其中：x=x,b,-x,a,，y=y,b,-y,a,上述解表示x方向积分步长为1，y方向增量为y/x。,y,n-1,y,x,y,n,x,n-1,x,n,y/x,第8页,2.1.1 直线DDA 算法,x,y,n-1,y,y,n,x,n-1,x,n,y/x,因为屏幕上坐标为整数坐标，则真正作为输出显示为：y,输出,=trunc(y,n,)，其中函数trunc()是指舍尾正数。所以y,输出,和y,n,之间量化误差最大为1。为了改进这方面误差，使y,0,初值增加0.5,使量化误差在(-0.5,0.5)范围之间。同理，若直线斜率大于1，则上述方程求解步骤可分为：x,0,=x,a,+0.5，x,n,=x,n-1,+x/y，y,0,=y,a,+0.5，y,n,=y,n-1,+1，其中x，y意义同上。上述解表示y方向积分步长为1，x方向增量为x/y,其它同上。,第9页,DDA,直线生成算法描述,if|x,b,-x,a,|y,b,-y,a,|then计算直线在y方向上增量：length=|y,b,-y,a,|,else 计算直线在x方向上增量：length=|x,b,-x,a,|,计算x方向单位增量：dx=(x,b,-x,a,)/length,计算y方向单位增量：dy=(y,b,-y,a,)/length,置初值：x=x,a,+0.5，y=y,a,+0.5,for i=1 to length do begin,输出点(trunc(x),trunc(y),计算下一个点坐标 x=x+dx，y=y+dy end,end of algorithm,第10页,DDA,直线生成算法C描述,Void lineDDA(int xa,int ya,int xb,int yb),int dx=xb-xa,dy=yb-ya,steps,k;,float xIncrement,yIncrement,x=xa,y=ya;,if(abs(dx)abs(dy)steps=abs(dx);,else steps=abs(dy);,xIncrement=dx/(float)steps;,yIncrement=dy/(float)steps;,setPixel(round(x),round(y);,for(k=0;ksteps;k+),x+=xIncrement;,y+=yIncrement;,setPixel(round(x),round(y);,动画演示算法,第11页,DDA直线生成算法小结,优点,：在同一坐标上,不可能连续停留两次。,缺点,：在本算法中，开始需要执行一个除法y/x 或 x/y来确定增量，这么用硬件来实现比较复杂和昂贵，用软件实现相对轻易些，但效率较低。,第12页,2.1.2中点画线法,假定直线斜率,k,在0,1之间，当前象素点为,（,x,p,y,p,）,，则下一个象素点有两种可选择点,P,1,（,x,p,+1,y,p,）或,P,2,（,x,p,+1,y,p,+1）。若,P,1,与,P,2,中点（,x,p,+1,y,p,+0.5）称为,M,，,Q,为理想直线与,x,=,x,p,+1垂线交点。当,M,在,Q,下方时，则取,P,2,应为下一个象素点；当,M,在,Q,上方时，则取,P,1,为下一个象素点。这就是中点画线法基本原理。,第13页,2.1.2中点画线法,过点(,x,0,y,0,)、(,x,1,y,1,)直线段,L,方程式为,F,(,x,y,),=ax+by+c=,0,，其中，,a=y,0,-,y,1,b,=,x,1,-,x,0,c,=,x,0,y,1,-,x,1,y,0,，欲判断中点,M,在,Q,点上方还是下方，只要把,M,代入,F,（,x,，,y,），并判断它符号即可。为此，我们结构判别式:,d,=,F,(,M,)=,F,(,x,p,+1,y,p,+0.5)=,a,(,x,p,+1)+,b,(,y,p,+0.5)+,c;,当,d,0时，,M,在,L,(,Q,点)上方，取,P,1,为下一个象素；,当,d=,0时，选,P,1,或,P,2,均可，约定取,P,1,为下一个象素；,第14页,2.1.2中点画线法,注意到,d,是,x,p,y,p,线性函数，可采取增量计算，提升运算效率。,若当前象素处于,d=,0情况，则取正右方象素,P,1,(,x,p,+1,y,p,),要判下一个象素位置，应计算,d,1,=,F,(,x,p,+2,y,p,+0.5)=,a,(,x,p,+2)+,b,(,y,p,+0.5)+c=,d,+,a,，增量为,a,。,若,d,0时，则取右上方象素,P,2,(,x,p,+1,y,p,+1)。要判断再下一象素，则要计算,d,2,=,F,(,x,p,+2,y,p,+1.5)=,a,(,x,p,+2)+,b,(,y,p,+1.5)+,c,=,d,+,a,+,b,，增量为,a,b,。画线从(,x,0,y,0,)开始，,d,初值,d,0,=,F,(,x,0,+1,y,0,+0.5)=,F,(,x,0,y,0,)+,a,+0.5,b,，,因,F,(,x,0,y,0,)=0，所以,d,0,=,a,+0.5,b,。,因为我们使用只是,d,符号，而且,d,增量都是整数，只是初始值包含小数。所以，我们能够用2,d,代替,d,来摆脱小数，写出仅包含整数运算算法程序。,第15页,2.1.2中点画线算法,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*/,第16页,2.1.2中点画线算法演示,程序演示,第17页,2.1.3,Bresenham,直线生成算法原理,r,r+1,q,q+1,t,s,T,i,S,i,设直线斜率小于1，即xy,x方向步长总是1，y方向是否有改变，取决于直线理论值与假设点之间误差值大小。考虑第i步,即点P,i,它前一点P,i-1,是最靠近直线坐标值,其坐标为(r,q),则P,i,坐标有两种选择：S,i,(r+1,q)和T,i,(r+1,q+1)。取哪一点需判别理论值和这两个假设点之间误差S,t大小。若St(或S-t0),则取点T,i,，反之取点S,i,。,第18页,2.1.3,Bresenham,直线生成算法原理,r,r+1,q,q+1,t,s,T,i,S,i,假设直线是从(x,a,y,a,)至(x,b,y,b,)，假如把直线平移使点(x,a,y,a,)与原点重合，则直线方程可写成y=y/xx，其中：x=x,b,-x,a,，y=y,b,-y,a,。则S,t可用下式计算：S=y/x(r+1)-qt=(q+1)-y/x(r+1)S-t=2y/x(r+1)-2q-1,x(S-t)=2(ry-qx)+2y-x 其中：x0。,令d,i,=x(S-t)，则d,i,与S-t符号相同只要判别di符号就可确定下一点坐标是S,i,还是T,i,。,第19页,2.1.3,Bresenham,直线生成算法原理,于是d,i,=2(ry-qx)+2y-x；当r=x,i-1,，q=y,i-1,时，d,i,=2x,i-1,y-2y,i-1,x+2y-x d,i+1,=2x,i,y-2y,i,x+2y-x d,i+1,-d,i,=2y(x,i,-x,i-1,)-2x(y,i,-y,i-1,)d,i+1,=d,i,+2y(x,i,-x,i-1,)-2x(y,i,-y,i-1,)所以，d,i,递推公式为：,d,1,=2y-x,d,i+1,=d,i,+2y当d,i,0时，取S,i,(x,i-1,+1,y,i-1,)d,i+1,=d,i,+2y-2x 当d,i,0时，取T,i,(x,i-1,+1,y,i-1,+1),第20页,Bresenham,直线生成算法描述,计算x和y方向增量：dx=|x,b,-x,a,|，dy=|y,b,-y,a,|,计算递推公式初值d,1,:d=2dy-dx,计算两个单位增量：incr1=2dy,incr2=2(dy-dx),if(x,a,x,b,)then 置起点为x=x,b,，y=y,b,，置终点为x,e,=x,a,y,e,=y,a,else 置起点为x=x,a,，y=y,a,，置终点为x,e,=x,b,，y,e,=y,b,输出起点(x,y),while(xx,e,)do begin,x=x+1,if(d0)then d=d+incr1,else y=y+1，d=d+incr2,输出点(x,y)end,end of algorithm,第21页,Bresenham,直线生成程序,void InterBresenhamline(int x0,int y0,int x1,int y1,int color),dx=x1-x0；dy=y1-y0；e=2*dy-dx;,x=x0；y=y0;,for(i=0;i=,0)y+;e=e-2*dx);,动画演示,第22页,Bresenham,直线生成,算法小结,本算法前提是直线斜率小于1，若直线斜率大于1，可用以上方法一样推出d,i,递推公式。,优点：,无乘除法(计算坐标时)；,在同一坐标上不可能连续停留两次。,第23页,