扫描线算法：计算边的 x

Question

我正在尝试在 Javascript 中实现扫描线算法。看起来我对 x 的计算是错误的，因为线条太短或太长。

应填充这些边：

这是我的扫描线代码填充它的方式：

我的边缘 table 有这些字段：

et.push({
    Ymin: Ymin, // minimum Y of the edge
    Ymax: Ymax, // maximum Y
    x: Xmin, // X value of Ymin point; updated for every scanline
    dx: Xmax - Xmin, // Delta X
    dy: Ymax - Ymin // Delta Y
});

每条扫描线后的新 X 是这样计算的：

// aet is active edge table
if (aet[i].dx != 0 && aet[i].dy != 0) {
    // this is not a vertical edge
    var incr = aet[i].dy / aet[i].dx; // =1/(dx/dy) ... dx/dy=m
    if (aet[i].dy > 0) {
        incr = incr;
    } else {
        incr = -incr;
    }
    aet[i].x += incr;
}

这个计算有什么问题？

Answer 1

您没有正确显示扫描线算法，但看起来好像您想处理从 Ymin 到 Ymax 的所有扫描线。 y 开始一个 Ymin 并为每个扫描线增加一个。

因此，每个扫描线的 x 应增加 dx/dy。

您可能不需要调整符号。相反，dy 的符号不是正就是负：

m = dx / dy                               # slope of the line
x[y + 1] = x[y] + m * dy = x[y] + m       # dy == (y + 1) - y == 1
x[y - 1] = x[y] + m * dy = x[y] - m       # dy == (y - 1) - y == -1

您在 x 方向扫描，因此排除了 dy == 0 的水平线。这也显示在您的数学中：当 dy == 0.

时，您不能除以 dy

扫描线算法：计算边的 x

Scanline algorithm: calculate x of edges

javascript

algorithm

graphics

scanline