2

我在理解 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)使它们成为整数，不再需要浮点数。我明白那个。

我不完全理解的部分是：

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

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

我知道 Bresenham 的基本问题是：如果我们目前处于像素状态x, y并且我们想要绘制下一个，我们应该选择x + 1, y还是x + 1, y + 1？- 我只是不明白那张支票是如何帮助我们回答这个问题的。

有些人称之为错误术语，有些人称之为阈值，我只是不明白它代表什么。

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

4

2 回答 2

2

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

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

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

由于您可以假设所有线都是从左到右绘制的，正斜率等于或小于 0.5，因此问题归结为：当前像素的下一个光栅化像素是向右还是向右和向上一个像素。

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

第二个决定和随后的决定类似地遵循并且误差被累积。决策变量 D 被初始化为 2Δy - Δx。如果 D < 0，则 D = D + 2Δy；否则 y = y + 1 和 D = D + 2(Δy - Δx)。x 变量始终递增。

Jim Arvo对 Bresenham 的算法有很好的解释。

于 2016-02-16T03:45:43.713 回答
1

在您的实现yf中，实际浮点 Y 坐标和绘制（积分）Y 坐标之间的距离为 0.5 +。该距离是您绘图的当前错误。您希望将误差保持在实线和绘制线之间最多半个像素（-0.5..+0.5），因此您的误差yf应该0.5+error在 0 和 1 之间。当它超过 1 时，您只需增加绘制的Y 坐标 ( yi) 减一，您需要将误差减一。举个例子：

slope = 0.3;
x = 0; yf = 0.5; y = 0; // start drawing: no error
x = 1; yf = 0.8; y = 0; // draw second point at (1, 0); error is +0.3
x = 2; yf = 1.1; y = 0; // error is too big (+0.6): increase y
       yf = 0.1; y = 1; // now error is -0.4; draw point at (2, 1)
x = 3; yf = 0.4; y = 1; // draw at (3, 1); error is -0.1
x = 4; yf = 0.7; y = 1; // draw at (4, 1); error is +0.2
x = 5; yf = 1.0; y = 1; // error is too big (+0.5); increase y
       yf = 0.0; y = 2; // now error is -0.5; draw point at (5, 2)

等等。

于 2016-02-16T03:52:37.357 回答