计算机图形学(直线的扫描转换I)

1、计算机图形学第3章 基本光栅图形算法1直线的扫描转换直线的扫描转换2圆的扫描转换圆的扫描转换3多边形的扫描转换多边形的扫描转换4区域填充区域填充5字符的生成字符的生成6光栅图形的反走样算法光栅图形的反走样算法22014-2015-1:CG:SCUEC本章内容直线的扫描转换生成直线算法的基本要求生成直线算法的基本要求基本增量算法基本增量算法中点法中点法BresenhamBresenham算法算法3直线扫描转换的定义直线扫描转换的定义2014-2015-1:CG:SCUECv 所画的直线是离散的像素集合所画的直线是离散的像素集合v 只有画水平线只有画水平线,垂直线垂直线,及正方及正方形对角线时形对

2、角线时,像素点集的位置像素点集的位置才是准确的才是准确的A(x1,y1)、B(x2,y2)、v 在计算机显示器上画一条直线在计算机显示器上画一条直线和在纸上画一条直线有什么本和在纸上画一条直线有什么本质的区别质的区别? ?v 显示器是一个有限的像素矩阵显示器是一个有限的像素矩阵4直线扫描转换的定义2014-2015-1:CG:SCUEC直线扫描转换的定义v在计算机显示器上画一条直线，只能在显示器在计算机显示器上画一条直线，只能在显示器所给定的有限个像素组成的点阵中，选择能最所给定的有限个像素组成的点阵中，选择能最佳地逼近于该直线的一组像素，并对这些像素佳地逼近于该直线的一组像素，并对这些像素按

3、指定的属性进行写操作。这就是通常所说的按指定的属性进行写操作。这就是通常所说的用显示器绘制直线，即用显示器绘制直线，即直线的扫描转换直线的扫描转换。v直线扫描转换的主要工作：快速找出像素点阵直线扫描转换的主要工作：快速找出像素点阵中距直线最近的网格点，用这些网格点对应的中距直线最近的网格点，用这些网格点对应的像素表示该直线。像素表示该直线。2014-2015-1:CG:SCUEC5v给定一个写像素函数给定一个写像素函数DrawPixelDrawPixel（x,y,color),x,y,color),能不能直接用数学公式生成直线？能不能直接用数学公式生成直线？A(x0,y0)B(x1,y1)vo

4、id DirectLine(int x0, int y0, int x1, int y1, int color) int x； float dx, dy, b, k; dx = x1-x0, dy=y1-y0; k=dy/dx, b=y0-k*x0; for (x=x0; x x1; x+) DrawPixel (x, int(k*x+b), color); 生成直线算法的基本要求62014-2015-1:CG:SCUECoxyk1(xi,yi)(xi+1,yi+1)v 数学公式生成直线的讨论：数学公式生成直线的讨论： 生成的直线可能不直生成的直线可能不直 算法复杂度高，运算速度慢算法复杂度高

5、，运算速度慢生成直线算法的基本要求7v 生成直线算法的基本要求生成直线算法的基本要求 生成的直线要直生成的直线要直 直线的端点要准确，保证绘制无定向性直线的端点要准确，保证绘制无定向性 直线的亮度、色泽要均匀，避免在视觉上造成一段亮直线的亮度、色泽要均匀，避免在视觉上造成一段亮一段暗的感觉一段暗的感觉 画线的速度要尽可能的快画线的速度要尽可能的快 有可能产生隔行显示有可能产生隔行显示2014-2015-1:CG:SCUEC问题问题直接用直线方程直接用直线方程y=kx+b来生成直线，之来生成直线，之所以算法复杂度高，是因为在迭代过程所以算法复杂度高，是因为在迭代过程中每次都要用到浮点数的乘法运算

6、，那中每次都要用到浮点数的乘法运算，那是否可以去掉浮点数的乘法运算呢？是否可以去掉浮点数的乘法运算呢？基本增量算法8v 最基本的增量算法是最基本的增量算法是DDADDA算法算法 数值微分分析器数值微分分析器(Digital Differential Analyzer)(Digital Differential Analyzer) DDADDA算法的本质是用数值方法解直线的微分方程算法的本质是用数值方法解直线的微分方程v 基本思想：基本思想：如果在一个迭代算法中，每一步的如果在一个迭代算法中，每一步的x值和值和y值都可以由前一步的的值加一个增量得到，那么这值都可以由前一步的的值加一个增量得到，那

