Алгоритм Scanline: вычисление x ребер

Question

Я пытаюсь реализовать алгоритм scanline в Javascript. Похоже, мое вычисление х неверно, так как линии короткие или длинные.

Эти края должны быть заполнены:

Вот как мой код сканлайна заполняет его:

Моя таблица ребер имеет следующие поля:

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 когда dy == 0,