DDA法

已知过端点P0（x0, y0）, P1 (x1, y1)的直线段； 直线斜率k = (y1-y0) / (x1-x0) .

画线过程为： 从x的左端点x0开始，向x右端点 步进，步长=1（像素），按y=k x + b 计算相应的y坐标，并去像素点（x, round (y) ）作为当前点的坐标。

可以提高效率：

设步长为Δx， 有x i+1 = xi +Δx, 于是： yi+1=kxi+1 +b = kxi + kΔx +b= yi +kΔx

当Δx=1时， 有yi+1 = yi +k 。 这样计算每一点，只需做一次加法运算。

note:

round (y) = int (y+0.5)， 当K>1时，必须把x, y的地位互换：y增加1，x相应增加1/k。

缺点：由于y与k须用浮点数表示，每一步都要对y进行四舍五入后取整，使得该算法不利于硬件实现。

改进 

目标：进一步将一个加法改为一个整数法加。

中点画线法：

通过观察发现，在画线段的过程中，当前像素点为（xp, yp），下一个像素点有两种选择P1（xp+1, yp）和P2（xp+1, yp+1）。若M=（xp+1, yp+0.5）为P1和P2之间中点。Q为理想直线与x = xp +1垂线的交点。 则当M在Q的下方时，P2为下一个像素点；当M在Q的上方时，应取P1为下一点。（如下图）

对直线段L（p0（x0, y0）, p1(x1, y1) ），采用方程

F (x, y ) = ax+by+c = 0 表示，其中 a = y0 – y1,

b = x1 - x0 ,  c = x0y1 – x1y0

于是有

 线内： F (x, y) = 0

上方： F (x, y) > 0

下方： F (x, y) < 0

要判断M在Q点上方还是下方，只要把M点坐标代入F(x, y)，并判断符号即可。

即判断 d = F(M) = F（xp+1, yp+0.5）= a (xp+1)+ b (yp+0.5) + c 的符号

d是xp, yp的线性函数，为提高计算效率，可以采用增量计算。

l       若d>=0，则取正右方象素P1 (xp+1, yp), 要判断下一个象素，应计算

     d1= F(xp +2, yp +0.5)=a (xp+2)+ b (yp+0.5) + c = d + a； 增量为a

l       若d<0，则取右上方象素P2 (xp+1, yp +1)。要判断再下一象素，应计算

     d2= F(xp +2, yp +1.5)=a (xp+2)+b (yp+1.5) + c= d + a + b ；增量为a＋b

设从点（x0, y0）开始画线，d的初值d0 = F (x0+1, y+0.5) = F ( x0, y0 ) + a + 0.5b.

F ( x0, y0 ) = 0, 则 d0 = a + 0.5 b

进一步，由于d的增量都是整数，只有初始值包含小数，可以用2d代替d来摆脱浮点运算。 这是不影响符号判断的。

Bresenham算法

Bresenham算法类似于中点法，由误差项符号决定下一个像素取右边点还是右上点。

算法原理：

设直线方程为 y = kx +b, 则有 yi+1= yi + k (xi+1 – xi) = yi + k .

设x列的坐标为（xi, yi）, 那么下一个像素的列坐标为xi+1,

而行坐标要么仍为yi，要么递增1为yi+1。

是否增1取决于误差项d的值（如上图）

d的初值为0.

x下标每增加1，d的值相应增加k.

当d≥0.5时，直线与xi+1列的交点更接近于

像素（xi +1, yi +1），即该像素在y方向递增1.

同时作为下一次计算的基点，因此d值减1.

当d<0.5时，交点更接近于像素（xi +1, yi）。

为方便计算，令e = d - 0.5, e的初值为-0.5. 增量为k.

void Bresenhamline (int x0,int y0, int x1, int y1, int color) 
/**//* 起点(x0, y0) 终点（x1, y1）*/ 
{ 
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画线法程序

void IntegerBresenhamline (int x0,int y0, int x1, int y1, int color) 
/**//* 起点(x0, y0) 终点（x1, y1）*/ 
{ 
int x, y, dx, dy, e; 
dx = x1-x0,  dy = y1- y0,  e = -dx; 
 x=x0, y=y0; 
for (i=0; i <= dx; i++){   
drawpixel (x, y, color); 
x=x++，e=e+2*dy; 
if (e >= 0 ){ y++, e = e - 2*dx; } 
} 
}