3

我在整个互联网上进行了搜索，发现了数百个 Bresenham 画线算法的实现。但是，我觉得奇怪的一件事是，它们中只有两三个可以覆盖所有八个八位字节。尽管如此，它们仍在许多应用中使用。

例如，这位女士实现了 Bresenham 算法的这个版本（第 415 行）。但是，它并没有覆盖整个 360 度。这家伙似乎正在开发一个图书馆。但它仍然不能正常工作。

你能告诉我为什么吗？

这家伙的实现工作正常。但是，我想这不是布雷森纳姆算法。它与理论几乎没有相似之处。

最后，我发现以下版本的 Bresenham's Line Drawing Algorithm 可以正常工作。

#include "utils.h"

void Bresenham(int x1, int y1, int const x2, int const y2, int color)
{
    int dx = x2 - x1;
    // if x1 == x2, then it does not matter what we set here
    int ix((dx > 0) - (dx < 0));

    dx = abs(dx) << 1;

    int dy = y2 - y1;
    // if y1 == y2, then it does not matter what we set here
    int iy((dy > 0) - (dy < 0));
    dy = abs(dy) << 1;

    PlotPixel(x1, y1, color);

    if (dx >= dy)
    {
        // error may go below zero
        int error(dy - (dx >> 1));

        while (x1 != x2)
        {
            if ((error >= 0) && (error || (ix > 0)))
            {
                error -= dx;
                y1 += iy;
            }
            // else do nothing

            error += dy;
            x1 += ix;

            PlotPixel(x1, y1, color);
        }
    }
    else
    {
        // error may go below zero
        int error(dx - (dy >> 1));

        while (y1 != y2)
        {
            if ((error >= 0) && (error || (iy > 0)))
            {
                error -= dy;
                x1 += ix;
            }
            // else do nothing

            error += dx;
            y1 += iy;

            PlotPixel(x1, y1, color);
        }
    }
}

int main()
{
    int gm = DETECT;
    int gd = DETECT;

    initgraph(&gm, &gd, "");

    double x1 = 0;
    double y1 = 0;
    double r = 50;
    double x2 = 0;
    double y2 = 0;
    double signx = 0;
    double signy = 0;

    for(int theta=0 ; theta<=360 ; theta++)
    {
        x2 = r * cos(DegreeToRad((double) theta));
        y2 = r * sin(DegreeToRad((double) theta));

        x1 = 5 * cos(DegreeToRad((double) theta));
        y1 = 5 * sin(DegreeToRad((double) theta));

        Bresenham(x1, y1, x2, y2, YELLOW);

        //delay(10);
    }

    getch();
    closegraph();
    return 0;
}

原始代码很奇怪。所以，我需要你的帮助来理解这一点。

  • 为什么他将 dx 和 dy 左移，然后在计算之前再次右移它们？

  • 理论所说的 dt 和 ds 在哪里？

  • 根据理论，dt 和 ds 应该在 while 循环的每一步都经过测试。但是，这段代码没有这样做。为什么？

  • 该理论似乎没有任何错误值处理的迹象。error代码计算有什么用？他是怎么计算的error？他是如何error使用价值的？

  • 测试背后的逻辑是什么if(dx >= dy)？

4

3 回答 3

5

这是我自己版本的 Bresenham 的解释。

我们从直线的参数方程 开始(X + t.Dx, Y + t.Dy)，其中t是范围内的参数[0, 1]。端点显然是(X, Y)和(X + Dx, Y + Dy)。

要将其转换为数字线，我们希望每行或每列恰好有一个像素，以确保连续线为准。所以定义D = Max(|Dx|, |Dy|)，我们将绘制D+1对应于小数的点t：(X + I.Dx/D, Y + I.Dy/D)，with Iin [0, D]。

让我们假设一下0 <= Dy < Dx = D，等式简化为(X + I, Y + I.Dy/Dx)。由于最后一项可能不是整数，我们将使用round(I.Dy/Dx) = floor(I.Dy/Dx + 1/2) = floor((I.Dy + Dx/2) / Dx).

后一个表达式是在大于公差的分母上遵循算术级数的数的商。因此，当您增加 时I，比率要么保持不变，要么增加1. 对于无除法的实现，我们使用了一个技巧：保留除法的商和余数，让Q和R，每次增加I时，更新这些。

让N = I.Dy + Dx/2, 和Q = N / Dx, R = N % Dx. 然后增加I, I' = I + 1, N' = N + Dy, Q' = (N + Dy) / Dx, R' = (N + Dy) % Dx. 如您所见，以下规则成立：

if R + Dy >= Dx
    Q' = Q + 1; R' = R + Dy - Dx
else
    Q' = Q; R' = R + Dy

我们现在将所有元素放在一起，调整符号并区分更水平和更垂直的情况（您会注意到，没有必要Q明确表示）：

# Increments
Sx= Sign(Dx); Sy= Sign(Dy)

# Segment length
Dx= |Dx|; Dy= |Dy|; D= Max(Dx, Dy)

# Initial remainder
R= D / 2

if Dx > Dy:
    # Main loop
    for I= 0..D:
        Set(X, Y)

        # Update (X, Y) and R
        X+= Sx; R+= Dy # Lateral move
        if R >= Dx
            Y+= Sy; R-= Dx # Diagonal move
