详解直线扫描算法

上传人:cn****1 文档编号:431006148 上传时间:2022-11-24 格式:DOCX 页数:16 大小:17.76KB
返回 下载 相关 举报
详解直线扫描算法_第1页
第1页 / 共16页
详解直线扫描算法_第2页
第2页 / 共16页
详解直线扫描算法_第3页
第3页 / 共16页
详解直线扫描算法_第4页
第4页 / 共16页
详解直线扫描算法_第5页
第5页 / 共16页
点击查看更多>>
资源描述

《详解直线扫描算法》由会员分享,可在线阅读,更多相关《详解直线扫描算法(16页珍藏版)》请在金锄头文库上搜索。

1、先标明这转载自http:/ zxx图形学神马的全都是数学,看来以后我不能搞这个,伤脑筋,所以先把我现在懂 得先记录下来吧。不过呢,我的水平实在有限,对于算法这种东西实在难以说明 白,请大家包涵。书上讲的实在是太过简略,所以这里我把一些简单的推导过程都记录下来:1.重温bresenham未改进算法(斜率在0-1之间的直线)我想要记录的是bresenham改进算法,所以在讲解改进算法之前,我先用一个简 单的例子说明一下未改进算法的思想:这是一个斜率k在0-1之间的一条直线,我就用斜率为0-1之间的直线来重温:首先,如图1所示,假设x列的像素已定,其坐标为(x,y),那么下一个坐标 一定是:(x+1

2、,y+1)或者(x+1,y)。而是哪一个取决于d的值,如果d0.5那么就是 (x+1,y+1),如果d=1时,就让d减一,这 样就保证了 d在0-1之间。当 d0.5,下一个点取(x+1,y+1)当d0,下一个点取(x+1,y+1)当e0使用这个替换以后,我们就可以消除除法和小数了,这里要注意一个问题,我们 一定要保持e和e的符号是相同的,那么就要保证dx大于0!所以说,在 这种情况下,我们的dx一定要大于0,如果小于0,可以交换起点和终点坐标, 总之起点一定要从x坐标小的点开始。而且我们要注意以前当e0时,我们要e=e-1,现在:e=e/ (2*dx)所以 e/ (2*dx) = e/ (2

3、*dx) -1展开 e = e-2*dx。具体的代码如下:void CMyDrawLineView:DrawBresenham(int x1,int x2,int y1,int y2,COLORREF color,CDC* pDC)int x,y,dx,dy,e;dx=x2-x1;dy=y2-y1;x=x1;y=yLCString s;这里一定要注意,由于使用的是改进算法,所以dx 一定是要大于0才能 保证其符号不变if(dx=0&dy=0)|(dx=0&dy=0) /如果 k 大于 0if(dx0)/dx小于0说明终点xdx=-dx;x=x2;dy=-dy;y=y2;if(dydx)/第一种

