线段的扫描转换算法[精选].doc

线段的扫描转换算法 摘要：本文主要讨论基本光栅图形算法中的线段图形对象的扫描转化算法。包括数字微分(DDA)画线算法和Bresenham画线算法，并比较两算法的优缺点。最后介绍OpenGL函数生成直线。 关键字：线段 数字微分(DDA)画线算法 Bresenham画线算法 OpenGL函数 计算机图形学(Computer Graphics，简称CG)是利用计算机处理图形信息的一门学科，包括图形信息的表示、输入输出与显示、图形的几何变换、图形之间的运算以及人机交互绘图等方面的技术。计算机图形学既是一门科学，它包括一些数学基础和理论，又是一门技术，包括一些技巧和方法。计算机图形学的研究领域包括图形系统的硬件设备、基本图元的生成技术、图形变换技术、人机交互绘图技术、图形运算和处理技术、实体造型技术和真实图形的表示。在过去的几十年里，计算机图形学无论是在理论研究，还是在实际应用的深度和广度方面，都取得了令人可喜的成果，其主要推动力来自于图形用户的要求以及软件和硬件技术的突破。目前，计算机图形学的应用领域多样且范围广泛。包括图形用户界面，计算机辅助设计与制造，科学计算可视化，地理信息系统，娱乐，计算机艺术，虚拟现实，逆向工程等等领域。 本文章中主要讨论基本光栅图形算法中的线段图形对象的扫描转化算法。光栅化是从连续到离散的过程。在绘制具有连续性质的图形时，需要确定最佳逼近它们的像素，这个过程称为光栅化。确定像素集合及其颜色，用于显示图形对象的过程，称为图形对象的扫描转换。线段扫描算法的任务是根据传入的线段的两个端点的坐标，求出构成线段的所以像素点的坐标。常用的线段扫描算法有数字微分(DDA)画线算法和Bresenham画线算法。 扫描转换直线段是指计算出落在直线段上或充分靠近它的一串像素，并以此像素集近似代替原连续直线段在屏幕上显示的过程。本文我们只讨论具有1个像素宽度的直线段的扫描转换。即当该线段的斜率落在-1到1之间时，它在每个列扫描线上仅有一个像素；当该线段的斜率的绝对值大于1时，它在每个行扫描线上仅有一个像素。为了讨论方便，我们将像素看作是中心为网格点(x,y)的圆点，像素间的距离是均匀的，像素相互不重叠。 一、数字微分(DDA)画线算法 DDA称为数值微分画线算法，是直线生成算法中最简单的一种。原理相当简单，就是最直观的根据斜率的偏移程度，决定是以x为步进方向还是以y为步进方向。然后在相应的步进方向上，步进变量每次增加一个像素，而另一个相关坐标变量则为Y=X+m（以X为步进变量为例，m为斜率）.当斜率在-1到1之间是让X增长值为1，Y的增长值为K。当斜率大于1时。让Y增长值为1，X的增量为1/K。这样做的目的是让每次变化的值不能大于1。这样可以让像素点更加整齐CPoint p1,p2;? p1.x=0; ?p1.y=0; ?p2.x=300; ?p2.y=400;//坐标点初始化?double dx,dy,k,y,x; ?COLORREF rgg=RGB(0,0,0);? //黑色?dx=p2.x -p1.x; ?dy=p2.y-p1.y; ?k=dy/dx;//求斜率?if(fabs(k)1)//当斜率在-1到1之间的时候?{ ??y=p1.y; ??for(x=p1.x;x=p2.x;x++)//以X为增量{ ???pDC-SetPixel(x,int(y+0.5),rgg); ???y=y+k; ??} ?} ?else//斜率大于1的时候?{ ??x=p1.x;??for(y=p1.y;y=p2.y;y++)//以Y为增量? //X的增量为1/K??{???????pDC-SetPixel(int(x+0.5),y,rgg);?x=x+1.0/k;??}?} 二、Bresenham画线算法 Bresenham?画线算法是由Bresenham提出的一种精确而有效的光栅线生成算法，该算法仅仅使用了整数的增量来实现的。Bresenham算法将对整形参数的符号检测，整形参数的值比于实际险段之间的偏量。 Bresenham算法内容 对于直线方程?Y = kX + b; ⒈0?k? 1?时候的算法 ???1,输入线段的两个端点Point1和Point2，并且存储到Point1(x1,y1)和Point2(x2,y2)中； ???2,将Point1载入桢缓存，绘画第一个起始点； ???3,计算常量△x、△y、2△y和2(△y-△x)，并且获得一个决策参数的第一个值：P = 2△y -?△x； ???4,从n = 0开始，在沿线经过每个Xn处，进行下面的监测: ????????如果Pn 0,?下一个点绘制的是(Xn+1,yn)，并且Pn+1= Pn + 2△y ????????如果P0= 0 ,下一个点