「图形学」直线扫描——Bresenham算法改进了中点Bresenham算法?

时间:2022-06-11 09:51:43

前言

博主目前在学习《计算机图形学基础》这本书,使用的是第二版。

此书第五章开始讲解基本图形生成算法。

在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;
}

 

结论

这两种算法等价,并没有高低之分,更没有所谓改进