DE68919024T2

DE68919024T2 - Verfahren und Prozessor zur Abtastumsetzung.

Info

Publication number: DE68919024T2
Application number: DE68919024T
Authority: DE
Inventors: Hazime Oki Electric I Hatanaka; Nobuhito Oki Electr Matsushiro; Ikuo Oki Electric Ind Co Oyake; Takayoshi Oki Electric Yoshida
Original assignee: Oki Electric Industry Co Ltd
Current assignee: Oki Electric Industry Co Ltd
Priority date: 1988-08-15
Filing date: 1989-08-15
Publication date: 1995-06-08
Anticipated expiration: 2009-08-16
Also published as: US5115402A; JPH0251786A; EP0356103A3; DE68919024D1; EP0356103B1; EP0356103A2; JP2690110B2

Description

HINTERGRUND DER ERFINDUNG

Diese Erfindung betrifft ein Abtast-Umwandlungsverfahren zum Umwandeln eines graphischen Zeichenelements, das durch seinen Umriß beschrieben wird, in eine Pixel-Tabelle, die für eine Raster-Ausgabe geeignet ist, und einen Prozessor zum Ausführen dieses Abtast-Umwandlungsverfahrens.
Eine Abtast-Umwandlung wird weit verbreitet auf Gebieten, wie beispielsweise Desktop-Publishing (rechnerunterstützte Druckvorlagengestaltung), CAD (rechnergestützte Entwicklung) und Computergraphik praktiziert. Auf dem Gebiet der rechnerunterstützten Druckvorlagengestaltung ermöglichen beispielsweise Seitenbeschreibungssprachen, wie beispielsweise die bekannte PostScript- Sprache, daß graphische Zeichenelemente, wie beispielsweise Zeichen und allgemeine graphische Figuren, durch ihre Umrisse ausgedrückt werden. Wenn solche graphischen Zeichenelemente an einer Raster-Ausgabevorrichtung, wie beispielsweise einem Punkt-Matrix- oder einem Laserdrucker oder einer Kathodenstrahlröhren-(CRT)-Anzeigeeinheit gedruckt oder angezeigt werden, müssen die Umrisse mit Pixeln aufgefüllt werden, die auf den Abtastlinien der Ausgabevorrichtung angeordnet sind. Dieses Auffüll-Verfahren ist das Abtast- Umwandlungsverfahren.
In der Vergangenheit ist das Abtast-Umwandlungsverfahren normalerweise durch einen Mikroprozessor für allgemeine Zwecke ausgeführt worden, aber es benötigt eine extensive Berechnung, die eine beachtliche Zeit dauern kann. Demgemäß sind Software-Techniken entwickelt worden, um die Zeit zu verkürzen, wie es beispielsweise auf den Seiten 456-460 von Fundamentals of Interactive Computer Graphics von J.D. Foley und A. van Dam, veröffentlicht von Addison Wesley Publishing Company im Jahre 1984, beschrieben ist.
Das Abtast-Umwandlungsverfahren, das in diesem Dokument beschrieben ist, verwendet eine nach Speicherbereichen sortierte Kanten-Tabelle mit einem "Speicherbereich" für jede Abtastzeile. Eine Information über den Umriß eines graphischen Zeichenelements ist in dieser Tabelle gespeichert, wobei eine Information für jede Kante in dem Speicherbereich der minimalen y-Koordinate der Kante gespeichert ist. Das Abtast-Umwandlungsverfahren wird für eine Abtastzeile pro Zeiteinheit ausgeführt. Eine aktive Kanten-Tabelle, die die Kanten anzeigt, die die gegenwärtige Abtastzeile schneiden, wird durch Verwenden der Information in der nach Speicherbereichen sortierten Kanten-Tabelle erzeugt und erneuert.
Ein Problem dieses Abtast-Umwandlungsvefahrens nach dem Stand der Technik besteht darin, daß es bezüglich seines Ausnutzens eines Speichers ineffizient wird, wenn die Anzahl von Abtastzeilen sehr groß ist. Einige Raster- Ausgabevorrichtungen haben eine Auflösung von 10.000 x 10.000 Punkten pro Seite. Wenn das oben beschriebene Abtast-Umwandlungsverfahren angewendet würde, würde es eine Kanten-Tabelle mit 10.000 Speicherbereichen verwenden, und zwar auch für graphische Zeichenelemente mit einer viel kleineren Anzahl von Kanten.
Das Abtast-Umwandlungsverfahren könnte bemerkenswert beschleunigt werden durch eine Ausführung an einem bestimmten Prozessor anstelle eines Mikroprozessors für allgemeine Zwecke. Idealerweise sollte der bestimmte Prozessor als ein einzelner integrierter Schaltkreis auf einem Halbleiterschip implementiert sein. Die zum Speichern der Kanten-Tabelle bei dem Abtast- Umwandlungsverfahren nach dem Stand der Technik benötigte Speicherplatzgröße schließt jedoch einen derartigen bestimmten Prozessor auf einem einzelnen Chip eher aus, auch wenn eine Integration sehr großen Ausmaßes (VLSI) verwendet wird. Die Kanten-Tabelle muß daher in einem externen Speicher gespeichert werden, aber dies kompliziert den Aufbau des Verarbeitungssystems. Es ist auch eine zusätzliche Zeit erforderlich, um eine Kanten-Information zwischen dem bestimmten Prozessor und dem externen Speicher zu transferieren, wodurch das Abtast-Umwandlungsverfahren verzögert wird.
Ein weiteres Problem bei dem Abtast-Umwandlungsverfahren nach dem Stand der Technik besteht darin, daß es den zum Unterscheiden zwischen dem Inneren und dem Äußeren eines graphischen Zeichenelements benutzten Algorithmus beschränkt, weshalb es Beschränkungen der Art auferlegt, in der ein graphisches Zeichenelement definiert werden kann. Das Abtast-Umwandlungsverfahren nach dem Stand der Technik benutzt einen Typ von "geradzahlig-ungeradzahlig- Algorithmus", bei dem von jeder Kante angenommen wird, daß sie eine Grenze zwischen dem Inneren und dem Äußeren ist. Dies verhindert die richtige Abtast- Umwandlung von graphischen Zeichenelementen mit einem sich selbst schneidenden Umriß, der zweimal um einen inneren Bereich herumlaufen kann.
Die PostScript-Sprache ermöglicht beispielsweise, daß zwei Algorithmen zur Innen-Außen-Unterscheidung ausgewählt werden: der "geradzahlig- ungeradzahlig-Algorithmus" und der "Nicht-Null-Windungs-Algorithmus". Der "Nicht-Null-Windungs-Algorithmus" läßt zu, daß ein Umriß eine beliebige Anzahl von Malen um einen inneren Bereich herumläuft, und schafft so eine zusätzliche Flexibilität bei der Definition graphischer Zeichenelemente. Das oben bechriebene Abtast-Umwandlungsverfahren nach dem Stand der Technik unterstützt den "Nicht-Null-Windungs-Algorithmus" nicht, weshalb er nicht den vollen Bereich von Eigenschaften unterstützt, die durch die weit verbreitet benutzte PostScript- Sprache vorgesehen sind und bei vielen Computergraphik-Anwendungen benötigt werden.

ZUSAMMENFASSUNG DER ERFINDUNG

Es ist demgemäß eine Aufgabe der vorliegenden Erfindung, ein graphisches Zeichenelement auf eine Weise einer Abtast-Umzuwandlung zu unterziehen, die einen Speicher effizient benutzt.
Eine weitere Aufgabe dieser Erfindung ist es, eine Auswahl zwischen Algorithmen zum Unterscheiden zwischen dem Inneren und dem Äußeren eines graphischen Zeichenelements bereitzustellen.
Eine weitere Aufgabe dieser Erfindung besteht darin, einen Abtast- Umwandlungsprozessor auf einem einzelnen Halbleiter-IC-Chip zu implementieren.
Diese Erfindung schafft ein Abtast-Umwandlungsverfahren zum Umwandeln eines graphischen Zeichenelements, das in einem x-y-Koordinatensystem durch einen Umriß definiert ist, der durch Kanten verbundene Scheitelpunkte aufweist, in Pixel- Daten, die auf Abtastlinien angeordnet sind, die parallel zu der x-Achse sind. Sie sieht auch einen Abtast-Umwandlungsprozessor vor.
Das Abtast-Umwandlungsverfahren ist im Anspruch 1 beansprucht und der Abtast- Umwandlungsprozessor ist im Anspruch 12 beansprucht.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

Fig. 1 ist ein Blockdiagramm eines Abtast-Umwandlungsprozessors, der die vorliegende Erfindung verkörpert.
Fig. 2 ist ein allgemeines Flußdiagramm eines Abtast- Umwandlungsverfahrens, das die vorliegende Erfindung verkörpert.
Fig. 3 ist ein detaillierteres Flußdiagramm des Dateneingabeverfahrens, das das Verfahren zum Erzeugen von Scheitelpunkt-Datenblöcken enthält.
Fig. 4 veranschaulicht die Wortstruktur eines Scheitelpunkt-Datenblocks.
Fig. 5 veranschaulicht ein graphisches Zeichenelement mit einem sich selbst schneidenden Umriß.
Fig. 6 veranschaulicht die Scheitelpunkt-Zeigerstruktur für das graphische Zeichenelement in Fig. 5.
Fig. 7 ist ein detailliertes Flußdiagramm des Verfahrens zum Erzeugen von Kanten-Datenblöcken.
Fig. 8 veranschaulicht U- und D-Kanten.
Fig. 9 veranschaulicht die Wortstruktur eines Kanten-Datenblocks.
Fig. 10 veranschaulicht die Kanten-Neigungsdaten, die für das graphische Zeichenelement in Fig. 5 gespeichert sind.
Fig. 11 veranschaulicht die Kanten-Ketten, die für das graphische Zeichenelement in Fig. 5 erzeugt sind.
Fig. 12 ist ein detailliertes Flußdiagramm des Verfahrens zum Abtasten des graphischen Zeichenelements und zum Umwandeln davon in Pixel- Daten.
Fig. 13 veranschaulicht den "Nicht-Null-Windungs-Algorithmus".
Fig. 14 veranschaulicht den "geradzahlig-ungeradzahlig-Algo- rithmus".
Fig. 15 veranschaulicht den Anfangszustand der aktiven Kanten-Ketten für das graphische Zeichenelement in Fig. 5.
Fig. 16 veranschaulicht das Hinzufügen von Blöcken zu der aktiven Kanten- Kette.
Fig. 17 veranschaulicht das Austauschen eines Blocks auf der aktiven Kanten-Kette.
Fig. 18 veranschaulicht das Löschen von Blöcken von der aktiven Kanten- Kette.
Fig. 19 veranschaulicht die Neuordnung von Blöcken auf der aktiven Kanten- Kette.
Fig. 20 veranschaulicht das Beenden des Abtast-Umwandlungsver- fahrens.
Fig. 21 veranschaulicht graphische Zeichenelemente, die durch zwei konzentrische Kreise definiert sind.