else:
    # Main loop
    for I= 0..D:
        Set(X, Y)

        # Update (X, Y) and R
        Y+= Sy; R+= Dx # Lateral move
        if R >= Dy
            X+= Sx; R-= Dy # Diagonal move

C/C++ 实现（@anonymous）

void Set(int x, int y, int color)
{
    PlotPixel(x, y, color);
}

int Sign(int dxy)
{
    if(dxy<0) return -1; 
    else if(dxy>0) return 1; 
    else return 0;
}
void Bresenham(int x1, int y1, int x2, int y2, int color)
{
    int Dx = x2 - x1;
    int Dy = y2 - y1;

    //# Increments
    int Sx = Sign(Dx); 
    int Sy = Sign(Dy);

    //# Segment length
    Dx = abs(Dx); 
    Dy = abs(Dy); 
    int D = max(Dx, Dy);

    //# Initial remainder
    double R = D / 2;

    int X = x1;
    int Y = y1;
    if(Dx > Dy)
    {   
        //# Main loop
        for(int I=0; I<D; I++)
        {   
            Set(X, Y, color);
            //# Update (X, Y) and R
            X+= Sx; R+= Dy; //# Lateral move
            if (R >= Dx)
            {
                Y+= Sy; 
                R-= Dx; //# Diagonal move
            }
        }
    }
    else
    {   
        //# Main loop
        for(int I=0; I<D; I++)
        {    
            Set(X, Y, color);
            //# Update (X, Y) and R
            Y+= Sy; 
            R+= Dx; //# Lateral move
            if(R >= Dy)
            {    
                X+= Sx; 
                R-= Dy; //# Diagonal move
            }
        }
    }
}
于 2015-08-27T15:01:41.023 回答
2

为什么他将 dx 和 dy 左移，然后在计算之前再次右移它们？

他以期望它是准确的方式使用了一半的 int。但是半个 int 会被截断。因此，通过使用本质上加倍的表示，他可以使用右移作为未截断的除以二。这不是我很久以前了解布雷森纳姆的方式。但意图似乎很明确。

理论所说的 dt 和 ds 在哪里？

我没有仔细阅读您的理论链接，但是我学习 Bresenham 的方式比这更简单。最初的观点是非常原始的 CPU，您希望在其中最小化计算。

该理论似乎没有任何错误值处理的迹象。代码计算的错误有什么用？他是如何计算误差的？他如何使用错误值？

我希望只是术语上的差异会让您感到困惑。该算法的关键点（任何形式）是一个累加器，表示累积“错误”与非数字化线。该“错误”通常可能有不同的名称，但无论名称如何，它都是代码的核心。您应该能够看到它在每个步骤中用于决定该步骤的数字化方向。

测试 if(dx >= dy) 背后的逻辑是什么？

这个想法是，快速变化的方向每一步改变 1，而缓慢改变的方向每一步改变 0 或 1，具体取决于累积的“误差”。回到代码大小是一个主要因素的时候，这个算法的真正诀窍是对其进行编码，以便在 X 更快与 Y 更快的主要区别之间共享代码。但显然，如果您将 X 变化更快的情况与 Y 变化更快的情况分开来看，整个事情就很容易理解。

于 2015-08-27T14:13:43.143 回答
0
  • 为什么他将 dx 和 dy 左移，然后在计算之前再次右移它们？

我在下面解释。

  • 理论所说的 dt 和 ds 在哪里？

他们走了，实现实现了中点画线算法。不过，您可以从另一种算法派生出一种算法。这是给读者的练习:-)

  • 根据理论，dt 和 ds 应该在 while 循环的每一步都经过测试。但是，这段代码没有这样做。为什么？

和上面一样。它正在测试错误，这是一回事。

  • 该理论似乎没有任何错误值处理的迹象。代码计算的错误有什么用？他是如何计算误差的？他如何使用错误值？

线的方程a*x + b*y + c = 0，其中a = x2 - x1和b = -(y2 - y1)可以给出误差的指示，与点到线a*x + b*y + c的距离成正比(x, y)，具有实系数a和。我们可以将方程与一个不等于 0的任意实常数相乘，它仍然适用于线上的每个点。bck

假设我们只画第一象限。在每个步骤中，我们希望评估a*x + b*y + c以(x + 1, y + 1/2)查看（中）点与线的距离有多远，并据此决定我们是否增加 y，但距离无关紧要，只有它的符号。对于第一象限，如果直线高于中点，则距离为正，(x + 1, y + 1/2)如果低于中点，则距离为负。如果这条线在中点之上，我们必须“向上”。

所以我们知道初始(x, y), a*x + b*y + c = 0，但是如何(x + 1, y + 1/2)呢？误差项等于a + b/2。我们不喜欢一半，所以我们将（左移）a和b乘以 1 得到 的初始误差2*a + b，这就是右移的原因。如果误差是正的，那么这条线就在中点之上(x + 1, y + 1/2)，我们必须往上走。如果是负数，那么这条线低于中点，我们就离开了y。我们在每一步都增量地更新错误，这取决于我们是否增加了y。

经过一番思考，您可以将算法扩展到所有象限。

  • 测试 if(dx >= dy) 背后的逻辑是什么？

我们测试线的陡度。这使得交换变得不必要。

于 2015-09-01T13:08:56.020 回答