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.

   
 

 
         
   

© 2005   Matian Panten   •  Udo Petzel