中点画线算法.ppt

《中点画线算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中点画线算法讲授者：曲毅中点画线算法直线扫描转换计算机图形学图形扫描转换知识点地位在屏幕上在纸上VS画一条连接点P0(1，1)和P1(5，3)的直线段(连续的)(离散的)扫描转换中点法案例引入就是要找出显示平面上最佳逼近理想直线的那些象素的坐标值，并将这些象素置成所要求的颜色算法原理假定直线斜率k在0~1之间（x方向步进1，求y的取值）当前象素点为P(xp,yp)下一个象素点有两种可选择点Pu(xp+1,yp+1)，Pu与Pd的中点M(xp+1,yp+0.5)F(M)>0F(M)=0F(M)<0F(M)<0时，点M在直线下方，

2、取M上方点Pu为下一个象素点F(M)>0时，点M在直线上方，取M下方点Pd为下一个象素点F(M)=0时，点M在直线上，取Pu或Pd均可，默认取Pd为下一个象素点Pu(xp+1,yp+1)M(xp+1,yp+0.5)Pd(xp+1,yp)P(xp,yp)Pd(xp+1,yp)判别方法条件背景过点(x0,y0)、(x1,y1)的直线段L的方程为F(x,y)=ax+by+c=0，其中，a=y0-y1,b=x1-x0,c=x0y1-x1y0F(M)的符号作为判别的依据中点画线算法算法实现每一个像素的计算量是4个加法，2个乘法d=F(M

3、)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c判别式下一像素点效率分析乘法加法初始值xp=x0,yp=y0注意到d是xp,yp的线性函数，可采用增量计算，提高运算效率中点画线算法算法优化若当前象素处于d>=0情况，取Pd(xp+1,yp)要判断下一个象素位置，应计算d=F(M’)=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a增量为a判别式增量若d<0时，则取象素Pu(xp+1,yp+1)要判断再下一象素，则要计算d=F(M’)=F(xp+2,yp+1.5)=a(xp+2)+

4、b(yp+1.5)+c=d+a+b增量为a＋bPd(xp+1,yp)Pu(xp+1,yp+1)M’(xp+2,yp+0.5)M’(xp+2,yp+1.5)中点画线算法算法优化判别式初值画线从(x0,y0)开始，F(x0,y0)=0，d的初值d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b=a+0.5b我们使用的只是d的符号，而且d的增量都是整数，只是初始值包含小数。因此，我们可以用2d代替d来摆脱浮点数d0=2a+bd增量=2ad增量=2a+2b浮点数整数效率分析整数化改进注意到中点画线算法把初始值和2个增量

5、都扩大2倍算法总结算法流程F(x,y)=ax+by+c=0，a=y0-y1,b=x1-x0起点(x0,y0)、终点(x1,y1)初始化a=y0-y1；b=x1-x0d=2a+b，d1=2a；d2=2(a+b)x=x0；y=y0；画像素(x,y)x

6、d2=2(a+b)=6012345132下一个像素点起始点终止点当前像素点001xyd10-321331-1425521动画演示初始条件实现过程算法实例用中点画线方法扫描转换连接两点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)=6012345132下一个像素点起始点终止点当前像素点001xyd10-321331-1425521动画演示初始条件实现过程将中点画线法推广到任意斜率的直线段拓展思考THEEND