直线的绘制(光栅化)

1、第3章 基本光栅图形生成技术3.2 线的生成算法： 在数学上，直线是连续的，由无数个点构成的集合。x,y坐标均为实数。 但在显示器上，只能用有限的像素表示，像素的坐标是整数值。 因此，绘制时，需要将直线段离散化为有限的像素，这些像素应该尽可能地连续、尽量避免出现锯齿，并最佳逼近于给定的直线段。此外，绘制直线是非常基本的绘图操作，一个图中往往包括成千上万条直线，所以，算法应该尽可能地快。缺点缺点：每步都需要一个浮点乘法运算和一个四舍五入运算，所以效率太低。由于一个图中可以包含成千上万条直线，所以要求绘制算法应尽可能的快。 给定直线段的两个端点给定直线段的两个端点P P0 0(x(x0 0,y,y

2、0 0) )和和 P P1 1(x(x1 1,y,y1 1) )，斜率截距直线方程：)/()(/0101xxyyxyk00 xkyb从起点到终点，x每次增加(或减少)1，用直线方程计算对应的y值，再用SetPixel(x, int(y+0.5),color)输出该像素。上述方法称为直线绘制基本算法。直线绘制基本算法。直线绘制基本算法直线绘制基本算法bkxy数值微分(DDA)法 画线过程从x的左端点x0开始，向x右端点步进，x+=x，计算相应的y坐标：y=kx+b，取像素点(round(x), round(y)作为当前点的坐标。（xi,int(yi+0.5)（xi,yi)（xi+1,yi+1)（

3、xi+1,int(yi+1+0.5)图3-1 DDA算法基本原理 bkxy给定直线段的两个端点给定直线段的两个端点P P0 0(x(x0 0,y,y0 0) )和和 P P1 1(x(x1 1,y,y1 1) )，直线方程：设第i个点(xi,yi), yi= kxi+b第i+1个点(xi+1,yi+1), 令xi+1= xi+ x,则yi+1=k(xi+ x)+b=yi+kx = yi+y, y= k x当当 x =1时时 yi+1 = yi+k 复杂度：加法复杂度：加法+取整取整上述采用的增量计算方法称为数值微分算法数值微分算法(Digital Differential Analyzer，简

4、称DDA)。数值微分法的本质，是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。注意注意: : x, y的选择.void DDALine(int x0,int y0,int x1,int y1,int color) int i； float dx, dy, length,x,y; if (fabs(x1-x0)=fabs(y1-y0) length=fabs(x1-x0); else length=fabs(y1-y0); dx = (x1-x0)/length; dy=(y1-y0)/length; i=1;x= x0;y= y0; while(i=length

5、) SetPixel (int(x+0.5), int(y+0.5), color); x=x+dx; y=y+dy; i+; DDA算法与基本算法相比，减少了浮点乘法，提高了效率。但是x与dx、y与dy用浮点数表示，每一步要进行四舍五入后取整，不利于硬件实现，因而效率仍有待提高。 Bresenham算法Bresenham算法1965年提出，基本原理是：借助于一个误差量(直线与当前实际绘制像素点的距离)，来确定下一个像素点的位置。算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查误差量的符号，就可以确定该下一列的像素位置。 Yi +1yyixixi+1d2d1图3-3 根据误差量来确定理

6、想的像素点 假设当前直线上的像素坐标为(xi, yi)，那么下一步需要在列xi+1上确定扫描线y的值。y值要么不变，要么递增1，可通过比较d1和d2来决定。 如图3-3所示，对于直线斜率k在01之间的情况，从给定线段的左端点P0(x0, y0)开始，逐步处理每个后续列(x位置)，并在扫描线y值最接近线段的像素上绘出一点。判别式（误差参数）：iiiybxkyyd) 1(1（) 1(1) 1(2bxkyyydiii（12222121(221iiiiybkkxybxkdd）cxyyxxxyxbyyxddxiiii222222)(21设y=y1y0, x=x1x0，则k=y/x，代入上式，得； ) 1

7、2(2bxyc是常量，与像素位置无关。令)dd( xdi21对于k+1步，误差参数为：cyxxydiii11122cyxxyddxdiii22)(21)(2)(2111iiiiiiyyxxxydd此时参数c已经消去，且xi+1=xi+1,得：)(2211iiiiyyxydd如果选择右上方像素，即： ，则：11iiyyxyddii221iiyy1yddii21xyd 20如果选择右方像素，即： ，则： 判别式（误差参数）的递推计算：以下是当0k1时的Bresenham画线算法程序算法程序：void Bresenham_Line (int x0,int y0,int x1, int y1,int

8、color) int dx,dy, det1,det2, i,x,y,e; dx=x1-x0; dy=y1-y0; det1=2*dy; det2=2*(dy-dx) ; x=x0;y=y0; e=2*dy-dx; for (i=0; i=0) y+; e+=det2; else e+=det1; 实验二1.创建一个类CLine， 成员变量包括：CPoint m_StartPoint; CPoint m_EndPoint;COLORREF m_Color; 均设置为私有成员变量。成员函数(均为公有）包括：构造函数：CLine (CPoint start, CPoint end, COLORREF color);获取属性的函数：Get(CPoint &start, CPoint &end, COLORREF &color);设置属性的函数：Set(CPoint start, CPoint end, COLORREF color)；直接利用MFC中的画线函数绘制该直线段的函数：void Draw(CDC *pDC);利用DDA 算法绘制该直线段的函数：void Dr