javascript - 扫描线算法：计算边缘的 x

Question

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

这些边缘应该被填充：

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

我的边缘表有这些字段：

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

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

因此，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。这也显示在您的数学中：您不能除以dywhen dy == 0。