【图形学基础算法】叁-PTP法生成直线

发表于 | 更新于：

  这篇文章中我们简单介绍 PTP (point to point comparison method ：逐点比较法) 生成直线算法，它是在画线过程中，每画一点就与理想直线比较，已决定下一点的走向，以步步紧逼的方法点亮最接近直线的一组像素。

  逐点比较发绘制前，先将直线平移，使 y 坐标较小的点位于坐标原点，这样整条直线都可在第一象限和第二象限中去讨论。这里平移的方法是从直线的两端点中找出 y 较小的点，将起点和终点均减去此点坐标。

  平移后，根据另一个点的 x 来判断直线斜率（小于 0 则斜率为负 ，在第二象限，大于 0 相反）。

  算法根据点在理想直线的位置来判断像素移动（每次移动一个像素），如果像素在直线上方则根据象限不同选择向左还是向右移动，如果在直线下方则向上移动。

  偏差公式表示为： 。M 为画笔的当前位置， 和 则是当前位置的 ， 坐标绝对值。而 A 则是终点的坐标（起点是原点）绝对值。当 的时候，则代表当前点在理想点上方，我们下一步的点应该是 或者 ，相反则是 。

  这里的公式我们每次需要计算两次乘法，计算量较大。可以进行优化，我们通过前一点的偏差来推算后一点的偏差。

  设画笔的当前位置为 ，此时 ， 方向应走 +1 步到 ，即

  此时 为： ，若下一步的时候 , ，则 方向应走 +1 步到 ，即

   为 ： 。

  递推可得每一步的结果，而对于第二象限，当 ， 走 +1 ，，当 ， 走 -1 ，。

  最终代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void DrawLinePTP(int x1, int y1, int x2, int y2,
                 unsigned char r, unsigned char g, unsigned char b,
                 Texture &tex) {
    int x, y, xA, yA;
    if (y1 > y2) {
        yA = y1 - y2;
        xA = x1 - x2;
    } else {
        yA = y2 - y1;
        xA = x2 - x1;
    }
    int f = x = y = 0;
    int n = abs(xA) + abs(yA);

    for (int i = 0; i < n; ++i) {
        if (xA > 0) {
            if (f >= 0) {
                ++x;
                f -= yA;
            } else {
                ++y;
                f += xA;
            }
        } else {
            if (f >= 0) {
                ++y;
                f += xA;
            } else {
                --x;
                f += yA;
            }
        }
        if (y1 > y2) tex.SetPixel(x + x2, y + y2, r, g, b);
        else tex.SetPixel(x + x1, y + y1, r, g, b);
    }
}
0%