DETAILLIERTE BESCHREIBUNG DER AUSFÜHRUNGSBEISPIELE

Ein neues Abtast-Umwandlungsverfahren und ein Prozessor zum Umwandeln eines graphischen Zeichenelements, das in einem x-y-Koordinatensystem durch einen Umriß definiert ist, der aus durch Kanten verbundenen Scheitelpunkten besteht, in Pixel-Daten, die auf Abtastlinien angeordnet sind, die parallel zu der x-Achse des Koordinatensytems sind, wird nachfolgend unter Bezugnahme auf die Zeichnungen beschrieben. Der neue Abtast-Umwandlungsprozessor wird unter Bezugnahme auf Fig. 1 beschrieben. Das neue Abtast-Umwandlungsverfahren wird unter Bezugnahme auf die Fig. 2 bis 20 beschrieben.
Die Beschreibung des Verfahrens wird sich insbesondere mit der Abtast- Umwandlung eines graphischen Zeichenelements mit einem polygonalen Umriß zur Ausgabe auf einer monochromen Raster-Ausgabevorrichtung mit einem Bereich von Intensitätspegeln beschäftigen. Das graphische Zeichenelement wird durch eine Scheitelpunktliste definiert, die aus der x-Koordinate, der y-Koordinate und einem Intensitätspegel jedes Scheitelpunkts auf seinem Umriß-Polygon besteht. Ein graphisches Zeichenelement mit einem sich selbst schneidenden Umriß wird als Beispiel benutzt.
Als Abänderung wird die Abtast-Umwandlung eines graphischen Zeichenelements, das durch ein Paar konzentrischer Kreise definiert ist, unter Bezugnahme auf Fig. 21 erörtert.
Fig. 1 ist ein Blockdiagramm eines neuen Abtast-Umwandlungsprozessors, der Information über ein graphisches Zeichenelement von einer Ausgabevorrichtung für ein graphisches Zeichenelement (in der Zeichnung nicht gezeigt) empfängt, diese Information in Pixel-Daten umwandelt, und die Pixel-Daten zu einem Bildspeicher, wie beispielsweise einem Datenblock-Puffer oder einem Bildauffrischungspuffer, ausgibt. Von dem Bildspeicher können die Pixel-Daten zu einer Raster- Ausgabevorrichtung (in der Zeichnung nicht gezeigt), wie beispielsweise einem Drucker oder einer Kathodenstrahlröhre (CRT) geliefert werden.
Der Abtast-Umwandlungsprozessor besteht aus einem Eingangsregister 1 und einem Ausgangsregister 2 für den Austausch von Daten mit der Ausgabevorrichtung für ein graphisches Zeichenelement. Das Eingangsregister 1 bietet ein temporäres Speichern für Daten, die von der Ausgabevorrichtung für ein graphisches Zeichenelement empfangen werden. Das Ausgangsregister 2 bietet ein temporäres Speichern für Information, wie beispielsweise Befehle und Anfragen, die für ein graphisches Zeichenelement zu der Ausgabevorrichtung zu senden ist.
Das Eingangsregister 1 und das Ausgangsregister 2 werden durch eine Steuereinheit 3 gesteuert, die ihnen Steuersignale mittels Signalleitungen sendet, die in der Zeichnung nicht einzeln gezeigt sind. Die Steuereinheit 3 steuert auch die anderen Einheiten des unten beschriebenen Abtast-Umwandlungsprozessors.
Eine Information über ein graphisches Zeichenelement, das unter Verwendung des Eingangsregisters 1 und des Ausgangsregisters 2 unter Steuerung durch die Steuereinheit 3 erhalten wird, wird in einem Abtast-Uwmandlungsspeicher 4 gespeichert. Der Abtast-Umwandlungsspeicher 4 speichert auch Scheitelpunkt- Datenblöcke und Kanten-Datenblöcke, deren detaillierte Struktur in den Fig. 4, 6, 9, 10 und 11 veranschaulicht ist.
Der Abtast-Umwandlungsspeicher 4 ist mit dem Eingangsregister 1 und dem Ausgangsregister 2 durch einen Datenbus 5 verbunden. Der Datenbus 5 verbindet auch andere Einheiten des Abtast-Umwandlungsprozessors, wie es unten beschrieben ist.
Wenn Daten in dem Abtast-Umwandlungsspeicher 4 gespeichert sind, sind sie an einer Stelle gespeichert, die durch eine Adresse in einem Adreßregister 6 angezeigt wird. Die Adreßinformation in diesem Adreßregister 6 wird zum Zugreifen auf den Abtast-Umwandlungsspeicher 4 auf lineare Art benutzt.
Ein Adreßbus 7 befördert die Adreßinformation von dem Adreßregister 6 zu dem Abtast-Umwandlungsspeicher 4.
Die Stelle, an der Scheitelpunkt- und Kanten-Datenblöcke in dem Abtast- Umwandlungsspeicher 4 gespeichert sind, werden durch Adressen in einer Block- Adreßregister-Datei 8 angezeigt. Beispielsweise speichert die Block-Adreßregister- Datei 8 Start-Kantenzeiger zu den ersten Kanten-Datenblöcken auf Kanten-Ketten, was später beschrieben wird. Der Adreßbus 7 fördert Adreßinformation von der Block-Adreßregister-Datei 8 zu dem Abtast-Umwandlungsspeicher 4. Wenn die Block-Adreßregister-Datei 8 verwendet wird, um auf den Abtast- Umwandlungsspeicher 4 zuzugreigen, werden Adressen von Stellen in den Blöcken direkt durch die Steuereinheit 3 erzeugt.
Das Abtast-Umwandlungsverfahren enthält Additions-, Subtraktions- und Logik- Operationen, die durch eine Arithmetik- und Logikeinheit (ALU) 9 unter der Steuerung durch die Steuereinheit 3 ausgeführt werden. Diese Operationen werden beispielsweise durchgeführt, um Blockadressen zu inkrementieren, die von der Block-Adreßregister-Datei 8 erhalten werden, und um Werte zum Unterscheiden zwischen dem Inneren und dem Äußeren eines graphischen Zeichenelements zu inkrementieren. Zu diesem letzteren Zweck hat die ALU 9 einen internen Zähler 9a.
Das Abtast-Umwandlungsverfahren enthält auch Multiplikations- und Divisionsoperationen, die durch einen Multiplizierer/Dividierer 10 ausgeführt werden.
Die Steuereinheit 3 steuert die anderen Einheiten durch Ausführen von Mikroprogrammen, die in einer Mikroprogramm-Speichereinheit 11 gespeichert sind. Diese Mikroprogramme bestehen aus wenigstens einem ersten Mikroprogramm zum Durchführen eines Verfahrens, das in Fig. 3 veranschaulicht ist, einem zweiten Mikroprogramm zum Durchführen eines Verfahrens, das in Fig. 7 veranschaulicht ist, und einem dritten Mikroprogramm zum Durchführen des Verfahrens, das in Fig. 12 veranschaulicht ist.
Als Ergebnis des Ausführens dieser Mikroprogramme wird das eingegebene graphische Zeichenelement in Segmente aufgeteilt, die auf den Abtastlinien der Raster-Ausgabevorrichtung angeordnet sind. Die Segmente werden in Pixel-Daten umgewandelt, die zu einem Bildspeicher-Controller 12 geliefert werden.
Der Bildspeicher-Controller 12 beendet das Abtast-Umwandlungsverfahren durch Schreiben der Pixel-Daten in einen Bildspeicher 13. Von dem Bildspeicher 13 können die Pixel-Daten zu der Raster-Ausgabevorrichtung geliefert werden, wenn es nötig ist.
Der Bildspeicher 13 ist kein Teil des Abtast-Umwandlungsprozessors, so daß eine weitere Beschreibung davon weggelassen wird.
Als nächstes wird das neue Abtast-Umwandlungsverfahren unter Bezugnahme auf die Fig. 2 bis 20 beschrieben. Diese Beschreibung wird auch die Operation des neuen in Fig. 1 gezeigten Abtast-Umwandlungsprozessors erklären.
Fig. 2 ist ein allgemeines Flußdiagramm des neuen Abtast- Umwandlungsverfahrens. Es beginnt mit dem Erhalten von Eingabedaten für ein graphisches Zeichenelement von einer externen Ausgabevorrichtung für ein graphisches Zeichenelement und dem Erzeugen von Scheitelpunkt-Datenblöcken, die durch Scheitelpunkt-Zeiger in einer Reihenfolge zyklisch verbunden sind, die der Reihenfolge von Scheitelpunkten auf dem Umriß des graphischen Zeichenelements entspricht (Schritt 100). Dieses Verfahren wird später unter Bezugnahme auf Fig. 3 beschrieben. Die Scheitelpunkt-Datenblöcke werden in dem Abtast- Umwandlungsspeicher 4 in Fig. 1 gespeichert.
Als nächstes werden Kanten-Datenblöcke aus den Scheitelpunkt-Datenblöcken erzeugt (Schritt 101). Die Kanten-Datenblöcke bestehen aus den minimalen und maximalen y-Koordinatenwerten an entsprechenden Kanten, dem x- Koordinatenwert des Scheitelpunkts mit der minimalen y-Koordinate an der Kante, dem inkrementalen x-Koordinatenwert in bezug auf ein Einheitsinkrement in dem y- Koordinatenwert an der Kante, und anderer Information. Ein Merkmal dieses Verfahrens besteht darin, daß die Kanten-Datenblöcke in Kanten-Ketten gruppiert werden, die aufeinanderfolgende nach oben geneigte oder nach unten geneigte Kanten darstellen, wobei die Kanten-Datenblöcke auf jeweiligen Kanten-Ketten durch Kanten-Kettenzeiger in ansteigender Reihenfolge ihrer minimalen y- Koordinatenwerte verbunden sind. Dieses Verfahren wird später unter Bezugnahme auf Fig. 7 beschrieben.
Schließlich wird das graphische Zeichenelement an aufeinanderfolgenden Abtastlinien abgetastet, die Kanten-Datenblöcke werden zum Identifizieren von Kanten verwendet, die die Abtastlinien schneiden, die x-Koordinatenwerte in den Kanten-Blöcken werden verwendet, um Segmente zu erzeugen, die auf den Abtastlinien in dem Inneren des graphischen Zeichenelements angeordnet sind, und die Segmente werden in Pixel-Daten umgewandelt, die zu dem Bildspeicher 13 in Fig. 1 ausgegeben werden (Schritt 102). Während dieses Verfahrens werden die x- Koordinatenwerte unter Verwendung der inkrementalen x-Koordinatenwerte erneuert. Dieses Verfahren wird später unter Bezugnahme auf Fig. 12 beschrieben.
Ein weiteres Merkmal dieses Verfahrens besteht darin, daß die Scheitelpunkt- Datenblöcke zum Einsparen von Speicherplatz wiederum als die Kanten- Datenblöcke benutzt werden können. Darüber hinaus benötigt das Verfahren keine Kanten-Tabelle mit einem Eintrag für jede Abtastlinie wie bei dem Stand der Technik, so daß es einen relativ geringen Abtast-Umwandlungs-Speicherplatz benötigt. Folglich kann er durch einen integrierten Schaltkreis auf einem einzelnen Halbleiterchip implementiert werden. Insbesondere kann der gesamte Abtast- Umwandlungsprozessor in Fig. 1 einschließlich des Abtast-Umwandlungsspeichers 4 (aber nicht des Bildspeichers 13, der kein Teil des Abtast- Umwandlungsprozessors ist) auf einem einzelnen Halbleiterchip integriert werden, was den Aufbau von Desktop-Publishing-, CAD- und Computergraphik-Systemen ermöglicht, die eine hohe Geschwindigkeit haben und vergleichsweise einfach im Aufbau sind.
Als nächstes wird das Verfahren zum Erhalten der Daten über ein graphisches Zeichenelement und zum Erzeugen von Scheitelpunkt-Datenblöcken unter Bezugnahme auf Fig. 3 detaillierter beschrieben.
Als erstes werden die Daten für ein graphisches Zeichenelement von der Ausgabevorrichtung für ein graphisches Zeichenelement eingegeben. Dies wird dadurch erreicht, daß man die Steuereinheit 3 in Fig. 1 Befehle in dem Ausgangsregister 2 anordnen läßt, die veranlassen, daß die Ausgabevorrichtung für ein graphisches Zeichenelement durch Schreiben von Daten für ein graphisches Zeichenelement in das Eingangsregister antwortet. Die Daten für ein graphisches Zeichenelement werden in dem Eingangsregister 1 verzögert, und dann in einem Eingabedaten-Bereich in dem Abtast-Umwandlungsspeicher 4 gespeichert (Schritt 110).
Die Daten für ein graphisches Zeichenelement bestehen sowohl aus einer Scheitelpunkt-Liste als auch aus Information, die den zum Unterscheiden des Inneren und des Äußeren des graphischen Zeichenelements zu benutzenden Algorithmus bestimmt. Die Scheitelpunkt-Liste gibt die x-Koordinate, die y- Koordinate und den Intensitätspegel jedes Scheitelpunkts an, die den polygonalen Umriß des graphischen Zeichenelements definieren. Der Umriß des graphischen Zeichenelements besteht aus Kanten, die die Scheitelpunkte in ihrer Reihenfolge bezüglich der Scheitelpunkt-Liste verbinden, wobei der letzte Scheitelpunkt auch mit dem ersten verbunden wird. Der erste Scheitelpunkt wird Scheitelpunkt-Zahl 0 genannt, der nächste Scheitelpunkt Scheitelpunkt-Zahl 1 usw., bis zur Scheitelpunkt-Zahl M-1 (der letzte Scheitelpunkt), wobei M die Gesamtanzahl von Scheitelpunkten ist. Die Scheitelpunkt-Liste kann durch Nachführen auf dem Umriß des graphischen Zeichenelements in entweder der Uhrzeigerrichtung oder der Gegenuhrzeigerrichtung erzeugt werden.
Wenn eine Eingabe der Daten für ein graphisches Zeichenelement beendet ist, werden Scheitelpunkt-Datenblöcke erzeugt. Zuerst werden ein Scheitelpunkt-Zahl- Parameter IN und ein Block-Zahl-Parameter BL initialisiert (Schritt 111). Der Scheitelpunkt-Zahl-Parameter IN wird zu Null initialisiert. Der Block-Zahl-Parameter BL wird zu einem Wert N initialisiert, der beispielsweise aus der Zahl von Scheitelpunkten M und dem Verhältnis der Blockgröße zu der Eingabedatenmenge pro Scheitelpunkt berechnet werden kann. Der Block-Zahl-Parameter wird in der Block-Adreßregister-Datei 8 in Fig. 1 gespeichert.
Als nächstes werden die Scheitelpunkt-Daten des Scheitelpunktes mit der Zahl, die durch den Scheitelpunkt-Zahl-Parameter IN angezeigt ist, aus dem Eingabedaten- Bereich geholt (Schritt 112), und in einem Block in dem Abtast- Umwandlungsspeicher 4 gespeichert, wobei die Blockadresse durch den Block- Zahl-Parameter BL angezeigt wird (Schritt 113).
Fig. 4 zeigt die Struktur eines Scheitelpunkt-Datenblocks. Der Block besteht aus einer Anzahl von Worten, die der Einfachheit halber in Fig. 4 als neun Worte gezeigt sind, obwohl die Zahl von Worten in der Praxis normalerweise eine Zweierpotenz sein wird. In dem ersten Wort (W1) wird ein Wert gespeichert, der gleich dem gegenwärtigen Wert des Block-Zahl-Parameters BL plus 1 ist, welcher ein Scheitelpunkt-Zeiger (vp) zu dem nächsten Scheitelpunkt-Datenblock wird. Die x- Koordinate des Scheitelpunktes wird in dem dritten Wort W3 gespeichert, die y- Koordinate des Scheitelpunktes wird in dem vierten Wort W4 gespeichert, und der Intensitätspegel des Scheitelpunktes wird in dem achten Wort W8 gespeichert. Das siebte Wort W7 wird auf einen Wert, wie beispielsweise Null, gelöscht, und die anderen Worte, die in dieser Stufe bedeutungslose Daten enthalten, bleiben unverändert.
Die Wortadressen in dem Block werden durch die Steuereinheit 3 über das Adreßregister 6 in Fig. 1 zugeführt.
Als nächstes wird entschieden, ob der Strukturierungsprozeß, der aus Schritten 112 und 113 besteht, für den letzten Scheitelpunkt in den eingegebenen Daten für ein graphisches Zeichenelement beendet worden ist (Schrift 114). Wenn er nicht beendet worden ist, werden der Block-Zahl-Parameter BL und der Scheitelpunkt- Zahl-Parameter IN inkrementiert und dann springt das Verfahren zu dem oben beschriebenen Schritt 112 zurück (Schritt 115).
Wenn das Strukturierungsverfahren für den letzten Scheitelpunkt beendet worden ist, wird der Scheitelpunkt-Zeiger (vp) des letzten Blocks durch den Wert N ersetzt, der auf den ersten Block zeigt (Schritt 116). Die Scheitelpunkt-Datenblöcke werden nun durch die Scheitelpunkt-Zeiger in einer zyklischen Reihenfolge verbunden, die der Reihenfolge der Scheitelpunke auf dem Umriß des graphischen Zeichenelements entspricht. Der Wert N wird auch in einem gemeinsamen Block CBL gespeichert, und zwar genauer gesagt in einem Ursprungs-Zeigereintrag (rpe) in dem gemeinsamen Block CBL (Schritt 117). Der gemeinsame Block wird in der Block-Adreßregister-Datei 8 in Fig. 1 gespeichert.
Ein Beispiel der Datenstruktur, die aus dem vorangehenden Verfahren resultiert, wird unter Bezugnahme auf die Fig. 5 und 6 beschrieben. Fig. 5 zeigt ein graphisches Zeichenelement, das aus acht Scheitelpunkten v0 bis v7 besteht, die in der Gegenuhrzeigerrichtung verbunden sind. Die Koordinaten und Intensitäten dieser Scheitelpunkte werden in einer Reihenfolge von v0 bis v7 eingegeben und dann werden diese Scheitelpunkt-Daten in Blöcken N bis N+7 gespeichert, wie es in Fig. 6 veranschaulicht ist. Die Scheitelpunkt-Zeiger in den Blöcken N bis N+7 (die Daten in dem ersten Wort W1 in jedem Block) haben eine zyklische Struktur, während der Ursprungs-Zeigereintrag (rpe) in dem gemeinsamen Block CBL den Block N des ersten Scheitelpunktes anzeigt.
Als nächstes wird das Verfahren zum Erzeugen von Kanten-Datenblöcken unter Bezugnahme auf Fig. 7 beschrieben.
Zuerst wird ein Blockparameter BP auf den Wert in dem Ursprungs-Zeigereintrag (rpe) des gemeinsamen Blocks CBL initialisiert (Schritt 120). Dann werden die y- Koordinatenwerte in dem Scheitelpunkt-Datenblock, der gegenwärtig durch den Blockparameter BP angezeigt wird, und der nächste Scheitelpunkt-Datenblock (der durch den Scheitelpunkt-Zeiger in jenem Block angezeigt wird) verglichen, um zu bestimmen, ob die Kante, die die zwei entsprechenden Scheitelpunkte verbindet, in der Richtung nach oben oder nach unten geneigt ist (Schritt 121). Wenn die y- Koordinate in dem gegenwärtigen Block kleiner als die y-Koordinate in dem nächsten Block ist, wird bestimmt, daß die Kante eine nach oben geneigte Kante ist, was hierin nachfolgend eine U-Kante genannt wird. Andererseits wird bestimmt, daß die Kante nach unten geneigt ist, was hierin nachfolgend eine D-Kante genannt wird (Schritt 122).
Fig. 8 zeigt die Kanten des graphischen Zeichenelements in Fig. 5, die als U- oder D-Kanten bezeichnet sind. Der normale Richtungssinn von oben und unten ist umgekehrt, weil die positive y-Achse nach unten zeigt, wie es bei den x-y- Koordinatensystemen von CRT-Anzeigen üblich ist.
Wenn bestimmt wird, daß die Kante eine D-Kante ist, wird der Blockparameter BP auf den Wert erneuert, der durch den Scheitelpunkt-Zeiger (vp) des gegenwärtigen Scheitelpunkt-Datenblocks angezeigt wird, d.h. er wird erneuert, um den nächsten Scheitelpunkt-Datenblock anzuzeigen, und das Verfahren springt zum Schritt 121 zurück (Schritt 123). Wenn bestimmt wird, daß die Kante eine U-Kante ist, werden Kanten-Daten, die diese Kante beschreiben, nun in dem Block gespeichert, der gegenwärtig durch den Blockparameter BP angezeigt wird (Schritt 124).
Demgemäß wird der Block in dem Abtast-Umwandlungsspeicher 4, der bis jetzt Scheitelpunkt-Daten für einen der Scheitelpunkte der Kante hielt, als der Speicherbereich für die Kanten-Daten benutzt. Genauer gesagt werden die Kanten- Daten in dem Block gespeichert, der bis jetzt die Daten hielt, die seinen Anfangs- Scheitelpunkt in bezug auf die zyklische Reihenfolge der Scheitelpunkte auf dem Umriß des graphischen Zeichenelements betreffen. Für eine geschlossene Kurve gleicht die Anzahl von Scheitelpunkten der Anzahl von Kanten, so daß die Scheitelpunkt-Datenblöcke anzahlmäßig zur abermaligen Verwendung als die Kanten-Datenblöcke genau ausreichend sind.
Fig. 9 veranschaulicht die Wortstruktur der Kanten-Daten. Ein aktiver Kanten- Zeiger (aep) wird in dem ersten Wort W1 gespeichert, ein Kanten-Kettenzeiger (ecp) wird in dem zweiten Wort W1 gespeichert, die x-Koordinate des Scheitelpunkts mit dem minimalen y-Koordinatenwert an der Kante wird in dem dritten Wort W3 gespeichert, jener minimale y-Koordinatenwert (xmin) wird in dem vierten Wort W4 gespeichert, der inkrementale x-Koordinatenwert (dx/dy) in bezug auf ein Einheitsinkrement des y-Koordinatenwerts wird in dem fünften Wort W5 gespeichert, der maximale y-Koordinatenwert (ymax) an der Kante wird in dem sechsten Wort W6 gespeichert, eine Kanten-Neigungsinformation, die anzeigt, ob die Kante eine U-Kante oder eine D-Kante ist, wird in dem siebten Wort W7 gespeichert, der Intensitätswert des Scheitelpunkts mit dem minimalen y- Koordinatenwert wird in dem achten Wort W8 gespeichert, und das Inkrement (dl/dy) des Intensitätswerts in bezug auf ein Einheitsinkrement des y- Koordinatenwerts wird in dem neunten Wort W9 gespeichert. Im Schritt 124 werden Daten in dem dritten bis neunten Wort (W3 bis W9) gespeichert. Die ersten zwei Worte behalten ihre existierenden Werte, wobei der Scheitelpunkt-Zeiger (vp) in dem ersten Wort W1 gespeichert wird und bedeutungslose Daten in dem zweiten Wort W2.
Ein Erzeugen der inkrementalen Daten, die in dem fünften und neunten Wort W5 und W9 gespeicehrt sind, erfordern Multiplikations- und Divisionsoperationen, die durch den Multipilzierer/Dividierer 10 in Fig. 1 durchgeführt werden.
Wenn das Erzeugen und Speichern von Daten für eine Kante im Schritt 124 beendet worden ist, wird der Blockparameter BP auf den Wert des Scheitelpunkt- Zeigers (vp) des gegenwärtigen Blocks erneuert, was den nächsten Scheitelpunkt- Datenblock anzeigt (Schritt 125), nachdem entschieden ist, ob Daten erzeugt und für alle Kanten gespeichert worden sind (Schritt 126). Diese Entscheidung kann danach getroffen werden, ob Kanten-Neigungsdaten in dem siebten Wort W7 des Blocks gespeichert sind, der durch den Blockparameter BP angezeigt wird, weil dieses Wort auf einen Wert wie beispielsweise Null gelöscht ist, der weder die U- noch die D-Neigung darstellt, wenn die Scheitelpunkt-Daten gespeichert sind.
Wenn das Entscheidungsergebnis im Schritt 126 negativ ist, wird ein Rücksprung zu dem oben beschriebenen Schritt 124 durchgeführt, um Daten für weitere Kanten zu erzeugen und zu speichern. Wenn das Entscheidungsergebnis bestätigend ist, geht das Verfahren weiter zum Schritt 127, das später beschrieben wird.
Es ist wichtig, daß das Verfahren zum Erzeugen und Speichern von Kantendaten im Schritt 124 mit einer U-Kante beginnt. Wenn dieses Verfahren mit einer D-Kante beginnen würde, würde während des Verarbeitens des vorangehenden Blocks Information verloren, die zum Erzeugen der inkrementalen Daten in dem fünften und neunten Wort W5 und W9 benötigt wird.
Für das Beispiel eines graphischen Zeichenelements in Fig. 8 erzeugt das Verfahren durch einen Schritt 126 Blöcke von Kanten-Daten, wie es in Fig. 10 veranschaulicht ist, wobei Daten für die Kanten W01 bis E70, die in Fig. 5 gezeigt sind, in den Blöcken N bis N+7 gespeichert werden. Die Kanten E01, E12, E45 und E56 sind U-Kanten, so daß Information, die eine U-Kante bezeichnet, in dem siebten Wort der Blöcke N, N+1, N+4 und N+5 gespeichert wird. Die Kanten E23, E34, E67 und E70 sind D-Kanten, so daß Information, die eine D-Kante bezeichnet, in Blöcken N+2, N+3, N+6 und N+7 gespeichert wird.
Nachdem die Blöcke von Kanten-Daten erzeugt worden sind, wie es oben beschrieben ist, werden Kanten-Ketten durch ein Verfahren gebildet, das beispielhaft durch Schritte 127 bis 146 in Fig. 7 dargestellt ist. Eine Kanten-Kette stellt eine aufeinanderfolgende Reihe von U-Kanten oder D-Kanten dar. Die entsprechenden Kanten-Datenblöcke werden durch Einstellen von Kanten- Kettenzeigern (ecp) in ihren zweiten Worten W2 gruppiert.
Das Verfahren zum Bilden von Kanten-Ketten kann wie folgt abgebrochen werden. Zuerst wird eine U-Kante, der eine D-kante vorangeht, gefunden (Schritte 127 bis 131 in Fig. 7).
Als nächstes werden die Kanten-Datenblöcke, die diese und alle folgenden U- Kanten darstellen, aus einer Kanten-Kette in einer ansteigenden Reihenfolge ihrer minimalen y-Koordinatenwerte verbunden, und ein Start-Kanten-Zeiger auf dem ersten Kanten-Datenblock auf dieser Kanten-Kette wird in einem gemeinsamen Datenblock eingestellt (Schritte 132 bis 136 und Schritt 143). Dann wird die nächste D-Kante gefunden, die Kanten-Datenblöcke davon und alle folgenden D- Kanten werden auf einer Kanten-Kette in einer ansteigenden Reihenfolge ihrer minimalen y-Koordinatenwerte verbunden, und ein Start-Kanten-Zeiger auf dem ersten Kanten-Datenblock auf dieser Kanten-Kette wird in dem gemeinsamen Datenblock eingestellt (Schritte 137 bis 142).
Dann wird die nächste U-Kante gefunden und getestet, um zu entscheiden, ob es die Kante ist, die in den Schritten 127 bis 131 gefunden ist. In Fig. 7 wird diese Entscheidung tatsächlich während des Erzeugens der vorangehenden Kette von D- Kanten als Schritt 139 durchgeführt. Wenn das Entscheidungsergebnis negativ ist, wird das in dem vorangehenden Abschnitt beschriebene Verfahren wiederholt.
Schließlich werden die Start-Kanten-Zeiger in dem gemeinsamen Block in ansteigender Reihenfolge der minimalen y-Koordinatenwerte in den Kanten- Datenblöcken sortiert, auf die sie zeigen, und die aktiven Kanten-Zeiger in allen Kanten-Datenblöcken werden gelöscht.
Ein detailliertes Verfahren zum Ausführen des Kanten-Ketten-Bildungsprozesses wird nun unter Bezugnahme auf Fig. 7 beschrieben.
Zuerst wird der Blockparameter BP wieder auf den Wert in dem Ursprungs- Zeigereintrag (rpe) in dem gemeinsamen Block CBL initialisiert (Schritt 127). Als nächstes wird das siebte Wort W7 des Blocks, das durch den Blockparameter BP angezeigt wird, gelesen, um zu bestimmen, ob die zugehörige Kante eine U-Kante oder eine D-Kante ist (Schritt 128). Wenn die Kante eine U-Kante ist, wird der Blockparameter BP auf den Wert erneuert, der durch den Scheitelpunkt-Zeiger (vp) in dem ersten Wort angezeigt wird (Schritt 129), und ein Rücksprung zum Schritt 127 wird durchgeführt.
Wenn die Kante eine D-Kante ist, wird der Blockparameter BP ähnlich dazu auf den Wert erneuert, der durch den Scheitelpunkt-Zeiger angezeigt wird (Schritt 130), und das siebte Wort W7 in dem Block, der nun durch den Blockparameter BP angezeigt wird, wird gelesen, um zu bestimmen, ob die Kante, die zu jenem Block gehört, eine U-Kante oder eine D-Kante ist (Schritt 131). In diesem Fall wird, wenn die Kante eine D-Kante ist, ein Rücksprung zum Schritt 130 durchgeführt, aber wenn die Kante eine U-Kante ist, geht das Verfahren zum Schritt 132 weiter, das unten beschrieben ist.
Der Effekt der vorangehenden Schritte 127 bis 131 besteht darin, eine U-Kante zu finden, der auf dem Umriß des graphischen Zeichenelements eine D-Kante vorangeht. Wenn eine derartige U-Kante gefunden worden ist, wird ihre Blockzahl in einem ersten Start-Kantenzeiger (sep0) in dem gemeinsamen Block CBL eingestellt (Schritt 132).
Als nächstes wird der Blockparameter BP auf den Wert erneuert, der durch den Scheitelpunkt-Zeiger (vp) in dem gegenwärtigen Block angezeigt wird (Schritt 133), und das siebte Wort W7 in dem Block, der nun durch den Blockparameter BP angezeigt wird, wird gelesen, um zu bestimmen, ob die zugehörige Kante eine U- Kante oder eine D-Kante ist (Schritt 134).
Wenn die Kante eine U-Kante ist, da sie der vorangehenden U-Kante folgt, wird die Blockzahl dieses Blocks in dem Kanten-Kettenzeiger (ecp) des vorangehenden Blocks gespeichert (Schritt 135), und ein Rücksprung zum Schritt 133 wird durchgeführt. Eine Wiederholung der Schritte 133 bis 135 erzeugt eine Kanten- Kette aus Kanten-Datenblöcken, die aufeinanderfolgende U-Kanten darstellt.
Wenn das Ergebnis der Entscheidung im Schritt 134 darin besteht, daß die Kante eine D-Kante ist, wird ein besonderer Wert (wie beispielsweise -1) in dem Kanten- Kettenzeiger (ecp) des vorangehenden Blocks gespeichert, um die Kanten-Kette zu beenden, die aufeinanderfolgende U-Kanten darstellt (Schritt 136). Ein spezieller Beendigungswert wird auch in dem Kanten-Kettenzeiger des gegenwärtigen Blocks gespeichert (Schritt 137). Der Grund für den Schritt 137 besteht darin, daß Kanten- Datenblöcke, die D-Kanten darstellen, dann, wenn sie durch Nachfolgen der Scheitelpunkt-Zeiger gefunden werden, in einer abfallenden Reihenfolge ihrer minimalen y-Koordinatenwerte gefunden werden, weshalb der letzte Block auf der Kanten-Datenkette zuerst gefunden wird.
Als nächstes wird der Blockparameter BP auf den Wert erneuert, der durch den Scheitelpunkt-Zeiger angezeigt wird (Schritt 138), und dieser Wert wird mit dem Wert in dem ersten Start-Kantenzeiger (sep0) in dem gemeinsamen Block CBL verglichen (Schritt 139). Wenn diese zwei Werte ungleich sind, was anzeigt, daß das Verfahren zum Bilden von Kanten-Ketten nicht beendet ist, wird das siebte Wort W7 in dem Block, der nun durch den Blockparameter BP angezeigt wird, gelesen, um zu bestimmen, ob die zugehörige Kante eine U-Kante oder eine D-Kante ist (Schritt 140).
Wenn die Kante eine D-Kante ist, da sie der vorangehenden D-Kante folgt, wird die BIockzahl des vorangehenden Kanten-Datenblocks in dem Kanten-Kettenzeiger (ecp) des gegenwärtigen Blocks gespeichert, wodurch diese Blöcke in einer ansteigenden Reihenfolge ihrer minimalen y-Koordinatenwerte verbunden werden, und das Verfahren springt zu dem oben angegebenen Schritt 138 zurück (Schritt 141).
Wenn das Entscheidungsergebnis im Schritt 140 derart ist, daß die Kante eine U- Kante ist, wodurch die aufeinanderfolgende Reihe von D-Kanten beendet wird, wird die Blockzahl des vorangehenden Blocks in dem nächsten Start-Kantenzeiger (sep1, sep2, ...) in dem gemeinsamen Block CBL als ein Zeiger auf den ersten Block auf der Kanten-Kette gespeichert (Schritt 142). Dies beendet das Erzeugen einer Kanten-Kette aus Kanten-Datenblöcken, die aufeinanderfolgende D-Kanten darstellen.
Als nächstes wird die Blockzahl des gegenwärtigen Blocks in dem nächsten Start- Kantenzeiger in dem gemeinsamen Block CBL als ein Zeiger auf den ersten Block in einer U-Kanten-Kette gespeichert (Schritt 143). Dann wird ein Rücksprung zum Schritt 133 durchgeführt, um mit der Bildung dieser U-Kanten-Kette fortzufahren.
Wenn das Entscheidungsergebnis im Schritt 139 derart ist, daß der Wert des Blockparameters BP dem Wert des ersten Start-Kantenzeigers (sep0) in dem gemeinsamen Block CBL gleicht, was anzeigt, daß alle Kanten-Ketten beendet worden sind, wird die Blockzahl des vorangehenden Blocks in dem nächsten Start- Kantenzeiger in dem gemeinsamen Block CBL als ein Zeiger auf den ersten Block einer Kanten-Kette gespeichert (Schritt 144), dann werden die Start-Kantenzeiger in dem gemeinsamen Block CBL in ansteigender Reihenfolge der minimalen y- Koordinatenwerte in den Blöcken neu sortiert, auf die sie zeigen (Schritt 145).
Wenn das Erzeugen von Kanten-Ketten auf diese Weise beendet ist, werden die ersten Worte W1 aller Kanten-Blöcke, die bisher die Scheitelpunkt-Zeiger (vp) hielten, in Vorbereitung für das nächste Verfahren gelöscht, bei dem sie aktive Kanten-Zeiger halten werden (Schritt 146). Dies beendet das Verfahren zum Bilden einer Kanten-Kette.
Für das in den Fig. 5 und 8 veranschaulichte Beispiel eines graphischen Zeichenelements gibt es vier Gruppen aufeinanderfolgender U-Kanten oder D- Kanten: eine Gruppe besteht aus den Kanten E01 und E12, eine Gruppe besteht aus den Kanten E67 und E70, eine Gruppe besteht aus den Kanten E23 und E34 und eine Gruppe besteht aus den Kanten E45 und E56. Ein Ausführen des oben beschriebenen Verfahrens erzeugt somit vier Kanten-Ketten CH1 bis CH4, wie es in Fig. 11 veranschaulicht ist.
Als nächstes wird das Verfahren zum Abtasten des graphischen Zeichenelements, zum Erzeugen von Segmenten, die auf den Abtastlinien in dem Inneren des graphischen Zeichenelements angeordnet sind, und zum Umwandeln dieser Segmente in Pixel-Daten zur Ausgabe zu einem Bildspeicher unter Bezugnahme auf Fig. 12 detailliert beschrieben.
Dieses Verfahren untersucht das graphische Zeichenelement auf aufeinanderfolgenden Abtastlinien, die von der Abtastlinie mit dem minimalen y- Koordinatenwert, der in dem graphischen Zeichenelement auftritt, zu der Abtastlinie mit dem maximalen y-Koordinatenwert, der in dem graphischen Zeichenelement auftritt, fortschreiten. Der y-Koordinatenwert der Abtastlinie, die gerade untersucht wird, wird in einem Parameter gespeichert, der in Fig. 12 mit sy bezeichnet ist.
Während dieses Verfahrens wird eine aktive Kanten-Kette, die Kanten darstellt, die die gegenwärtige Abtastlinie schneiden, mittels der aktiven Kanten-Zeiger (aep) in den ersten Worten der Kanten-Datenblöcke beibehalten. Ein Ursprungs-Zeiger (aep0) zu dem ersten Block in der aktiven Kanten-Kette wird in dem gemeinsamen Block CBL beibehalten. Ein Beibehalten der aktiven Kanten-Kette enthält Verfahren zum Sortieren und das abermalige Verbinden der aktiven Kanten-Zeiger, die durch bekannte Techniken ausgeführt werden, die nicht im Detail beschrieben werden. Da die aktiven Kanten-Zeiger am Ende des vorangehenden Verfahrens gelöscht wurden, ist die aktive Kanten-Kette anfangs leer.
Das Verfahren beginnt durch Initialisieren des Abtastlinien-Koordinatenwertes (sy) zu dem minimalen y-Koordinatenwert (ymin) des ersten Kanten-Datenblocks auf der ersten Kanten-Kette, die durch den ersten Start-Kantenzeiger (sep0) in dem gemeinsamen Block CBL angezeigt wird (Schritt 150 in Fig. 12).
Als nächstes werden alle Kanten-Datenblöcke, die am Anfang der Kanten-Ketten angeordnet sind und bei denen der minimale y-Koordinatenwert (ymin) dem Abtastlinien-y-Koordinatenwert (sy) gleicht, zu der aktiven Kanten-Kette addiert (SChritt 151). Bei diesem Schritt werden die Start-Kantenzeiger in dem gemeinsamen Block CBL verwendet, um die Blöcke am Anfang der Kanten-Ketten zu identifizieren. Da die Start-Kantenzeiger in ansteigender Reihenfolge des minimalen y-Koordinatenwerts sortiert sind, kann dieser Schritt schnell durchgeführt werden. In vielen Fällen wird es lediglich notwendig sein, einen Block zu testen.
Als nächstes werden die Kanten-Datenblöcke auf der aktiven Kanten-Kette in ansteigender Reihenfolge der x-Koordinatenwerte in ihren dritten Worten W3 sortiert, und ihre aktiven Kanten-Zeiger (aep) werden wieder in dieser Reihenfolge verbunden (Schritt 152). Die Blockzahl von dem Block, der nun der erste Block auf der aktiven Kanten-Kette ist, wird in dem ursprünglichen aktiven Kanten-Zeiger (aep0) in dem gemeinsamen Block CBL gespeichert, und ein spezieller Wert (wie beispielsweise -1) wird in dem Block gespeichert, der nun der letzte Block auf der aktiven Kanten-Kette ist, um anzuzeigen, daß es der letzte ist.
Als nächstes werden Segmente, die auf der folgenden Abtastlinie in dem Inneren des graphischen Zeichenelements angeordnet sind, unter Verwendung der x- Koordinaten in den dritten Worten der Blöcke auf der aktiven Kanten-Kette erzeugt (Schritt 153). Der Algorithmus, der zum Unterscheiden zwischen dem Inneren und dem Äußeren des graphischen Zeichenelements benutzt wird, kann entweder der "Nicht-Null-Windungs-Algorithmus" oder der "geradzahlig/ungeradzahlig- Algorithmus" sein, wie es durch die Ausgabevorrichtung eines graphischen Zeichenelements bestimmt wird, wenn die Daten eines graphischen Zeichenelements ursprünglich eingegeben wurden.
Wenn der "Nicht-Null-Windungs-Algorithmus" bestimmt wird, wird der Zähler 9a in der ALU 9 auf 0 gelöscht, und dann werden die Kanten-Neigungsdaten in dem siebten Wort W7 der Blöcke auf der aktiven Kanten-Kette in der Reihenfolge der aktiven Kantenzeiger untersucht. Für jeden Block wird der Zähler 9a um 1 inkrementiert, wenn die Kanten-Neigungsdaten eine U-Kante anzeigen, und um 1 dekrementiert, wenn die Kanten-Neigungsdaten eine D-Kante anzeigen. Wann immer der Wert des Zählers 9a sich von 0 zu einem von 0 verschiedenen Wert ändert, wird der x-Koordinatenwert in dem dritten Wort W3 des zugehörigen Blocks als der Anfang eines Segments genommen. Wenn als nächstes der Wert des Zählers 9a zu 0 zurückkehrt, wird der x-Koordinatenwert in dem dritten Wort W3 des zugehörigen Blocks als das Ende jenes Segments genommen.
Fig. 13 veranschaulicht diesen Algorithmus für eine der Abtastlinien, die das Beispiel eines graphischen Zeichenelements in Fig. 5 schneiden. Für diese Abtastlinie besteht die aktive Kanten-Kette aus Kanten-Datenblöcken, die die Kanten E12 (U), E56 (U), E23 (D) und E67 (D) darstellen. Der Wert des Zählers 9a ändert sich von Null zu Eins an der Kante E12, dann zu Zwei an der Kante 56, dann zu Eins an der Kante E23 und kehrt an der Kante E67 zu Null zurück. Ein einzelnes Element wird somit von der x-Koordinate der Kante E12 bis zu der x-Koordinate der Kante E67 erzeugt (in der Zeichnung durch die dicke Linie angezeigt).
Wenn der "geradzahlig/ungeradzahlig-Algorithmus" bestimmt wird, wird der Zähler 9a in der ALU 9 auf 0 gelöscht, und dann werden die Blöcke auf der aktiven Kanten- Kette in der Reihenfolge der aktiven Kanten-Zeiger genommen und der Zähler 9a wird für jeden Block um Eins inkrementiert. Wenn sich der Zähler 9a von einem geradzahligen Wert zu einem ungeradzahligen Wert ändert, wird der x- Koordinatenwert in dem dritten Wort W3 des zugehörigen Blocks als der Anfang eines Segments genommen. Wenn der Zähler 9a von einem ungeradzahligen Wert zu einem geradzahligen Wert zurückkehrt, wird der x-Koordinatenwert in dem dritten Wort W3 des zugehörigen Blocks als das Ende jenes Segments genommen.
Fig. 14 veranschaulicht den "geradzahlig/ungeradzahlig-Algorithmus" für dieselbe Abtastlinie in Fig. 13. Der Wert des Zählers 9a ändert sich von Null zu Eins an der Kante E12, zu Zwei an der Kante E56, zu Drei an der Kante E23, und zu Vier an der Kante E67. Somit werden Segmente von der x-Koordinate der Kante E12 bis zu der x-Koordinate der Kante E56 und von der x-Koordinate der Kante E32 bis zu der x- Koordinate der Kante E67 erzeugt (in der Zeichnung durch die dicken Linien angezeigt).
Wie es in den Fig. 13 und 14 veranschaulicht ist, kann die Ausgabevorrichtung für ein graphisches Zeichenelement durch Auswählen des Algorithmus zur Unterscheidung zwischen innen und außen wählen, ob Teile eines graphischen Zeichenelements, die durch den Umriß doppelt enthalten sind, als Inneres oder Äußeres zu dem graphischen Zeichenelement anzusehen sind. Diese Wahl vereinfacht die Definition vieler Typen graphischer Zeichenelemente, wie beispielsweise jener mit einer Vielzahl von überlappenden Teilen.
Nachdem auf diese Weise Segmente auf der gegenwärtigen Abtastlinie erzeugt worden sind, werden sie in Pixel-Daten umgewandelt, die zu dem Bildspeicher- Controller 12 in Fig. 1 geliefert und in dem Bildspeicher 13 gespeichert werden (Schritt 154). Bei diesem Verfahren werden die Intensitätsdaten in den achten Worten W8 der Blöcke, die zu den Endpunkten eines Segments gehören, verwendet, um einen Intensitätswert für jedes Pixel in dem Segment zu berechnen. Eine Interpolation wird durchgeführt, so daß sich die Pixelwerte von der Intensität an einem Endpunkt zu der Intensität an dem anderen Endpunkt schrittweise verdunkeln. Es werden auch Pixel-Adressen erzeugt und zu dem Speicher- Controller 12 geliefert. Die notwendigen Berechnungen werden durch die ALU 9 und den Multiplizierer/Dividierer 10 auf Anweisung von der Steuereinheit 3 ausgeführt. Das Segment-zu-Pixel-Umwandlungsverfahren ist wohlbekannt, so daß eine detaillierte Beschreibung weggelassen wird.
Als nächstes wird die aktive Kanten-Kette gesucht, um alle Kanten-Datenblöcke darauf zu finden, deren maximale y-Koordinatenwerte (y-max) dem Abtastlinien-y- Koordinatenwert (sy) gleichen (Schritt 155). Wenn keine gefunden werden, geht das Verfahren weiter zum Schritt 160, der später beschrieben ist.
In jedem Block, in dem der maximale y-Koordinatenwert (ymax) dem Abtastlinien-y- Koordinantenwert (sy) gleicht, wird der Kanten-Kettenzeiger (ecp) des Blocks gelesen, um zu bestimmen, ob der Block der letzte Block auf seiner Kanten-Kette ist (Schritt 156). Wenn er nicht der letzte Block auf seiner Kanten-Kette ist, wird der Block auf der aktiven Kanten-Kette durch den Block ersetzt, der durch seinen Kanten-Kettenzeiger angezeigt wird, wobei dieser der nächste Kanten-Datenblock auf seiner Kanten-Kette ist (Schritt 157).
Wenn ein Block im Schritt 156 als der letzte Block auf seiner Kanten-Kette angesehen wird, wird er von der aktiven Kanten-Kette gelöscht (Schritt 158), und es wird entschieden, ob die aktive Kanten-Kette nun leer ist (Schritt 159). Wenn die aktive Kanten-Kette leer ist, endet das Abtast-Umwandlungsverfahren.
Nachdem das vorangehende Verfahren für alle Blöcke beendet worden ist, in denen der maximale y-Koordinatenwert dem Abtastlinien-y-Koordinatenwert gleicht, werden der x-Koordinatenwert in dem dritten Wort W3 und der Intensitätswert in dem achten Wort jedes Blocks auf der aktiven Kanten-Kette durch den inkrementalen x-Koordinatenwert dx/dy in dem sechsten Wort und dem inkrementalen Intensitätswert dl/dy in dem neunten Wort jenes Blocks erneuert (Schritt 160). Dann wird der Abtastlinien-y-Koordinatenwert (sy) um eine Einheit zu dem Wert auf der nächsten Abtastlinie inkrementiert, und es wird ein Rücksprung zum Schritt 151 durchgeführt, um die nächste Abtastlinie zu verarbeiten (Schritt 161). So fährt das Verfahren fort, bis die aktive Kanten-Kette leer ist, an welchem Punkt das graphische Zeichenelement vollständig in Pixel-Daten umgewandelt worden ist.
Die Schritte in Fig. 12 werden als nächstes unter Bezugnahme auf die Fig. 15 bis 20 für das Beispiel eines graphischen Zeichenelements, das in Fig. 5 gezeigt ist, veranschaulicht. Genauer gesagt werden verschiedene bei der aktiven Kanten- Kette durchgeführte Arten von Änderungen veranschaulicht. Jede Zeichnung zeigt die gegenwärtige Abtastlinie, die bei einer bestimmten Position in dem graphischen Zeichenelement angeordnet ist, und veranschaulicht den Zustand der aktiven Kanten-Kette vor und nach der Verarbeitung jener Abtastlinie.
Fig. 15 zeigt den Anfangszustand, wenn die Abtastlinie bei dem kleinsten y- Koordinatenwert der Kante E01 ist (Schritt 150 in Fig. 12). Vor diesem Zustand ist die aktive Kanten-Kette leer. In diesem Zustand werden zwei Blöcke zu der aktiven Kanten-Kette addiert: die Blöcke N und N + 7, die die Kanten-Daten für die Kanten E01 und E70 speichern.
Fig. 16 veranschaulicht die Addition neuer Blöcke zu der aktiven Kanten-Kette. Wenn die Abtastlinie den minimalen y-Koordinatenwert der Kanten E34 und E45 erreicht, werden die Blöcke N + 3 und N + 4, die diese Kanten darstellen, zu der aktiven Kanten-Kette addiert (Schritt 151 in Fig. 12), und die aktive Kanten-Kette wird erneut sortiert (Schritt 152 in Fig. 12), so daß sie aus den Blöcken N, N + 3, N + 4 und N + 7 in dieser Reihenfolge besteht.
Fig. 17 veranschaulicht das Ersetzen eines Blocks auf der aktiven Kanten-Kette durch den nächsten Block in seiner Kanten-Kette. Wenn die Abtastlinie den maximalen y-Koordinantenwert der Kante E01 erreicht, wird der entsprechende Block N getestet (in Schritt 156 in Fig. 12) und es wird gefunden, daß er nicht der letzte Block auf seiner Kanten-Kette ist, so daß er auf der aktiven Kanten-Kette durch den Block ersetzt wird, der durch seinen Kanten-Kettenzeiger angezeigt wird (Schritt 157 in Fig. 10). Das heißt, daß der Block N durch den Block N + 1, der die Kante E12 darstellt, ersetzt wird.
Fig. 18 veranschaulicht das Löschen von Blöcken von der aktiven Kanten-Kette. Wenn die Abtastlinie den maximalen y-Koordinatenwert der Kante E56 und E67 erreicht, werden die entsprechenden Blöcke N + 5 und N + 6 getestet (im Schritt 156 in Fig. 12), und es wird gefunden, daß sie nicht die letzten Blöcke auf ihren Kanten-Ketten sind, so daß sie von der aktiven Kanten-Kette gelöscht werden (Schritt 158 in Fig. 12).
Fig. 19 veranschaulicht das Neuordnen von Blöcken auf der aktiven Kanten-Kette. In dieser Zeichnung hat die Abtastlinie einen Punkt, der kein Scheitelpunkt ist, eines Schnitts der Kanten E56 und E23 erreicht. Bei dem nächsten bis zum letzten Schritt beim Verarbeiten dieserAbtastlinie (Schritt 160 in Fig. 12) werden die x- Koordinaten in den dritten Worten der Kanten-Datenblöcke zu ihren Werten auf der nächsten Abtastlinie erneuert, was zum Ergebnis hat, daß die x-Koordinatenwerte der Blöcke N + 5 und N + 2 nicht länger in ansteigender Reihenfolge sind. Wenn die aktive Kanten-Kette in Vorbereitung für das Erzeugen von Segmenten auf der nächsten Abtastlinie neu sortiert wird (Schritt 152 in Fig. 10), wechseln diese zwei Blöcke demgemäß die Plätze.
Fig. 20 veranschaulicht das Beenden des Verfahrens. Wenn die Abtastlinie den maximalen y-Koordinatenwert der Kanten E12 und E23 erreicht, da die entsprechenden Blöcke N + 1 und N + 2 die letzten Blöcke auf ihren jeweiligen Kanten-Ketten sind, werden sie von der aktiven Kanten-Kette gelöscht, wie es im Zusammenhang mit Fig. 18 erklärt ist. Dann wird die aktive Kanten-Kette getestet und als leer befunden (Schritt 159 in Fig. 12), so daß das Abtast- Umwandlungsverfahren endet.
Wenn das Verfahren endet, sind Pixel-Daten für das gesamte Innere des graphischen Zeichenelements in dem Bildspeicher 13 gespeichert worden. Diese Daten können erneut von dem Bildspeicher 13 gelesen werden, einer Raster- Ausgabevorrichtung zugeführt werden, und durch wohlbekannte Verfahren ausgegeben werden.
Als nächstes werden mehrere Abänderungen des neuen Abtast- Umwandlungsverfahrens beschrieben.
Als erste Abänderung können dreidimensionale graphische Zeichenelemente durch Einschließen von z-Koordinatendaten in die Eingabedaten und durch Addieren dieser Daten und Daten, wie beispielsweise der Änderungsrate des z- Koordinatenwerts in Relation zu einer Änderung bei dem y-Koordinatenwert zu den Kanten-Daten verarbeitet werden. Eine unter der Oberfläche verborgene Verarbeitung kann durchgeführt werden durch Speichern von z-Koordinatendaten in einem z-Puffer in dem Bildspeicher 13 und Vergleichen dieser Daten mit den z- Koordinaten von Pixeln, die während des Abtast-Umwandlungsverfahrens erzeugt werden.
Als zweite Abänderung kann das graphische Zeichenelement statt Intensitätspegel aufzuweisen binärwertig sein, oder es kann Farbwerte aufweisen. In dem Fall von Farbe können separate Intensitätswerte und Intensitäts-Inkrementwerte für einen Satz primärer Farben, wie beispielsweise rot, grün und blau, gespeichert werden, was ermöglicht, daß eine Farbschattierung geschaffen wird.
Als dritte Abänderung ist es möglich, anstelle eines Speicherns der maximalen y- Koordinaten (ymax) jeder Kante, die Differenz zwischen den maximalen und minimalen y-Koordinaten zu speichern und eine entsprechende Änderung im Schritt 155 in Fig. 12 durchzuführen. Diese Abänderung wäre dann geeignet, wenn die Eingabedaten, die von der Ausgabevorrichtung für ein graphisches Zeichenelement empfangen werden, aus relativen Koordinatendaten statt aus absoluten Koordinatendaten bestehen würden.
Als vierte Abänderung muß das graphische Zeichenelement nicht geradlinige Kanten aufweisen; sein Umriß kann aus Kanten bestehen, die beispielsweise durch kreisförmige Bögen oder sogenannte Bezier-Kurven definiert werden. Für solche Kanten kann der wohlbekannte "Vorwärts-Differenz-Algorithmus" angewendet werden, um die x-Koordinatenwerte im Schritt 160 in Fig. 12 zu erneuern.
Als fünfte Abänderung kann der Umriß des graphischen Zeichenelements zwei oder mehrere getrennte geschlossene Kurven umfassen. In diesem Fall werden die Scheitelpunkt-Daten durch die Scheitelpunkt-Zeiger in einer Vielzahl von zyklischen Strukturen verbunden, wobei für jede davon das Verfahren zum Erzeugen von Kanten-Datenblöcken separat durchgeführt wird. Nachdem alle Kanten- Datenblöcke erzeugt worden sind, werden als nächstes alle Start-Kantenzeiger in dem gemeinsamen Block in einer ansteigenden Reihenfolge der minimalen y- Koordinaten sortiert, und die Scheitelpunkt-Zeiger werden zur Verwendung als aktive Kantenzeiger gelöscht. Die nachfolgenden Abtast- und Umwandlungsverfahren werden auf dieselbe Weise wie für eine einzelne geschlossene Kurve ausgeführt.
Die letzten zwei Abänderungen sind in Fig. 21 veranschaulicht, die drei graphische Zeichenelemente zeigt, die jeweils durch zwei konzentrische Kreise definiert sind. Die Weise, auf die diese graphischen Zeichenelemente abgetastet und umgewandelt werden, hängt von der relativen Ausrichtung (im Uhrzeigersinn oder im Gegenuhrzeigersinn) der zwei Kreise ab, und davon, ob der "Nicht-Null- Windungs-Algorithmus" oder der "geradzahlig/ungeradzahlig-Algorithmus" verwendet wird. Wenn der "Nicht-Null-Windungs-Algorithmus" verwendet wird, wird der zentrale Bereich gefüllt, wenn beide Kreise in derselben Richtung ausgerichtet sind, und nicht gefüllt, wenn die Kreise in unterschiedlichen Richtungen ausgerichtet sind, wie es auf der linken Seite der Fig. 21 veranschaulicht ist. Wenn der "geradzahlig/ungeradzahlig-Algorithmus" verwendet wird, wird der zentrale Bereich ungeachtet der relativen Ausrichtungen nicht gefüllt.
Die Wortstruktur der Scheitelpunkt-Daten und der Kanten-Daten ist nicht auf die in den Fig. 4 und 9 gezeigten Strukturen beschränkt.

