1

给定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;
}

（我的意思是，除了初始化之外，显然。假设你只得到了线的长度和方向，并且必须退出斜坡等等。）

4

2 回答 2

5

Bresenham 算法起源于 60 年代，当时计算机可以装进大壁橱。它的标志是/是：

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

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

于 2013-09-18T09:25:55.943 回答
3

1)x += i * xinc;这是一个四舍五入为整数的浮点乘法。它不能保证您从开始x到最终遍历所有整数x。这意味着您的线路可能有孔......

2）您的 Bresenham 实施是错误的。您不向x. x您在每次迭代中递增并添加delta_y到错误计数器。当错误计数器大于delta_x您从错误计数器中递增y和减去delta_x时。

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

3）为了效率：这有点棘手。最古老的计算机无法轻松进行浮点计算。在 Pentium 之前，通常没有任何 x87 协处理器，所有浮点计算都是在软件中完成的。这比做简单的整数运算要慢 1000 倍。现在所有的计算机都可以进行 SIMD 操作（即它们使用浮点向量扩展）；情况可能不再如此。

于 2013-09-18T07:57:17.463 回答