4、情况,k-(0,1)e=-dx;for(int i=0;iSetPixel(x,y,color);x+;e=e+dy+dy;if(e=0)y+;e=e-dx-dx;B.斜率在1-无穷之间如图二在这种情况下,我们可以看到y的变化速度比x快,所以说,我们这里 每次让y加1,而不是让x加1,所以我们每次让y加1时,x的增长是d,注意, 此处的d不是斜率k,而是1/k,按照以往我们的目的,我们要消除除法和小数:1.消除除法e=e+d;e=e+dx/dy;dy*e=dy*e+dx;2.消除0.52*dy*e=2*dy*e+2dx;由于算法中只用到误差项的符号,所以可以使用如下替换:e=2*e*dy注意:

5、为了让代换后符号不改变,必须保证dy0,如果不满足,则可以按上述方 法交换起点终点坐标。代码如下:void CMyDrawLineView:DrawBresenham(int x1,int x2,int y1,int y2,COLORREF color,CDC* pDC)int x,y,dx,dy,e;dx=x2-x1;dy=y2-y1;x=x1;y=yi;CString s;这里一定要注意,由于使用的是改进算法,所以dx 一定是要大于0才能 保证其符号不变if(dx=0&dy=0)ll(dx=0&dy=0) /如果 k 大于 0if(dx=dx)/第一种情况,k-(0,1)e=-dy;for

6、(int i=0;iSetPixel(x,y,color);y+;e=e+dx+dx;if(e=0)x+;e=e-dy-dy;C.斜率在0-(-1)之间如图三,在这种情况下可以类比斜率在0-1之间的情况,不过呢,我们要注意一 个问题,就是现在的斜率是负数,我们使用时,需要改变符号,下面直接看改进:1. 消除除法e=e-dy/dx (注意是减号,因为现在的斜率是负数)e*dx=e*dx-dy2. 消除小数2*e*dx= 2e*dx-2dy由于算法中只用到误差项的符号,所以可以使用如下替换:e=2*e*dx注意:为了让代换后符号不变,必须保证dx0d d代码如下:void CMyDrawLineV

7、iew:DrawBresenham(int x1,int x2,int y1,int y2,COLORREF color,CDC* pDC)int x,y,dx,dy,e;dx=x2-x1;dy=y2-y1;x=x1;y=yLCString s;这里一定要注意,由于使用的是改进算法,所以dx 一定是要大于0才能 保证其符号不变if(dx=0&dy=0)|(dx=0&dy=0) /如果 k 大于 0elseint tempx,tempy; 保存x和y的绝对值if(dx0)/dx小于0说明终点xtempx=-dx;tempy=dy;if(dytempy)/第三种情况,k-(-1,0)if(dx0)

8、/dx小于0说明终点xdx=-dx;x=x2;dy=-dy;y=y2;e=-dx;for(int i=0;iSetPixel(x,y,color);x+;e=e-dy-dy;if(e=0)y; e=e-dx-dx;D.斜率在(-1)-负无穷之间如图四,在这种情况下可以类比斜率在1到正无穷之间的情况,不过呢,我们要 注意一个问题,就是现在的斜率是负数,我们使用时,需要改变符号,下面直接 看改进:1. 消除除法e=e-dx/dy (注意是减号,因为现在的斜率是负数)e*dy=e*dy-dx2. 消除小数2*e*dy= 2*e*dy-2dx由于算法中只用到误差项的符号,所以可以使用如下替换:e=2*

9、e*dy注意:为了让代换后符号不变,必须保证dy0代码如下:void CMyDrawLineView:DrawBresenham(int x1,int x2,int y1,int y2,COLORREF color,CDC* pDC)int x,y,dx,dy,e;dx=x2-x1;dy=y2-y1;x=x1;y=yLCString s;这里一定要注意,由于使用的是改进算法,所以dx 一定是要大于0才能 保证其符号不变if(dx=0&dy=0)ll(dx=0&dy=0) /如果 k 大于 0elseint tempx,tempy; /保存x和y的绝对值 if(dx0) /dx小于0说明终点x

10、tempx=-dx; tempy=dy;if(dy0)tempx=dx; tempy=-dy;if(tempxtempy)/第四种情况,k-(-1,min)if(dy0)/dx小于0说明终点xdx=-dx;x=x2;dy=-dy;y=y2;e=-dy;for(int i=0;iSetPixel(x,y,color);y+;e=e-dx-dx;if(e=0)x-;e=e-dy-dy;/if(edy)/ e=e-dy-dy;/完整的程序如下:/*x1直线起点xx2:直线终点xyl:直线起点yy2:直线终点ycolor:直线颜色*/void CMyDrawLineView:DrawBresenham

11、(int x1,int x2,int y1,int y2,COLORREF color,CDC* pDC)int x,y,dx,dy,e;dx=x2-x1;dy=y2-y1;x=x1;y=yLCString s;这里一定要注意,由于使用的是改进算法,所以dx 一定是要大于0才能保 证其符号不变if(dx=0&dy=0)ll(dx=0&dy=0) /如果 k 大于 0if(dx0)|(dx=0&dy0)/dx 小于 0 说明终点 xdx=-dx;x=x2;dy=-dy;y=y2;if(dydx)/第一种情况,k-(0,1)e=-dx;for(int i=0;iSetPixel(x,y,color);x+;e=e+dy+dy;if(e=0)y+;e=e-dx-dx;else/第二种情况,k-(1,max)e=-dy;for(int i=0;iSetPixel(x,y,color);y+;e=e+dx+dx;if(e=0)x+;e=e-dy-dy;

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 办公文档 > 活动策划

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号