基本光栅图形算法--直线的扫描转换(I).ppt

2007-2008-2:CG:SCUEC 基本光栅图形算法--直线的扫描转换(I) 2006-2007-2:CG:SCUEC 主要内容 生成直线的基本增量算法 原理，实现 生成直线的中点法* 原理，实现 生成直线的Bresenham算法 原理，实现 改进的Bresenham算法（二步法） 原理，实现 2006-2007-2:CG:SCUEC 在计算机屏幕上画一条直线和在纸上画一条直线有什么本质的区别? 光栅显示器:画点设备，有限的象素矩阵 基本知识 这里的直线实际上为直线段 画一条从（x1, y1）到（x2, y2）的直线，实质上是一个发现最佳逼近直线的象素序列 只有画水平线,垂直线,及正方形对角线时,象素点集的位置才是准确的 A(x1,y1)、 B(x2,y2)、 2006-2007-2:CG:SCUEC 生成直线算法的基本要求(2-1) 能不能直接用数学公式画直线段？ A(x0,y0) B(x1,y1) void 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); ? o x y k1 (xi,yi) (xi+1,yi+1) 讨论： 容易造成隔行显示 算法复杂度高，运算速度慢 2006-2007-2:CG:SCUEC 生成直线算法的基本要求(2-2) 直接用数学公式画直线段有缺陷 直线不直 直线可能出现间断 用硬件实现困难 生成直线算法的基本要求 线段上点的浓度要均匀，即象素是均匀分布的 所画的线应是直的，并且两个端点要准确 所显示的亮度应沿直线不变，且与直线的长度和方向无关 最后直线的生成速度要快 2006-2007-2:CG:SCUEC 基本增量算法 作为最底层的光栅图形算法，直线算法在通常的CAD/图形系统中，会被大量应用，因此，哪怕节约一个加法或减法，也是很了不起的改进。 由此出发点，导致增量算法的思想。 如果在一个迭代算法中，每一步的x值和y值都可以由前一步的的值加一个增量得到，那么这种算法就称为增量算法。如 x从最左端开始，每次递增一个?x ，y递增一个?y, 即xi+1=xi+ ?x, yi+1=yi+ ?y 最基本的增量算法是DDA算法 数值微分分析器（Digital Differential Analyzer） DDA算法的本质是用数值方法解直线的微分方程 2006-2007-2:CG:SCUEC 生成直线的DDA算法（2－1） 设直线的起点坐标为(x0 , y0)，终点坐标为(x1 , y1)，令?x = x1 – x0， ?y = y1 - y0，则直线微分方程为: 该方程的数值解的递推公式为 xi+1 = xi + ?x ?t (?t 表示步长） yi+1 = yi + ?y ?t 2006-2007-2:CG:SCUEC 如果取 ?t=1/?x，我们有： xi+1 = xi + 1 yi+1 = yi + k 即x方向每次增加1，y方向增加k(直线的斜率)； 生成直线的DDA算法（2－2） 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; ? 2006-2007-2:CG:SCUEC 例子 例：画直线段 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 1 3 1.2+0.5 1 4