Claims

1. Abtast-Umwandlungsverfahren zum Umwandeln eines graphischen Zeichenelements, das in einem x-y-Koordinatensystem durch einen Umriß mit durch Kanten verbundenen Scheitelpunkten defininiert ist, in Pixel-Daten, die auf Abtastlinien angeordnet sind, die parallel zu der x-Achse des x-y-Koordinatensystems sind, wobei das Verfahren folgende Schritte aufweist:

(a) Erlangen (110) von Eingangsdaten für ein graphisches Zeichenelement mit einer Scheitelpunktliste, die die Koordinaten der Scheitelpunkte angibt, die den Umriß des graphischen Zeichenelements definieren, und Erzeugen (111-117) von Scheitelpunkt-Datenblöcken, die die Scheitelpunkte wenigstens durch ihre Koordinaten definieren, wobei die Scheitelpunkt- Datenblöcke durch Scheitelpunkt-Zeiger in einer Reihenfolge zyklisch verbunden werden, die der Reihenfolge der Scheitelpunkte auf dem Umriß entspricht;

(b) Konstruieren von Kanten-Datenblöcken (Fig. 7) aus den Scheitelpunkt-Datenblöcken, wobei die Kanten-Datenblöcke wenigstens die minimalen und maximalen y-Koordinatenwerte an jeweiligen Kanten, den x-Koordinatenwert des Scheitelpunkts mit der minimalen y-Koordinate an jeweiligen Kanten und den inkrementalen x-Koordinatenwert in bezug auf ein Einheitsinkrement in dem y-Koordinatenwert an jeweiligen Kanten umfassen;

