前言
博主目前在学习《计算机图形学基础》这本书,使用的是第二版。
此书第五章开始讲解基本图形生成算法。
在5.1.3 Bresenham算法中,如是写到:
虽然中点Bresenham算法是一种效率非常高的算法,但也还有改进的余地。
而后,开始介绍Bresenham算法。
思考
然而通过学习和理解,博主发现这两种算法的原理完全相同:
每次在最大位移方向上走一步,而另一个方向上走步还是不走步取决于误差项的判别。
于是博主产生了疑问:
Bresenham算法真的改进了中点Bresenham算法吗?
如果是,到底改进了哪里?
分析
博主认为
两种算法核心均是在寻找最接近实际值的格点
均是以格点的二分之一处为分界线
均是逐位依次扫描
思维以及处理方式不同
所以猜测
这两种算法等价,并没有高低之分,更没有所谓改进
证明
博主在此提供的是证明其编程代码等价,由此说明两种算法在效率上是完全一致的。
中点Bresenham
void MidBresenhamLine(int x0, int y0, int x1, int y1) { int dx, dy; int d, UpIncre, DownIncre; int x, y; if(x0 > x1) { x = x1; x1 = x0; x0 = x; y = y1; y1 = y0; y0 = y; } x = x0; y = y0; dx = x1 - x0; dy = y1 - y0; d = dx - 2 * dy; UpIncre = 2 * dx - 2 * dy; DownIncre = -2 * dy; while(x <= x1) { putpixel(x, y);
x++; if(d < 0) { y++; d += UpIncre; } else { d += DownIncre; } } }
Bresenham
void BresenhamLine(int x0, int y0, int x1, int y1) { int dx, dy; int e; int x, y; if(x0 > x1) { x = x1; x1 = x0; x0 = x; y = y1; y1 = y0; y0 = y; } dx = x1 - x0; dy = y1 - y0; x = x0; y = y0; e = -dx; while(x <= x1) { putpixel(x, y);
x++; e = e + 2 * dy; if(e > 0) { y++; e = e - 2 * dx; } } }
两段代码在迭代计算x、y的部分:
x++; if(d < 0) { y++; d += UpIncre; } else { d += DownIncre; }
x++; e = e + 2 * dy; if(e > 0) { y++; e = e - 2 * dx; }
令e = –a - 2 * dy ,此时 初始化 a = dx – 2 * dy
后者代入得:
x++; a = a - 2 * dy; if(a < -2 * dy) { y++; a = a + 2 * dx; }
令a = d - 2 * dy , 此时,初始化 d = dx
x++; d = d - 2 * dy; if( d < 0) { y++; d = d + 2 * dx; }
此时,使初始化 d = dx – 2 * dy
代码块等价变换得
x++; if( d < 0) { y++; d = d + 2 * dx; } d = d - 2 * dy;
又可变换为
x++; if( d < 0) { y++; d = d + 2 * dx; d = d - 2 * dy; } else { d = d - 2 * dy; }
很容易看出该代码块与中点Bresenham算法的核心代码块完全等价
x++; if(d < 0) { y++; d += UpIncre; } else { d += DownIncre; }
结论
这两种算法等价,并没有高低之分,更没有所谓改进