7、么这种算法就称为增量算法。种算法就称为增量算法。2014-2015-1:CG:SCUEC生成直线的DDA算法v设直线的起点坐标为设直线的起点坐标为(x0 , y0)，终点坐标为，终点坐标为(x1 , y1)，令令 x = x1 x0， y = y1 - y0，则直线微分方程为，则直线微分方程为:, dxdyxydtdtv该方程的数值解的递推公式为该方程的数值解的递推公式为xi+1 = xi + x t ( t 表示步长）表示步长）yi+1 = yi + y t92014-2015-1:CG:SCUECv如果取 t=1/x，我们有： xi+1 = xi + 1 yi+1 = yi + kv即x方

8、向每次增加1，y方向增加k(直线的斜率)；生成直线的DDA算法void DDALine1(int x0,int y0,int x1,int y1,int color) int x；float dx, dy, y, k;dx = x1-x0, dy=y1-y0; k=dy/dx, y=y0; for (x=x0; x x1, x+) drawpixel (x, int(y+0.5), color); y = y + k; 102014-2015-1:CG:SCUECDDA算法画线举例例：用例：用DDADDA法画线法画线)2 , 5()0 , 0(10PP0 1 2 3 4 5321Line: P

9、0(0,0)P1(5,2)x y+0.5 int(y+0.5)0 0.5 01 0.4+0.5 0 2 0.8+0.5 1 3 1.2+0.5 1 4 1.6+0.5 2 5 2.0+0.5 2 注：网格点表示象素112014-2015-1:CG:SCUECv 讨论：讨论： 根直接用数学公式画直线相比，算法效率有较大提高。根直接用数学公式画直线相比，算法效率有较大提高。 还是有可能造成隔行显示还是有可能造成隔行显示DDA算法的分析oxyoxy(xi,yi)(xi+1,yi+1)(xi,yi)(xi+1,yi+1)122014-2015-1:CG:SCUECv为了解决隔行显示的问题，分成两种情况

10、考虑：首先为了解决隔行显示的问题，分成两种情况考虑：首先考虑直线斜率的绝对值小于考虑直线斜率的绝对值小于1的情况，这时的情况，这时| x| | y| 0，我们取，我们取 t=1/| x|，DDA数值解的递推公式为数值解的递推公式为: xi+1 = xi + 1， yi+1 = yi + k v其次考虑直线斜率的绝对值大于其次考虑直线斜率的绝对值大于1的情况，这时的情况，这时0| x| | y|，我们取，我们取 t=1/| y|，DDA数值解的递推公式为数值解的递推公式为: xi+1 = xi + 1/k， yi+1 = yi + 1 v综合起来，综合起来， 取步长取步长 t = min1/|

11、x|,1/| y|即即根据斜率根据斜率 k 的偏移程度，决定是以的偏移程度，决定是以 x 为步进方向还是以为步进方向还是以 y 为步进为步进方向。然后在相应的步进方向上，步进变量每次增加方向。然后在相应的步进方向上，步进变量每次增加一个像素，而另一个相关坐标变量则为一个像素，而另一个相关坐标变量则为 yi+1 = yi + k （以（以 x 为步进变量为例为步进变量为例xi+1 = xi+1）DDA算法的改进132014-2015-1:CG:SCUECDDA算法的进一步改进v 讨论：如果直线段的两个端点不是整数怎么办？讨论：如果直线段的两个端点不是整数怎么办？142014-2015-1:CG:

12、SCUECvoid DDALine (float xs, float ys, float xe, float ye, int color)int n, ix, iy, idx, idy ;int Flag; /插补方向标记插补方向标记int Length; /插补长度插补长度float x, y, dx, dy;dx = xe - xs;dy = ye - ys;if (fabs(dy) = fabs(dx) /X方向长，方向长，|斜率斜率|1Length = abs(Round(ye)-Round(ys);Flag=0;iy = Round(ys); /初始初始Y点点idy = sign(d

13、y); /Y方向单位增量方向单位增量x= xs+dx/dy*(float)(iy)-ys); /初始初始X点修正点修正dx=dx/fabs(dy); /X方向增量方向增量(斜率的倒数斜率的倒数)if (Flag) /X方向单位增量方向单位增量for (n=0; n= Length; n+) /X方向插补过程方向插补过程DrawPixel(ix, Round(y), color);ix+=idx;y+=dy; /End of for /End of ifelse /Y方向斜率增量方向斜率增量for (n=0; n 0, F(x, y) 0, 分别表示点分别表示点(x, y)在直线上、直线上方和直

14、线下方在直线上、直线上方和直线下方( )(1 ,0.5)(1)(0.5)iiiiidFMF xyaxb yc v要判断点要判断点M M在直线上，上方还是下方可将在直线上，上方还是下方可将M M代入代入下面的判别式判断其正负即可下面的判别式判断其正负即可202014-2015-1:CG:SCUECvdi 0，取PB为下一像素vdi = 0，可在两个点中任取一个，约定取下方的点PBMP=(x,y)QPTPBv思考：这样做，每一个像素的计算量是多少？21中点法的具体实现v答案：每一个像素的计算量是4个加法，两个乘法。比DDA算还要坏，“山穷水尽疑无路了吗？”2014-2015-1:CG:SCUECv

15、 若若di 0时，时，22ddady 当当d abs(y1-y0) /X方向长，方向长，|斜率斜率| x1) /起点在右方，和终点交换起点在右方，和终点交换 x=x0;x0=x1;x1=x;y=y0;y0=y1;y1=y; a = y0 - y1; b = x1 - x0; if (a 0) / 斜率斜率0step =1;d = (a1) + b; /判别式的初始值判别式的初始值dt1 = a =0时的判别式增量时的判别式增量dt2 = (a + b) 1; /d时的判别式增量时的判别式增量x=x0;y=y0;DrawPixel(x,y,color); /画起点画起点完整的中点法算法描述29 while(x x1) if ( d 1 if (y0 y1)x=x0;x0=x1;x1=x;y=y0;y0=y1;y1=y; a = x0 - x1; b = y1 - y0; if (a 0) a = -a; step = -1;else step =1;完整的中点法算法描述30d = (a1) + b; /判别式的初始值