算法原理如下:过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂 直网格线的交点,然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算,使得 对于每一列,只要检査一个误差项的符号,就可以确定该列的所求象素。 如下图所示。设直线方程为)=y+k(x- 其中k=dydx。假设x列的象素已经 确定为X,其行坐标为y。那么下一个象素的列坐标为x+1,而行坐标要么不变为y,要么递增1为y+1 是否增1取决于如图所示误差项d的值。因为直线的起始点在象素中心,所以误差项d的初值d0=0。X 下标每增加1,d的值相应递增直线的斜率值k,即d=d+k。一旦￠l,就把它减去1,这样保证d在0、 1之间。当￠0.5时,直线与X+1列垂直网格交点最接近于当前象素(x,y)的右上方象素(X+1,y +1);而当d<0.5时,更接近于右方象素(x+1,y)。为方便计算,令e=d-0.5,e的初值为-0.5, 增量为k。当e≥0时,取当前象素(X,y)的右上方象素(x+1,y+1):而当e<0时,更接近于右方 象素(X+1,y)。 图21.4 Bresenham算法所用误差项的几何含义 Bresenham画线算法程序: void Bresenhamline(int Xo, int yo, int XI, int yi, int color) I int x, y, dx, dy: float k. e dx =XrXo, dy= yr-yo, k=dy/dx e=-0.5, X=Xo, y=yo for(=0;k≤dx;++) i drawpixel (x, y, color) X=X+1, e=e+k. y++,e=e-1} 举例:用 Bresenham方法扫描转换连接两点P0(0,0)和P1 (5,2)的直线段 10-0.1 21-0.7 31-0.3 42-0.9 52-0.5 上述 bresenham算法在计算直线斜率与误差项时用到小数01 与除法。可以改用整数以避免除法。由于算法中只用到误差项 的符号,因此可作如下替换:e=2*e*ax 改进的 Bresenham画线算法程序: void Inter Bresenhamline(int Xo, int yo, int XI, int yi, int color) dx= X -Xo, dy= yr-yo, e=-dx X-Xo, y=yo, idrawpixel(x, y, color if(e≥0){ 2d×} 计算机图形学第二章第20页共27页计算机图形学 第二章 第 20 页 共 27 页 算法原理如下：过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂 直网格线的交点，然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算，使得 对于每一列，只要检查一个误差项的符号，就可以确定该列的所求象素。 如下图所示。 设直线方程为 ，其中 k=dy/dx。 假设 x 列的象素已经 确定为 xi，其行坐标为 yi。那么下一个象素的列坐标为 xi＋1，而行坐标要么不变为 yi，要么递增 1 为 yi＋1。 是否增 1 取决于如图所示误差项 d 的值。因为直线的起始点在象素中心，所以误差项 d 的初值 d0＝0。X 下标每增加 1，d 的值相应递增直线的斜率值 k，即 d＝d＋k。一旦 d≥1，就把它减去 1，这样保证 d 在 0、 1 之间。当 d≥0.5 时，直线与 xi＋1 列垂直网格交点最接近于当前象素（xi，yi）的右上方象素（xi＋1，yi ＋1）；而当 d<0.5 时，更接近于右方象素（xi＋1，yi）。为方便计算，令 e＝d－0.5，e 的初值为－0.5， 增量为 k。当 e≥0 时，取当前象素（xi，yi）的右上方象素（xi＋1，yi＋1）；而当 e<0 时，更接近于右方 象素（xi＋1，yi）。 图 2.1.4 Bresenham 算法所用误差项的几何含义 Bresenham 画线算法程序： void Bresenhamline (int x0,int y0,int x1, int y1,int color) { int x, y, dx, dy; float k, e; dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0; for (i=0; i dx; i++) { drawpixel (x, y, color); x=x+1，e=e+k; if (e 0) { y++, e=e-1;} } } 举例：用 Bresenham 方法扫描转换连接两点 P0（0,0）和 P1 （5,2）的直线段。 x y e 0 0 -0.5 1 0 -0.1 2 1 -0.7 3 1 -0.3 4 2 -0.9 5 2 -0.5 上述 bresenham 算法在计算直线斜率与误差项时用到小数 与除法。可以改用整数以避免除法。由于算法中只用到误差项 的符号，因此可作如下替换： 改进的 Bresenham 画线算法程序： void InterBresenhamline (int x0,int y0,int x1, int y1,int color) { dx = x1-x0, dy = y1- y0, e=-dx; x=x0, y=y0; for (i=0; i dx; -e+) {drawpixel (x, y, color); x++, e=e+2*dy; if (e 0) { y++; e=e-2*dx;} } }