0

我有一个程序，它使用Bresenham 的线算法来扫描一行中的像素。这是读取像素而不是写入像素，在我的特定情况下，读取它们的成本很高。

但是，我可以确定不需要读取某些像素范围。它看起来像这样：

Normal scan of all pixels:

*start
 \
  \
   \
    \
     \
      *end

Scan without reading all pixels:

*start
 \
  \
        - At this point I know I can skip (for example) the next 100 pixels
          in the loop. Crucially, I can't know this until I reach the gap.
     \
      *end

中间的间隙要快得多，因为我可以遍历像素而不读取它们。

但是，我可以以任何方式修改循环，直接在循环内向前跳转 100 个像素，直接在行算法中提前 100 步计算所需的值吗？

4

2 回答 2

0

你的主循环看起来基本上是这样的：

  while (cnt > 0) // cnt is 1 + the biggest of abs(x2-x1) and abs(y2-y1)
  {
    ReadOrWritePixel(x, y);

    k += n; // n is the smallest of abs(x2-x1) and abs(y2-y1)
    if (k < m) // m is the biggest of abs(x2-x1) and abs(y2-y1)
    {
      // continuing a horizontal/vertical segment
      x += dx2; // dx2 = sgn(x2-x1) or 0
      y += dy2; // dy2 = sgn(y2-y1) or 0
    }
    else
    {
      // beginning a new horizontal/vertical segment
      k -= m;
      x += dx1; // dx1 = sgn(x2-x1)
      y += dy1; // dy1 = sgn(y2-y1)
    }

    cnt--;
  }

因此，跳过一些 q 像素相当于进行以下调整（除非我在某处犯了错误）：

  • cnt new = cnt old - q
  • k新= (k旧+ n * q) % m
  • x新= x旧+ ((k旧+ n * q) / m) * dx1 + (q - ((k旧+ n * q) / m)) * dx2
  • y新= y旧+ ((k旧+ n * q) / m) * dy1 + (q - ((k旧+ n * q) / m)) * dy2

请注意，/ 和 % 是整数除法和模运算符。

于 2013-03-08T14:31:06.590 回答
0

Bresenhams 中点算法通过将数字差delta_x = (by-ay)、delta_y = (ax-bx)相加来计算点与从 (ax,ay)->(bx,by) 的理论线的“距离” 。

因此，如果要跳过 7 个像素，则必须添加 accum += 7*delta_x; 然后除以 delta_y 可以检查应该在 y 方向上移动多少像素并取余数 accum = accum % delta_y 一个应该能够继续在正确的位置。

好消息是该算法源于避免除法的必要性......

免责声明：任何告诉可能需要调整半增量。

于 2013-03-08T14:08:20.310 回答