(c) Gruppieren der Kanten-Datenblöcke (Fig. 7) in Kanten- Ketten, wobei jede Kette aufeinanderfolgende nach oben geneigte oder aufeinanderfolgende nach unten geneigte Kanten darstellt, wobei die Kanten-Datenblöcke an jeweiligen Kanten-Ketten durch Kanten-Kettenzeiger in ansteigender Reihenfolge ihrer minimalen y-Koordinatenwerte verbunden werden; und

(d) Abtasten des graphischen Zeichenelements (Fig. 12) auf aufeinanderfolgenden Abtastlinien, Benutzen der Kanten-Ketten zum Identifizieren von Kanten, die die Abtastlinien schneiden, Benutzen der x-Koordinatenwerte zum Erzeugen von Segmenten, die auf jeweiligen Abtastlinien in dem Inneren des graphischen Zeichenelements angeordnet sind, wobei das Innere von dem Äußeren mittels eines bekannten Mgorithmus unterschieden wird, Umwandeln der Segmente in Pixel-Daten, und Benutzen der inkrementalen x-Koordinatenwerte zum Erneuern der x-Koordinatenwerte.

2. Abtast-Umwandlungsverfahren nach Anspruch 1, wobei die Kanten- Datenblöcke weiterhin eine Information über die Kantenneigung umfassen, die anzeigt, ob jeweilige Kanten nach oben oder nach unten geneigt sind.

