ScanLine Visualisierung

Beschriebung zum Applet:

Zeichenfläche:
Hier kann durch klicken mit der Maus ein Polygon gezeichnet werden.
Kanten Tabelle:
Hier werden die Kanten des Polygons nach dem kleinsten Y-Wert aufsteigend sortiert angezeigt.

Pro Kante wird notiert:
- Kante = Name der Kante
- Y-Min = unterer y-Wert
- X-Start = x-Wert an dem Punkt mit ymin(kann größerer x-Wert sein!)
- Y-Max = oberer y-Wert
- dx/dy =horizontaler Versatz zwischen zwei Scanlines (entspricht 1/Anstieg)
Aktive Kanten Tabelle:
Hier werden die Kanten des Polygons, die von der Scanline geschnitten werden, also die aktiven Kanten, nach dem X-Wert aufsteigend sortiert angezeigt.

Pro Kante wird notiert:
- Kante = Name der Kante
- Y-Min = unterer y-Wert
- X-Start = x-Wert an dem Punkt mit ymin(kann größerer x-Wert sein!)
- Y-Max = oberer y-Wert
- dx/dy =horizontaler Versatz zwischen zwei Scanlines (entspricht 1/Anstieg)
Polygonauswahl:
Über dieses Drop-Down Menü hat man die Möglichkeit eines der vordefinierten Polygone aus zu wählen.
Start-, Vor- bzw. Von-Vorne-Button:
Mit dem Start-Button kann man den Algorithmus starten. Ist der Algorithmus einmal gestartet, wird aus dem Start-Button ein Vor-Button. Mit diesem kann man den Algorithmus Schritt für Schritt durchlaufen. D.h. bei jedem betätigen des Vor-Buttons wird die Scanline in Y-Richtung um eins erhöht. Ist der Algorithmus beendet, also das ganze Polygon gefüllt, wird aus dem Vor-Button ein Von-Vorne-Button. Mit diesem Wird der Algorithmus an dem gleichen Polygon wie zuvor nochmal gestartet.
Lösch-Button:
Mit dem Lösch-Button kann man die Zeichenfläche säubern und der Algorithmus kann wieder von Vorne gestertet werden.
Ausgabe:
In dem Ausgabefeld werden aktuelle Informationen zum besseren Verständnis des Algorithmus angezeigt.
Legende:
Die Legende dient zur Erklärung der im Algorithmus zur Ausgabe verwendeten Farben.

Beschreibung des Algorithmus:

Der Scanline Algorithmus ist ein Iterativer Algorithmus zum Füllen von beliebigen Polygonen.

Der Algorithmus arbeite folgendermaßen:

Abtasten (Scannen) das Polygons Pixelzeile (Scanline) für Pixelzeile von unten nach oben.
Suche alle Schnittpunkte der Scanlines mit Polygonkanten
Sortiere die Schnittpunkte nach wachsenden X-Koordinaten (Aufbau der Aktiven Kanten Tabelle).
Fülle alle Pixel zwischen Schnittpunkten nach Parität:
Parität ist anfangs 0 und wechselt bei jedem Schnittpunkt. Gezeichnet wird bei Parität 1.

Überlegungen/Sonderfälle:

Wie bestimmt man für einen nicht-ganzzahligen Schnittpunkt, welches der beiden Nachbarpixel innen liegt?
Erreicht man den Schnittpunkt, während man "innen" ist, wird abgerundet, während man "außen" ist, wird aufgerundet.
Wie verfährt man mit Schnittpunkten an ganzzahligen Pixelkoordinaten?
Ein ganzzahliger Schnittpunkt wird am Beginn einer Spanne als "innen", am Ende einer Spanne als "außen" betrachtet.
Wie verfährt man mit doppelt belegten Schnittpunkten?
Der ymin-Wert einer Kante wird als zugehörig, der ymax-Wert einer Kante als nicht zugehörig betrachtet.
Wie verfährt man mit horizontalen Kanten?
Untere Kanten werden dargestellt, obere nicht.

Codedokumentation:

Da das Aplett mit Java (www.sun.com) geschrieben wurde, ist die Codebeschreibung mit javadoc erstellt worden.

Den Link zu der Dokumentation finden Sie hier.