请为我解释这个 Bresenham Line 绘图代码
please explain this Bresenham Line drawing code for me
我在整个 Internet 上进行了搜索，找到了数百个 Bresenham 线图算法的实现。但是，我发现奇怪的一件事是，只有两个或三个可以覆盖所有八个八位字节。尽管如此，它们仍在许多应用中使用。
例如，this lady implemented this version (line 415) of Bresenham's algorithm. But, it doesn't cover the whole 360 degrees. This guy here 似乎正在开发一个库。但是仍然不能正常工作。
你能告诉我为什么吗？
This guy's implementation works fine. But, I suppose it is not Bresenham's Algorithm. It has a very few similarity with 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 的？他如何使用 error 值？
测试背后的逻辑是什么if(dx >= dy)？
Why is he left shifting dx and dy and then, before calculation, again
right-shifting them?
他以一种期望它准确的方式使用了 int 的一半。但是半个 int 会被截断。因此，通过使用本质上加倍的表示，他可以使用右移作为未截断的除以二。那不是我很久以前学习布雷森纳姆的方式。但意图似乎很明确。
Where are the dt and ds that the theory talks about?
我没有仔细阅读你的理论link，但我学习 Bresenham 的方法比那更简单。最初的观点是针对非常原始的 CPU，您希望在其中最小化计算。
The theory seems to have no indication of any error value processing.
What is the use of error that the code is calculating? How is he
calculating the error? How is he using the error value?
我想只是术语上的差异会让您感到困惑。该算法（以任何形式）的关键点是一个累加器，表示累加 "error" 与非数字化线。 "error" 通常可能有一个不同的名字，但不管用什么名字，它都是代码的核心。您应该能够看到它在每个步骤中用于决定该步骤数字化的方向。
What is the logic behind the test if(dx >= dy)?
这个想法是，变化较快的方向每一步变化 1，而变化较慢的方向每步变化 0 或 1，具体取决于累积 "error"。当代码大小是一个主要因素时，这个算法的真正诀窍是对其进行编码，以便在 X 更快与 Y 更快的主要差异之间共享代码。但很明显，如果您将 X 变化更快的情况与 Y 变化更快的情况分开看，那么整个事情就很容易理解。
这是对我自己版本的 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
}
}
}
}
- 为什么他左移 dx 和 dy 然后在计算之前再次
右移它们？
我在下面解释。
- 理论讲的dt和ds在哪里？
他们走了，实现实现了中点画线算法。不过，您可以从另一种算法中推导出一种算法。这是 reader 的练习:-)
- 根据理论，dt和ds应该在每个
while循环的步骤。但是，这段代码并没有这样做。为什么？
同上。是检测错误，是一回事
- 理论上似乎没有任何错误值处理的迹象。
代码计算的错误有什么用？他怎么样
计算误差？他是如何使用错误值的？
线a*x + b*y + c = 0的方程，其中a = x2 - x1和b = -(y2 - y1)可以给出误差的指示，因为a*x + b*y + c与点的距离成正比(x, y) 与实数系数 a、b 和 c。我们可以将方程乘以一个不等于 0 的任意实常数 k，它仍然适用于直线上的每个点。
假设我们只在第一象限绘制。在每一步中，我们都希望对 (x + 1, y + 1/2) 进行 a*x + b*y + c 评估，以查看（中）点与直线的距离，并据此决定是否增加 y，但距离无关紧要，只有它的标志。对于第一象限，如果线位于中点 (x + 1, y + 1/2) 上方，则距离为正，如果低于中点，则距离为负。如果这条线在中点之上，我们必须走 "up".
所以我们知道初始 (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) 背后的逻辑是什么？
我们测试直线的陡度。这使得交换变得不必要。
我在整个 Internet 上进行了搜索，找到了数百个 Bresenham 线图算法的实现。但是，我发现奇怪的一件事是，只有两个或三个可以覆盖所有八个八位字节。尽管如此，它们仍在许多应用中使用。
例如，this lady implemented this version (line 415) of Bresenham's algorithm. But, it doesn't cover the whole 360 degrees. This guy here 似乎正在开发一个库。但是仍然不能正常工作。
你能告诉我为什么吗？
This guy's implementation works fine. But, I suppose it is not Bresenham's Algorithm. It has a very few similarity with 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的？他如何使用error值？测试背后的逻辑是什么
if(dx >= dy)？
Why is he left shifting dx and dy and then, before calculation, again right-shifting them?
他以一种期望它准确的方式使用了 int 的一半。但是半个 int 会被截断。因此，通过使用本质上加倍的表示，他可以使用右移作为未截断的除以二。那不是我很久以前学习布雷森纳姆的方式。但意图似乎很明确。
Where are the dt and ds that the theory talks about?
我没有仔细阅读你的理论link，但我学习 Bresenham 的方法比那更简单。最初的观点是针对非常原始的 CPU，您希望在其中最小化计算。
The theory seems to have no indication of any error value processing. What is the use of error that the code is calculating? How is he calculating the error? How is he using the error value?
我想只是术语上的差异会让您感到困惑。该算法（以任何形式）的关键点是一个累加器，表示累加 "error" 与非数字化线。 "error" 通常可能有一个不同的名字，但不管用什么名字，它都是代码的核心。您应该能够看到它在每个步骤中用于决定该步骤数字化的方向。
What is the logic behind the test if(dx >= dy)?
这个想法是，变化较快的方向每一步变化 1，而变化较慢的方向每步变化 0 或 1，具体取决于累积 "error"。当代码大小是一个主要因素时，这个算法的真正诀窍是对其进行编码，以便在 X 更快与 Y 更快的主要差异之间共享代码。但很明显，如果您将 X 变化更快的情况与 Y 变化更快的情况分开看，那么整个事情就很容易理解。
这是对我自己版本的 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
}
}
}
}
- 为什么他左移 dx 和 dy 然后在计算之前再次 右移它们？
我在下面解释。
- 理论讲的dt和ds在哪里？
他们走了，实现实现了中点画线算法。不过，您可以从另一种算法中推导出一种算法。这是 reader 的练习:-)
- 根据理论，dt和ds应该在每个 while循环的步骤。但是，这段代码并没有这样做。为什么？
同上。是检测错误，是一回事
- 理论上似乎没有任何错误值处理的迹象。 代码计算的错误有什么用？他怎么样 计算误差？他是如何使用错误值的？
线a*x + b*y + c = 0的方程，其中a = x2 - x1和b = -(y2 - y1)可以给出误差的指示，因为a*x + b*y + c与点的距离成正比(x, y) 与实数系数 a、b 和 c。我们可以将方程乘以一个不等于 0 的任意实常数 k，它仍然适用于直线上的每个点。
假设我们只在第一象限绘制。在每一步中，我们都希望对 (x + 1, y + 1/2) 进行 a*x + b*y + c 评估，以查看（中）点与直线的距离，并据此决定是否增加 y，但距离无关紧要，只有它的标志。对于第一象限，如果线位于中点 (x + 1, y + 1/2) 上方，则距离为正，如果低于中点，则距离为负。如果这条线在中点之上，我们必须走 "up".
所以我们知道初始 (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) 背后的逻辑是什么？
我们测试直线的陡度。这使得交换变得不必要。