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

LESSON03基本图形生成算法第1页基本图形生成算法总体目标：掌握二维图形学基本思想，了解二维图形生成基本原理掌握直线段生成算法、反走样算法。掌握圆弧生成及线形处理掌握字符生成基本思想第2页基本概念光栅显示器上显示图形，称之为光栅图形。确定最正确迫近图形象素集合，并用指定颜色和灰度设置象素过程称为图形扫描转换或光栅化。二维图形光栅化必须确定区域对应象素集，将各个象素设置成指定颜色和灰度，也称之为区域填充。在光栅图形中，非水平和垂直直线用象素集合表示时，会呈锯齿状，这种现象称之为走样(aliasing)；用于降低或消除走样技术称为反走样(antialiasing)。第3页2.1直线生成算法概述在计算机产生图形中，用到大量直线，画好直线是非常有意义，其普通准则是：线条应该显得笔直：由连续点组成直线要显示在离散网格平面上，一定会有不经过网格点，如左下列图。在这种情况下，必须选择靠近直线网格点来迫近这条直线。若选择好，线就显得较直；不然就会较弯曲，如右下列图。第4页2.1直线生成算法概述直线端点位置应该准确：画出线段假如不准确，往往会使两条线之间不能很好镶接，如右图。直线浓度应该均匀：线段浓度与单位线段中所显示点数成正比。要保持线段浓度均匀端点应该等距分布。只有严格平行和成45°线才能做到。第5页2.1直线生成算法概述直线浓度应该与线段长度和斜率无关：

要取得均匀线段浓度，应该保持每单位长度点数是个常数。普通，采取线段近似长度，以及生成直线算法，使在线段近似长度范围内保持线段浓度均匀。显示线段速度应快：

生成直线可用软件和硬件来实现，普通情况下，硬件要比软件实现得快。第6页2.1直线生成算法概述直线惯用生成算法数值微分(DDA：DigitalDifferentialAnalyzer

)法

中点画线法Bresenham算法第7页2.1.1直线DDA算法直线微分方程表示为：

dx/dy=△x/△y

设直线斜率小于等于1，

起点坐标为(xa,ya)，

终点坐标为(xb,yb)，

则方程求解步骤分为：

x0=xa

+0.5，xn=xn-1+1

y0=ya

+0.5，yn=yn-1+△y/△x

其中：△x=xb

-xa，△y=yb-ya

上述解表示x方向积分步长为1，y方向增量为△y/△x。yn-1yxynxn-1xn△y/△x第8页2.1.1直线DDA算法xyn-1yynxn-1xn△y/△x因为屏幕上坐标为整数坐标，则真正作为输出显示为：

y输出=trunc(yn)，其中函数trunc()是指舍尾正数。

所以y输出和yn之间量化误差最大为1。

为了改进这方面误差，

使y0初值增加0.5,

使量化误差在(-0.5,0.5)范围之间。

同理，若直线斜率大于1，

则上述方程求解步骤可分为：

x0=xa+0.5，xn=xn-1+△x/△y，

y0=ya+0.5，yn=yn-1+1，

其中△x，△y意义同上。

上述解表示y方向积分步长为1，

x方向增量为△x/△y,其它同上。第9页DDA直线生成算法描述if|xb-xa|≤|yb-ya|then

计算直线在y方向上增量：length=|yb-ya|else计算直线在x方向上增量：length=|xb-xa|计算x方向单位增量：dx=(xb-xa)/length计算y方向单位增量：dy=(yb-ya)/length置初值：x=xa+0.5，y=ya+0.5fori=1tolengthdo

begin 输出点(trunc(x),trunc(y)) 计算下一个点坐标x=x+dx，y=y+dy

endendofalgorithm第10页DDA直线生成算法C描述VoidlineDDA(intxa,intya,intxb,intyb){intdx=xb-xa,dy=yb-ya,steps,k;floatxIncrement,yIncrement,x=xa,y=ya;if(abs(dx)>abs(dy))steps=abs(dx);elsesteps=abs(dy);xIncrement=dx/(float)steps;yIncrement=dy/(float)steps;setPixel(round(x),round(y));for(k=0;k<steps;k++){x+=xIncrement;y+=yIncrement;setPixel(round(x),round(y));}}

