logo标签列表

请为我解释这段 Bresenham 直线绘制代码。

c++algorithmlinebgibresenham
4
我在互联网上搜索了很多Bresenham线段算法的实现，但是我发现奇怪的是，只有两三个可以覆盖所有八个象限，尽管它们被用于很多应用中。例如，这位女士 实现了这个版本（第415行） 的Bresenham算法。但是，它不能覆盖整个360度。这个人似乎正在开发一个库，但仍然无法正常工作。你能告诉我为什么吗？

这个人的实现工作得很好。但是，我认为它不是Bresenham算法。它与理论有非常少的相似之处。

最后，我找到了以下版本的Bresenham直线绘制算法，它能够正常工作。

#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在哪里？

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

  • 理论似乎没有任何关于错误值处理的指示。代码计算error有什么用处？他是如何计算error的？他如何使用error值？

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

3个回答
6
这是我个人版本的Bresenham解释。
我们从一条线的参数方程开始，即(X + t.Dx, Y + t.Dy)，其中t是范围[0, 1]内的参数。端点显然为(X, Y)和(X + Dx, Y + Dy)。
为了将其转换为数字线，我们希望每行或每列恰好有一个像素，以确保连续的线。因此，定义D = Max（|Dx|，|Dy|），我们将绘制与分数t相对应的D + 1个点：(X + I.Dx / D, Y + I.Dy / D)，其中I在[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
            }
        }
    }
}
你如何推断出 t=I/D？ - user366312
后一表达式是数字的商，按算术级数递增，在一个大于公差的分母上。 - user366312
你在最终代码中用了这个逻辑在哪里： if R + Dy >= Dx Q' = Q + 1; R' = R + Dy - Dx else Q' = Q; R' = R + Dy？ - user366312
在更新（X，Y）和R中 - user1196549
干得好！你能提供一些支持你这里讨论的参考/网站链接吗？那样会帮助我更深入地学习。 - user366312
显示剩余4条评论
2
为什么他要对dx和dy进行左移操作，然后在计算之前再右移回来呢？
他使用了int的一半，希望它是准确的。但是一半的int会被截断。因此，通过使用固有加倍的表示方法，他可以使用右移作为非截断的除以二。这不是我很久以前学习Bresenham算法的方式。但是意图似乎很明确。
dt和ds在哪里？理论中没有提及？
我没有仔细阅读你的理论链接，但是我学习Bresenham的方式比那更简单。最初的问题是针对非常原始的CPU，您希望尽量减少计算量。
理论似乎没有任何关于错误值处理的指示。代码正在计算什么误差？他是如何计算误差的？他如何使用误差值？
我认为只是术语上的差异让您感到困惑。算法（以任何形式）的关键点是一个累加器，表示与非数字化线相比的累积“误差”。这个“误差”通常可能会有不同的名称，但无论如何，它都是代码的核心。您应该能够看到它在每个步骤中用于决定该步骤在哪个方向上数字化。
如果 dx>= dy，测试的逻辑背后是什么？
想法是更快的变化方向每步变化1次，而较慢的变化方向取决于这个累积“误差”每步变化0或1次。当代码大小是一个主要因素时，该算法的真正技巧是编写共享X变化速度更快与Y变化速度更快之间的代码。但是如果单独看X变化速度更快的情况和Y变化速度更快的情况，则整个过程显然很容易理解。
0
  • 为什么他要将dx和dy左移，然后在计算之前再右移呢？

我下面会解释。

  • 理论中提到的dt和ds在哪里？

它们已经消失了，实现了中点线段绘制算法。你可以从一个算法推导出另一个算法。这是读者的练习 :-)

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

同上。它正在测试错误，这是相同的事情。

  • 理论似乎没有任何关于错误值处理的指示。代码计算错误的用途是什么？他如何计算错误？他如何使用错误值？

直线的方程式为a*x + b*y + c = 0，其中a = x2 - x1，b = -(y2 - y1)，可以给出误差的指示，因为a*x + b*y + c与点(x, y)到该直线的距离成比例，其中a、b和c是实系数。我们可以用任意实常数k乘以该方程式，只要不等于0，它仍然适用于直线上的每个点。

假设我们只在第一象限内绘制。在每个步骤中，我们希望评估a*x + b*y + c对于(x + 1, y + 1/2)，以查看(mid)点与直线的距离有多远，并根据此决定是否增加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 来逐步更新误差。

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

  • 测试条件（dx>=dy）背后的逻辑是什么？

我们测试直线的陡峭程度，这使得交换操作变得不必要。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接