计算机图形学 第2版 课件2-DDA画线算法

DDA法绘制直线段内容大纲1直线段的数学模型2DDA绘制直线段算法推导3任意方向直线段的DDA算法4DDA绘制直线段的程序设计5控制线型的程序设计思路6反走样处理简介1直线段的数学模型直线的代数方程：y=kx+b已知直线段的起点(xs,ys),终点(xe,ye)直线方程为：(y-ys)/(ye-ys)=(x-xs)/(xe-xs)已知x,可求出y：

y=(ye-ys)(x-xs)/(xe-xs)+ys已知y,可求出x：x=(xe-xs)(y-ys)/(ye-ys)+xs如何在显示器中绘制直线？需要推导出绘制算法如何显示直线段？如何找到逼近像素？2DDA绘制直线算法推导绘制直线段一般需要进行栅格化（又叫光栅化）处理：将几何数据经过一系列变换后转换为像素呈现在显示设备上。2DDA绘制直线算法推导DDA为数值微分法

(DigitalDifferentalAnalyzer)

直线方程：y=kx+b

两边微分：dy/dx=k

数值化（离散化）：(yi+1-yi)/(xi+1-xi)=k

DDA法关键公式(yi+1-yi)/(xi+1-xi)=k（xs,ys)(xe,ye)2DDA绘制直线算法推导设第一象限方向直线段k<1(xi+1-xi)=1xi+1=xi+1(yi+1-yi)/1=kyi+1=yi+kxy1个像素间隔i=0,1,….xe-xs,x0=xs,y0=ys注意：每步计算的y值要取整2DDA绘制直线算法推导xi+1=xi+1yi+1=yi+0.25

【例】设直线段起点为(1,1),终点为（5,2）,绘制该直线段。x0=1y0=1x1=2y1=y0+0.25=1.25≈1k=(2-1)/(5-1)=0.25x2=3y2=y1+0.25=1.5≈2

x3=4y3=y2+0.25=1.75≈2

x4=5y4=y3+0.25=2如果第一象限直线段k>1(yi+1-yi)/(xi+1-xi)=k（xs,ys)(xe,ye)2DDA绘制直线算法推导(yi+1-yi)=1yi+1=yi+11/(xi+1-xi)=kxi+1=xi+1/kxy1个像素间隔i=0,1,….ye-ys,x0=xs,y0=ys每步计算的x值要取整（xs,ys)xy3任意方向直线段的DDA算法xi+1=xi+1,yi+1=yi+k①⑧④⑤①②③④⑤⑥⑦⑧|k|<1

②③⑥⑦①if(xe<xs)交换(xs,ys)与(xe,ye)④⑤⑧|k|>=1yi+1=yi+1,xi+1=xi+1/k②③if(ye<ys)交换(xs,ys)与(xe,ye)

⑥⑦if(xe<xs)交换(xs,ys)与(xe,ye)

if(ye<ys)交换(xs,ys)与(xe,ye)x0=xs,y0=ys

i=0,1,….ye-ys,yi+1=yi+1,xi+1=xi+1/k

x0=xs,y0=ys,i=0,1,….xe-xsxi+1=xi+1,yi+1=yi+k4DDA绘制直线段的程序设计voidLine_DDA(CDC*pDC,intxs,intys,intxe,intye,COLORREFcolor){intt;floatx,y,k=(float)(ye-ys)/(xe-xs);if(fabs(k)<1){if(xe<xs)t=xe,xe=xs,xs=t,t=ye,ye=ys,ys=t;y=ys;for(x=xs;x<=xe;x++)pDC->SetPixel(x,y,color),y=y+k;}

else{if(ye<ys)t=xe,xe=xs,xs=t,t=ye,ye=ys,ys=t;x=xs;for(y=ys;y<=ye;y++)pDC->SetPixel(x,y,color),x=x+1/k;}}|k|<1|k|>=1

增加计数变量m、n作为控制开关将“画点”语句改为：if(m<10){画点;m++;}elseif(n<5)n++;elsem=0,n=0;5控制线型的程序设计思路1055控制线型的程序设计思路6反走样处理简介用离散量表示连续量引起的图形失真，叫走样(Liasing)减少走样现象的技术和方法称为反走样