3. Abtast-Umwandlungsverfahren nach Anspruch 2, wobei der Schritt

(b) folgende Schritte aufweist:

(b1) Initialisieren eines Blockparameters;

(b2) Vergleichen der y-Koordinaten in dem Scheitelpunkt- Datenblock, der durch den Blockparameter angezeigt wird, und dem nächsten Scheitelpunkt-Datenblock, um die Neigung der Kante zu bestimmen, die durch die Scheitelpunkte definiert ist, die durch diese Scheitelpunkt-Datenblöcke dargestellt wird;

(b3) wenn die Kante nach unten geneigt ist, Erneuern des Blockparameters, um den nächsten Datenblock anzuzeigen und Zurückspringen zum Schritt (b2);

(b4) Speichern von Kanten-Daten für die Kante, die die Scheitelpunkte verbindet, die durch den Scheitelpunkt-Datenblock, der durch den Blockparameter angezeigt wird, und den nächsten Scheitelpunkt-Datenblock dargestellt werden, in einem Kanten- Datenblock, der durch den Blockparameter angezeigt wird;

(b5) Erneuern des Blockparameters, um den nächsten Scheitelpunkt-Datenblock anzuzeigen; und

(b6) Bestimmen, ob Kanten-Daten für alle Kanten des graphischen Zeichenelements gespeichert worden sind, und Zurückspringen zum Schritt (b4), wenn sie es nicht sind.

