线生成算法

一条线连接两点。它是图形中的基本元素。要绘制一条线，您需要可以在两个点之间绘制一条线。在以下三种算法中，我们将直线上的一个点称为$X_{0}，Y_{0}$，将直线上的第二个点称为$X_{1}，Y_{1}$。

DDA算法

数字差分分析器 (DDA) 算法是简单的线生成算法，此处将逐步说明。

步骤 1 - 获取两个端点 $(X_{0}, Y_{0})$ 和 $(X_{1}, Y_{1})$ 的输入。

步骤 2 - 计算两个端点之间的差异。

dx = X1 - X0
dy = Y1 - Y0

步骤 3 - 根据步骤 2 中计算出的差异，您需要确定放置像素的步骤数。如果 dx > dy，则 x 坐标需要更多步骤；否则在 y 坐标中。

if (absolute(dx) > absolute(dy))
   Steps = absolute(dx);
else
   Steps = absolute(dy);

步骤 4 - 计算 x 坐标和 y 坐标的增量。

Xincrement = dx / (float) steps;
Yincrement = dy / (float) steps;

步骤 5 - 通过成功地相应增加 x 和 y 坐标来放置像素并完成线条的绘制。

for(int v=0; v < Steps; v++)
{
   x = x + Xincrement;
   y = y + Yincrement;
   putpixel(Round(x), Round(y));
}

布雷森汉姆线一代

Bresenham算法是另一种增量扫描转换算法。该算法的一大优点是，它仅使用整数计算。以单位间隔跨 x 轴移动，并在每一步在两个不同的 y 坐标之间进行选择。

例如，如下图所示，从位置 (2, 3) 开始，您需要在 (3, 3) 和 (3, 4) 之间进行选择。您想要更接近原始线的点。

布雷森汉姆线一代

在样本位置 $X_{k}+1,$ 处，与数学线的垂直间距标记为 $d_{upper}$ 和 $d_{lower}$。

笨蛋和笨蛋

从上图中，$x_{k}+1$ 处数学直线上的 y 坐标为 -

Y = m($X_{k}$+1) + b

因此，$d_{upper}$ 和 $d_{lower}$ 给出如下 -

$$d_{下} = y-y_{k}$$

$$= m(X_{k} + 1) + b - Y_{k}$$

和

$$d_{上} = (y_{k} + 1) - y$$

$= Y_{k} + 1 - m (X_{k} + 1) - b$

您可以使用它们来简单地决定哪个像素更接近数学线。这个简单的决定是基于两个像素位置之间的差异。

$$d_{下} - d_{上} = 2m(x_{k} + 1) - 2y_{k} + 2b - 1$$

让我们用dy/dx代替m，其中dx和dy是端点之间的差值。

$$dx (d_{下} - d_{上}) =dx(2\frac{\mathrm{d} y}{\mathrm{d} x}(x_{k} + 1) - 2y_{k} + 2b - 1)$$

$$ = 2dy.x_{k} - 2dx.y_{k} + 2dy + 2dx(2b-1)$$

$$ = 2dy.x_{k} - 2dx.y_{k} + C$$

因此，一条线上第k步的决策参数 $P_{k}$由下式给出 -

$$p_{k} = dx(d_{下} - d_{上})$$

$$ = 2dy.x_{k} - 2dx.y_{k} + C$$

决策参数$P_{k}$的符号与$d_{lower} - d_{upper}$的符号相同。

如果$p_{k}$为负，则选择下方的像素，否则选择上方的像素。

请记住，坐标变化沿 x 轴以单位步长发生，因此您可以通过整数计算完成所有操作。在步骤 k+1，决策参数给出为 -

$$p_{k +1} = 2dy.x_{k + 1} - 2dx.y_{k + 1} + C$$

从中减去 $p_{k}$ 我们得到 -

$$p_{k + 1} - p_{k} = 2dy(x_{k + 1} - x_{k}) - 2dx(y_{k + 1} - y_{k})$$

但是，$x_{k+1}$ 与 $(xk)+1$ 相同。所以 -

$$p_{k+1} = p_{k} + 2dy - 2dx(y_{k+1} - y_{k})$$

其中，$Y_{k+1} – Y_{k}$ 为 0 或 1，具体取决于 $P_{k}$ 的符号。

第一个决策参数 $p_{0}$ 在 $(x_{0}, y_{0})$ 处计算，计算公式为 -

$$p_{0} = 2dy - dx$$

现在，记住上述所有要点和计算，这是斜率 m < 1 的 Bresenham 算法 -

步骤 1 - 输入线的两个端点，将左端点存储在 $(x_{0}, y_{0})$ 中。

步骤 2 - 绘制点 $(x_{0}, y_{0})$。

步骤 3 - 计算常数 dx、dy、2dy 和 (2dy – 2dx) 并获得决策参数的第一个值：

$$p_{0} = 2dy - dx$$

步骤 4 - 在沿线的每个 $X_{k}$ 处，从 k = 0 开始，执行以下测试 -

如果 $p_{k}$ < 0，则下一个要绘制的点是 $(x_{k}+1, y_{k})$ 并且

$$p_{k+1} = p_{k} + 2dy$$ 否则，

$$(x_{k}, y_{k}+1)$$

$$p_{k+1} = p_{k} + 2dy - 2dx$$

步骤 5 - 重复步骤 4 (dx – 1) 次。

当 m > 1 时，确定每次增加 y 的同时是否需要增加 x。

求解后，决策参数 $P_{k}$ 的方程将非常相似，只是方程中的 x 和 y 互换。

中点算法

中点算法源自 Bresenham，并由 Pitteway 和 Van Aken 修改。假设您已将点 P 放置在 (x, y) 坐标处，并且直线的斜率为 0 ≤ k ≤ 1，如下图所示。

现在您需要决定是否将下一个点放在 E 或 N 处。这可以通过识别最接近点 N 或 E 的交点 Q 来选择。如果交点 Q 最接近点 N，则 N 被视为下一点；否则E。

中点算法

为了确定这一点，首先计算中点 M(x+1, y + ½)。如果E和N的垂线的交点Q在M的下方，则取E作为下一个点；否则取N作为下一个点。

为了检查这一点，我们需要考虑隐式方程 -

F(x,y) = mx + b - y

对于任何给定 X 处的正 m，

  • 如果 y 在线，则 F(x, y) = 0
  • 如果 y 在线上方，则 F(x, y) < 0
  • 如果 y 在线下方，则 F(x, y) > 0
隐式方程