计算机图形学计算机图形学专专 业业 计算机科学与技术计算机科学与技术 班班 级级 09010901 学学 号号 20091150101022009115010102 姓姓 名名 张聪张聪 时时 间间 2012.06.52012.06.5 湖湖 北北 师师 范范 学学 院院计计 算算 机机 科科 学学 与与 技技 术术 学学 院院直线的生成算法直线的生成算法一、实验目的：一、实验目的：通过本次实验掌握各种直线生成算法的基本原理和算法设计（包括 Bresenham 算法，中点画线法及 DDA 生成直线画法） 。二、算法介绍：二、算法介绍：1、Bresenham 算法算法本算法由 Bresenham 在 1965 年提出。设直线从起点（x1, y1）到终点（x2, y2） 。 直线可表示为方程 y=mx+b。其中 b = y1 - m * x1, 我们的讨论先将直线方向限于 1a 象限（图 2.1.1）在这种情况下，当直线光栅 化时，x 每次都增加 1 个单元，即 xi+1=xi+1 而 y 的相应增加应当小于 1。为了光栅化，yi+1 只可能选择如下两种位置之一 （图 2.1.2） 。图 2.1.2 yi+1 的位置选择 yi-1=yi 或者 yi+1=yi+1 选择的原则是看精确值 y 与 yi 及 yi+1 的距离 d1 及 d2 的大小而定。计算式为：y=m(xi+1)+b (2.1.1) d1=y-yi (2.1.2) d2=yi+1-y (2.1.3) 如果 d1-d20，则 yi+1=yi+1，否则 yi+1=yi。因此算法的关键在于简便地求出 d1-d2 的符号。将式（2.1.1） 、 （2.1.2） 、 （2.1.3）代入 d1-d2，得用 dx 乘等式两边，并以 Pi=dx(d1-d2)代入上述等式，得Pi=2xidy-2yidx+2dy+dx(2b-1) (2.1.4) d1-d2 是我们用以判断符号的误差。由于在 1a 象限，dx 总大于 0，所以 Pi 仍旧 可以用作判断符号的误差。Pi+1 为： Pi+1=Pi+2dy-2dx(yi+1-yi) (2.1.5) 误差的初值 P1，可将 x1, y1，和 b 代入式（2.1.4）中的 xi, yi 而得到： P1=2dy-dx 综述上面的推导，第 1a 象限内的直线 Bresenham 算法思想如下：1、画点(x1, y2); dx=x2-x1; dy=y2-y1； 计算误差初值 P1=2dy-dx; i=1； 2、求直线的下一点位置： xi+1=xi+1； if Pi0 则 yi+1=yi+1； 否则 yi+1=yi； 3、画点（xi+1, yi-1） ； 4、求下一个误差 Pi+1； if Pi0 则 Pi+1=Pi+2dy-2dx; 否则 Pi+1=Pi+2dy； 5、i=i+1; if i0，M 在 L(Q 点)上方，取右方 P1为下一个象素； 当 d=0，选 P1或 P2均可，约定取 P1为下一个象素； 但这样做，每一个象素的计算量是 4 个加法，两个乘法。 d 是 xp, yp的线性函数，因此可采用增量计算，提高运算效率。 若当前象素处于 d0 情况，则取正右方象素 P1 (xp+1, yp), 要判下一个象素 位置，应计算 d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a； 增量为 a。 若 d0 时，则取右上方象素 P2 (xp+1, yp+1)。要判断再下一象素，则要计算 d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ；增量为 ab 3、DDA 生成直线画法生成直线画法0101 xxyyk已知过端点 的直线段 L：y=kx+b,直线斜率为从 x 的左端点 开始，向 x 右端点步进。步长=1(个象素)，计算相应的 y 坐 标 y=kx+b；取象素点(x, round(y)作为当前点的坐标。三、实验小结三、实验小结通过本次学习掌握了各种直线生成算法的基本原理和算法设计（包括 Bresenham 算法，中点画线法及 DDA 生成直线画法） 。对老师上课讲的内容有 了更加深入的理解。但在一些具体的问题上还存在不熟悉的地方，希望在今后 的学习中有所改善。),(),(111000yxPyxP0x