4. Abtast-Umwandlungsverfahren nach Anspruch 3, wobei der Schritt

(c) folgende Schritte aufweist:

(c1) Finden einer nach oben geneigten Kante, der eine nach unten geneigte Kante vorangeht;

(c2) Verbinden der Kanten-Datenblöcke dieser Kante und jeder der darauffolgenden nach oben geneigten Kanten auf einer Kanten- Kette in ansteigender Reihenfolge ihrer minimalen x- Koordinatenwerte, und Einstellen eines Start-Kantenzeigers zu dem ersten Kanten-Datenblock auf dieser Kanten-Kette in einem gemeinsamen Datenblock;

(c3) Finden der nächsten nach unten geneigten Kante, Verbinden der Kanten-Datenblöcke dieser Kante und jeder darauffolgenden nach oben geneigten Kante auf einer Kanten-Kette in ansteigender Reihenfolge ihrer minimalen y-Koordinatenwerte, und Einstellen eines Start-Kantenzeigers zu dem ersten Kanten-Datenblock auf dieser Kanten-Kette in dem gemeinsamen Datenblock;

(c4) Finden der nächsten nach oben geneigten Kante, Ent- scheiden, ob es die im Schritt (cl) gefundene Kante ist, und Zurückspringen zum Schritt (c2), wenn sie es nicht ist;

