5

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

ooo
  ooo
    ooo
      oo

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

oo
  oo
    oo
      oo

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

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

我将尝试通过线性插值 x 坐标来解决这个问题，将其四舍五入到像素网格，然后找到相应的 y。（再次，将 x/y 换成陡峭的线）。但是，无论该解决方案如何解决，我都会对其他建议以及以前的经验感兴趣。

4

3 回答 3

6

引入 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)
于 2012-09-11T11:44:34.650 回答
0

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

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;
}
于 2012-09-11T11:43:19.647 回答
0

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

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

这是朴素的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;
        }
    }
}
于 2017-05-04T22:35:37.837 回答