绘制直线的光栅化算法

假设线段的两个端点为 (x_{0},y_{0})(x_{1},y_{1}) 假设x_{0}\leq x_{1}

于是直线方程可以用斜截式y=kx+b(其中k b已知)表示,从而对x进行遍历，根据方程得到实数点(x,y) 再四舍五入得到在光栅显示器的显示坐标 (round(x),round(y))

这样的算法是可以实现直线的光栅化的，而问题在于效率并不高。在遍历x计算y的时候使用的方程有一个乘法的存在(k*x)，而这会大大影响渲染效率。于是一场消灭乘法的智慧盛宴开始了。

考虑直线 y=kx+b 假设我们遍历横坐标x来在屏幕上画这条直线，也就是说我们每次向右前进一个像素，考虑在这个x坐标下的y是什么。

假设我们考虑完了点(x_{i},y_{i}) 这时我们看到(x_{i+1},y_{i+1})中有:

用二维数组模拟屏幕像素用DDA算法显示的一条线段

#include 
    #include 
    using namespace std; bool pic[50][50]; void DrawLine(int x0,int y0,int x1,int y1) { double k = (y1-y0)*1.0/(x1-x0); double y = y0; for(auto x = x0 ; x <= x1 ; ++ x) { pic[(int)round(y)][x] = true; y += k; } } void ShowPic() { for(auto i = 49 ; i >= 0 ; -- i) { for(auto j:pic[i]) { if(j) cout << 'x'; else cout << 'o'; } cout << endl; } } int main() { DrawLine(2,2,48,30); ShowPic(); return 0; }

但是显然我们需要更加完善的算法，现在有两个问题：

至于第2点的效率问题，虽然我们已经把乘法变成了加法，但是这是一个浮点数的加法。虽然现代计算机都有协处理器来计算浮点数，但和整数加法效率想想也知道是没法比的。幸运的是人类的智慧没有在此止步，采用整数加法的直线光栅化算法很快便由 Jack E. Bresenham 发明了。

怎么看一点(x_{0},y_{0})在一个一般式Ax+By+C=0的上方还是下方(或是在线上)呢？结论是将点坐标代入式B(Ax_{0}+By_{0}+C)中，和0比较。若式子等于0，则点在直线上，若式子大于0则在直线上方，小于0则在直线下方。 这其实是一个很简单的结论，但是问过的人包括一些老师绝大多数都把这点搞错了。

考虑斜率属于(0,1)的情况。假设现在我们画完了点(x_{i},y_{i})，那么下一个点必然画在(x_{i}+1,y_{i})或者(x_{i}+1,y_{i}+1)。那么我们不妨画在那个最接近原始直线的点。我们考虑两个点的中点(x_{i}+1,y_{i}+0.5)在直线上方还是下方，从而确定应该画哪个点。如果中点在直线上方，那么显然应该画点(x_{i}+1,y_{i})，反之画点(x_{i}+1,y_{i}+1)。

伪代码

y = y0 foreach x in (x0,x1): draw(x,y) if(B*(A*(x+1)+B*(y+0.5)+C) < 0) ++y;//中点与下面的点同侧，所以画上面的点

下面考虑:

• 如果下一个点画在了(x_{i}+1,y_{i}+1),紧接着考虑的应该是中点M_{1}(x_{i}+2,y_{i}+1.5)，代入直线一般式方程得到d_{1} = F(x_{i}+2,y_{i}+1.5)=A(x_{i}+2)+B(y_{i}+1.5)+C = A(x_{i}+1)+B(y_{i}+0.5)+C+A+B=d_{0}+A+B
• 如果下一个点画在了(x_{i}+1,y{i})考虑的应该是中点M_{2}(x_{i}+2,y_{i}+0.5)，代入直线一般式方程得到d_{2}=F(x_{i}+2,y_{i}+0.5)=A(x_{i}+2)+B(y_{i}+0.5)+C = A(x_{i}+1)+B(y_{i}+0.5)+C+A=d_{0}+A

于是我们得到了关于d的递推公式

d_{new}=d_{old}+A+B(B*d<0时)

d_{new}=d_{old}+A(B*d>=0时)

这时，我们的中点画线算法至少达到了和DDA算法一样的效率(浮点数加法)。但是这里的A和B都是整数，所以我们考虑把d全部扩大一倍(因为和0比较不影响)，这样2d_{0}=2A+B，成功避开了浮点数加法。

使用中点画线法模拟生成的直线:

#include 
    #include 
    using namespace std; bool pic[50][50]; void DrawALine(int x0,int y0,int x1,int y1) { int d = 2*(y0-y1)+(x1-x0);//这里的d为实际上d的两倍 int y = y0; for(auto x = x0 ; x <= x1 ; ++ x) { pic[y][x] = true; if(d < 0) { d += 2*(y0-y1)+2*(x1-x0); ++ y; } else d += 2*(y0-y1); } } void ShowPic() { for(auto i = 49 ; i >= 0 ; -- i) { for(auto j:pic[i]) { if(j) cout << 'o'; else cout << 'x'; } cout << endl; } } int main() { DrawALine(2,2,45,20); ShowPic(); return 0; }

至此，中点画线算法已经把直线光栅化的效率推至极限(整数加法)。Bresenham算法在此基础上，扩展了中点画线算法的适用范围。

d = 0 y = y0 ／／在此根据不同的方程处理好k的值 foreach x in (x0,x1) draw(x,y) d += k if(d>=1) d -= 1; if(d > 0.5) ++y;

这样算法的效率是浮点数加法，下面改进成整数加法。

• 首先可以将d与0.5比较(浮点数比较)进行优化
  令e = d-0.5，这样e的初始值变成0.5，并且当e>=0.5时将e-=1。这样只需要看e的符号就可以知道画在哪个像素上了。
  
  
• 从上一点继续考虑
  既然我们只用到了e的符号，那么也可以用2e\Delta x做到这一点。所以现在e的初始值为-\Delta x，又因为k=\Delta y/\Delta x 所以每次加k就是加2\Delta y。如果大于\Delta x那么就减去2\Delta x。
  
  

#include 
    #include 
    using namespace std; bool pic[50][50]; void DrawALine(int x0,int y0,int x1,int y1) { int dx = fabs(x0-x1); int dy = fabs(y0-y1); int y = y0; int e = -2*dx; for(auto x = x0 ; x <= x1 ; ++ x) { pic[y][x] = true; e += 2*dy; if(e > 0) ++y; if(e >= dx) e -= 2*dx; } } void ShowPic() { for(auto i = 49 ; i >= 0 ; -- i) { for(auto j:pic[i]) { if(j) cout << 'x'; else cout << 'o'; } cout << endl; } } int main() { DrawALine(2,2,40,10); ShowPic(); return 0; }

从代码可以看到效率是整数加法的。Bresenham算法总结了DDA算法和中点画线算法的优点，应用更加广泛。

至此，几种最基本的直线光栅化算法就介绍完了。直线光栅化是构造所有图形的基础，效率也极大程度影响渲染效率。

原文链接