-
Die vorliegende Erfindung betrifft das Füllen von Polygonen,
das heißt bei Datenverarbeitungs-Ausgabegeräten wie
Grafikrasteranzeigen ein Verfahren zum Ausfüllen des
Bereichs, der von den Rändern eines angezeigten Polygons
definiert wird.
-
Es gibt eine allgemeine Routine zum Füllen von Polygonen, die
in J. D. Foley und A. Van Dam, Fundamentals of Interactive
Computer Graphics (Addison-Wesley, 1982), S. 456-460,
beschrieben ist. Diese allgemeine Routine wird als
kantentabellengesteuerte Routine bezeichnet. Dieser
Routinentyp wird in Computergrafik-Anwendungen als eine der
Standardroutinen eingesetzt, die zur Durchführung bestimmter
Grafikaufgaben aufgerufen werden. Zu diesen Grafikaufgaben
zählen das Zeichnen von Geraden, Kreisen, Bögen usw. und auch
das Füllen von Polygonen. Diese Aufgaben werden
typischerweise in einer Bibliothek bereitgestellt, die
Grafikfunktionen enthält, wie etwa eine
Grafikunterstützungsbibliothek (GSL, Graphics Support
Library). Im allgemeinen ist eine
Grafikunterstützungsbibliothek ein Paket aus Grafik-
Subroutinen, die typischerweise mit einem Verarbeitungssystem
geliefert werden, so daß die Benutzer auf Anzeigen mit einer
höheren Schnittstelle schreiben können, ohne die Komplexität
einer bestimmten Anzeige und das Verfahren zum Schreiben auf
diese Anzeige kennen zu müssen.
-
Für einige einfachere Polygonformen wird diese Routine zu
zeitaufwendig. Eine Routine wird übermäßig zeitaufwendig,
wenn die Benutzer einer Grafikanwendung nach der Auswahl der
Routine zum Füllen von Polygonen warten müssen, bevor das
resultierende gefüllte Polygon auf dem Anzeigebildschirm
erscheint. Für die Kundenzufriedenheit ist es wichtig, daß
die Füllgeschwindigkeit ohne Abstriche bei der Präzision der
Polygonfüllung möglichst hoch ist.
-
Eine andere bekannte Routine verwendet die in J. E.
Bresenham, "Algorithm for Computer Control of a Digital
Plotter", IBM Systems Journal, Bd. 4, Nr. 1 (1965), S. 25-30,
beschriebene Bresenham-Routine. Diese Bresenham-Routine ist
ebenfalls in J. D. Foley und A. Van Dam, Fundamentals of
Interactive Computer Graphics (Addison-Wesley, 1982), S. 433-
436, beschrieben. Die Bresenham-Routine wird verwendet, um
die Linien des Polygonrandes abzutasten und die Punkte zu
generieren, die den Polygonrand bilden. Allerdings wählt
diese bekannte Polygon-Füllroutine den ersten Punkt nach
einer Änderung in der Abtastzeile. Das Problem bei dieser
Routine besteht darin, daß sie die Füllung nicht präzise
innerhalb der Ränder des Polygons vornimmt. Das resultierende
angezeigte Polygon sieht aus, als sei es unvollständig
gefüllt. Die Füllung erreicht also nicht an allen Stellen den
Rand des Polygons.
-
Es gibt eine Vielzahl verschiedener Polygonformen. Je nach
der Form eines bestimmten Polygons kann es eine Polygon-
Füllroutine geben, die für die bestimmte Polygonform
effizienter ist als für Polygone mit anderen Formen. Der
Artikel "Method To Determine The Convexity of Polygons", IBM
Technical Disclosure Bulletin, Bd. 28, Nr. 5, Oktober 1985,
S. 2203-2208, legt dar, daß es für konvexe Polygone
Füllroutinen gibt, die effizienter sind als die für
allgemeine Polygone.
-
Unter Bezugnahme auf Fig. 1A stellt der genannte Artikel
fest, daß ein Polygon 10 konvex ist, wenn alle Innenwinkel an
den Eckpunkten A, B, C, D, E weniger als 180 Grad betragen.
Fig. 1B zeigt ein Polygon 11, das nach dieser Definition
nicht konvex ist, da es an seinem Eckpunkt E einen
Innenwinkel aufweist, der größer als 180 Grad ist.
-
In dem Artikel wird ein Verfahren beschrieben, das
feststellt, ob alle Innenwinkel weniger als 180 Grad betragen
und das Polygon somit konvex ist. Das Verfahren nimmt das
Kreuzprodukt für jeweils zwei benachbarte Vektoren, die von
den Kanten des Polygons gebildet werden. Wenn alle
Kreuzprodukte dasselbe Vorzeichen haben, handelt es sich um
ein konvexes Polygon. Das Kreuzprodukt zeigt an, ob jede
Seite des Polygons in dieselbe Richtung abbiegt. Wie in Fig.
1A gezeigt, sind alle Biegungen auf dem Weg um das Polygon
10, beginnend bei Eckpunkt E, in Richtung des Pfeils 12 nach
links. In Fig. 1B dagegen sind auf dem Weg um das Polygon 11
in Richtung des Pfeils 13, beginnend bei Eckpunkt D, alle
Biegungen nach links außer bei Eckpunkt E, bei dem die
Biegung nach rechts erfolgt.
-
Der obige Test würde somit die in Fig. 2A und 2B gezeigten
Polygone 20, 21 als konvex klassifizieren, da alle
Innenwinkel kleiner als 180 Grad sind. Außerdem erfolgen, wie
in Fig. 2A oder Fig. 2B gezeigt, auf dem Weg um das Polygon
20, 21 in Richtung des Pfeils 22, 23, beginnend bei Eckpunkt
B, alle Biegungen nach links. Allerdings haben die in Fig. 2A
und 2B gezeigten Polygone 20, 21 sich schneidende Linien und
gehen mehr als einmal herum. Diese Polygontypen sind
komplexer und werden von den einfacheren und effizienteren
Füllmethoden, die bisher schon im Fach bekannt waren, nicht
präzise gefüllt. Daher bestimmt das in dem obengenannten
Artikel beschriebene Verfahren die Konvexität von Polygonen
nicht für alle Polygontypen richtig.
-
Ein weiteres Problem ist, daß die früheren Verfahren zum Test
von Polygonen Polygone mit Formen, wie sie in Fig. 3A und 3B
dargestellt sind, zusammen mit allen anderen allgemeinen
Polygonen klassifizierten. Die Polygone 30, 31 in Fig. 3A und
Fig. 3B sind als x-konkav. Das Polygon 31 in Fig. 3B ist
xkonkav und hat zudem sich schneidende Linien.
-
Die vorliegende Erfindung stellt ein Verfahren zum Füllen von
Polygonen in einer zeilenweisen, pixelgesteuerten
Datenverarbeitungsausgabe bereit, bei dem ein zu füllendes
Polygon durch einen Rand aus mehreren Linien definiert ist,
der durch eine Vielzahl auswählbarer Pixel pro Abtastzeile
definiert werden kann, bei dem eine allgemeine Polygon-
Füllroutine verwendet wird, sofern nicht ein mit den
Eckpunkten des Polygons durchgeführter Einmal-herum-Test
bestanden wird, was dadurch definiert ist, daß das Vorzeichen
der Differenz zwischen Ordinaten quer zur Richtung der
Abtastzeile von aufeinanderfolgenden Eckpunkten des Polygons
sich genau zwei oder dreimal in einem Durchlauf um das
Polygon ändert, wobei in diesem Fall eine schnellere
Füllroutine verwendet wird und wobei möglicherweise auch
andere Tests zusätzlich bestanden werden müssen.
-
Ein nachstehend beschriebenes Ausführungsbeispiel der
Erfindung implementiert je nach der besonderen Form des
Polygons eine von drei Polygon-Füllroutinen zur Optimierung
der zum Füllen eines Polygons benötigten Verarbeitungszeit.
An dem Polygon werden mehrere Tests durchgeführt, um
festzustellen, ob das Polygon in die Klasse der Polygone
fällt, die mit einer bestimmten Polygon-Füllroutine zu füllen
sind.
-
Für eine Klasse von Polygonen, nämlich streng konvexe
Polygone, wird die zum Füllen eines Polygons benötigte
Verarbeitungszeit durch eine erste Polygon-Füllroutine
optimiert, indem für eine Hälfte des Polygons für jede
Abtastzeile des Polygons ein Maximalwert gespeichert wird und
für die andere Hälfte des Polygons für jede Abtastzeile des
Polygons ein Minimalwert gespeichert wird. Diese Routine
speichert genau einen Wert, da die Routine weiß, ob an
irgendeinem besonderen Punkt auf dem Polygon der Punkt zu den
Maximal- oder Minimalwerten gehört.
-
Für eine andere Klasse von Polygonen, den x-konkaven
Polygonen, ist die erste Polygon-Füllroutine ungeeignet, um
ein Polygon in dieser Polygonklasse präzise zu füllen. In
dieser Klasse von Polygonen wird die zum Füllen eines
Polygons benötigte Verarbeitungszeit optimiert, indem für
jede Abtastzeile des Polygons zwei Minimal- und Maximalwerte
gespeichert werden. Die Füllinie wird dann für jede
Abtastzeile von dem kleinsten Minimalwert um größten
Maximalwert gezogen.
-
Die erste Polygon-Füllroutine füllt Polygone, die streng
konvex sind. Die zweite Polygon-Füllroutine füllt eine
größere Gruppe von Polygonen als die erste Polygon-
Füllroutine. Die zweite Polygon-Füllroutine füllt alle
Polygone, die mit genau einer durchgehenden Linie pro
Abtastung gefüllt werden können. Die Polygone in dieser
Klasse können auch x-konkav sein und sich schneidende Linien
aufweisen.
-
Die erste Polygon-Füllroutine prüft, ob das Polygon streng
konvex ist, indem sie die Kombination von zwei Bedingungen
überprüft. Als erstes wird das Polygon auf die einheitliche
"Abbiegerichtung" überprüft. Es wird also festgestellt, ob
jede aufeinander folgende Linie des Polygons in dieselbe
Richtung abbiegt. Als Ergebnis dieses Tests wird
festgestellt, ob die Richtung im Uhrzeigersinn oder gegen den
Uhrzeigersinn ist. Für zwei beliebige benachbarte Linien mit
den Punkten (x0,y0), (x1,y1), (x2,y2) wird das Vorzeichen des
Vektorprodukts wie folgt berechnet:
-
(y1-y0)*(x2-x1) - (y2-y1)*(x1-x0)
-
Wenn der obige Ausdruck größer als null ist, biegt das
Polygon nach rechts ab, also im Uhrzeigersinn. Wenn der obige
Ausdruck kleiner als null ist, biegt das Polygon nach links
ab, also gegen den Uhrzeigersinn. Wenn alle benachbarten
Linien dasselbe Vektorproduktvorzeichen haben, erfüllt das
Polygon die erste Bedingung der einheitlichen
"Abbiegerichtung".
-
Die zweite Bedingung, die erfüllt sein muß, damit es sich um
ein streng konkaves Polygon handelt, ist der Einmal-herum-
Test in y-Richtung. Wenn er bestanden ist, bedeutet dies, daß
die Summe der Innenwinkel gleich 360 Grad ist.
-
Der Einmal-herum-Test besagt, daß die y-Koordinaten der
aufeinanderfolgenden Kanten zuerst alle ansteigen und dann
wieder fallen müssen, wenn sich die Ausgangsposition am
untersten Eckpunkt befindet und das Polygon nacheinander
entlang der Kanten durchlaufen wird. Eine erste Gruppe von
Kanten des Polygons muß demnach, mit anderen Worten, zuerst
ausnahmslos ansteigen, und die zweite Gruppe von Kanten des
Polygons muß dann ausnahmslos fallen.
-
Die Einmal-herum-Bedingung ist erfüllt, wenn sich, beginnend
bei der ersten Linie des Polygons, das algebraische
Vorzeichen von y(i+1)-y(i) für alle benachbarten Eckpunkte
genau zwei- oder dreimal ändert. Horizontale Linien werden
gewertet, als hätten sie dasselbe Vorzeichen wie die
vorherige Linie. Polygone, die diesen Test bestehen, sind
ykonvex. Dies bedeutet, daß es für jeden y-Wert eine und nur
eine durchgehende Füllinie gibt. Während des Durchlaufs durch
die Punkte des Polygons für den "Einmal-herum-Test" werden
der maximale und der minimale y-Wert und die entsprechenden
Positionen im Speicher festgehalten.
-
Wenn der Test auf die einheitliche Abbiegerichtung und der
Einmal-herum-Test bestanden sind, ist das Polygon streng
konvex. Die Linien des Polygons können in zwei Gruppen
eingeteilt werden, so daß die Linien der einen Gruppe die
Maximalwerte der Abtastzeilen definieren, während die andere
Gruppe die Minimalwerte definiert.
-
Für ein streng konvexes Polygon wird eine einzige Tabelle mit
zwei Werten pro y-Wert verwendet. Der y-Wert liegt zwischen
null und der größten Zahl von Abtastzeilen auf der
betreffenden Anzeige. Ausgehend vom Punkt des y-Minimalwertes
und gegen den Uhrzeigersinn durchlaufend wird für jede Linie
des Polygons der Maximalwert der Linie für jede Abtastzeile,
die sie schneidet, in einer Tabelle gespeichert. Eine
Ausnahme wird bei Eckpunkten gemacht, bei denen sich zwei
Linien auf derselben Abtastzeile schneiden. Mit Hilfe einer
besonderen Verarbeitung wird ein Maximalwert auf dieser
Abtastzeile eines Pixels gespeichert, das beiden Linien
gemeinsam sein kann. Dies wird für jede Linie des Polygons
fortgesetzt, bis der maximale Eckpunkt in y-Richtung (ymax)
erreicht ist. Von diesem Punkt an definieren die Linien nur
minimale Abtastzeilen. Für jede Linie des Polygons wird der
Minimalwert dieser Linie für jede Abtastzeile, die sie
schneidet, in einer Tabelle gespeichert. Wieder wird eine
Ausnahme bei Eckpunkten gemacht, bei denen sich zwei Linien
auf derselben Abtastzeile schneiden. Mit Hilfe einer
besonderen Verarbeitung wird ein Minimalwert auf dieser
Abtastzeile eines Pixels gespeichert, das beiden Linien
gemeinsam sein kann. Nachdem die Tabelle ausgefüllt wurde,
indem alle Linien des Polygons durchlaufen wurden, wird in
einem bevorzugten Ausführungsbeispiel die GSL-Mehrfachlinien-
Zeichenroutine aufgerufen, um im Bereich ymin bis ymax pro y
eine horizontale Linie zu zeichnen. Andere bevorzugte
Ausführungsbeispiele können andere Verfahren nutzen, um eine
Linie von dem ausgewählten Minimal-Pixel zum ausgewählten
Maximal-Pixel für jede Abtastzeile zu zeichnen.
-
Die zweite Polygon-Füllroutine füllt eine größere Gruppe von
Polygonen als die erste Polygon-Füllroutine.
-
Mit dieser zweiten Polygon-Füllroutine können alle Polygone
gefüllt werden, wenn das Polygon mit genau einer
durchgehenden Linie pro Abtastzeile gefüllt werden kann.
Polygone in dieser Gruppe sind x-konkav und/oder haben sich
schneidende Linien.
-
Die einzige Prüfung besteht hier in dem oben beschriebenen
Einmal-herum-Test in y-Richtung. Auch die Werte ymin und ymax
mit ihren zugehörigen Eckpunkten werden festgehalten. In
diesem Fall ist nicht bekannt, ob die Richtung im
Uhrzeigersinn oder gegen den Uhrzeigersinn ist. In der Tat
ist nämlich bei Polygonen mit sich schneidenden Linien die
Unterscheidung zwischen der Richtung im Uhrzeigersinn und der
Richtung gegen den Uhrzeigersinn irrelevant.
-
Wieder werden die Linien des Polygons in zwei Gruppen
eingeteilt, diejenigen zwischen ymin und ymax in der
ursprünglich präsentierten Reihenfolge. Die Linien des
Polygons in jeder Gruppe können auf einer gegebenen
Abtastzeile ein Minimum oder ein Maximum definieren. Daher
werden zwei Tabellen verwendet, um entweder den Minimalwert
oder den Maximalwert zu speichern, und zwar jeweils einen für
jede Gruppe von Linien.
-
Ausgehend von dem Punkt des y-Minimalwertes des Polygons und
durch die erste Gruppe von Linien fortschreitend werden
sowohl das Minimum als auch das Maximum einer gegebenen Linie
am Schnittpunkt mit einer Abtastzeile gespeichert. Um das
Polygon durchlaufend speichert die zweite Tabelle ebenso den
Minimal- und den Maximalwert einer gegebenen Linie an jedem
Schnittpunkt mit einer Abtastzeile für die zweite Gruppe von
Linien in dem Polygon.
-
Der Minimalwert für eine gegebene Abtastzeile ist das Minimum
der zwei Werte für diese Abtastzeile aus den beiden Tabellen.
Ebenso ist der Maximalwert für eine gegebene Abtastzeile das
Maximum der zwei Werte für diese Abtastzeile aus den beiden
Tabellen. An diesem Punkt werden entweder die beiden Tabellen
abgetastet und zu einer Tabelle kombiniert und die GSL-
Mehrfachlinienfunktion aufgerufen, oder es werden Zeiger auf
beide Tabellen an eine neue GLS-Mehrfachlinienroutine
weitergegeben, die sie kombiniert, wenn sie das Zeichnen
jeder einzelnen horizontalen Linie anfordert. Andere
bevorzugte Ausführungsbeispiele können andere Verfahren
verwenden, um eine Linie von dem ausgewählten Minimal-Pixel
zu dem ausgewählten Maximal-Pixel für jede Abtastzeile zu
zeichnen.
-
Bei den obigen Polygon-Füllroutinen gibt es zwei Phasen der
Routine. In der ersten Phase werden alle Linien des Polygons
abgetastet. Für jede Linie des Polygons wird an jedem Punkt
auf einer Linie des Polygons die Bresenham-Routine
eingesetzt. Die Verarbeitungszeit, die zum Füllen eines
Polygons benötigt wird, wird optimiert, da die Entscheidung,
ob der Wert eines Punktes in einer Minimum-Maximum-Tabelle
gespeichert werden soll, zu dem Zeitpunkt getroffen wird, zu
dem die Bresenham-Routine den betreffenden Punkt bearbeitet.
Auf diese Weise erfolgt die Nachverarbeitung, die zweite
Phase, als Bestandteil der Vorverarbeitung, der ersten Phase.
Sobald die erste Phase, die Vorverarbeitung, abgeschlossen
ist, ist nur eine geringfügige zusätzliche Verarbeitung
erforderlich, um das Polygon zu füllen.
-
Die zweite Phase, die Nachverarbeitung, ist bei der ersten
Polygon-Füllroutine praktisch nicht vorhanden. Während die
Bresenham-Routine läuft, erfolgt eine einzelne Speicherung in
einer Tabelle mit einem Minimal- und einen Maximalwert für
jeden y-Wert der Abtastzeile. Bei der Nachverarbeitung wird
das Polygon gefüllt, indem die Matrix von ymin bis ymax
abgetastet wird und eine Linie vom Minimal- zum Maximalwert
gezogen wird, der für jeden y-Wert gespeichert ist.
-
Bei der Nachverarbeitung der zweiten Polygon-Füllroutine wird
das Polygon gefüllt, indem zuerst für jeden y-Wert das
Maximum der gespeicherten Maximalwerte sowie das Minimum der
gespeicherten Minimalwerte ermittelt wird. Dann wird für
jeden y-Wert eine Linie vom kleinsten Minimalwert zum größten
Maximalwert gezogen.
-
Die vorliegende Erfindung wird im weiteren Verlauf anhand
eines Beispiels unter Bezugnahme auf beide genannten
Beispiele nach dem Stand der Technik und ein
Ausführungsbeispiel der Erfindung beschrieben, das in den
beiliegenden Zeichnungen dargestellt ist, wobei gilt:
-
Fig. 1A zeigt ein Polygon, das nach Definition durch
Verfahren nach dem Stand der Technik konvex ist.
-
Fig. 1B zeigt ein Polygon, das nach Definition durch
Verfahren nach dem Stand der Technik nicht konvex ist.
-
Fig. 2A zeigt ein Polygon, das nach Definition durch
Verfahren nach dem Stand der Technik konvex ist.
-
Fig. 2B zeigt ein Polygon, das nach Definition durch
Verfahren nach dem Stand der Technik konvex ist.
-
Fig. 3A zeigt ein Polygon, das als allgemeines Polygon zur
Verwendung einer allgemeinen Polygon-Füllroutine
klassifiziert wird.
-
Fig. 3B zeigt ein Polygon, das als allgemeines Polygon zur
Verwendung einer allgemeinen Polygon-Füllroutine
klassifiziert wird.
-
Fig. 4A zeigt die Hardware einschließlich einer Anzeige eines
Verarbeitungssystems zur Nutzung dieser Art der
Polygonfüllung.
-
Fig. 4B zeigt die logische Struktur des Verarbeitungssystems.
-
Fig. 4C zeigt die phyische Struktur des Verarbeitungssystems.
-
Fig. 5 zeigt eine Matrix, die mit der ersten Polygon-
Füllroutine verwendet wird.
-
Fig. 6 zeigt die zwei Matrizes, die mit der zweiten Polygon-
Füllroutine verwendet werden.
-
Fig. 7 zeigt ein durch Pixel dargestelltes Polygon, das mit
der ersten und der zweiten Polygon-Füllroutine gefüllt wird.
-
Fig. 8A stellt eine Klasse von Polygonen dar, die mit der
ersten Polygon-Füllroutine und mit der zweiten Polygon-
Füllroutine gefüllt werden können.
-
Figs. 8B und 8C stellen eine Klasse von Polygonen dar, die
mit der zweiten Polygon-Füllroutine gefüllt werden können.
-
Fig. 8D stellt eine Klasse von Polygonen dar, die nicht mit
der ersten oder der zweiten Polygon-Füllroutine gefüllt
werden können.
-
Fig. 9 zeigt die Anordnung eines Polygons in Oktanten.
-
Fig. 10 zeigt den Rundungsfehler, wenn die Durchlaufrichtung
umgekehrt wird.
-
Fig. 11A zeigt eine Klasse von Polygonen, die den
Einmalherum-Test bestehen und mit der zweiten Polygon-Füllroutine
gefüllt werden können.
-
Fig. 11B zeigt eine Klasse von Polygonen, die den
Einmalherum-Test nicht bestehen und nicht mit der zweiten Polygon-
Füllroutine gefüllt werden können.
-
Fig. 11C zeigt eine Klasse von Polygonen, die nicht streng
konvex sind, in x-Richtung konkav sind, den Einmal-herum-Test
bestehen und mit der zweiten Polygon-Füllroutine gefüllt
werden können.
-
Das hier beschriebene Ausführungsbeispiel der vorliegenden
Erfindung umfaßt eine Folge von zwei Routinen zum schnelleren
Füllen eines Polygons und eine langsamere bekannte allgemeine
Routine sowie den notwendigen Treiber für die Kombination.
Diese Routinen könnten mit jeder zeilenweisen,
-
pixelgesteuerten Ausgabe wie etwa der Anzeige 94 (Fig. 4A)
verwendet werden, die mit einem Verarbeitungssystem 90 wie
dem IBM RT PC ausgestattet ist. Fig. 4B zeigt die logische
Struktur 91 des Verarbeitungssystems 90. 4C zeigt die
physische Struktur 92 des Verarbeitungssystems 90. Der RT PC
ist ausführlicher beschrieben in IBM RT Personal Computer
Technology, Form No. SA23-1057. Jede Routine hat Vor- und
Nachteile. Je nach der relativen Geschwindigkeit von
Prozessor, Anzeigeadapter, Speicher und E/A ist die eine oder
andere Routine effizienter für eine bestimmte Implementierung
auf einer gegebenen Anzeige.
-
Die beiden schnellen Füllroutinen dienen zum schnellen Füllen
bestimmter Polygone, die eine bestimmte Formklassifikation
aufweisen. Die erste schnelle Polygon-Füllroutine verwendet
eine Tabelle 100 (Fig. 5) zur Speicherung von Werten 110 bei
jeder y-Position 101, und die zweite schnelle Polygon-
Füllroutine verwendet zwei Tabellen 111, 112 (Fig. 6) zur
Speicherung von Werten 113 bei jeder y-Position 101, die zum
Füllen eines Polygons benötigt werden.
-
Die erforderlich Größe der Tabelle 100 (Fig. 5), 111, 112
(Fig. 6) hängt von der Größe des jeweils verwendeten
Anzeigebildschirms 94 (Fig. 4A) ab. Wenn die verwendete
Anzeige 94 eine Monochromanzeige mit 375 Bildelementen
(Pixeln) in der y-Richtung 102 ist, benötigt die Tabelle 100,
111, 112 375 Einträge 103. Wenn die Anzeige 94 (Fig. 4A) eine
APA8-Anzeige mit 512 Bildelementen (Pixeln) in der y-Richtung
102 ist, benötigt die Tabelle 100, 111, 112 512 Einträge 103.
Wenn die Anzeige 94 (Fig. 4A) eine Megapixel-Anzeige mit 1024
Bildelementen (Pixeln) in der y-Richtung 102 ist, benötigt
die Tabelle 100, 111, 112 1024 Einträge 103. Die y-Einträge
101 in der Tabelle 100, 111, 112 würden zwischen null 105 und
der Grenze des Bildschirms minus eins 107 liegen. Die Größe
der Tabelle 100, 111, 112 richtet sich daher nach der Größe
der Anzeige 94.
-
Die schnellen Füllroutinen sind so ausgelegt, daß die Tabelle
100 (Fig. 5) bzw. die Tabellen 111, 112 (Fig. 6) nicht für
jede Positionierung des Polygons 120 initialisiert werden
müssen, wenn das tatsächliche Polygon 120 (Fig. 4A) (nicht
maßstabsgerecht dargestellt) in y-Richtung zwischen Pixeln
mit Werten von y=10 bis y=47 liegt. Verwendet werden nur die
Einträge 103 in den einzelnen Tabellen 100, 111, 112, deren
y-Werte 101 in der y-Richtung 102 (Fig. 4) innerhalb des
Polygonbereichs (y=10 bis y=47) liegen. Wenn der unterste
Eckpunkt A des Polygons 120 beim zehnten Pixel in der y-
Richtung 102 vom unteren Rand der Bildschirmanzeige 94
beginnt, muß keine Tabelle 100, 111, 112 initialisiert
werden, so daß der Nulleintrag 105 den Eckpunkt A bei der
zehnten Pixelposition darstellt. Wenn das Polygon eine
Gesamthöhe von 37 Pixeln hat, werden nur der 11. bis 48.
Tabelleneintrag 103 genutzt.
-
Die zweite schnelle Füllroutine verwendet die zwei in Fig. 6
dargestellten Tabellen 111, 112. Jede der Tabellen 111, 112
hat eine Minimum-Spalte 116 und eine Maximum-Spalte 118. Die
Tabellen 111, 112 haben ebenfalls eine Größe, die zwischen
null 105 und der Größe des Bildschirms minus eins 107 liegt.
-
In Fig. 7 sind, wie auf der Anzeige 94 (Fig. 4A) angezeigt,
die Linien 121 bis 124 des Polygons 120 durch Bildelemente
(Pixel) wie etwa die Pixel 130 dargestellt, die über die
gesamten Abtastzeilen 132 y10 bis y18 eingeschaltet sind, so
daß sie die Linie 121 des Polygons 120 darstellen. Die Linien
121 bis 124 des Polygons 120 werden nicht wirklich auf dem
Bildschirm 94 (Fig. 4A) dargestellt, sondern sind hier nur zu
Beschreibungszwecken gezeigt. Die Entscheidung, welche Pixel
130 für jede Abtastzeile 132 eingeschaltet werden müssen, um
die Linien 121 bis 124 am besten darzustellen, wenn sie
angezeigt werden, wird mit Hilfe der Bresenham-Routine
getroffen, beschrieben in J. E. Bresenham, "Algorithm for
Computer Control of a Digital Plotter", IBM Systems Journal,
Bd. 4, Nr. 1 (1965), und in J. D. Foley und A. Van Dam,
Fundamentals of Interactive Computer Graphics (Addison-
Wesley), 1982.
-
In beiden schnellen Füllroutinen werden die Punkte 130 eines
Polygons 120 (Fig. 7) mit Hilfe der Bresenham-Routine
erzeugt. Die Pixel 130, die mit Hilfe der Bresenham-Routine
ausgewählt wurden, um die Linie 121 darzustellen, sind in
Fig. 7 durch eine ausgefüllte 0 dargestellt. Die Pixel 130,
die mit Hilfe der Bresenham-Routine nicht ausgewählt wurden,
um eine Linie 121 des Polygons 120 darzustellen, sind in Fig.
7 durch ein X dargestellt. Jede aufeinanderfolgende Reihe von
Pixeln 130, 131 in der y-Richtung 102 wird durch eine Gruppe
von Abtastzeilen 132 dargestellt. Für jede Linie 121, 122,
123, 124 des Polygons 120 werden jeweils gleichzeitig Punkte
130 auf einer Abtastzeile 132 generiert, die zusammen eine
Linie 121, 122, 123, 124 des Polygons 120 darstellen.
-
Die beiden schnellen Füllroutinen haben jeweils einen
unterschiedlichen Bereich einer Gruppe von Polygonen 33 (Fig.
8A), 34 (Fig. 8B), 35 (Fig. 8C), die mit der betreffenden
Routine gefüllt werden können. Die zweite Routine kann eine
größere Gruppe von Polygonen 33, 34, 35 füllen als die erste
Routine 60. Diese Gruppe umfaßt die Gruppe aller Polygone,
die so gefüllt werden können, daß es für jeden y-Wert 102
eindeutig eine einzelne Linie 133 gibt, mit deren Hilfe das
Polygon 33, 34, 35 gefüllt werden kann. Diese Gruppe von
Polygonen 33, 34, 35 kann Polygone umfassen, die konkav 28 in
der x-Richtung 104 sind. Zusätzlich umfaßt diese Gruppe
Polygone 35, die sich schneidende Linien 37, 38 aufweisen.
Das Polygon 36 (Fig. 8D) zeigt, daß es für jeden y-Wert 102
nicht eindeutig eine einzelne Linie gibt, mit deren Hilfe das
Polygon 36 gefüllt werden kann. Bei den unteren y-Werte gibt
es für jeden y-Wert zwei Linien 134, 135. Daher kann ein
Polygon 36, das konkav 29 in der y-Richtung ist, nicht mit
Hilfe der zweiten schnellen Füllroutine gefüllt werden. Bei
der ersten schnellen Füllroutine umfaßt die Gruppe der
Polygone nur streng konvexe Polygone 33. Hier kann es weder
in x- noch in y-Richtung konkave Stellen und auch keine sich
schneidenden Linien geben.
-
Daher gibt es zu jeder schnellen Füllroutine eine Vorroutine,
die feststellt, ob das Polygon in den Bereich der Polygone
für die betreffende Routine paßt, und die Routine möglichst
schnell verläßt, wenn sie feststellt, daß es nicht paßt.
Obwohl einer der Tests beiden Routinen gemeinsam ist, kommt
er daher in beiden Vorroutinen vor. Nachstehend sind die
Tests beschrieben, die mit dem Polygon durchgeführt werden,
um festzustellen, zu welchem Bereich von Polygonen ein
bestimmtes Polygon gehört.
-
Im Mittelpunkt der folgenden Erörterung steht das Polygon 120
in Fig. 7. Zunächst muß die Definition des Begriffs der
Richtungssensitivität eines Polygons erörtert werden.
Dasselbe Polygon 120 kann im Uhrzeigersinn 25 oder gegen den
Uhrzeigersinn 26 durch eine Abfolge von x- und y-Koordinaten
um das Polygon 120 herum beschrieben werden. Die Anwendung
einer gegebenen Polygon-Füllroutine muß dasselbe Ergebnis
haben, unabhängig davon, ob die Polygon-Füllroutine im
Uhrzeigersinn 25 oder gegen den Uhrzeigersinn 26 angewandt
wurde. Das Polygon muß also dieselbe Füllung bekommen, ohne
Rücksicht auf die Richtung, in der das Polygon 120 bei der
Anwendung der Füllroutine durchlaufen wurde. Bei beiden hier
beschriebenen Füllroutinen gibt es unabhängig von der
Reihenfolge, in der die Koordinaten der resultierenden
Bresenham-Pixel 130 präsentiert werden, keine
Richtungssensitivität. Außerdem bestimmt der erste Test für
die erste schnelle Füllroutine für streng konvexe Polygone
die Richtung, im Uhrzeigersinn 25 oder gegen den
Uhrzeigersinn 26, in der das Polygon durchlaufen wird, wenn
die Koordinaten der zugehörigen Pixel 130 des Polygons 120
präsentiert werden. Die erste schnelle Füllroutine ist nicht
richtungssensitiv, da die Richtung ausdrücklich als Teil des
Tests der Routine erkannt wird. Wenn festgestellt wird, daß
die Richtung im Uhrzeigersinn 25 ist, wird die Reihenfolge
umgekehrt, in der die Punkte (Pixel) 130 abgetastet werden.
Die Punkte 130 werden immer gegen den Uhrzeigersinn 26 um ein
Polygon herum abgetastet.
-
In der zweiten schnellen Füllroutine gibt es keine
Richtungssensitivität, da es dort für jede Seite 115, 114 des
Polygons 120 zwei Tabellen 111, 112 (Fig. 6) gibt. Jede
Tabelle 111, 112 hat für jede Abtastzeile 132 in der y-
Richtung 102 einen Minimal- 116 und einen Maximalwert 118 in
der x-Richtung 104. Daher ist es unerheblich, ob das Polygon
120 auf der einen Seite 114 aufwärts und auf der anderen
Seite 115 abwärts durchlaufen wird oder umgekehrt. Das
Ergebnis besteht aus zwei Tabellen 111, 112, wobei in jeder
der Tabellen 111, 112 für jede Abtastzeile 132 in der y-
Richtung 102 ein Minimal- 116 und ein Maximalwert 118 in der
x-Richtung 104 steht. Für jede Abtastzeile 132 wird unter den
beiden Maximalwerten 118 der Maximalwert für die beiden
Tabellen 111, 112 und unter den beiden Minimalwerten 118 der
Minimalwert für die beiden Tabellen 111, 112 gewählt.
Anschließend wird eine Füllinie von dem gewählten Minimal-
Pixel zu dem gewählten Maximal-Pixel gezogen.
-
Dies wird unter Bezugnahme auf Fig. 6 und Fig. 7 illustriert.
Für die Abtastzeile 132, die den y-Wert 101 von y=13
darstellt, ist der Maximalwert 118 für die Linie 121 des
Polygons 120 das Pixel 46 mit einem Wert 118 von x=263 in
diesem Beispiel. Dieser Wert würde in der Tabelle B 112
gespeichert. Der Minimalwert 116 für die Linie 121 des
Polygons 120 bei der Abtastzeile y=13 ist x=262 bei Pixel 45.
Dieser Wert von x=262 würde dann in der Tabelle B 112 bei
Eintrag y=13 gespeichert. Für die Linie 124 des Polygons 120
ist bei der Abtastzeile 132 von y=13 der Wert des Pixels 54
x=256. Da es nur ein Pixel 130 gibt, das von der Bresenham-
Routine für die Linie 124 bei dieser Abtastzeile
eingeschaltet wird, ist dieser Wert sowohl der Maximal- als
auch der Minimalwert von x bei y=13. Dieser Wert von x=256
wird in der Tabelle y bei Eintrag y=13 gespeichert. Aus der
Tabelle A 111 und der Tabelle B 112 ist der Maximalwert der
Maximalwerte 118 für y=13 263, und der Minimalwert der
Minimalwerte 116 ist für y=13 256. Anschließend wird eine
Füllinie 142 von Pixel 54 zu Pixel 46 gezogen, indem alle
dazwischenliegenden Pixel 130, 132 eingeschaltet werden, was
durch die symbolische Einrahmung der Pixelmarkierungen an den
einzelnen Pixelpositionen angedeutet ist.
-
Für die erste schnelle Füllroutine wird festgestellt, ob das
Polygon 120 in den Bereich der Polygone für diese bestimmte
Füllroutine paßt, und zugleich werden unter der Annahme, daß
die Feststellung gelingt, bestimmte Initialisierungswerte
registriert. Es gibt drei Teile dieses effektiv erweiterten
Tests, die zu der Vorroutine gehören: der Richtungstest (im
Uhrzeigersinn/gegen den Uhrzeigersinn), der die
Abbiegerichtung als Nebenergebnis festhält; der Einmal-herum-
Test in x- oder in y-Richtung sowie die Bestimmung des y-
Minimums und des y-Maximums für das betreffende Polygon zur
Initialisierung der Tabelle. Wenn das Polygon die beiden
ersten dieser Tests besteht, wird von der GSFF-Routine der
operative Teil namens "Genline" dieser ersten schnellen
Füllroutine aufgerufen. Besteht das Polygon einen dieser
Tests nicht, gibt es einen Ausweg zu der allgemeinen
Füllroutine, die in J. D. Foley und A. Van Dam, Fundamentals
of Interactive Computer Graphics, S. 456-460, beschrieben
ist.
-
Der erste Test für die erste schnelle Füllroutine ist der
Richtungstest (im Uhrzeigersinn/gegen den Uhrzeigersinn), der
auch als Abbiegetest bezeichnet wird und in "Method To
Determine The Convexity of Polygons", IBM Technical
Disclosure Bulletin, Bd. 28, Nr. 5, Oktober 1985, beschrieben
ist.
-
Genauer umfaßt das bevorzugte Ausführungsbeispiel der
vorliegenden Erfindung diesen Abbiegetest zur Überprüfung der
einheitlichen Abbiegerichtung. Von Linie zu Linie eines
Polygons wird also ermittelt, ob jede neue Linie in derselben
Richtung abbiegt. Als Nebenprodukt dieses Tests wird auch
ermittelt, ob die Richtung im Uhrzeigersinn oder gegen den
Uhrzeigersinn ist. Wenn zwei benachbarte Linien 121, 122
(Fig. 7) die Punkte (x0,y0), (x1,y1), (x2,y2) haben, erfolgt
die Berechnung des Vorzeichens des Vektorprodukts wie folgt
-
(y1-y0)*(x2-x1) - (y2-y1)*(x1-x0)
-
Wenn der obige Ausdruck größer als 0 ist, dann biegt das
Polygon 120 zwischen diesen zwei Linien des Polygons nach
rechts ab. In diesem Beispiel wäre das Vektorprodukt der
Linien 121 und 122 des Polygons 120 kleiner als null, und
dies zeigt an, daß das Polygon nach links bzw. gegen den
Uhrzeigersinn 26 abbiegt. Dieser Abbiegetest wird für alle
Nachbarlinienpaare des Polygons wiederholt. Wenn sich bei
diesem Tests für dasselbe Polygon dasselbe Vorzeichen ergibt,
besteht das Polygon den Test auf die einheitliche
Abbiegerichtung.
-
Die zweite Bedingung, die erfüllt sein muß, damit ein Polygon
streng konvex ist, ist der Einmal-herum-Test in y-Richtung.
Wenn er bestanden ist, bedeutet dies, daß die Summe der
Innenwinkel gleich 360 Grad ist.
-
Der "Einmal-herum-Test" besagt, daß die y-Koordinaten 102 der
aufeinanderfolgenden Kanten 121, 122, 123, 124 zuerst alle
ansteigen und dann wieder fallen müssen, wenn sich die
Ausgangsposition für den Durchlauf um das Polygon am
untersten Eckpunkt 1 (Fig. 7) befindet und das Polygon
nacheinander entlang der Kanten 121, 122, 123, 124
durchlaufen wird. Eine erste Gruppe von Kanten 121, 122 des
Polygons 120 muß demnach, mit anderen Worten, zuerst
ausnahmslos ansteigen, und die zweite Gruppe von Kanten 123,
124 des Polygons 120 muß dann ausnahmslos fallen. Die
Einmalherum-Bedingung ist erfüllt, wenn sich, beginnend bei der
ersten Linie 121 des Polygons 120, und zwar nicht unbedingt
an deren unterstem Punkt, das algebraische Vorzeichen von
y(i+1)-y(i) für alle benachbarten Eckpunkte genau zwei- oder
dreimal ändert. Horizontale Linien werden gewertet, als
hätten sie dasselbe Vorzeichen wie die vorherige Linie.
Polygone, die diesen Test bestehen, sind y-konvex. Dies
bedeutet, daß es für jeden y-Wert 102 eine und nur eine
durchgehende Füllinie 142 gibt. Während des Durchlaufs durch
die Punkte 130 des Polygons 120 für den "Einmal-herum-Test"
58 (Fig. 5A) werden die maximalen und minimalen y-Werte und
Positionen im Speicher festgehalten. Bevor in dieser Polygon-
Füllroutine die Bresenham-Routine verwendet wird, werden in
der Tabelle 100 das y-Maximum 2 und das y-Minimum 1 mit dem
x-Wert an diesen Positionen initialisiert. Dieser selbe x-
Wert für das y-Maximum 2 wird in der Tabelle 100 sowohl im
Maximaleintrag 107 als auch im Minimaleintrag 106 für den y-
Maximaleintrag 103 gespeichert. Ebenso wird derselbe x-Wert
für das y-Minimum 1 in der Tabelle 100 sowohl im
Maximaleintrag 107 als auch im Minimaleintrag 106 für den y-
Minimaleintrag 103 gespeichert.
-
Der Test auf die einheitliche Abbiegerichtung in Verbindung
mit dem Einmal-herum-Test in y-Richtung, der gleichbedeutend
ist mit der Feststellung, daß die Summe der Innenwinkel des
Polygons gleich 360 Grad ist, stellt fest, daß das Polygon
120 streng konvex ist. Als Ergebnis des Bestehens dieser
beiden Tests wird dann das Vorzeichen des Vektorprodukts, das
in dem Test auf eine einheitliche Abbiegerichtung berechnet
wurde, zur Bestimmung der Richtung des Polygons 120
verwendet. Wenn der Wert des obigen Ausdrucks größer als null
ist, wurde das Polygon 120 im Uhrzeigersinn 25 durchlaufen.
Wenn der Wert des obigen Ausdrucks kleiner als null ist,
wurde das Polygon 120 gegen den Uhrzeigersinn 26 durchlaufen.
Da die erste schnelle Füllroutine auf einer unidirektionalen
Operation, also z. B. gegen den Uhrzeigersinn 26, beruht, wird
die Reihenfolge, in der die Punkte 130 durchlaufen werden,
umgekehrt, wenn das Vorzeichen des Ausdrucks eine
Präsentation im Uhrzeigersinn 25 anzeigt.
-
Sobald nach dem obigen Verfahren festgestellt wurde, daß das
Polygon 120 streng konvex ist, können in Fig. 7 die Linien
121, 122, 123, 124 des Polygons 120 in zwei Gruppen 114, 115
partitioniert werden, so daß die Linien 121, 122 der einen
Gruppe 114 Maximalwerte 107 (Fig. 5) von Abtastzeilen 132
definieren, während die andere Gruppe 123, 124 Minimalwerte
106 (Fig. 56) definiert. Unabhängig von der Präsentation des
Polygons 120 durch die Vorverarbeitung des Polygons in den
obigen Tests wird festgestellt, daß der Eckpunkt 1 den y-
Minimalwert und der Eckpunkt 2 den y-Maximalwert hat.
-
Beim Durchlauf um das Polygon 120 vom y-Minimalwert 1 gegen
der Uhrzeigersinn 26 zum y-Maximalwert 2 wird der Maximalwert
der Abtastzeile 132 im Maximalwerteintrag 107 (Fig. 5) der
Tabelle 100 für den entsprechenden Index 103 von y
gespeichert. Wenn die erste schnelle Füllroutine von einer
Abtastzeile 132 zu der als nächster folgenden Abtastzeile 132
geht, wird der Maximalwert 107 von x auf der vorherigen
Abtastzeile gespeichert. Dies wird für jede Abtastzeile 132
wiederholt, bis der y-Maximalwert 2 erreicht ist. Sobald der
y-Maximalwert 2 erreicht ist, wird das Polygon 120 abwärts
vom y-Maximalwert 2 zum y-Minimalwert 1 über die Linien 123,
124 durchlaufen, die zuvor partitioniert wurden. Für diese
Gruppe 115 partitionierter Linien 123, 124 wird der letzte
Punkt 130 auf der Abtastzeile 132 als Minimalwert 106 von x
für jeden y-Eintrag 103 in der Tabelle 100 gespeichert. Dies
wird für jede Abtastzeile 132 wiederholt.
-
Für die erste schnelle Füllroutine beginnt die Routine beim
y-Minimalwert (Pixel 1, Fig. 7) und geht gegen den
Uhrzeigersinn 26 zu dem als Pixel 2 dargestellten y-
Maximalwert weiter. Während dieses Durchlaufs vom y-
Minimalwert 1 zum y-Maximalwert 2 wird die Tabelle 100
verwendet, die für jedes y 102 Minimal- und Maximaleinträge
110 aufweist. Der maximale x-Wert (der letzte Punkt (das
letzte Pixel) 130 auf einer Abtastzeile 132) für jedes y 102
wird in der Tabelle 100 gespeichert. Sobald bei dem Durchlauf
der y-Maximalwert 2 erreicht ist, wird das Polygon vom y-
Maximalwert 2 zum y-Minimalwert 1 durchlaufen. Während dieses
Teils des Polygon-Durchlaufs wird der Minimalwert für ein
Pixel 130 auf jeder Abtastzeile 132 in der Tabelle
gespeichert. Es ist mit anderen Worten der letzte Punkt 130,
der auf der vorherigen Abtastzeile abgetastet wird, nachdem
zur nächsten y-Abtastzeile übergegangen wurde. Auf dem Weg
gegen den Uhrzeigersinn 26 von dem untersten Eckpunkt 1 zum
obersten Eckpunkt 2 des Polygons 120 wird der Maximalwert in
der Matrix gespeichert. Auf dem Weg gegen den Uhrzeigersinn
26 von dem obersten Eckpunkt 1 zum untersten Eckpunkt 2 des
Polygons 120 wird der Minimalwert in der Matrix gespeichert.
So würde etwa beim Durchlauf um das Polygon 120 gegen den
Uhrzeigersinn 26, beginnend bei der Linie 121, der x-Wert bei
dem Pixel 42 in dem Maximaleintrag 107 für den y-Eintrag 103
bei y=11 gespeichert, der die Abtastzeile 132 für y=11
darstellt. Für die nächste Abtastzeile 132 von y=12 würde der
Wert des Pixels 44 in dem Maximaleintrag 107 für den y-
Eintrag 103 bei y=12 gespeichert. Dies wird für jede
Abtastzeile 132 wiederholt. Ebenso würde beim Durchlauf um
das Polygon 120 vom Eckpunkt 2 abwärts der Minimalwert für
ein Pixel 130 bei einer Abtastzeile 132 in dem Minimaleintrag
106 für den entsprechenden y-Eintrag 103 gespeichert. Zum
Beispiel würde der Wert der Pixel 54, 53, 51 im
Minimaleintrag 106 in der Tabelle 100 für die Abtastzeilen
132 gespeichert, die y=13, y=12 bzw. y=11 darstellen.
-
Für die erste schnelle Füllroutine, die als GSFF bezeichnet
wird, gibt es drei Eingabeparameter, die für die gegenwärtige
Erörterung von Bedeutung sind. Ein erstes Argument, inlines,
bei dem es sich um die Anzahl der Linien 121 bis 124 in dem
Polygon 120 handelt; ein zweites Argument, inx, bei dem es
sich um die Matrix von x Punkten in dem Polygon 120 handelt;
und ein drittes Argument, das die Matrix von y Punkten in dem
Polygon 120 bezeichnet. Das Argument xs ist ein Zeiger auf
den Beginn der Matrix 100, die abwechselnd sowohl Minimal-
106 als auch Maximalwerte 107 enthält, wie in Fig. 5
dargestellt. Der erste Eintrag ist der x-Minimalwert bei y=0,
der zweite Eintrag ist der x-Maximalwert bei y=0, der dritte
Eintrag ist der x-Minimalwert 106 bei y=1, der vierte Eintrag
ist der x-Maximalwert 107 bei y=1 usw. Dies setzt sich bis
zur Größe des Bildschirms minus 1 fort, bei einem Bildschirm
mit 1024 Pixeln in y-Richtung 102 also z. B. bis 1023. Das
Argument ys 155 ist einfach eine Matrix von Punkten
0,0,1,1,2,2,3,3 usw. bis zur Größe des Bildschirms minus 1,
also z. B. bis 1023,1023. Die ys-Matrix 101 wird einmal
initialisiert. Wenn diese Matrix 101 aufgerufen wird, wird
sie mit einem Paar aus x 110 und y 101 aufgerufen, um den
richtigen y-Wert mit dem richtigen x-Wert zu bekommen.
-
Die Routine setzt sich fort mit der Initialisierung des
Einmal-herum-y-Tests und des Abbiegetests einschließlich des
y-Minimalwerts und des y-Maximalwerts beim ersten Punkt. Als
nächstes kommt eine für-Schleife, die jeweils jeden der zuvor
erörterten Tests einmal durchführt. Die für-Schleife
berechnet laufend den Abbiegetest, aktualisiert laufend den
y-Minimalwert und den y-Maximalwert und aktualisiert den
Einmal-herum-Test. Wenn sich in dem Abbiegetest das
Vorzeichen des inneren Produkts ändert, wird ein lokales Flag
gesetzt. In dem Einmal-herum-Test ist das neue Vorzeichen
gleich 0, wenn er negativ ist, und gleich 1, wenn er positiv
ist. Zu dem alten Zähler wird eins hinzuaddiert, wenn das
neue Vorzeichen nicht gleich dem alten Vorzeichen ist. Dieser
Zähler zählt die Vorzeichenänderungen. Wenn das lokale Flag
gesetzt ist, das anzeigt, daß die Richtung, die in früheren
Vorkommen der Schleife berechnet wurde, anders ist als die
soeben berechnete Richtung, oder wenn der Zähler der
Vorzeichenänderungen von y vier - oder theoretisch auch mehr
als vier - erreicht, wird der Test nicht bestanden, ein
kombiniertes Flag "nicht bestanden" wird gesetzt, und die
Schleife wird verlassen. Wenn das kombinierte Flag "nicht
bestanden" nicht gesetzt ist, läuft die Schleife weiter.
-
Der nächste Schritt ist der y-Hoch-Test. Wenn das neue y
höher ist als das vorherige y-Maximum, wird der y-Maximalwert
auf den neuen Wert aktualisiert. Der Index, bei dem der neue
y-Maximalwert gefunden wurde, wird gespeichert. Dasselbe
geschieht mit dem Minimum. Wenn das Maximum nicht
überschritten wurde, wird der y-Minimalwert überprüft, um
festzustellen, ob der neue y-Wert niedriger als der vorherige
y-Minimalwert ist. Wenn dies der Fall ist, wird der y-
Minimalwert mit dem neuen y-Minimalwert aktualisiert. Der
Index wird ebenfalls aktualisiert, so daß er die Position des
y-Minimalwerts angibt. Damit endet die Schleife, die als
Vortest betrachtet werden kann.
-
Die Gesamtzahl der Punkte für die y-Matrix 101 (Fig. 5) wird
berechnet als Zweifaches der Summe y-Maximum minus y-Minimum
plus eins.
-
An diesem Punkt kann es eingerichtet werden, daß zu Zwecken
der Fehlerbeseitigung ein bedingungsabhängiger Ausdruck in
Verbindung mit einer Diagnoseausgabe erfolgt. Wenn das Flag
"nicht bestanden" gleich eins ist, wurde der Vortest nicht
bestanden. Wenn die Richtungen unterschiedlich sind, druckt
die Routine aus, daß der Konvexitätstest nicht bestanden
wurde. Wenn vier oder mehr Vorzeichenänderungen auftraten,
druckt die Routine aus, daß der Einmal-herum-Test nicht
bestanden wurde.
-
An diesem Punkt würde außerdem eine allgemeinere Routine zum
Füllen des Polygons aufgerufen, wenn der Vortest nicht
bestanden wurde, da die erste schnelle Füllroutine GSFF nicht
für den Polygontyp verwendet werden kann, den der Benutzer
zum Füllen ausgewählt hat.
-
Wenn das Flag "nicht bestanden" während des gesamten Vortests
nicht gesetzt wurde, läuft die GSFF-Routine weiter.
-
Wenn die Richtung, von der im Vortest festgestellt wurde, daß
sie konstant ist, gleich null ist, dann ist sie bereits gegen
den Uhrzeigersinn, und die Punkte 130 werden für jede Linie
121 bis 124 in dem Polygon von dem unteren Punkt aus gegen
den Uhrzeigersinn abgetastet. Wenn der untere Punkt nicht die
erste Linie des Polygons ist, werden die Parameter für
Genline, den eigentlichen Aufruf zum Herzen der ersten
schnellen Füllroutine, so adaptiert, daß dies berücksichtigt
wird. Die Schritte vor dem Genline-Aufruf stellen sicher, daß
auf die richtige Linie gezeigt wurde und daß sie gegen den
Uhrzeigersinn lief usw.
-
Genline hat fünf Argumente zu den - möglicherweise
adaptierten - Parametern, wie oben beschrieben. Das erste
Argument ist eine Adresse für die Minimum-Maximum-Matrix 100
(Fig. 5), in der für jeden y-Wert 103 die Werte von xmin 106
und und xmax 107 gespeichert sind. Die nächsten zwei
Argumente sind der x- und der y-Wert des j-ten Punktes in der
Abtastzeile, und die letzten zwei Argumente sind der x- und
der y-Wert des Punktes unmittelbar nach dem j-ten Punkt.
Daher wird Genline mit einem Zeiger auf die Matrix 100 sowie
mit einer Linie aufgerufen, die durch einen x- und einen y-
Wert für ein erstes Pixel und den benachbarten x- und y-Wert
für das zweite Pixel beschrieben ist.
-
Genline berechnet für jeden y-Wert einer Abtastzeile 132 den
Minimal- 106 und den Maximalwert 107. Es wird davon
ausgegangen, daß das Polygon 120 streng konvex ist und in
einer gegen den Uhrzeigersinn 26 laufenden Reihenfolge
präsentiert wird. Daher kann das Polygon 120 mit einer
einzigen horizontalen Linie 142 für jeden y-Wert 102 gefüllt
werden. Es wird nur eine Tabelle 100 verwendet, und für jede
Abtastzeile 132 wird nur ein Minimal- 106 und ein Maximalwert
107 in dieser Tabelle 100 gespeichert. Eine Linie mit
mehreren Pixeln 130 bei demselben y-Wert 102 wird behandelt,
indem x nur aktualisiert wird, wenn sich y ändert. Für Linien
in den Oktanten I, II, VII, VIII besteht die Aktualisierung
in dem Maximum 107, für Linien in den Oktanten III, IV, V, VI
besteht die Aktualisierung dagegen in dem Minimum 106. Wie in
Fig. 9 dargestellt, beginnt der Oktant I bei 0 Grad, wobei y
gleich null und x ein beliebiger positiver Wert ist, und
endet bei 45 Grad. Der Oktant II reicht von 45 Grad bis 90
Grad. Dies setzt sich in gleicher Weise für die Oktanten I
bis VIII fort. Eine Linie eines Polygons befindet sich in dem
Oktanten I, wenn der Winkel der Linie zwischen 0 und 45 Grad
liegt. Eine Linie eines Polygons befindet sich in dem
Oktanten II, wenn der Winkel der Linie zwischen 45 und 90
Grad liegt. Eine Linie eines Polygons befindet sich in einem
der acht Oktanten in Abhängigkeit von dem Winkel der Linie.
Das Polygon 120 ist innerhalb dieser Oktanten so organisiert,
daß die Punkte beim Durchlauf aufwärts an der Vorderfront
121, 122 nur in den Oktanten VII, VIII, I, II liegen können.
-
Die Tabelle 100 (Fig. 5) ist speziell für die erste schnelle
Füllroutine bestimmt, könnte aber auch für andere
Implementierungen genutzt werden. Der Schlüssel liegt darin,
daß alle y-Werte konstant sind und nur einmal bei der
Initialisierung berechnet werden, da es für jedes y 103 nur
ein x-Minimum 106 und ein x-Maximum 107 gibt.
-
Die Tabelle ist, wie in Fig. 5 dargestellt, folgendermaßen
organisiert:
-
y0 xmin
-
y0 xmax
-
y1 xmin
-
y1 xmax
-
y2 xmin
-
y2 xmax
-
ymax xmin
-
ymax xmax
-
Der Wert xmin wird für den Wert ymax initialisiert, und der
Wert xmax wird für den Wert ymax initialisiert. Dadurch
erübrigt sich das Speichern des minimalen oder maximalen x-
Wertes am ersten Punkt einer Linie. Der erste Punkt 141, 161
(Fig. 7) wird beim Zeichnen einer Linie ausgeschlossen, doch
jeder darauf folgende Punkt 130 wird eingeschlossen. Nur der
Teil der Tabelle 100 von ymin 1 bis ymax 2 des gegebenen
Polygons 120 wird zum Füllen des Polygons verwendet.
-
Daher erzeugt Genline die Punkte 130 für eine Linie 121 bis
124 des Polygons 120. Die Steigung der Linie wird erzeugt und
die Adresse der gegenwärtigen Position in der Matrix
berechnet. Diese Adresse zeigt auf das Minimum von x 106 in
der Tabelle 100 an der gegenwärtigen Position. Wenn y z. B. 10
ist, zeigt der Zeiger auf die 20. Position 108 in der Matrix
100. Dieser Eintrag 108 enthält den x-Minimalwert 106 für
y10, und der nächste Eintrag 109 enthält den x-Maximalwert
107 für y10.
-
Der Sonderfall, daß die Linie des Polygons 120 horizontal
ist, wird folgendermaßen abgedeckt
-
Wenn der erste y-Wert gleich dem zweiten y-Wert ist,
handelt es sich um eine horizontale Linie. Wenn auf der
horizontalen Linie x2 größer als x1 ist, liegen alle
Punkte auf derselben Abtastzeile, und die
Implementierung der Bresenham-Routine ist nicht
erforderlich. In diesem Fall wird der größte der Werte
x, x2 als x max gespeichert. Wenn x2 kleiner als x1 ist,
liegt die Linie in dem Oktanten III, IV, V oder VI, und
der kleinste der Werte x, x1 wird als x min 106
gespeichert.
-
Mit anderen Worten wird zu jeder der Linien des Polygons der
betreffende Oktant ermittelt, und die Linien des Polygons
werden nacheinander durchlaufen, während konzeptuell bei
diesem sequentiellen Durchlauf immer wieder von einer
vorherigen zur nächsten Abtastzeile übergegangen wird. Wenn
die aktuelle Linie im Oktanten I liegt, wird nach dem
Übergang von der vorherigen zur nächsten Abtastzeile ein
letztes auswählbares Pixel auf der vorherigen Abtastzeile
gewählt, und wenn die nächste Abtastzeile eine letzte
Abtastzeile ist, wird das letzte auswählbare Pixel auf der
nächsten Abtastzeile gewählt. Wenn die Linie im Oktanten V
liegt, wird nach dem Übergang von der vorherigen zur nächsten
Abtastzeile das letzte auswählbare Pixel auf der vorherigen
Abtastzeile gewählt, und wenn die nächste Abtastzeile eine
letzte Abtastzeile ist, wird das letzte auswählbare Pixel auf
der nächsten Abtastzeile gewählt. Wenn die Linie im Oktanten
II oder im Oktanten III oder im Oktanten VI oder im Oktanten
VII liegt, wird das auswählbare Pixel auf der nächsten
Abtastzeile gewählt. Wenn die Linie im Oktanten IV oder im
Oktanten VIII liegt, wird nach dem Übergang von der
vorherigen zur nächsten Abtastzeile das erste auswählbare
Pixel auf der nächsten Abtastzeile gewählt.
-
In welchem Oktanten die Linie 121 bis 124 liegt, wird
berechnet. Die Logik verzweigt in Abhängigkeit davon, ob x1
oder x2 größer ist, ob y1 oder y2 größer ist, und welches
relative Vorzeichen die Steigungen haben. In Abhängigkeit von
diesen drei Variablen gibt es acht verschiedene Fälle. Dann
wird gemeinsam mit den Bresenham-Konstanten "a" und "b" der
Oktant eingerichtet, in dem die Linie gezogen wird.
-
Die Konstanten "a" und "b" dienen zur Erzeugung von drei
weiteren Bresenham-Konstanten, die als "bma", "b2" und "i"
bezeichnet werden. Die Konstante bma 170 ist gleich zweimal b
minus a. Die Konstante b2 171 ist gleich zweimal b. Die
Konstante i 172 ist die Fehlerkonstante, die gleich zweimal b
minus a minus x2 kleiner als x1 ist. Der Term x2 kleiner als
x1 erzwingt eine korrekte Rundung, so daß dieselben Punkte
unabhängig von der Richtung gewählt werden, in der das
Polygon durchlaufen wird. Ein Beispiel hierfür ist in Fig. 10
gezeigt.
-
Wenn eine Bresenham-Linie gezogen wird, indem Punkte in einer
Richtung durchlaufen werden, ergibt sich typischerweise nicht
dieselbe Bresenham-Linie, wenn die Punkte in der
Gegenrichtung durchlaufen werden. Eine einfache Möglichkeit,
dies zu zeigen, ist eine Linie 8, die eine Steigung von
aufweist, wie in Fig. 10 dargestellt. Wenn die Linie bei
(0,0), Pixel 81, beginnt und bei (2,1), Pixel 84, endet,
liegt die Ideallinie direkt zwischen den Pixeln 82 und 83.
Die Bresenham-Routine ist so definiert, daß hier aufgerundet
wird. Daher würde statt Pixel 82 Pixel 83 eingeschaltet, wenn
die Linie im ersten Oktanten läge. Die Bresenham-Linie würde
daher aus den Pixeln 81, 83, 84 bestehen. Würde dieselbe
Linie dagegen so gezogen, als läge sie im Oktanten V, wäre
der Ausgangspunkt bei 2,1, und die Linie würde nach 0,0
durchlaufen. Beim Durchlauf in Gegenrichtung würde durch
Aufrunden das Pixel 82 ausgewählt. Um sicherzustellen, daß
dieselbe Linie dieselben Punkte unabhängig von der Richtung
umfaßt, in der sie durchlaufen wird, wird unabhängig von der
Richtung immer dieselbe Rundung erzwungen.
-
Der Rest der Ausführung von Genline verzweigt sich, um je
nach dem Oktanten, in dem die aktuelle der Linien 121 bis 124
liegt, den entsprechenden der acht verschiedenen Fälle
abzudecken. So geht etwa für Oktant I die Linie aufwärts, wie
zuvor für die Oktanten I, II, VII, VIII definiert wurde.
Daher versucht die Routine, für jedes y den Maximalwert von x
zu speichern. Der erste Punkt 141 (Fig. 7) wird in der
Schleife ausgeschlossen. Die Schleife beginnt bei x gleich x1
plus 1. Diese Schleife wird für x kleiner oder gleich x2
ausgeführt. Wenn der Fehlerkoeffizient kleiner als null ist,
bedeutet dies, daß der Wert nicht groß genug war, um zur
nächsten Abtastzeile zu gelangen. Die Konstante b2 wird zu i
hinzuaddiert, und die Schleife wird erneut ausgeführt. Wenn i
größer oder gleich null ist, bedeutet dies, daß der
Mittelpunkt überschritten ist und auf die nächste Abtastzeile
zugegriffen wird. In diesem Fall wird der vorherige Wert (x
minus 1) 42, 44, 46 usw. auf der vorherigen Abtastzeile in
der Tabelle als x max 107 für den vorherigen Wert von y
gespeichert. Auf diese Weise wird der letzte Maximalwert 42,
44, 46 jeder Abtastzeile 132 gespeichert. In den anderen vier
Oktanten wird ein Minimalwert gesucht. In den Oktanten I, IV,
V und VIII ist x indiziert, und in den anderen Quadranten ist
y indiziert. Außerdem gibt es einige Sonderfälle, in denen
das Ende einer Abtastzeile 132 erreicht ist und noch keine
Werte gespeichert sind. In diesem Fall wird der letzte x-Wert
(dargestellt durch x minus eins, da x in der für-Schleife
bereits inkrementiert wurde) für diese Abtastzeile
gespeichert.
-
In allen anderen Fällen wird auch das letzte Pixel der
vorherigen Abtastzeile gespeichert. Für jede Linie 121 bis
124 des Polygons 120 wird die Genline-Routine aufgerufen.
Welcher Teil der Routine implementiert wird, hängt davon ab,
in welchem Oktanten die Linie liegt.
-
Die Routine speichert für jede Linie 121 bis 124 des Polygons
120 nur eine Pixelposition 130 pro Abtastzeile 132. Dies
minimiert die Zahl der erforderlichen Speicheroperationen. Da
das Polygon streng konvex ist, gibt es genau einen Minimal-
106 und einen Maximalwert 107, die für jede Abtastzeile 132
gespeichert werden.
-
Das Haupttreiberprogramm ruft die erste schnelle Füllroutine
GSFF auf, die wiederum, wenn dies zugelassen ist, Genline
aufruft. Wird der GSFF-Vortest nicht bestanden, resultiert
der Abbruch zum Treiber in einem Aufruf der zweiten schnellen
Füllroutine, GSFF2. Wenn die Bedingungen des GSFF2-Vortests
erfüllt werden, ruft sie eine eigene Genline-Routine,
Genline 2, auf.
-
Die zweite schnelle Füllroutine GSFF2 prüft auch, ob das
betreffende Polygon innerhalb des Bereichs der Polygone
liegt, die sich für die zweite Polygon-Füllroutine eignen.
Dieser Test ist einfacher als der Test für die erste Polygon-
Füllroutine, da der Test für die zweite Polygon-Füllroutine
nur den Einmal-herum-Test und den y-Richtungstest umfaßt.
Solange die y-Werte 102 eines bestimmten Polygons nur steigen
und dann fallen, sofern am untersten Punkt des Polygons
begonnen wird, kann das Polygon mit dieser zweiten schnellen
Füllmethode gefüllt werden.
-
Ausgehend von einem beliebigen Punkt des geschlossenen
Polygons wird überprüft, ob das algebraische Vorzeichen von
y2-y1
sich entweder zwei- oder dreimal ändert. Dadurch wird
die Bedingung der "y-Konvexität" erfüllt. Dies bedeutet, daß
es für jeden y-Wert 102 eine und nur eine durchgehende
Füllinie 133 (Fig. 8A, 8B, 8C) gibt. Horizontale Linien
werden gewertet, als hätten sie dasselbe Vorzeichen wie die
vorherige Linie. Außerdem werden gleichzeitig die maximalen
und die minimalen y-Werte festgehalten. Wenn das Polygon den
GSFF2-Vortest nicht besteht, erfolgt der Abbruch zum Treiber,
der anstelle von Genline 2 die normale Polygon-Füllroutine GSL
aufruft.
-
Unter Bezugnahme auf Fig. 11A für diesen Einmal-herum-Test
und von dem Eckpunkt P aus im Uhrzeigersinn 25 durchlaufend
wird die Vorzeichenänderung von Delta y festgehalten. Beim
Übergang vom Eckpunkt P zum Eckpunkt Q ist Delta y positiv.
Beim Übergang vom Eckpunkt Q zum Eckpunkt R ist Delta y
negativ. Beim Übergang vom Eckpunkt R zum Eckpunkt S ist
Delta y negativ. Beim Übergang vom Eckpunkt S zum Eckpunkt T
ist Delta y negativ. Beim Übergang vom Eckpunkt T zum
Eckpunkt U ist Delta y positiv. Beim Übergang vom Eckpunkt U
zum Eckpunkt P ist Delta y positiv. Analysiert man die
Änderungen in der Änderung, änderte sich das Vorzeichen von
Delta y dreimal. Wenn ein Polygon den Einmal-herum-Test
besteht, ist die Zahl der verschiedenen Vorzeichenänderungen
genau zwei oder drei. Nimmt man dasselbe Polygon 61 wie in
Fig. 11A, wäre der Zähler der Vorzeichenänderungen zwei, wenn
das Polygon 61 beginnend bei dem Eckpunkt T im Uhrzeigersinn
durchlaufen würde. Vom Eckpunkt T zum Eckpunkt Q sind alle
Delta-y-Werte positiv, und vom Eckpunkt Q zum Eckpunkt T im
Uhrzeigersinn 25 sind alle Delta-y-Werte negativ.
-
Wenn der Zähler jeder Gruppe von Delta-y-Vorzeichenänderungen
größer als drei ist, besteht das Polygon den Einmal-herum-
Test nicht, wie in Fig. 11B zu sehen ist. Das in Fig. 11B
gezeigte Polygon 62 weist vier verschiedene Änderungen des
Vorzeichens von Delta y auf, wenn das Polygon 62 beginnend
beim Eckpunkt V im Uhrzeigersinn durchlaufen wird. Das in
Fig. 11B gezeigte Polygon 62 stellt ein Polygon dar, das
nicht mit dieser zweiten Polygon-Füllroutine 80 gefüllt
werden könnte. Dieses Polygon 62 könnte nicht mit nur einer
Abtastzeile 134, 135 gefüllt werden, wie sie zwischen Punkt 5
und Punkt 6 gezeigt ist. Obwohl die beiden Punkte 5 und 6
denselben y-Wert 102 haben, werden zum Füllen des Polygons 62
zwei verschiedene Linien 134, 135 benötigt.
-
Die zweite schnelle Füllroutine könnte so modifiziert werden,
daß sie Polygone füllt, die die Eigenschaften des Polygons 62
in Fig. 11B aufweisen, doch dann würde die Routine komplexer.
Zum Beispiel könnte die Routine so erweitert werden, daß sie
zwei Gruppen von Minimum- und Maximumwerten hat und diese
Werte initialisiert. Allerdings wird die Routine dadurch
komplexer, und die Allgemeingültigkeit der Routine geht
verloren.
-
Das in Fig. 11C gezeigte Polygon 63 ist nicht streng konvex,
doch dieses Polygon 63 paßt noch in die zweite Polygon-
Füllroutine 80. Dieses Polygon 63 ist konkav in der x-
Richtung. Dennoch besteht dieses Polygon 63 den Einmal-herum-
Test. Beim Durchlaufen des Polygons 63 im Uhrzeigersinn 25
beginnend beim Eckpunkt J ist Delta y vom Eckpunkt J zum
Eckpunkt K positiv. Vom Eckpunkt K zum Eckpunkt L und vom
Eckpunkt L zum Eckpunkt M ist das Vorzeichen von Delta y
negativ. Vom Eckpunkt M zum Eckpunkt J ist das Vorzeichen von
Delta y dann wieder positiv. Unabhängig von der
Ausgangsposition gibt es entweder zwei oder drei Änderungen
des Vorzeichens von Delta y. Dieses Polygon kann durch eine
einzige y-Abtastzeile 132 für jeden y-Wert 102 gefüllt
werden.
-
Wenn der Einmal-herum-Test bestanden ist, ruft GSFF2 Genline 2
auf, wie bereits erwähnt. Genline 2 hat Ähnlichkeit mit
Genline 1. Anstatt jedoch den letzten Punkt auf der
Abtastzeile 132 zu speichern, speichert Genline 2 den ersten
und den letzten Punkt auf einer Abtastzeile 132. Die Steigung
wird wie bei Genline 1 berechnet. Es wird dieselbe
Oktantenlogik befolgt wie bei Genline 1, und die Bresenham-
Routine wird auf dieselbe Weise initialisiert. Es wird
dieselbe für-Schleife von x gleich x plus eins bis x kleiner
oder gleich x2, oder je nach Quadrant die zugehörige y-
Schleife, ausgeführt. Der einzige Unterschied besteht darin,
daß jetzt sowohl der Minimal- als auch der Maximalwert
ausgewählt werden. Wenn i kleiner als null ist, bedeutet
dies, daß sich nichts ändert. Wenn i gleich i plus b minus a
ist, bei Tabelle plus eins, wird der vorherige Maximalwert
von x gespeichert. Sofort wird die Tabelle um eins erhöht,
und der gegenwärtige Wert von x, der auf der neuen
Abtastzeile liegt, wird ebenfalls gespeichert. Für jede
Abtastzeile wird die Füllinie vom kleinsten Minimalwert zum
größten Maximalwert der Werte gezogen, die in den beiden
Matrizes gespeichert sind.
-
Die Ausführung von Genline 2 beginnt an dem Punkt, an dem y
den Minimalwert 1 hat. Für jede Linie 121 bis 124 wird der
Minimal- und der Maximalwert auf jeder Abtastzeile 132 in
zwei Tabellen 111, 112 (Fig. 6) gespeichert. Jede Tabelle
111, 112 hat zwei Einträge 116, 118 für jeden y-Wert 103. Für
die Linien 121, 122 zwischen ymin 1 und ymax 2 werden gegen
den Uhrzeigersinn 26 Einträge in einer zweiten Tabelle 112
vorgenommen. Für die Linien 123, 124 zwischen ymax 2 und ymin
1 werden gegen den Uhrzeigersinn 26 Einträge in einer ersten
Tabelle 111 vorgenommen.
-
Auf dem aufsteigenden Weg um das Polygon 120 wird die Tabelle
B 112 verwendet, auf dem absteigenden Weg um das Polygon wird
die Tabelle A 111 verwendet. In dieser Routine wird mehr
gespeichert und verarbeitet, als in der ersten schnellen
Füllroutine erforderlich ist. Dadurch ist die zweite schnelle
Füllroutine langsamer als die erste. Der Vorteil ist jedoch,
daß mit ihr eine größere Klasse von Polygonen gefüllt werden
kann (Fig. 1A, 1B, 3A, 3B, 8A, 8B, 8C, 11A, 11B, 11C).
Trotzdem ist sie immer noch wesentlich schneller, benötigt
also wesentlich weniger Verarbeitungszeit, als die allgemeine
Polygon-Füllroutine.
-
Nach dem Ausfüllen der Tabellen 111, 112 und vor dem Aufrufen
einer Mehrfachlinien-Zeichenroutine zum Zeichnen einer
horizontalen Linie 142 pro y 102 im Bereich ymin 1 bis ymax 2
werden die beiden Tabellen 111, 112 zu einer Tabelle
kombiniert. Das Kombinieren besteht aus dem Ermitteln des
kleinsten von zwei Minimalwerten und des größten von zwei
Maximalwerten für jede Abtastzeile 132. Alternativ dazu
könnte die Mehrfachlinien-Zeichenroutine so geschrieben
werden, daß sie einen Zeiger auf beide Tabellen 111, 112
nimmt und den Minimal- und den Maximalwert für jede
Abtastzeile nach und nach anlegt.
-
Auf dem aufsteigenden Weg um das Polygon 120 werden die
beiden Werte des ersten Pixels 41, 43, 45 und des letzten
Pixels 42, 44, 46 auf jeder Abtastzeile 132 gespeichert. Ist
dies abgeschlossen, wird die Matrix B für jede Abtastzeile
132 mit dem Minimal- und dem Maximalwert von x ausgefüllt.
Auf dem absteigenden Weg um das Polygon 120 wird für jede
Abtastzeile 132 der Minimal- und dem Maximalwert von x in der
Matrix A 111 gespeichert. Durch die Bedingung der Konvexität
gibt es genau eine Linie auf dem aufsteigenden Weg und eine
Linie auf dem absteigenden Weg. Als abschließende
Nachverarbeitung werden jeweils beide Zeiger auf beide
Matrizes an die Anzeige geschickt, oder eine
Nachverarbeitungseinheit bestimmt den kleinsten Minimalwert
und den größten Maximalwert für jede Abtastzeile, die dann zu
der Anzeige geschickt wird.
-
Es wird darauf hingewiesen, daß die Richtungen x und y, die
für die vorangegangene Beschreibung herangezogen wurden, rein
konventionell sind und der beschriebene Ansatz so adaptiert
werden kann, daß er jede beliebige Anzeige berücksichtigt,
bei der die Abtastzeilen nicht in x-Richtung, sondern in y-
Richtung verlaufen.