动画演示算法第11页DDA直线生成算法小结优点：在同一坐标上,不可能连续停留两次。缺点：在本算法中，开始需要执行一个除法△y/△x或△x/△y来确定增量，这么用硬件来实现比较复杂和昂贵，用软件实现相对轻易些，但效率较低。第12页2.1.2中点画线法假定直线斜率k在0~1之间，当前象素点为（xp,yp），则下一个象素点有两种可选择点P1（xp+1,yp）或P2（xp+1,yp+1）。若P1与P2中点（xp+1,yp+0.5）称为M，Q为理想直线与x=xp+1垂线交点。当M在Q下方时，则取P2应为下一个象素点；当M在Q上方时，则取P1为下一个象素点。这就是中点画线法基本原理。第13页2.1.2中点画线法过点(x0,y0)、(x1,y1)直线段L方程式为F(x,y)=ax+by+c=0，其中，a=y0-y1,b=x1-x0,c=x0y1-x1y0，欲判断中点M在Q点上方还是下方，只要把M代入F（x，y），并判断它符号即可。为此，我们结构判别式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c;

当d<0时，M在L(Q点)下方，取P2为下一个象素；

当d>0时，M在L(Q点)上方，取P1为下一个象素；

当d=0时，选P1或P2均可，约定取P1为下一个象素；第14页2.1.2中点画线法注意到d是xp,yp线性函数，可采取增量计算，提升运算效率。

若当前象素处于d>=0情况，则取正右方象素P1(xp+1,yp),要判下一个象素位置，应计算d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a，增量为a。

若d<0时，则取右上方象素P2(xp+1,yp+1)。要判断再下一象素，则要计算d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b，增量为a＋b。画线从(x0,y0)开始，d初值d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b，因

F(x0,y0)=0，所以d0=a+0.5b。

因为我们使用只是d符号，而且d增量都是整数，只是初始值包含小数。所以，我们能够用2d代替d来摆脱小数，写出仅包含整数运算算法程序。第15页2.1.2中点画线算法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*/第16页2.1.2中点画线算法演示程序演示第17页2.1.3Bresenham直线生成算法原理rr+1qq+1tsTiSi设直线斜率小于1，即△x＞△y,

x方向步长总是1，y方向是否有改变，

取决于直线理论值与假设点之间误差值大小。

考虑第i步,即点Pi,它前一点Pi-1

是最靠近直线坐标值,其坐标为(r,q),

则Pi坐标有两种选择：

Si

(r+1,q)和Ti

(r+1,q+1)。

取哪一点需判别理论值和

这两个假设点之间误差S,t大小。

若S＞t(或S-t＞0),则取点Ti，反之取点Si。第18页2.1.3Bresenham直线生成算法原理rr+1qq+1tsTiSi 假设直线是从(xa,ya)至(xb,yb)，

假如把直线平移使点(xa,ya)

与原点重合，则直线方程可写成

y=△y/△x·x，

其中：△x=xb-xa，

△y=yb-ya。

则S,t可用下式计算：

S=△y/△x·(r+1)-q

t=(q+1)-△y/△x·(r+1)

S-t=2·△y/△x·(r+1)-2q-1 △x(S-t)=2(r·△y-q·△x)+2△y-△x其中：△x＞0。 令di=△x(S-t)，则di与S-t符号相同

只要判别di符号就可确定下一点坐标是Si还是Ti。第19页2.1.3Bresenham直线生成算法原理

于是

di=2(r·△y-q·△x)+2·△y-△x；

当r=xi-1，q=yi-1时，

di=2xi-1·△y-2yi-1△x+2△y-△x

di+1=2xi·△y-2yi·△x+2△y-△x

di+1-di=2△y(xi-xi-1)-2△x(yi-yi-1)

di+1=di+2△y(xi-xi-1)-2△x(yi-yi-1)

所以，di递推公式为：

d1=2△y-△x di+1=di+2△y

当di＜0时，取Si

(xi-1+1,yi-1)

di+1=di+2△y-2△x

当di≥0时，取Ti

(xi-1+1,yi-1+1)第20页Bresenham直线生成算法描述计算x和y方向增量：dx=|xb-xa|，dy=|yb-ya|计算递推公式初值d1:

d=2dy-dx计算两个单位增量：incr1=2dy,incr2=2(dy-dx)if(xa＞xb)then

置起点为x=xb，y=yb，置终点为xe=xa,ye=yaelse置起点为x=xa，y=ya，置终点为xe=xb，ye=yb输出起点(x,y)while(x＜xe)dobegin

x=x+1if(d＜0)thend=d+incr1

elsey=y+1，d=d+incr2

输出点(x,y)endendofalgorithm 第21页Bresenham直线生成程序voidInterBresenhamline(intx0,inty0,intx1,inty1,intcolor)