《计算机图形学(直线的扫描转换I)》由会员分享，可在线阅读，更多相关《计算机图形学(直线的扫描转换I)（31页珍藏版）》请在金锄头文库上搜索。
1、计算机图形学 第3章 基本光栅图形算法 1直线的扫描转换 2 圆的扫描转换 3 多边形的扫描转换 4区域填充 5字符的生成 6光栅图形的反走样算法 22014-2015-1:CG:SCUEC 本章内容 直线的扫描转换 生成直线算法的基本要求 基本增量算法 中点法 Bresenham算法 3 直线扫描转换的定义 2014-2015-1:CG:SCUEC v 所画的直线是离散的像素集合 v 只有画水平线,垂直线,及正方 形对角线时,像素点集的位置 才是准确的 A(x1,y1)、 B(x2,y2)、 v 在计算机显示器上画一条直线 和在纸上画一条直线有什么本 质的区别? v 显示器是一个有限的像素矩
2、阵 4 直线扫描转换的定义 2014-2015-1:CG:SCUEC 直线扫描转换的定义 v在计算机显示器上画一条直线，只能在显示器 所给定的有限个像素组成的点阵中，选择能最 佳地逼近于该直线的一组像素，并对这些像素 按指定的属性进行写操作。这就是通常所说的 用显示器绘制直线，即直线的扫描转换。 v直线扫描转换的主要工作：快速找出像素点阵 中距直线最近的网格点，用这些网格点对应的 像素表示该直线。 2014-2015-1:CG:SCUEC5 v给定一个写像素函数DrawPixel（x,y,color), 能不能直接用数学公式生成直线？ A(x0,y0) B(x1,y1) void Direct
3、Line(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; xx1; x+) DrawPixel (x, int(k*x+b), color); 生成直线算法的基本要求 62014-2015-1:CG:SCUEC o x yk1 (xi,yi ) (xi+1,yi+1) v 数学公式生成直线的讨论： 生成的直线可能不直 算法复杂度高，运算速度慢 生成直线算法的基本要求 7 v 生成直线算法的基本要求
4、生成的直线要直 直线的端点要准确，保证绘制无定向性 直线的亮度、色泽要均匀，避免在视觉上造成一段亮 一段暗的感觉 画线的速度要尽可能的快 有可能产生隔行显示 2014-2015-1:CG:SCUEC 问题 直接用直线方程y=kx+b来生成直线，之 所以算法复杂度高，是因为在迭代过程 中每次都要用到浮点数的乘法运算，那 是否可以去掉浮点数的乘法运算呢？ 基本增量算法 8 v 最基本的增量算法是DDA算法 数值微分分析器(Digital Differential Analyzer) DDA算法的本质是用数值方法解直线的微分方程 v 基本思想：如果在一个迭代算法中，每一步的x值和 y值都可以由前一步
5、的的值加一个增量得到，那么这 种算法就称为增量算法。 2014-2015-1:CG:SCUEC 生成直线的DDA算法 v设直线的起点坐标为(x0 , y0)，终点坐标为(x1 , y1)， 令x = x1 x0， y = y1 - y0，则直线微分方程为: v该方程的数值解的递推公式为 xi+1 = xi + x t (t 表示步长） yi+1 = yi + y t 92014-2015-1:CG:SCUEC v如果取 t=1/x，我们有： xi+1 = xi + 1 yi+1 = yi + k v即x方向每次增加1，y方向增加k(直线的斜率)； 生成直线的DDA算法 void DDALine
6、1(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; xx1, x+) drawpixel (x, int(y+0.5), color); y = y + k; 102014-2015-1:CG:SCUEC DDA算法画线举例 例：用DDA法画线 0 1 2 3 4 5 3 2 1 Line: P0(0,0)P1(5,2)x y+0.5 int(y+0.5) 0 0.5 0 1 0.4+0.5 0 2 0.8+0.5
7、1 3 1.2+0.5 1 4 1.6+0.5 2 5 2.0+0.5 2 注：网格点表示象素 112014-2015-1:CG:SCUEC v 讨论： 根直接用数学公式画直线相比，算法效率有较大提高 。 还是有可能造成隔行显示 DDA算法的分析 o x y o x y (xi,yi) (xi+1,yi+1 ) (xi,yi ) (xi+1,yi+1) 122014-2015-1:CG:SCUEC v为了解决隔行显示的问题，分成两种情况考虑：首先 考虑直线斜率的绝对值小于1的情况，这时|x| |y| 0，我们取 t=1/|x|，DDA数值解的递推公式为: xi+1 = xi + 1， yi+1
8、 = yi + k v其次考虑直线斜率的绝对值大于1的情况，这时0|x| |y|，我们取 t=1/|y|，DDA数值解的递推公式为: xi+1 = xi + 1/k， yi+1 = yi + 1 v综合起来， 取步长t = min1/|x|,1/|y|即根据斜率 k 的偏移程度，决定是以 x 为步进方向还是以 y 为步进 方向。然后在相应的步进方向上，步进变量每次增加 一个像素，而另一个相关坐标变量则为 yi+1 = yi + k （ 以 x 为步进变量为例xi+1 = xi+1） DDA算法的改进 132014-2015-1:CG:SCUEC DDA算法的进一步改进 v 讨论：如果直线段的两
9、个端点不是整数怎么办？ 142014-2015-1:CG:SCUEC void 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方向长，|斜率|1 Length = abs(Round(ye)-Round(ys); Flag=0; iy = Round(y
10、s); /初始Y点 idy = sign(dy); /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 if else /Y方向斜率增量 for (n=0; n 0, F(x, y) 0) / 斜率0 step =1; d = (a1) + b; /判别式的
11、初始值 dt1 = a =0时的判别式增量 dt2 = (a + b) 1; /d时的判别式增量 x=x0;y=y0; DrawPixel(x,y,color); /画起点 完整的中点法算法描述 29 while(x 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; 完整的中点法算法描述 30 d = (a1) + b; /判别式的初始值 dt1 = a 0时的判别式增量 dt2 = (a + b) 1; /d0时的判别式增量 x=x0;y=y0; DrawPixel(x,y,color); /画起点 while(y y1) if ( d 0) y+; x += step; d += dt2; else y+; d += dt1; DrawPixel(x, y, color); /End of while /End of if 完整的中点法算法描述 312014-2015-1:CG:SCUEC
