algorithm - 了解算法的 Bresenham 错误累积部分？

Question

我在理解错误累积部分在 Bresenham 的画线算法中的工作原理时遇到问题。

假设我们有 x1和 x2 .让我们假设 x1 < x2 , y1 < y2 , 和 (x2 - x1) >= (y2 - y1)为简单起见:

让我们从简单的画线开始。它看起来像:

void DrawLine(int x1, int y1, int x2, int y2)
{
    float y = y1 + 0.5f;
    float slope = (float)(y2 - y1) / (x2 - x1);
    for (int x = x1; x <= x2; ++x)
    {
        PlotPixel(x, (int)y);
        y += slope;
    }
}

让我们让它更像 Bresenham'ish，并将 y 的整数和浮点部分分开:

void DrawLine(int x1, int y1, int x2, int y2)
{
    int yi = y1;
    float yf = 0.5f;
    float slope = (float)(y2 - y1) / (x2 - x1);
    for (int x = x1; x <= x2; ++x)
    {
        PlotPixel(x, yi);
        yf += slope;
        if (yf >= 1.0f)
        {
            yf -= 1.0f;
            ++yi;
        }
    }
}

此时我们可以乘以yf和 slope通过 2 * (x2 - x1)使它们成为整数，不再有 float 。我明白这一点。

我不完全理解的部分是:

    if (yf >= 1.0f)
    {
        yf -= 1.0f;
        ++yi;
    }

这实际上是如何运作的？为什么我们要与 1.0 进行比较然后递减？

我知道 Bresenham 的基本问题是:如果我们目前在像素 x, y我们想画下一个，我们应该选择x + 1, y吗？或 x + 1, y + 1 ？ - 我只是不明白该检查如何帮助我们回答这个问题。

有人称它为error term，有人称它为threshold，我只是不明白它代表什么。

任何解释表示赞赏，谢谢。

Answer 1

Bresenham 的线栅格化算法以整数算法执行所有计算。在您的代码中，您使用的是浮点类型，您不应该这样做。

首先考虑您知道在线上的两个像素。起始像素和结束像素。该算法计算的是近似线的像素，使得栅格化线在两个输入像素上开始和停止。

其次，绘制的所有线条都是斜率在 0 到 0.5 之间的线条的反射。垂直线有一个特例。如果您的算法对于此输入是正确的，那么您需要初始化光栅化器的起始状态以正确光栅化一条线:起始像素 (x, y)、Δx、Δy 和决策变量 D。

既然你可以假设所有的线都是从左到右画的，正斜率等于或小于 0.5，问题归结为:是当前像素右侧或右侧向上一个像素的下一个光栅化像素。

您可以通过跟踪栅格化线偏离真实线的程度来做出此决定。为此，将线方程重写为隐式函数 F(x, y) = Δyx - Δxy + Δxb = 0 并重复计算 F(x + 1 y + 0.5)。由于这需要 float 学运算，因此您需要专注于确定您是在真实线上、上方还是下方。因此，F(x + 1 y + 0.5) = Δy - 0.5Δx 并乘以二 2 * F(x + 1 y + 0.5) = 2Δy - Δx。这是第一个决定，如果结果小于零，则对 x 加一，对 y 加零。

第二次决策和后续决策类似，错误累积。决策变量 D 被初始化为 2Δy - Δx。如果 D < 0，则 D = D + 2Δy；否则 y = y + 1 和 D = D + 2(Δy - Δx)。 x 变量始终递增。

Jim Arvo 有一个 great explanation of Bresenham's algorithm .