请为我解释一下这个布雷森纳姆线绘图代码

Question

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

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

你能告诉我为什么吗？

这家伙的实施效果很好。但是，我认为这不是布雷森汉姆算法。它与理论有很少的相似之处。

最后，我发现以下版本的 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在哪里？

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

• 该理论似乎没有表明任何错误值处理。error代码计算的有什么用？他是如何计算的error？他如何利用这个error价值？

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

Answer 1

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

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

要将其转换为数字线，我们需要每行或每列恰好一个像素，以确保连续线为准。因此定义D = Max(|Dx|, |Dy|)，我们将绘制与小数:D+1相对应的点，其中in 。t(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) / DxR' = (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
            }
        }
    }
}