Scanline-Algorithmus: x der Kanten berechnen

Question

Ich versuche, den Scanline-Algorithmus in Javascript zu implementieren. Es sieht so aus, als ob meine Berechnung von x falsch ist, da die Linien zu kurz oder zu lang sind.

sollten Diese Kanten werden gefüllt:

Dies ist, wie mein Scanline-Code füllt es:

Meine Kantentabelle hat diese Felder:

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 
}); 

Das neue X nach dem Abend ry scanline wird auf diese Weise berechnet:

// 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; 
} 

Was ist falsch in dieser Berechnung?

Answer 1

Sie zeigen den Scanline-Algorithmus nicht korrekt an, aber es sieht so aus, als ob Sie alle Scanlinien von Ymin bis Ymax behandeln möchten. y startet eine Ymin und erhöht sich für jede Scanlinie um eins.

Daher sollte die x für jede Scanline um dx/dy erhöht werden.

Sie müssen das Vorzeichen wahrscheinlich nicht anpassen. Stattdessen ist das Zeichen der dy entweder positiv oder negativ:

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 

Sie in x Richtung abtasten und damit horizontale Linien, für die dy == 0 auszuschließen. Das zeigt sich auch in Ihrer Mathematik: Sie können nicht durch dy teilen, wenn dy == 0.