002计算机图形学之直线画线算法
我们知道直线方程的斜截式是如下的样子:
y = kx +b
在显示器上显示直线的话,如果使用如上的方程,每描一个点
对斜截式进行转换成如下:
$y_{k+1}=y_{k}+m$
由此我们可以根据起点依次推算到最后一个点,实现如下:
inline int round(const float a) { return int(a + 0.5); }
void lineDDA(int x0, int y0, int xEnd, int yEnd)
{
int dx = xEnd - x0, dy = yEnd - y0, steps, k;
float xIncrement, yIncrement, x = x0, y = y0;
if (fabs(dx) > fabs(dy))
steps = fabs(dx);
else
steps = fabs(dy);
xIncrement = float(dx) / float(steps);
yIncrement = float(dy) / float(steps);
//SetPixel(round(x), round(y));
for (k = 0; k < steps; k++) {
x += xIncrement;
y += yIncrement;
//SetPixel(round(x), round(y));
}
}
取消了乘法,计算速度更快。
主要思想是,由于我们在缓存区上画点,全部是整数。那么在画线的时候,当斜率k小于1的时候,下一个点是取(x+1,y+1)还是(x+1,y)取决于点(x+1,y+0.5)是在该直线的上方或者下方,从而将可以通过判断一个参数的的符号来得到下一个点的位置,提高了代码的效率。
算法可以表达为如下:
|m|<1 时的Bresenham画线算法
考虑到xy平面各种八分和四分区域的对称性,此算法对任意斜率的线段具有通用性。