计算机图形学中Bresenham画线算法的一种优化算法
计算机图形学中Bresenham画线算法的一种优化算法
三角形的相似定理：两边共线，第三边平行的三角形是相似三角形，对应边是成比例的，且相似比都等于高h1和h2之比。
优化的Bresenham算法的基本思想是，将每一个像素点处的小浮点数计算，乘以一个倍数，使得每一步的计算都只有整数计算。
设dx,dy皆为常量，是线段横坐标的变化量和纵坐标的变化量。不失一般性，设dx>dy，且起点是在某一像素点的精确位置处，像素长度为1，接下来需要判定下一个像素点的位置，这种情况下我们每次总是令横坐标x+1，考察下一个像素点的纵坐标y是否需要加1。
传统Bresenham算法，实际上是比较线段与像素分割线交点在一个像素的上半边还是下半边，也就是直接比较图中黄色部分和蓝色部分哪个更长，从而确定下一个像素点的纵坐标是否需要加1。这种长度必定是小于1的，并且是浮点数，不利于计算。
改进后的Bresenham算法，是将原来单个像素内的比较，扩大到整个线段长度上来。如上图中所示，去比较扩大后的黄色部分和蓝色部分哪个更长。如果把线段横坐标变化量记作dx，把纵坐标变化量记作dy的话，根据相似三角形定理，黄色部分的扩大倍数等于蓝色部分的扩大倍数，等于每对三角形的高的扩大倍数，也就是dx倍。这样，我们只需要比较dx-dy与dy的长度，也就是比较dx/2与dy的长度。如果dx/2<dy，也就是上图中的情况，那么就判定下一个像素的纵坐标需要加1。
但是，当需要决定下一个像素点的位置时，我们无法再像前一个点那样在对齐像素网格的情况下使用扩大倍数的方法了。因此我们平移该线段，使其经过上一次已确定的像素格点，这样我们就又能利用相似三角形的关系进行扩大再运算了，只是这次的运算稍有不同。
我们可以在上图中发现在一个大的灰色三角形中，有若干相似三角形的存在。其中较深一些的那根线段就是我们为了对齐像素格点而作的辅助线段，它是原线段沿x轴和y轴正方向平移一个单位长度后的线段。平移不改变dx和dy，所以大灰色三角形内相似三角形的扩大倍数依然是dx。现在要想判断下一像素点的位置，只需判断黄色部分加蓝色部分，与绿色部分，哪个大哪个小。实际上就是判断扩大后的黄色部分加蓝色部分，与扩大后的绿色部分，哪个大哪个小。也就是判断如果dx/2，比扩大后的绿色部分小的话，下一个像素点的纵坐标就要加1。
从扩大后的三个部分来看，扩大后的绿色部分的值就是平移后的深灰色线段的dy减去扩大后的蓝色部分，也就是原线段的dy减去扩大后的蓝色部分。那么判定下一像素点纵坐标是否加1的条件就是dx<dy - 扩大后蓝色部分。我们把蓝色部分就叫做err。那么之后的像素点纵坐标加1判断就以此类推，流程是：平移线段到上次确定的像素格点-> 求 dy-err-> 与dx/2对比 -> 决定下一像素点纵坐标是否加1。
需要注意的是err这个量的产生原因。我们看到上图中扩大后的蓝色部分err除以扩大倍数dx，就是小的蓝色部分，小蓝色部分的长度就是err/dx。小的蓝色部分恰好是平移后线段与原线段的纵截距差。也就是说，err是由平移线段相对于原线段的纵截距造成的。
实际上我们在每次递推运算的时候，只有第一次平移是基于原线段的，之后并不是从原线段平移出一个线段，而是在上次平移线段的基础上，向下一个确定好的像素点平移。这样，如果要计算当前偏移线段与原线段的纵截距差err/dx，就要先计算本次偏移线段与上次偏移线段的纵截距差，再加上上次偏移线段与原线段的纵截距差，即err/dx要累加起来才是当前偏移线段与原线段的纵截距差，等价于err也要累加。
那么为什么每次原线段都平移到上次确定的像素格点呢？其实平移到其他的格点作辅助线也是可以的，只不过平移到上次确定的格点后，就恰好能通过格点的移动知道本次的偏移量，有利于进行递推运算。
那么每次平移辅助线段之后，造成的这个截距差的变化是多少呢？算出累加后的截距差，也就算出了err，也就可以决定下一像素点纵坐标是否加1了。
考察直线方程：
y = k * x + b, k = dy/dx
变换成一般式，即：
dy * x – dx * y + C = 0, C = dx * b
注意dx,dy皆为常量，是线段横坐标的变化量和纵坐标的变化量，与上文相符。
横坐标正向平移一个单位长度的直线方程：
dy * x – dx * y + C + err= 0
其中，err = -dy，转换为纵截距差的形式：
y = k * x + b + (err/dx) , k = dy/dx
可见线段平移后，纵截距差恰好是上文中所述的err/dx，而且我们计算出了横坐标平移一个单位长度后，err =-dy，纵截距差也就可以计算出来了。
同理，横坐标正向平移一个单位长度的直线方程：
dy * x – dx * y + C + err= 0
其中，err = +dx。
到此，在每一步判定流程中未知的err也计算出来了，此时根据上文叙述的相似三角形原理即可通过dx<dy– err来判定下一点的纵坐标是否加1。注意，我们现在一直在讨论的是dx>dy的情况，dx<dy的情况类似可证。
程序如下：
voidline(int x0, int y0, int x1, int y1) {
int dx = abs(x1-x0), sx = x0<x1 ? 1 : -1;
int dy = abs(y1-y0), sy = y0<y1 ? 1 : -1;
int err = (dx>dy ? dx : -dy)/2, e2;
for(;;){
setPixel(x0,y0);
if (x0==x1 && y0==y1) break;
e2 = err;
if (e2 >-dx) { err -= dy; x0 += sx; }
if (e2 < dy) { err += dx; y0 += sy; }
}
}
当dx>dy时，是否会出现程序中{ err-= dy; x0 += sx; }一行不被执行的情况？也就是说程序中不执行x+1？
设想极端情况，err已经接近-dx但大于-dx，执行err -=dy;，此时一定满足if (e2< dy)，则err +=dx;，由于dx>dy，此时err恢复到大于-dx。实际上算法的巧妙也在这里。
最后，感谢我的同门赵兄，上文所述皆基于他的想法。