沿着"Bresenham线"进行线性插值

Question

我正在使用线性插值来在屏幕上的两个二维坐标之间进行对象动画。这已经非常接近我想要的效果，但由于四舍五入，我得到了一种锯齿状的运动。ASCII艺术如下：

ooo
  ooo
    ooo
      oo

注意它是如何按照曼哈顿网格行走的，而不是进行45度转弯。我想要的是沿着Bresenham算法所创建的线性插值：

oo
  oo
    oo
      oo

对于每个x，只有一个相应的y。(对于陡峭的线条，交换x/y)

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

我将尝试通过线性插值x坐标，将其舍入到像素网格，然后找到相应的y。(对于陡峭的线条，再次交换x/y)。不管这种解决方案如何，我都对其他建议和以前的经验感兴趣。

- Johannes Hoff

---

我认为你的四舍五入想法听起来是可行的。 - Neil

我不确定另一种舍入方式是否能解决这个问题。您真的需要将坐标舍入到像素网格吗？您用什么进行渲染？ - Qnan

@Qnan：是的，在这种情况下，我需要将其舍入到像素网格，因为我要粘贴图像。完美像素是唯一看起来好的东西。 - Johannes Hoff

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)

- Nico Schertler

---

您可能需要考虑到0.5的四舍五入会变成1，这在原则上是不公平的。结果是一条不对称的线。在某些情况下，您无法避免它（例如在连接2x3网格中的角点时），但在其他情况下，您可以避免它（例如在5x3网格中）。即使是标准的Windows绘图程序也会犯这个错误。解决方案可以是在线的中间切换0.5的四舍五入方向。 - Palo

如果一条线通过相邻两个像素的中间，就会出现.5。你不能唯一地决定其中一个（即一个不比另一个更正确）。向上取整只是一种约定，而不是错误。 - Nico Schertler

不，这在某些情况下是可以的，但在其他情况下会导致不对称的线条，看起来很丑陋。只需使用上述方法，您就可以获得更适合和更漂亮的线条呈现。毕竟这是计算机图形，所以是的，您可以为自己的约定感到自豪...并且看起来...丑陋。 - Palo

啊，现在我明白你的意思了。是的，那是一个有效的方法。 - Nico Schertler

Answer 2

这是我最终得出的解决方案：

public static Vector2 BresenhamLerp(Vector2 a, Vector2 b, float percent)
{
    if (a.x == b.x || Math.Abs(a.x - b.x) < Math.Abs(a.y - b.y))
    {
        // Didn't do this part yet. Basically, we just need to recurse
        // with x/y swapped and swap result on return
    }

    Vector2 result;
    result.x = Math.Round((1-percent) * a.x + percent * b.x);

    float adjustedPercent = (result.x - a.x + 0.5f) / (b.x - a.x);
    result.y = Math.Round((1-adjustedPercent) * a.y + adjustedPercent * b.y);

    return result;
}

- Johannes Hoff

Answer 3

这是我刚刚发现可行的方法。可能不是最美丽的插值，但每次迭代只需要在一条线上进行1-2个浮点数加法，并进行一次预计算。通过计算曼哈顿矩阵上的步数来工作。

啊，它还没有捕捉到线垂直（dx = 0）的情况

这是naive bresenham，但理论上迭代也可以只使用整数。如果你想摆脱浮点颜色值，事情会变得更难，因为线可能比颜色差异更长，所以delta-color < 1。

void Brepolate( uint8_t* pColorBuffer, uint8_t cs, float xs, float ys, float zs, uint8_t ce, float xe, float ye, float ze )
{
    float nColSteps = (xe - xs) + (ye - ys);
    float fColInc = ((float)cs - (float)ce) / nColSteps;
    float fCol = cs;

    float dx = xe - xs;
    float dy = ye - ys;

    float fCol = cs;

    if (dx > 0.5)
    {
        float de = fabs( dy / dx );
        float re = de - 0.5f;

        uint32_t iY = ys;
        uint32_t iX;

        for (   uint32_t    iX = xs;
                            iX <= xe;
                            iX++ )
        {
            uint32_t off = surf.Offset( iX, iY );
            pColorBuffer[off] = fCol;
            re += de;
            if (re >= 0.5f)
            {
                iY++;
                re -= 1.0f;
                fCol += fColInc;
            }
            fCol += fColInc;
        }
    }
}

- antipattern