(c5) Sortieren der Start-Kantenzeiger in dem gemeinsamen Block in ansteigender Reihenfolge des minimalen y-Koordinatenwerts in dem Kanten-Datenblock, auf den dadurch gezeigt wird.

5. Abtast-Umwandlungsverfahren nach Anspruch 4, wobei die Kanten- Datenblöcke auch aktive Kantenzeiger aufweisen und die aktiven Kantenzeiger am Ende des Schritts (c5) gelöscht werden.

6. Abtast-Umwandlungsverfahren nach Anspruch 5, wobei der Schritt

(d) folgende Schritte aufweist:

(d1) Initialisieren eines Abtastlinien-y-Koordinatenwerts zu dem minimalen y-Koordinatenwert in dem ersten Kanten-Datenblock auf der ersten Kanten-Datenkette;

(d2) Finden aller Kanten-Datenblöcke, von denen der minimale y-Koordinatenwert dem Abtastlinien-y-Koordinatenwert gleicht, und Addieren dieser Kanten-Datenblöcke zu einer aktiven Kanten- Kette, auf der sie durch ihre aktiven Kanten-Zeiger verbunden sind;

(d3) Sortieren der aktiven Kanten-Kette in ansteigender Reihenfolge der x-Koordinatenwerte der Kanten-Datenblöcke darauf;

