c++ - 请为我解释这个 Bresenham Line 绘图代码

Question

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

例如，this lady已实现 this version (line 415) Bresenham 的算法。但是，它并没有涵盖整个 360 度。 This guy here似乎正在开发一个图书馆。但它仍然无法正常工作。

你能告诉我为什么吗？

This guy's implementation工作良好。但是，我想这不是 Bresenham 的算法。它与 the theory 几乎没有相似之处。 .

最后，我找到了the following version正确运行的 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，然后在计算之前再次右移它们？

• the theory 的 dt 和 ds 在哪里？谈论？

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

• 理论似乎没有任何错误值处理的迹象。代码正在计算的 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分数对应的点 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) / 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
            }
        }
    }
}