Bresenham直线算法与朴素向量加法

Question

假定xlen是delta-x，ylen是delta-y，len是行的长度，为什么这段代码是：

//Bresenham implementation
float x = x0, y = y0;

if (slope < 1) {
    while (x < xlen) {
        paintpt(x, y));
         x += step;
        if (left.y > right.y) 
            y += slope * step;
        else 
            y -= slope * step;
   }
}

有比这段代码更高效的吗？

//Naive vector addition
int x = x0, y = y0;
float xinc = xlen / len, yinc = ylen / len;

for (float i = 0; i < len; i++) {
   paintpt(x, y);
   x += i * xinc;
   y += i * yinc;
}

(我的意思是，除了初始化之外，很明显。假设你只得到了线的长度和方向，并且不得不退出斜坡之类的东西。)

Answer 1

1) x += i * xinc; --这是一个浮点数乘法，四舍五入为整数。它并不能保证从启动x到最终的x都会遍历所有的整数。这意味着你的线上可能有洞。

2) Bresenham的实现是错误的。您不向x添加步骤。在每次迭代时增加x，并将delta_y添加到错误计数器。当错误计数器大于delta_x时，可以从错误计数器增加y和减法delta_x。

这是对delta_y大于0且低于delta_x的行的解释。对所有其他情况进行轮换。

3)效率:这有点棘手。最老的计算机不能轻易地进行浮点计算。直到奔腾之前，通常没有任何x87协处理器，所有浮点计算都是在软件中完成的。这比做简单整数算法慢1000倍。如今，所有的计算机都可以进行SIMD操作(例如，它们使用浮点向量扩张)；现在可能不再是这种情况了。

Answer 2

Bresenham算法起源于60年代，那时计算机可以放进大壁橱里。其特点是：

• 没有浮点数的数学，
• 没有乘法/除法。

因为在那些日子里，即使整数除法和乘法也是“昂贵的”。“真”Bresenham实现不会被除法/乘，也不会使用浮点运算。您的实现是“错误的”。检查这里是否为“真”。