algorithm - 沿 "Bresenham line"的线性插值

Question

我正在使用线性插值来为屏幕上两个二维坐标之间的对象设置动画。这与我想要的非常接近，但由于四舍五入，我得到了锯齿状的运动。在 ASCII 艺术中:

ooo
  ooo
    ooo
      oo

注意它如何在曼哈顿网格中行走，而不是转 45 度。我想要的是沿线的线性插值 Bresenham's algorithm会创建:

oo
  oo
    oo
      oo

对于每个x，只有一个对应的y。 (并将 x/y 换成陡峭的线)

那我为什么不直接使用 Bresenham 算法呢？我当然可以，但该算法是迭代的，我只想知道沿直线的一个坐标。

我将尝试通过对 x 坐标进行线性插值，将其舍入到像素网格，然后找到相应的 y 来解决此问题。 (同样，将 x/y 换成陡峭的线条)。不过，无论该解决方案的结果如何，我都会对其他建议和以前的经验感兴趣。

Answer 1

Bresenham 的线条算法的引入是为了比通常的方法更快地绘制一条完整的线条。它有两个主要优点:

• 它适用于整数变量
• 它在绘制完整的线时迭代工作，速度很快

第一个优势不是很大，如果你只计算一些坐标的话。当只计算一些坐标时，第二个优点变成了缺点。所以毕竟没有必要使用Bresenham算法。

相反，您可以使用不同的算法，结果是同一行。例如 DDA(数字差分分析仪)。这基本上与您提到的方法相同。

第一步:计算斜率。

m = (y_end - y_start) / (x_end - x_start)

第二步:计算迭代步长，简单来说就是:

i = x - x_start

第三步:计算对应的y值:

y = y_start + i * m
  = y_start + (x - x_start) * (y_end - y_start) / (x_end - x_start)