沿"Bresenham line"的线性插值

Question

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

ooo
  ooo
    ooo
      oo

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

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)

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

Answer 3

这就是我刚刚发现的可行方法。可能不是最漂亮的插值，但它只是在一次预先计算的情况下，每次迭代增加1-2个浮点值。通过计算曼哈顿矩阵上的步数来工作。

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

这是幼稚的bresenham，但迭代在理论上也只能使用整数。如果你想去掉float颜色值，事情会变得更困难，因为线可能比色差长，所以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;
        }
    }
}