(d4) Erzeugen von Segmenten, die auf der Abtastlinie angeordnet sind, die durch den Abtastlinien-y-Koordinatenwert in dem Inneren des graphischen Zeichenelements angezeigt wird;

(d5) Umwandeln der Segmente in Pixel-Daten;

(d6) Suchen der aktiven Kanten-Kette, um alle Kanten- Datenblöcke darauf zu finden, deren maximaler y-Koordinatenwert dem Abtastlinien-y-Koordinatenwert gleicht;

(d7) wenn ein im Schritt (d6) gefundener Kanten-Datenblock nicht der letzte Kanten-Datenblock auf seiner Kanten-Kette ist, Ersetzen von ihm auf der aktiven Kanten-Kette durch den nächsten Kanten-Datenblock auf seiner Kanten-Kette;

(d8) wenn ein im Schritt (d6) gefundener Kanten-Datenblock der letzte Kanten-Datenblock auf seiner Kanten-Kette ist, Löschen desselben von der aktiven Kanten-Kette, Bestimmen, ob die aktive Kanten-Kette nun frei ist, und Beenden des Abtast- Umwandlungsverfahrens, wenn sie es ist;

(d9) Erneuern der x-Koordinatenwerte in den Kanten-Datenblöcken auf der aktiven Kanten-Kette gemäß den inkrementalen x- Koordinatenwerten in jeweiligen Kanten-Datenblöcken;

(d10) Inkrementieren des Abtastlinien-y-Koordinatenwerts und Zurückspringen zum Schritt (d2).

7. Abtast-Umwandlungsverfahren nach Anspruch 1, wobei ein "geradzahlig-ungeradzahlig-Algorithmus" zum Unterscheiden zwischen dem Inneren und dem Äußeren des graphischen Zeichenelements benutzt wird.

8. Abtast-Umwandlungsverfahren nach Anspruch 2, wobei ein "Nicht- Null-Windungs-Algorithmus" zum Unterscheiden zwischen dem Inneren und dem Äußeren des graphischen Zeichenelements benutzt wird.

9. Abtast-Umwandlungsverfahren nach Anspruch 2, wobei die Eingangsdaten für das graphische Zeichenelement, die in dem Schritt (a) erhalten werden, eine Information enthalten, die einen "geradzahlig-ungeradzahlig-Algorithmus", oder einen "Nicht-Null- Windungs-Algorithmus" bestimmt.

10. Abtast-Umwandlungsverfahren nach Anspruch 3, wobei der Scheitelpunkt-Datenblock, der durch den Blockparameter angezeigt wird, und der Kanten-Datenblock, der durch den Blockparameter angezeigt wird, derselbe Block sind.

11. Abtast-Umwandlungsverfahren nach Anspruch 1, wobei die Kanten- Datenblöcke auch einen Intensitätswert des Scheitelpunkts mit der minimalen y-Koordinate an jeweiligen Kanten und einen inkrementalen Intensitätswert in bezug auf ein Einheitsinkrement in dem y-Koordinatenwert an jeweiligen Kanten aufweisen, und wobei die Pixel-Daten Intensitätswerte aufweisen, die zwischen Endpunkten der Segmente interpoliert sind.

12. Abtast-Umwandlungsprozessor zum Umwandeln eines graphischen Zeichenelements, das in einem x-y-Koordinatensystem durch einen Umriß definiert ist, der aus durch Kanten verbundenen Scheitelpunkten besteht, in Pixel-Daten, die auf Abtastlinien angeordnet sind, die parallel zu der x-Achse des x-y-Koordinatensystems sind, wobei der Prozessor folgendes aufweist:

ein Eingangsregister (1) zum zeitweiligen Speichern von Eingangsdaten für ein graphisches Zeichenelement, die eine Scheitelpunktliste aufweisen, die die Koordinaten der Scheitelpunkte angibt, die den Umriß des graphischen Zeichenelements definieren;

ein Ausgangsregister (2) zum zeitweiligen Speichern von Information, wie beispielsweise Befehle und Anfragen;

eine Steuereinheit (3) zum Steuern des Eingangsregisters und des Ausgangsregisters, und anderer Einheiten des Abtast-Umwandlungsprozessors;

einen Abtast-Umwandlungsspeicher (4) zum Speichern von Daten eines graphischen Zeichenelements, die über das Eingangsregister erhalten werden, von Scheitelpunkt-Datenblöcken, die die Scheitelpunkte wenigstens durch ihre Koordinaten definieren, wobei die Scheitelpunkt-Datenblöcke durch Scheitelpunkt-Zeiger zyklisch verbunden sind, und von Kanten-Datenblöcken, die wenigstens jeweils einen minimalen y-Koordinatenwert, einen maximalen y-Koordinatenwert, einen x-Koordinatenwert und einen inkrementalen x-Koordinatenwert speichern, wobei die Kanten-Datenblöcke durch Kanten-Kettenzeiger auf einer Vielzahl von Kanten-Ketten in ansteigender Reihenfolge der minimalen y-Koordinatenwerte verbunden sind, wobei jede Kette aufeinanderfolgende nach oben geneigte oder aufeinanderfolgende nach unten geneigte Kanten darstellt;

einen Datenbus (5) zum Verbinden des Eingangsregisters, des Ausgangsregisters, des Abtast-Umwandlungsspeichers und anderer Einheiten des Abtast-Umwandlungsprozessors;

ein Adreßregister (6) zum Anzeigen von Stellen, an denen Daten in dem Abtast-Umwandlungsspeicher gespeichert sind;

einen Adreßbus (7) zum Übertragen von Adreßinformation von dem Adreßregister zu dem Abtast-Umwandlungsspeicher;

eine Blockadressenregister-Datei (8) zum Liefern der Adressen der Scheitelpunkte-Datenblöcke und der Kanten-Datenblöcke zu dem Abtast-Umwandlungsspeicher über den Adreßbus, und zum Speichern von Start-Kantenzeigern zu den Kanten-Ketten;

ein Rechenwerk (9) zum Empfangen einer Blockadresseninformation von der Blockadressenregister-Datei, und zum Ausführen einer Addition, einer Subtraktion und von logischen Operationen daran;

einen Multiplizierer/Dividierer (10) zum Ausführen von Multiplikations- und Divisionsoperationen zum Berechnen von Werten, wie beispielsweise Inkrementwerte;

eine Mikroprogramm-Speichereinheit (11) zum Speichern von Mikroprogrammen, die durch die Steuereinheit ausgeführt werden, die ein erstes Mikroprogramm zum Erzeugen der Scheitelpunkt- Datenblöcke aus den Eingangsdaten des graphischen Zeichenelements, ein zweites Mikroprogramm zum Konstruieren der Kanten- Datenblöcke aus den Scheitelpunkt-Datenblöcken, und ein drittes Mikroprogramm zum Abtasten des graphischen Zeichenelements auf aufeinanderfolgenden Abtastlinien aufweist, die Kanten-Ketten zum Identifizieren von Kanten benutzt, die jeweilige Abtastlinien schneiden, die x-Koordinatenwerte zum Erzeugen von Segmenten benutzt, die auf jeweiligen Abtastlinien in dem Inneren des graphischen Zeichenelements angeordnet sind, wobei das Innere von dem Äußeren mittels eines bekannten Algorithmus unterschieden wird, die Segmente in Pixel-Daten umwandelt, und die inkrementale x-Koordinatenwerte zum Erneuern der x-Koordinatenwerte benutzt; und

einen Speicher-Controller (12) zum Empfangen der Pixel-Daten und zum Schreiben derselben in eine externe Vorrichtung, wie beispielsweise einen Bildspeicher (13).

13. Abtast-Umwandlungsprozessor nach Anspruch 12, wobei die Kanten- Datenblöcke in denselben Speicherstellen wie die Scheitelpunkt- Datenblöcke gespeichert sind.

14. Abtast-Umwandlungsprozessor nach Anspruch 12, wobei das dritte Mikroprogramm einen "geradzahlig-ungeradzahlig-Algorithmus" zum Unterscheiden zwischen dem Inneren und dem Äußeren des graphischen Zeichenelements verwendet.

15. Abtast-Umwandlungsprozessor nach Anspruch 12, wobei die Kanten- Datenblöcke auch eine Information über eine Kanten-Neigung aufweisen, wobei die Information anzeigt, ob jeweilige Kanten nach oben oder nach unten geneigt sind.

16. Abtast-Umwandlungsprozessor nach Anspruch 15, wobei das dritte Mikroprogramm einen "Nicht-Null-Windungs-Algorithmus" zum Unterscheiden zwischen dem Inneren und dem Äußeren des graphischen Zeichenelements verwendet.

17. Abtast-Umwandlungsprozessor nach Anspruch 15, wobei das dritte Mikroprogramm entweder einen "geradzahlig-ungeradzahlig- Algorithmus" oder den "Nicht-Null-Windungs-Algorithmus" zum Unterscheiden zwischen dem Inneren und dem Äußeren des graphischen Zeichenelements auswählt.

18. Abtast-Umwandlungsprozessor nach Anspruch 12, wobei die Kanten- Datenblöcke auch einen Intensitätswert des Scheitelpunktes mit der minimalen y-Koordinate an jeweiligen Kanten, und einen inkrementalen Tntensitätswert in bezug auf ein Einheitsinkrement in dem y-Koordinatenwert an jeweiligen Kanten aufweisen.