DE3689331T2 - Transformationsschaltung für Rasteroperationen. - Google Patents

Description

• Bei der Video-Darstellung gibt es Techniken, die als Rasterops, was eine Abkürzung für Rasteroperationen ist, bezeichnet werden. Im allgemeinen bedeutet Rasterops, wie sie zum Beispiel von C. Braccini et al. als "Fast Geometrical Manipulations of Digital Images" in Computer Graphics and Image Processing, Band 3, Nr. 2, Juni 1980, Seiten 127-141 beschrieben worden sind, das Konzept, Informationen, die als Muster angeordnet sind, von einem Teil des Speichers in einen anderen Teil des Speichers zu bringen, wobei man das Muster oder eine Version davon bewahrt. Bekannte Schaltungsanordnungen, wie in WO 85/02035 beschrieben, expandieren oder kontrahieren ein durch Pixelbits von Informationen definiertes Muster. Allerdings wurden solche Expansionen und Kontraktionen mit ganzzahligen Vielfachen der Dimensionen und nicht mit gebrochenen Vielfachen der Dimensionen durchgeführt. Zusätzlich sind Rasterops-Schaltkreise nach dem Stand der Technik mit Einrichtungen versehen, um Bilder, wie man sie auf dem Video- Bildschirm anschauen kann, zu rotieren (um Vielfache von 90 Grad). Wenn allerdings ein Bild um einen beliebigen, von 90 Grad verschiedenen Winkel rotiert wird, erinnern die Kantenlinien eines solchen rotierten Bildes sehr oft an die Konfiguration einer Stufenfunktion und einige Pixel, die nötig sind, ein zusammenhängendes Bild zu vermitteln, fehlen. Die vorliegende Erfindung, wie sie in Anspruch 1 dargelegt ist, ist so gestaltet, daß sie diese Lücken ausfüllt. Zusätzlich erlaubt das vorliegende System viele verschiedene Transformationen zwischen dem Quell- und dem Zielbild. Zum Beispiel ermöglicht das vorliegende System dem Benutzer, eine Anzahl verschiedener Schriftart- bzw. Fontgrößen darzustellen, wenn er nur eine einzige Font-Ressource benutzt.
• In dieser Beschreibung wird die Folge von parallelen Vektoren, die bei der Durchführung einer Rasteroperation gezeichnet werden, als "gezeichnete" Vektoren bezeichnet. Die Folge der Ursprungspunkte dieser "gezeichneten" Vektoren bildet einen Vektor, der als "Ursprungs-Vektor" bezeichnet wird. Zum Beispiel zeigen in Fig. 2 die Zahlen 17 und 39 "gezeichnete" Vektoren und die Zahl 23 zeigt den Ursprungs-Vektor an, von dem ausgehend die "gezeichneten" Vektoren gezeichnet werden. Im Falle, daß das Quellbild aus einer Vielzahl von parallelen, von einem sich in Y-Richtung erstreckenden Vektor (d. h. dem Y-Vektor) ausgehenden, sich in X-Richtung erstreckenden Vektoren (d. h. den X-Vektoren) zusammengesetzt ist, sind die "gezeichneten" Vektoren die X- Vektoren des Quellbildes und die transformierten (d. h. die rotierten und/oder im Maßstab veränderten) X-Vektoren des transformierten Bildes und die "Ursprungs"-Vektoren sind der Y-Vektor des Quellbildes und der transformierte Y-Vektor des transformierten Bildes. Die vorliegende Schaltungsanordnung umfaßt Schaltkreise für die Erzeugung der Quelladressen, Schaltkreise zur Erzeugung der Zieladressen der gezeichneten Vektoren und Schaltkreise für die Erzeugung der Zieladressen der Ursprungs-Vektoren. Der Quelladressen-Schaltkreis stellt eine Folge von Pixeladressen zur Verfügung, die im Bildspeicher ein rechteckiges Gebiet definieren. Die Schaltkreise für die Zieladressen der gezeichneten Vektoren erzeugen eine Folge von Pixeladressen, die im Bildspeicher beliebigen Linien folgen. Die Schaltkreise für die Zieladressen der Ursprungs-Vektoren erzeugen eine Folge von Pixeladressen, die im Bildspeicher einer anderen Linie folgen als der Linie, der die Pixeladressen von der Schaltung für die Zieladressen der gezeichneten Vektoren folgen. Jeder Punkt entlang dem Ursprungs-Vektor dient als Ursprung für einen gezeichneten Vektor. Die Kombination der entlang dem Ursprungs-Vektor ausgehenden, gezeichneten Vektoren ergibt eine Folge von Pixeladressen, die ein beliebig orientiertes Parallelogramm im Bildspeicher definieren. Dieses Parallelogramm ist eine Transformation des Quell-Rechtecks, d. h. jeder gezeichnete Ziel-Vektor ist eine Transformation eines entsprechenden gezeichneten Quell-Vektors und der Ziel-Ursprungs-Vektor ist eine Transformation des Quell-Ursprungs-Vektors. Dementsprechend kann das Bild des Quell-Rechtecks in ein beliebiges Parallelogramm im Bildspeicher transformiert werden. Zusätzlich schließt das vorliegende System Schaltkreise ein, die Skalierungs-Faktoren verarbeiten, um zu ermöglichen, daß das Quellbild und das transformierte Bild verschiedene Größen haben.
• Jede der Zieladressen-Schaltungen schließt einen X-Adreß-Schaltkreis, einen Y- Adreß-Schaltkreis, eine Zähler-Schaltung und eine Schaltung für den Bresenham-Algorithmus ein. Das vorliegende System wird bei einer Schaltung angewendet, die einen Zeitgeber-Schaltkreis enthält, der ein 960-Nanosekunden-Zeitraster während einer horizontalen Ablenkphase erzeugt. Jeder zweite Zeitrahmen (Zeitraster) wird für das Wiederauffrischen des Bildschirms benützt. Die übrigen Zeitraster werden benützt, um im Bit-Map-Speicher Pixelinformationen von einer Quelladresse zu lesen und Pixelinformationen in eine Zieladresse zu schreiben. Die X- und Y-Adreß-Schaltkreise stellen die Adressen zur Verfügung, in die diese Pixelinformationen geschrieben werden sollen. Die Zähler-Schaltung bestimmt, wann ein Vektor, der gerade gezeichnet wird, vollständig ist. Wenn alle Pixelwerte eines gezeichneten Vektors geschrieben sind, sendet die Zähler- Schaltung eine Nachricht an das System, auf die hin die Ursprungs-Vektor-Adresse erhöht wird. Die Schaltungen für den Bresenham-Algorithmus stellen Steuersignale zur Verfügung, die das System anweisen, die Pixeladressen längs der Vektorkomponenten der Haupt- und Nebenachsen zu erhöhen oder eine Folge von Pixeladressen zu erzeugen, die einer beliebigen Linie im Bildspeicher folgen. Die Schaltungen für den Bresenham-Algorithmus werden auch benützt, um dadurch Lücken auszufüllen, daß sie das, was eine normale, zweifach erhöhende, diagonale Plazierung eines Pixelwertes sein würde, unterbrechen und statt dessen eine einfach erhöhende Adreßprozedur mit der entsprechenden Plazierung des Pixelwertes dorthin, gefolgt von einer zweiten, zur normalen, diagonalen Lage führenden Adreßerhöhung veranlassen. Die zweistufige Prozedur führt dazu, daß eine Lücke gefüllt wird. Die Zieladressen-Schaltung für die Ursprungs-Vektoren erzeugt eine Folge von Pixeladressen, die einer anderen Linie im Bildspeicher folgen. Jeder Punkt längs dem Ursprungs-Vektor wird als Ursprungs-Punkt für einen gezeichneten Vektor benützt. Das oben erklärte führt zu einer Folge von Pixeladressen, die ein beliebig orientiertes Parallelogramm im Bildspeicher definieren. So kann das rechteckige Gebiet des Quellbildes in ein beliebig konfiguriertes Parallelogramm an einem anderen Ort (Zielort) im Bildspeicher transformiert werden. Zusätzlich werden Skalierungs-Schaltkreise eingesetzt, damit Quell- und Zielbild verschiedene Größe haben können. Der Zweck und die Grundzüge der vorliegenden Erfindung werden unter Hinweis auf die Zeichnungen im Detail beschrieben, wobei:
• Fig. 1 eine Blockschaltung des gesamten Systems mit einem Bit-Map-Speichersystem ist;
• Fig. 2 ein Parallelogramm im Zielbereich des Speichers darstellt;
• Fig. 3 die Oktanten, in denen ein Vektor gezeichnet werden kann, und die mit jedem Oktanten assoziierten DX- und DY-Bedingungen zeigt;
• Fig. 4-7 Teile der Zieladressen-Schaltungen für die gezeichneten Vektoren zeigen;
• Fig. 4 ein logischer Schaltkreis ist, der den Bresenham-Algorithmus für die Erzeugung von Zieladressen gezeichneter Vektoren implementiert;
• Fig. 5. ein logischer Schaltkreis ist, der Pixeladressen, die erhöht werden, zählt, um zu bestimmen, wann ein gezeichneter Vektor vollständig ist;
• Fig. 6. ein logischer Schaltkreis ist, der Y-Adreß-Komponenten für gezeichnete Vektoren erzeugt;
• Fig. 7. ein logischer Schaltkreis ist, der X-Adreß-Komponenten für gezeichnete Vektoren erzeugt;
• Fig. 8-11 Teile der Zieladressen-Schaltungen für die Ursprungs-Vektoren zeigen;
• Fig. 8 ein logischer Schaltkreis ist, der den Bresenham-Algorithmus für die Erzeugung von Zieladressen für Ursprungs-Vektoren implementiert;
• Fig. 9 ein logischer Schaltkreis ist, der Pixeladressen, die erhöht werden, zählt, um zu bestimmen, wann das letzte Pixel des Ursprungs-Vektors erzeugt worden ist;
• Fig. 10 ein logischer Schaltkreis ist, der Y-Adreß-Komponenten für Ursprungs- Vektoren erzeugt;
• Fig. 11 ein logischer Schaltkreis ist, der X-Adreß-Komponenten für Ursprungs- Vektoren erzeugt;
• Fig. 12 ein logischer Schaltkreis ist, der ein Bestandteil des Skalierungs-Schaltkreises für gezeichnete Vektoren ist und der Steuersignale erzeugt, die benutzt werden, um ein Bild längs der Komponenten-Achse des gezeichneten Vektors zu skalieren;
• Fig. 13 ein logischer Schaltkreis ist, der ein Bestandteil des Skalierungs-Schaltkreises für Ursprungs-Vektoren ist und der Steuersignale erzeugt, die benutzt werden, um ein Bild längs der Komponenten-Achse der Ursprungs-Vektoren zu skalieren;
• Fig. 14 ein Quellbild, das rotiert worden ist, und die Wirkung des Bresenham- Algorithmus darstellt; und
• Fig. 15 ein rotiertes Bild darstellt, das Lückenfüllung benötigt;
• Fig. 1 zeigt die Zieladressen-Schaltung 13 für Ursprungs-Vektoren, die Zieladressen-Schaltung 15 für gezeichnete Vektoren und die Quell-Logik-Schaltung 55. Die Quell-Logik-Schaltung 55 produziert Pixeladressen für das Lesen von Rasterop-Daten aus dem Quellbereich des Bildspeichers, während die Zieladressen-Schaltungen 15 bzw. 13 für gezeichnete Vektoren bzw. für Ursprungs-Vektoren Pixeladressen für das Schreiben der Daten in den Zielbereich des Bildspeichers produzieren. Die Quell- und Zielpixeladressen werden zur Adreßsammel-Schaltung 57 gesandt, wo sie gepuffert, mit Refresh-Adressen kombiniert und entsprechend den Zeilen und Spalten für das Schreiben in den Bit-Map-Speicher 63 über die Adressen-Schaltung 59 gemultiplext werden. Der Einfachheit halber betrachten wir nur einen Ein-Ebenen-Speicher und Pixelwerte gleich "1" oder "0". Die Quelladressen stellen die Basis für das Lesen der Pixelwerte, so daß, wenn die Zieladressen erzeugt werden, die Pixelwerte von den "adressierten" Quellorten intern im Bit-Map-Speicher 63 an die erzeugten Zieladressen transferiert werden. Der Anwender kann die Werte, die für den Ursprungs-Vektor und die Werte, die für die gezeichneten Vektoren benützt werden, wählen. Für jeden Vektor gibt es eine X-Ausdehnung DX und eine Y-Ausdehnung DY. Die Hauptachse ist definiert als die Achse mit der größten Ausdehnung, mit anderen Worten ist X die Hauptachse, wenn DX > DY . Für diese Diskussion nehmen wir an, daß die X-Achse die Hauptachse und die Y-Achse die Nebenachse ist. Der Anwender wählt die Haupt- und die Nebenachse, indem er die Werte von SDX, SDY, FDX und FDY (in Fig. 2 gezeigt) festlegt. Der Anwender entscheidet auch, wie das Bild im Zielbereich gezeichnet wird, indem er das arithmetische Vorzeichen festlegt, das DX und DY zugeordnet wird.
• In Fig. 2 wird der zu zeichnende Vektor 17 durch zwei vektorielle Komponenten FDX und FDY definiert. Wenn die horizontale Richtung rechts von Punkt 19 und die vertikale Richtung oberhalb der Linie 21 als positiv angesehen werden, dann sind beide vektoriellen Komponenten FDX und FDY in Fig. 2 positiv. Der Anwender gibt die FDX- und FDY-Werte als positive Größen in die Schaltung 15 von Fig. 1 ein. In Fig. 2 ist der durch die vektoriellen Komponenten SDX und SDY definierte Vektor 23 als der Ursprungs-Vektor ausgewählt. Da SDX vom Punkt 19 nach links gerichtet ist, hat es einen negativen Wert, während die Komponente SDY ein positives arithmetisches Vorzeichen hat. SDX und SDY werden mit den richtigen arithmetischen Vorzeichen in die Schaltung 13 von Fig. 1 eingegeben. In die Zieladressen-Schaltungen 13 und 15 wird der absolute Wert von DX (d. h. SDX oder FDX) vom absoluten Wert von DY (d. h. SDY oder FDY) subtrahiert und das Resultat davon zusammen mit den arithmetischen Werten von DX zu DY zeigen an, in welchem Oktanten der entsprechende Vektor liegt. Die Beziehungen von DX und DY und die Vorzeichen, die sie zusammen mit ihren Ziel-Oktanten modifizieren, können in Fig. 3 gesehen werden.
• Wie aus Fig. 3 ersichtlich, ist die Position des Oktanten, in dem der Vektor liegt, bekannt, wenn drei Parameter bekannt sind. Wenn das arithmetische Vorzeichen von DX, das arithmetische Vorzeichen von DY und, ob DX oder DY größer ist, bekannt sind, dann weiß das System, in welchem Oktanten der Vektor liegt. Wie zuvor erwähnt, stellt der Anwender (das Programm) die arithmetischen Vorzeichen und die Größen von DX und DY. Die die drei Parameter repräsentierenden Signale werden über die Leitungen 25 bzw. 27 an die programmierbaren logischen Arrays (PLAs) 29 und 31 gesandt. Die PLAs 29 bzw. 31 dienen dazu, Schalt-Einrichtungen in den Zieladressen-Schaltungen 13 und 15 für Ursprungs-Vektoren und gezeichnete Vektoren zu steuern. In einer bevorzugten Ausführungsform haben die PLAs die Bauteilnummer 825100 und sind von der Signetics Corporation hergestellt.
• Aus Fig. 1 ist auch ersichtlich, daß die Leitungen 33 bzw. 35 die Zieladressen- Schaltungen 13 bzw. 17 mit der Zustands-Maschine 37 verbinden. Wenn ein Vektor gezeichnet wird, zählt die Zieladressen-Schaltung 15 jedesmal, wenn die X-Adresse erhöht wird. Wenn der X-Zähler den Wert FDX erreicht, wird ein Signal, das anzeigt, daß der Vektor 17 vollständig gezeichnet ist, über die Leitung 35 an die Zustands-Maschine 37 gesandt. Die Zustands-Maschine 37 sendet ihrerseits ein Signal an beide PLAs 29 und 31. Als Reaktion auf dieses Signal der Zustands-Maschine 37 schaltet PLA 29 die Schalter in der Zieladressen-Schaltung 13, um die Adreßwerte längs der vektoriellen Komponenten -DX und +DY des Vektors 23 zu erhöhen. Zusätzlich initialisiert PLA 31 die Zieladressen-Schaltung 15, um eine Startadresse auf dem Ursprungs-Vektor 23 zur Verfügung zu stellen. Durch das Erhöhen der Komponentenadressen des Ursprungs- Vektors 23 und die Initialisierung der X- und Y-Adressen, um an den erhöhten Adressen des Ursprungs-Vektors 23 zu starten, wird ein zweiter Vektor 39 gestartet und schließlich gezeichnet. Die Zustands-Maschine 37 hat in einer bevorzugten Ausführungsform die Bauteilnummer 825100, hergestellt von Signetics Corporation.
• Wie weiterhin aus Fig. 1 ersichtlich, gibt es eine Skalierungs-Schaltung 41 für gezeichnete Vektoren und eine Skalierungs-Schaltung 43 für Ursprungs-Vektoren. Der Input für die Skalierungs-Schaltung 41 ist ein Skalierungs-Faktor ES für gezeichnete Vektoren auf Leitung 45 und der Input für die Skalierungs-Schaltung 43 ist ein Skalierungs-Faktor 55 für Ursprungs-Vektoren auf Leitung 47. Die Skalierungs-Faktoren und die Skalierungs-Schaltungen ermöglichen dem vorliegenden System, die Größe eines Bildes um gebrochene oder ganzzahlige Vielfache zu expandieren oder zu reduzieren. Die Expansion des Quellbildes (d. h. die Vergrößerung) wird erreicht, indem ein Pixelwert von der Quelle an mehrere Pixelorte des Zielbereichs kopiert wird. Verkleinerung wird erreicht, indem mehrere Pixelwerte von der Quelle in einen Pixelwert im Zielbereich transformiert werden.
• Zum Beispiel wird für das Vergrößern in der Skalierungs-Schaltung 41 für gezeichnete Vektoren der Skalierungs-Faktor FS (der immer kleiner als 1 ist) jedesmal akkumuliert, wenn eine Pixeladresse eines gezeichneten Vektors erzeugt wird. Die Skalierungs-Schaltung 41 ist so entworfen, daß sie ein Signal auf der Leitung 49 sendet, das der Zustands-Maschine 37 anzeigt, daß die Adresse des Vektors, der gerade gezeichnet wird, erhöht werden soll. Die Zustands-Maschine 37 sendet ein Steuersignal an das PLA 31, das seinerseits die Zieladressen-Schaltung 15 veranlaßt, die Adresse des Vektors, der gerade gezeichnet wird, zu erhöhen. Wenn die Summe der Skalierungs- Faktoren 1 überschreitet, dann sendet die Skalierungs-Schaltung 41 ein Signal auf Leitung 51, das die Zustands-Maschine 37 veranlaßt, ein Signal an PLA 53 zu senden. Daraufhin sendet PLA 53 ein Signal an die Quell-Logik-Schaltung 55. Die Quell-Logik- Schaltung 55 veranlaßt, daß die Quelladresse erhöht wird. Wie oben erwähnt, muß das System, um ein Bild zu vergrößern, die Pixelwerte von einer Quelladresse in mehrere Zieladressen kopieren. Beim Verkleinern eines Bildes muß das System eine Anzahl Pixelwerte vom Quellbild lesen, bevor es einen Pixelwert an einer einzigen Zieladresse hervorbringt. Um ein Beispiel zu geben, wenn ein Bild im Quellbereich einen vier Einheiten langen Vektor hätte und das Programm eine Vergrößerung um den Faktor 2,5 verlangte, dann wäre der resultierende Vektor zehn Einheiten lang. Das System behandelt diese Zuordnung, indem es drei Pixelwerte im vergrößerten Bild aus dem ersten Pixelwert im Quellbereich, zwei weitere Pixelwerte im vergrößerten Bild aus dem zweiten Pixelwert im Quellbereich, drei weitere Pixelwerte im vergrößerten Bild aus dem dritten Pixelwert im Quellbereich und zwei weitere Pixelwerte im vergrößerten Bild aus dem letzten Pixelwert im Quellbereich produziert. Also würde es zehn Pixelwerte im vergrößerten Bild für die vier Pixelwerte im Quellbereich geben. Die Skalierungs-Schaltungen 41 und 43 sind so entworfen, daß sie die geschilderte Durchschnittsbildung bei der Erzeugung von Pixelwerten im vergrößerten Bild bewerkstelligen.
• Die Adreßsammel-Logik 57 und der Bit-Map-Speicher 63 repräsentieren nicht Schaltungen, die Bestandteil dieser Erfindung sind, sondern sie werden gezeigt als Beispiel von Einrichtungen für die Verwendung der von der vorliegenden Erfindung erzeugten Signale.
• Fig. 1 zeigt zwei mit der Zieladressen-Schaltung 13 verbundene Eingangsleitungen 65 und 67. Die Werte X&sub1; und Y&sub1; auf den Leitungen 67 und 65 sind jeweils die X- und Y-Adressen für den Startpunkt des transformierten Bildes im Zielbereich des Speichers. Die SX- und die SY-Werte werden während einer Initialisierungs-Prozedur von Schaltung 13 zu Schaltung 15 transferiert. Dementsprechend ist nach einer Initialisierung und nachdem das System begonnen hat, ein Bild zu transformieren, der Startpunkt für jeden gezeichneten Vektor die Adresse des zuletzt generierten Pixelwertes des Ursprungs- Vektors. Man beachte, daß die zum Bit-Map-Speicher gesandten Adressen FX und FY nur von der Zieladressen-Schaltung 15 für gezeichnete Vektoren kommen. Daraus folgt, daß das transformierte Bild durch das Ändern der FX- und FY-Werte expandiert wird. Der Ursprungs-Vektor wird weiter gezogen und deshalb durch das Ändern der Initialisierungs-Adresse als Reaktion auf ein Steuersignal von der Zustands-Maschine 37 gezeichnet. Die Skalierungs-Schaltungen 41 und 43 empfangen Steuersignale (auf den Leitungen 69 und 71) von der Zustands-Maschine 37, um diese Schaltungen zu initialisieren. Die Zustands-Maschine 37 und die PLAs 29 und 31 sind programmierbare Bausteine und werden so programmiert, daß sie die in dieser Beschreibung dargelegten Schritte durchführen.
• Fig. 4-7 geben einen Satz von Schaltungen wieder, die in der Zieladressen- Schaltung 15 für gezeichnete Vektoren vorkommen. Fig. 8-11 geben einen Satz von Schaltungen wieder, die in der Zieladressen-Schaltung 13 für Ursprungs-Vektoren vorkommen. Fig. 11 zeigt die Schaltung, die die SX-Adresse produziert, die zum Input der Leitung 7-3 in Fig. 7 wird. Die in den Fig. 4-11 gezeigten Schaltungen sind in logischer Form dargestellt, d. h. als Schalter, Addier-Subtrahier-Einrichtungen, Akkumulatoren, Register und ähnliches. Tatsächlich werden diese Schaltungen aufgebaut aus einer Vielzahl von integrierten Schaltkreis-Chips, in denen das Schalten elektronisch ausgeführt wird. In einer bevorzugten Ausführungsform sind sowohl die Schalter für alle Schaltungen von Fig. 4-13, als auch die Schalter der Schaltung 55 von Fig. 1 Multiplexer und haben die Bauteilnummer 74153, hergestellt von Texas Instruments Corporation. Andere Schalteinrichtungen und andere Formen von Multiplexern könnten eingesetzt werden. In einer bevorzugten Ausführungsform haben sowohl die Addier-Subtrahier-Einrichtungen für alle Schaltungen der Fig. 4-13 als auch die Addier-Subtrahier-Einrichtung in Schaltung 55 in Fig. 1 die Bauteilnummer 74181, hergestellt von Texas Instruments Corporation. In einer bevorzugten Ausführungsform haben sowohl die Akkumulatoren für alle Schaltungen von Fig. 4-13 als auch der Akkumulator in Schaltung 55 in Fig. 1 die Bauteilnummer 7491, hergestellt von Texas Instruments Corporation. Andere Typen von Addier-Subtrahier-Einrichtungen sowie andere Akkumulator-Typen könnten verwendet werden. Die Register, wie die Register 8-13, haben die Bauteilnummer 7474, hergestellt von Texas Instruments Corporation.
• Während der Initialisierungs-Phase schaltet PLA 29 (als Reaktion auf Signale von der Zustands-Maschine 37) den Schalter 11-1 auf die "0"-Position 11-2. Zusätzlich wird der Schalter 11-3 auf die "0"-Position 11-4 geschaltet. Dementsprechend wird in der Addier-Subtrahier-Einrichtung (A-S) 11-5 Null zu Null addiert und die Summe Null wird in den Akkumulator 11-6 geladen. Es folgt, daß die SX-Adressen-Schaltung von Fig. 11 anfänglich auf Null rückgesetzt wird. Die Schaltungen der Fig. 4-10 werden in ähnlicher Weise für das Rücksetzen betrieben und so werden alle diese Schaltungen auf Null zurückgesetzt. Im nächsten Schritt während der Initialisierung stellt PLA 29 den Schalter 11-3 auf die X&sub1;-Eingangs-Leitung 11-7. Der Schalter 11-1 bleibt in der "0"-Position, d. h. verbunden mit Leitung 11-2. Während der passenden Taktzeit wird die X&sub1;-Adresse zu Null in der Addier-Subtrahier-Einrichtung 11-5 addiert und die Summe (d. h. X&sub1;) wird in den Akkumulator 11-6 transferiert. Der Wert im Akkumulator 11-6 liegt am Ausgang 11-8 als die SX-Adresse an, die an die Zieladressen-Schaltung 15 für gezeichnete Vektoren ausgegeben wird.
• Der Betrieb der Schaltungen von Fig. 10 ist identisch zu dem von Fig. 11, abgesehen davon, daß der Input die Y&sub1;-Adresse des Startpunktes des zu transferierenden Bildes ist, wie er auf Leitung 10-7 auftritt.
• Die Schaltungen von Fig. 6 und 7 empfangen die entsprechenden Eingangs-Signale SY und SX, die die Startadresse für den entsprechenden, zu zeichnenden Vektor von den Schaltungen von Fig. 10 und 11 repräsentieren. Die Adreßwerte SY und SX werden jeweils zu Null in den A-S-Einrichtungen 6-5 und 7-5 addiert, indem der Schalter 6-1 auf die "0"-Leitung 6-2 und der Schalter 6-3 auf die SY-Leitung 6-7 geschaltet werden und indem der Schalter 7-1 auf die "0"-Leitung 7-2 und der Schalter 7-3 auf die SX- Leitung 7-7 geschaltet werden. Die SY- und SX-Werte werden jeweils in den Akkumulatoren 6-6 und 7-6 gespeichert. Somit werden die anfänglichen Adreßwerte von FY und FX jeweils SY und SX gleichgesetzt, die ihrerseits jeweils gleich Y&sub1; und X&sub1; sind. Da sowohl der erste gezeichnete Vektor als auch der Ursprungs-Vektor an derselben X-Y-Adresse starten, wenn sie in den Bit-Map-Speicher transferiert werden (d. h. an den vom Anwender gewählten Startpunkt), folgt, daß anfänglich X&sub1; = SX = FX und Y&sub1; = SY = FY.
• Wenn wir zum Beispiel annehmen, daß das zu überführende Bild rechtwinklig begrenzt ist (entlang der X- und Y-Richtungen definiert), daß keine Rotation vorkommt und daß die gezeichneten Vektoren sich in X-Richtung erstrecken, dann brauchen nur die Fig. 7 und 10 diskutiert zu werden, da die gezeichneten Vektoren keine Y-Komponenten haben. Unter solchen Umständen schaltet PLA 31 den Schalter 7-3 (Fig. 7) auf die "1"-Eingangs-Leitung 7-12 und schaltet den Schalter 7-1 auf die Akkumulator-Eingangs-Leitung 7-13. Jedesmal, wenn ein Ausgangs-Signal auf Leitung 49 erscheint, taktet PLA 31 die A-S-Einrichtung 7-5. Mit den in der zuvor erwähnten Weise eingestellten Schaltern 7- 3 und 7-1 wird die Summe im Akkumulator 7-6 (d. h. FX, was anfänglich die letzte SX-Adresse ist) auf die Einheit addiert und so muß eine neue Adresse für einen neuen Pixelwert für den Vektor, der gerade gezeichnet wird, berechnet werden. Während jedem Lese- und Schreib-Zeitrahmen bleibt der FY-Wert konstant. Das Vorstehende ist richtig, weil PLA 31 den Schalter 6-1 auf die Akkumulator-Eingangs-Leitung 6-13 geschaltet und den Schalter 6-3 auf die "0"-Eingangs-Leitung 6-4 geschaltet hat. Mit diesen Schalterstellungen wird Null zum ursprünglichen Y-Wert aus dem Akkumulator addiert und FY bleibt konstant. Während dem Zeichnen des ersten Vektors auf dem Bildschirm werden beide Schalter 10-3 und 11-3 auf die Null-Position geschaltet (als Reaktion auf Signale von PLA 19), d. h. jeweils auf die Leitungen 10-4 und 11-4, und die Schalter 10-1 und 11-1 werden jeweils auf ihre Akkumulator-Eingangs-Leitungen 10-13 und 11-13 geschaltet. Daher sind die SY- und die SX-Adressen die Y&sub1;- und X&sub1;-Startadressen.
• Während Pixeladressen für den Vektor, der gerade gezeichnet wird, errechnet werden, werden die Adressen in der Zählerschaltung von Fig. 5, die anfänglich auf Null rückgesetzt ist, gezählt. Danach, während der weiteren Initialisierung, wird der Schalter 5-4 auf die Leitung 5-3 geschaltet, um den FDX-Wert zu empfangen, während der Schalter 5-1 auf Leitung 5-2 geschaltet wird, um den Rücksetz-Wert Null zu empfangen. FDX wird vom Anwender gestellt. Wenn allerdings FDX der A-S-Einrichtung 5-6 übergeben wird, wird es von Null abgezogen und daraufhin wird die Summe -FDX im Akkumulator 5-7 gespeichert. Das arithmetische Vorzeichen der Summe wird dem Register 5-8 zugeleitet. Wenn Pixeladressen für den Vektor, der gerade gezeichnet wird, berechnet werden, wird der Schalter 5-4 (durch PLA 31) auf den "1 "-Anschluß 5-5 gestellt. Zur selben Zeit wird der Schalter 5-1 auf die Akkumulator-Eingangs-Leitung 5-10 geschaltet. Gleichzeitig mit dem Berechnen der ersten Pixeladresse wird -FDX aus dem Akkumulator (in der Addier-Subtrahier-Einrichtung 5-6) auf +1 addiert. Solange das arithmetische Vorzeichen des Akkumulator-Inhalts negativ bleibt, stellt es einen negativen arithmetischen Vorzeichenwert im Register 5-8 zur Verfügung. Sowie "1"-en zu FDX addiert werden, werden die Akkumulator-Inhalte weniger negativ und erreichen schließlich Null. Der Wert Null wird als ein Vorzeichenwechsel im Register 5-8 erkannt. Ein arithmetischer Vorzeichenwechsel im Register 5-8 erzeugt ein Signal am Anschluß 5-9, und dieses Signal liegt auf Leitung 35 in Fig. 1 an.
• Das Zählsignal auf Leitung 35 in Fig. 1 wird an die Zustands-Maschine 37 übertragen, die darauf mit dem Senden von Signalen an die beiden PLAs 29 und 31 wie zuvor beschrieben reagiert. Aufgrund des Signals von PLA 29 und unter der Annahme, daß die Grundregeln von Fig. 3 angewandt werden (d. h. die positive Y-Richtung ist aufwärts), wird eine "1" zur Y&sub1;-Adresse in Fig. 10 addiert und der zweite zu zeichnende Vektor wird an einer Position oberhalb des ersten gezeichneten Vektors in der X-Y-Ebene begonnen, d. h. (X&sub1;, Y&sub1; + 1).
• Unter diesen Umständen schaltet PLA 29 den Schalter 10-1 auf die Akkumulator-Eingangs-Leitung 10-13 und schaltet den Schalter 10-3 auf die "1"-Eingangs-Leitung 10-12. Das PLA-Signal taktet die "1", die zur anfänglichen SY-Adresse (d. h. Y&sub1;) addiert werden soll, so daß der zweite gezeichnete Vektor an der neuen Adresse Y&sub1; + 1 gestartet wird. SX bleibt gleich X&sub1;, weil wir in unserem Beispiel ein rechteckiges Bild ohne Rotation übertragen. Zur selben Zeit zählt die Schaltung von Fig. 9 die Y-Adreß-Erhöhungen. Jedesmal, wenn eine Pixeladresse berechnet wird, um den Ursprungs-Vektor weiter zu definieren, erhöht die Zähler-Schaltung von Fig. 9 ihren Akkumulatorwert um +1. Der Akkumulator 9-7 wird anfänglich mit einem -SDY-Wert in der gleichen Weise geladen wie der Akkumulator 5-7 von Fig. 5 mit einem -FDX-Wert geladen wurde. Wenn der Wert im Akkumulator 9-7 bis auf Null erhöht wird, wird ein arithmetischer Vorzeichenwechsel erkannt und ein vorher festgelegtes Signal, das auf Leitung 33 in Fig. 1 übertragen wird, wird am Anschluß 9-9 erzeugt. Wenn das Ende des Ursprungs-Vektors erreicht ist, dann ist nur noch ein weiterer gezeichneter Vektor nötig, um die Transformation des Quellbildes zu vervollständigen und diese Meldung wird durch das Senden des Signals auf Leitung 33 mitgeteilt.
• Man beachte in Fig. 1, daß, wenn die SDX- und SDY-Adressen aus der Quell- Logik-Schaltung 55 erzeugt werden, sie, wie früher erwähnt, zur Adreßsammel-Schaltung 57 übertragen werden. Die SDX- und SDY-Adressen werden nicht erhöht, bis die Skalierungs-Schaltungen Signale auf den Leitungen 51 und 53 erzeugen. Die Erzeugung dieser Signale kann besser verstanden werden, wenn man die Funktionen der Schaltungen der Fig. 12 und 13 studiert. Wenn ein Bild gerade von einem Quellbereich des Speichers an einen neuen Ort gebracht und expandiert werden soll, wird das Bild um einen gewissen Faktor expandiert. Die Schaltungen von Fig. 12 und 13 befähigen das vorliegende System, Expansionen und Kontraktionen eines gebrochenen Vielfachen der Bildgröße zu handhaben. Man betrachte beispielsweise die Expansion eines rechteckigen Quell-Bildes, das 10 Pixel in der X-Richtung und 4 Pixel in der Y-Richtung hat. (Natürlich würde ein tatsächliches Bild vielfach größer als die oben angegebenen Dimensionen sein, weil ungefähr 10 Pixelzeilen pro Zeile sichtbaren Textes existieren.) Angenommen, es soll das Bild von 4 Pixel mal 10 Pixel um den Faktor 2,4 in der X-Richtung und um den Faktor 3,2 in der Y-Richtung expandiert werden. In diesem Fall verwendet die Skalierungs-Schaltung von Fig. 12 einen Skalierungs-Faktor FS von 1/2,4 oder 0,417, während die Skalierungs- Schaltung von Fig. 13 einen Skalierungs-Faktor SS von 1/3,2 oder 0,312 verwendet.
• Bezugnehmend auf Fig. 12 überträgt die Zustands-Maschine 37 während der Initialisierung auf Leitung 69 Signale, um den Schalter 12-1 auf die "0"-Eingangs-Leitung 12-2 zu schalten. Zusätzlich wird der Schalter 12-3 auf die "0"-Eingangs-Leitung 12-4 geschaltet. Deshalb wird ein Nullwert zu einem Nullwert addiert, um die Summe Null im Akkumulator zur Verfügung zu stellen, wobei die Skalierungs-Schaltung 41 auf Null zurückgesetzt wird. Die Skalierungs-Schaltung 43 in Fig. 13 wird genauso auf Null zurückgesetzt. Nach der Initialisierung wird der Schalter 12-3 auf die Skalierungs-Faktor-FS- Leitung 12-9 geschaltet. Ein Signalwert 0,417 wird von der Leitung 12-9 zur A-S-Einrichtung 12-5 übertragen. Zur gleichen Zeit wird der Schalter 12- 1 auf die Akkumulator- Eingangs-Leitung 12-8 geschaltet. Auf ein Taktsignal an der A-S-Einrichtung 12-5 wird der Wert 0,417 zu 0 addiert und im Akkumulator 12-6 gespeichert. Gleichzeitig mit der Addition des Faktors 0,417 wird eine Pixeladresse für den gezeichneten Vektor berechnet, und zwar als Reaktion auf ein Signal auf Leitung 49 und ein Taktsignal in der Zustands-Maschine 37. Das Signal auf Leitung 49 wird während der ganzen Zeit erzeugt, in der das System vergrößert. Flip-Flop 50 wird gesetzt, d. h. auf seine Q-Seite geschaltet, wenn das System im Vergrößerungs-Modus arbeitet. Das Überlaufsignal läuft durch das ODER-Gatter 65, um ein Steuersignal für das Erhöhen auf Leitung 51 bereitzustellen. Das Überlaufsignal wird als Reaktion darauf ausgegeben, daß der Inhalt des Akkumulators 12-6 eine ganze Zahl (d. h. einen ganzzahligen Wert) überschreitet. Wenn das System verkleinert, dann wird das Flip-Flop 50 auf seine -Seite geschaltet und auf Leitung 51 ist dann ein konstantes Erhöhungs-Steuersignal. Man erinnere sich, daß der gezeichnete Vektor vervollständigt ist, bevor das System die Adresse des Ursprungs-Vektors erhöht.
• Während der nächsten Taktzeit wird der Wert 0,417 aus dem Akkumulator 12-6 zu 0,417 von der Skalierungs-Faktor-FS-Leitung 12-9 addiert und der Wert 0,834 wird im Akkumulator gespeichert. In der Zwischenzeit ist eine zweite Pixeladresse für den expandierten Vektor berechnet worden, der gerade gezeichnet wird. Während der nächsten Taktzeit wird der Wert 0,834 aus dem Akkumulator 12-6 zu 0,417 von der Skalierungs- Faktor-FS-Leitung 12-9 addiert und demzufolge sollte der Akkumulator die Summe 1,251 gespeichert haben. Allerdings ist der Akkumulator 12-6 so entworfen, daß er den Wert "1" als Übertrag behandelt und damit ein Signal auf Leitung 12-11 bereitstellt. Das Übertrags-Signal auf Leitung 12-11 veranlaßt die Überlaufschaltung 12-7, über das ODER-Gatter 65 ein Signal auf Leitung 51 bereitzustellen. Daraus folgt, daß die Quelladresse SOX um "1" erhöht wird und daß ein Wert von 0,251 im Akkumulator verbleibt. Somit sind für die erste Pixeladresse im Quellbereich des Speichers drei Pixeladressen berechnet worden für den Vektor, der gerade gezeichnet wird. Tabelle 1 zeigt die Beziehung zwischen den Pixelwerten im Quell-Vektor und den Pixelwerten im gezeichneten Vektor. Es sollte beachtet werden, daß FDX des Zielbildes 24 Pixel sein werden, weil die 10 Pixel in der X-Richtung des Quellbildes um den Faktor 2,4 expandiert werden. Tabelle I Zeitrahmen Addierter Skalierungs-Faktor Aufgelaufener Wert im Akkumulator Übertrag Position des Quell-Pixels Gesamtzahl der addierten Pixel nein erste ja zweite dritte vierte fünfte sechste siebente achte neunte zehnte
• Tabelle I zeigt, daß für die erste, dritte, sechste und achte Quell-Pixeladresse jeweils drei Pixeladressen für den gezeichneten Vektor berechnet und für jede andere Quell-Pixeladresse jeweils nur zwei Pixeladressen für den gezeichneten Vektor berechnet worden sind. Jeder der 13 gezeichneten Vektoren folgte demselben Muster in der X-Richtung. Allerdings unterschiede sich das Muster in der Y-Richtung wegen dem unterschiedlichen Skalierungs-Faktor. Die Schaltung in Fig. 13 arbeitet in der gleichen Weise wie die Schaltung in Fig. 12, nur daß der Schalter 13-3 nur in Reaktion auf ein Zählsignal auf Leitung 35 in Fig. 1 auf die Skalierungs-Faktor-SS-Leitung 13-9 geschaltet wird.
• Die Bresenham-Algorithmus-Schaltung der Zieladressen-Schaltung für gezeichnete Vektoren wird in Fig. 4 gezeigt. Diese Schaltung ermöglicht, daß das Bild rotiert werden kann. Der Bresenham-Algorithmus stellt eine Technik oder eine Routine zur Verfügung, mit der ein beliebiger Vektor auf einem rechtwinkligen Pixelgitter angenähert werden kann. (Der Bresenham-Algorithmus wird von der Transformations-Schaltungsanordnung der Erfindung benützt, wurde aber nicht von der Anmelderin erfunden.) Um die dem rotierten Vektor entsprechenden Pixel auszuwählen, werden einige Pixel diagonal zu den vorher erzeugten Pixeln plaziert. Wenn die Adresse eines Pixelwertes diesen Pixelwert auf eine diagonal zur Position des letzten Pixelwertes liegende Position plaziert, dann wird sowohl die Adressen der Haupt- als auch der Nebenachse erhöht. Wenn die Adresse eines Pixelwertes den Pixelwert auf eine Pixel-Position längs der Hauptachse versetzt zum letzten Pixelwert plaziert, dann wird nur die Adresse der Hauptachse erhöht. Der Bresenham-Algorithmus stellt eine Basis für die Entscheidung zur Verfügung, ob sowohl die Adressen der Haupt- als auch der Nebenachse oder nur die Adresse der Hauptachse erhöht werden soll.
• Fig. 14 zeigt ein im Quellbereich des Speichers liegendes Bild S (für Source = Quelle) und ein im Zielbereich liegendes Bild D (für Destination = Ziel). Das Bild D wurde rotiert. Der Anwender entscheidet, um welchen Winkel das Zielbild rotiert werden soll und wählt FDY und SDX, um die passende Rotation zu bewirken. Für das in unserem vorigen Beispiel diskutierte Rechteck (10 Pixel mal 4 Pixel) wählen wir einen Rotationswinkel von 30º. Demzufolge hat FDY einen Wert von 5 Pixeln und SDX hat einen Wert von 2 Pixeln. Wenn der Bresenham-Algorithmus geringfügig abgewandelt wird, so daß die Endstriche längs der Hauptachse geteilt werden, erhält man einen besseren Durchschnitt der Pixelwerte längs der beabsichtigten, diagonalen Linie, wie sie dem Betrachter erscheint. Entsprechend dem Bresenham-Algorithmus wird, um die Adressen eines Vektors zu erzeugen, der absolute Wert der vektoriellen Komponente längs der Hauptachse vom absoluten Wert der vektoriellen Komponente längs der Nebenachse subtrahiert. Wenn die Differenz negativ ist, wird nur die Adresse der Hauptachse erhöht, wohingegen, wenn die Differenz positiv ist, sowohl die Adresse der Haupt- als auch die der Nebenachse erhöht wird. Weiterhin wird, falls die Differenz negativ ist, im folgenden Schritt der Differenzwert zum absoluten Wert der Komponente längs der Nebenachse addiert. Tabelle II legt den Bresenham-Algorithmus und die Art und Weise dar, in der er durch die Zieladressen-Schaltungen 13 und 15 angewandt wird. Tabelle II Schritt Bresenham-Algorithmus Numerische Rechnung Akku-Inhalt Interpret. des Vorzeichens FX-Adreß-Erhöhung FY-Adreß-Erhöhung JA NEIN
• In Tabelle II sind jedesmal, wenn der Akkumulator eine Differenz Null hatte (oder wenn ein positives Resultat da war), sowohl die X- als auch die Y-Adresse des Vektors, der gerade gezeichnet wurde, erhöht worden und jedesmal, wenn der Akkumulator einen negativen Wert hatte, ist nur die X-Adresse erhöht worden. In Fig. 14 sind die Pixel an den durch Tabelle II angegebenen Stellen gezeigt. Die Pixel in Fig. 14 sind in Bezug auf die Zeichnung kleiner gezeichnet als sie in Wirklichkeit sind (da wir angenommen haben, daß die Bildgröße 10 Pixel mal 4 Pixel war), um die Zeichnung aussagekräftiger zu machen. Der Startpunkt von Vektor 73 ist der Punkt 75. Man beachte, daß Schritt 1 in Tabelle II aussagt, daß sowohl die X- als auch die Y-Adresse erhöht werden soll und demzufolge liegt Pixel 77 eine Pixelposition nach rechts und eine Pixelposition darüber. Man beachte, daß Schritt 2 der Tabelle II aussagt, daß nur die X-Adresse erhöht werden sollte. Dementsprechend wird Pixel 79 eine Pixelposition nach rechts plaziert. Wenn man der Interpretation des arithmetischen Vorzeichens in Tabelle II folgt, kann man sehen, daß die Pixel in Fig. 14 entlang der gewünschten Position des zu zeichnenden Vektors 73 gruppiert sind und der Betrachter sieht diese Pixel als eine sich an den Vektor 73 approximierende Linie.
• Man betrachte nun den Betrieb der in Fig. 4 und 8 gezeigten Bresenham-Algorithmus-Schaltung. Zuerst muß das System entscheiden, was die Haupt- und die Nebenachsen für die gezeichneten Vektoren und die Ursprungs-Vektoren sind und in welchem Oktanten die Vektoren zu liegen kommen. Der Anwender weiß, wo das transformierte Bild gezeichnet werden soll und in Übereinstimmung mit den in Fig. 3 gezeigten Oktanten-Beziehungen stellt er die Vorzeichen für die Komponenten-Achsen zur Verfügung. Der Anwender weiß auch, wie weit das Bild rotiert werden soll und deshalb bestimmt der Anwender die Werte von FDX, FDY, SDX und SDY. Obwohl es für den Anwender eine einfache Angelegenheit wäre, die Information zur Verfügung zu stellen, welche Achse die Hauptachse ist, benützt das System die Schaltung für den Bresenham-Algorithmus, um diese Entscheidung zu treffen.
• Man betrachte Fig. 8, die die Schaltung für den Bresenham-Algorithmus ist, wie sie in der Zieladressen-Schaltung 13 für Ursprungs-Vektoren vorliegt. Während der Initialisierung sind die Schalter 8-1, 8-3 und 8-5 jeweils auf die "0"-Eingangs-Leitungen 8- 2, 8-4 und 8-6 geschaltet. Folglich werden alle Nullen zusammen addiert und die Bresenham-Schaltung von Fig. 8 wird auf Null zurückgesetzt. Danach wird während der Initialisierung der Schalter 8-3 auf auf die Leitung 8-7 geschaltet, während der Schalter 8-1 auf der "0"-Eingangs-Leitung 8-2 stehen bleibt. Folglich wird der SDX-Wert in der Addier- Subtrahier-Einrichtung 8-8 auf Null addiert. Gleichzeitig wird der Schalter 8-5 auf die SDY-Leitung 8-9 geschaltet und SDX wird von der A-S-Einrichtung 8-8 transferiert, um von SDY in der A-S-Einrichtung 8-10 subtrahiert zu werden. Die in der A-S-Einrichtung 8-10 berechnete Differenz wird im Akkumulator 8-11 gespeichert. Wenn die Differenz im Akkumulator 8-11 negativ ist, dann ist SDX die Komponente längs der Hauptachse; wenn die Differenz im Akkumulator 8-11 positiv ist, dann ist SDY die Komponente längs der Hauptachse. Das arithmetische Vorzeichen-Bit der Differenz wird im Flip-Flop 8-12 gespeichert und dieses Signal ist eines der drei Signale, die auf Leitung 25 ans PLA 29 gesandt werden. Die zwei anderen Signale auf Leitung 25, die die Vorzeichen-Werte von SDX und SDY anzeigen, werden in zwei (nicht gezeigten) Flip-Flops gespeichert, die ihre arithmetischen Vorzeichen-Eingänge direkt von den Eingangs-Signalen auf den Leitungen 26 in Fig. 1 empfangen. Die Schaltungen in Fig. 4 werden in der gleichen Weise wie die Schaltungen in Fig. 8 initialisiert.
• Während der Initialisierung hat (wie eben beschrieben) das System bestimmt, daß bezugnehmend auf den gezeichneten Vektor 73 (Fig. 14) X die Hauptachse und Y die Nebenachse ist. Vor dem ersten Zeitrahmen für das Lesen aus dem Quell- und dem Schreiben in den Zielbereich des Speichers, werden die Startadressen für FX und FY erzeugt, wie zuvor unter Bezugnahme auf die Schaltungen in Fig. 6 und 7 beschrieben. Bezugnehmend auf Fig. 4 wird während dem ersten Zeitrahmen für das Lesen aus dem Quell- und das Schreiben in den Ziel-Bereich der Schalter 4-1 auf die Akkumulator-Eingangs-Leitung 4-14 geschaltet; der Schalter 4-3 wird auf die FDX/2-Eingangs-Leitung 4-15 geschaltet; und der Schalter 4-5 wird auf die FDX-Eingangs-Leitung 4-9 geschaltet. Nachdem im Akkumulator von der Rücksetz-Prozedur (oben beschrieben) her Null steht, wird FDX/2 in der A-S-Einrichtung 4-8 von Null subtrahiert, und daraus resultiert das Differenz-Signal -FDX/2. Das Signal von PLA 31 veranlaßt die A-S-Einrichtung 4-8 zu subtrahieren. Der Wert -FDX/2 wird dann der A-S-Einrichtung 4-10 zugeleitet, wo der absolute Wert von FDX/2 vom absoluten Wert von FDY subtrahiert wird (also FDY - FDX/2 ). Aus den numerischen Werten der Tabelle II kann man sehen, daß die Berechnungen in den zwei A-S-Einrichtungen 4-8 und 4-10 zu 0 - 5 + 5 = 0 führen. Folglich steht Null im Akkumulator 4-11. Eine Null wird als ein arithmetisches Pluszeichen interpretiert und dieses Vorzeichen wird im Register 4-13 gespeichert. Register 4-13 ist in einer bevorzugten Ausführungsform ein 74S74, hergestellt von Texas Instruments Corporation. Das arithmetische Vorzeichen-Signal aus Register 4-13 wird auf Leitung 28 zum PLA 31 übertragen. PLA 31 reagiert auf das Pluszeichen-Signal mit dem Schalten der Schalter 7-3 und 6-3 auf ihre jeweiligen "1"-Eingangs-Leitungen und folglich werden sowohl die FX- als auch die FY-Adressen, wie in den letzten zwei Spalten in Tabelle II angezeigt, erhöht. Dementsprechend wird Pixel 77 in Fig. 14 plaziert wie gezeigt. Während dem nächsten Zeitrahmen, in dem der Quellbereich gelesen und in den Zielbereich geschrieben wird, schaltet PLA 31 den Schalter 4-3 an seinem FDX-Eingang auf Leitung 4- 7, während der Schalter 4-1 auf die Leitung 4-14 geschaltet bleibt und der Schalter 4-5 auf die FDY-Eingangs-Leitung 4-9 geschaltet bleibt. In Übereinstimmung mit den Schalterstellungen und den Operationen im letzten Zeitrahmen, stellt der Akkumulator 4-11 eine Null der A-S-Einrichtung 4-8 zur Verfügung, während die Leitung 4-7 FDX der A-S- Einrichtung 4-8 zur Verfügung stellt und das Steuersignal von PLA 31 veranlaßt, daß FDX von Null subtrahiert wird. Folglich wird der -FDX-Wert zu der A-S-Einrichtung 4-10 transferiert, in der FDX von FDY subtrahiert wird. Aus den numerischen Werten der Tabelle II kann man sehen, daß die Berechnungen in den zwei A-S-Einrichtungen 4-8 und 4-10 als Resultat 0 - 10 + 5 = -5 haben. Folglich steht ein -5-Wert im Akkumulator 4-11. Das arithmetische, negative Vorzeichen wird im Register 4-13 gespeichert und zum PLA 31 transferiert. Das PLA 31 reagiert auf das arithmetische, negative Vorzeichen mit dem Schalten des Schalters 6-3 auf die "0"-Eingangs-Leitung 6-4, während der Schalter 7-3 auf die "1"-Eingangs-Leitung 7-12 geschaltet bleibt. Dementsprechend wird nur die FX-Adresse erhöht, wie in den letzten beiden Spalten der Tabelle II angedeutet. Daraus folgt, daß Pixel 79 von Fig. 14 wie gezeigt plaziert wird. Das System setzt den Betrieb des Erzeugens von Signalen für PLA 31 fort, das seinerseits die Schaltungen von Fig. 6 und 7 anweist, die passenden FX- und FY-Signale zu erzeugen. Die Bresenham-Algorithmus-Schaltung von Fig. 8 arbeitet in identischer Weise und stellt damit PLA 29 (wobei die Leitung 30 analog zu Leitung 28 ist) Signale zur Verfügung, das seinerseits die Adreß-Schaltungen von Fig. 10 und 11 anweist, die SX- und SY-Adressen zu erzeugen. Die Adressen, die Pixel entlang dem Ursprungs-Vektor 74 in Fig. 14 bereitstellen sollen, werden nur erhöht, wenn die Zähler-Schaltung von Fig. 5 anzeigt, daß ein gezeichneter Vektor vollständig gezeichnet worden ist. Die Zähler-Schaltung von Fig. 5 zählt als Reaktion auf die Steuersignale von PLA 31 (wie zuvor beschrieben) jedesmal, wenn ein Pixelwert, so wie die Pixel 77 und 79, erzeugt wird.
• Zuvor wurde erwähnt, daß das vorliegende System eine Lückenfüllung bewirkt. Vor der Diskussion der Schalungen, die die Lückenfüllung bewirken, sollten wir die Notwendigkeit der Lückenfüllung betrachten. In Fig. 15 wird ein Vektor 81 gezeigt, der die selbe Steigung wie Vektor 73 in Fig. 14 hat, aber der doppelt so lang ist. Buchstaben wurden an die den Zentren der Pixel entsprechenden Positionen plaziert und natürlich würden die Pixelpositionen von Fig. 15 doppelt so groß sein wie die Pixelpositionen von Fig. 14. Fig. 15 ist übertrieben gezeichnet, um die Situation zu zeigen, in der Lücken auftreten. "A"s bezeichnen die Zentren der Pixel, die einen Vektor entlang Linie 81 bilden. "B"s bezeichnen die Zentren der Pixel, die einen zweiten Vektor entlang Linie 83 bilden. Die Positionen 85, 87, 89, 91 und 93 haben weder ein A noch ein B und werden deshalb als Lücken angesehen.
• Es gibt einen einfachen Test, das System zu warnen, daß Lücken im Zielparallelogramm möglich sind. Zuerst untersucht das System die arithmetischen Vorzeichen von SDX, SDY, FDX und FDY. Wenn eine ungerade Anzahl von Minuszeichen auftaucht, dann sind Lücken möglich. Zusätzlich werden Lücken nur während der Erzeugung von Pixeladressen auftreten, die einen gezeichneten Vektor bilden, wenn der Ursprung eines gezeichneten Vektors entlang dem Ursprungs-Vektor relativ zum Ursprung des nächsten gezeichneten Vektors diagonal versetzt ist. Schließlich kommen Lücken vor, wenn die beiden obigen Bedingungen vorliegen und die Adresse eines nachfolgenden Pixels auf einem gezeichneten Vektor im Verhältnis zu der Adresse eines vorher erzeugten Pixels diagonal plaziert ist. Die erste Bedingung wird in der Zustands-Maschine 37 erkannt und die zweite sowie die dritte Bedingung werden von den Schaltungen für den Bresenham-Algorithmus, die entsprechende Signale an die Zustands-Maschine ausgeben, erkannt.
• Es wird daran erinnert, daß die arithmetischen Vorzeichen der Eingangs-Signale auf den Leitungen 24 und 26 in Fig. 1 direkt erkannt werden und in nicht gezeigten Flip- Flops gespeichert werden. Diese arithmetischen Vorzeichen-Signale werden von diesen Flip-Flops zu einem Exklusiv-ODER-Gaffer in der Zustands-Maschine 37 gesandt und dessen Ausgangssignal wird in ein UND-Gatter für den Lückentest in der Zustands- Maschine 37 eingegeben. Ein Pluszeichen-Signal auf der Leitung 25 von der Schaltung für den Bresenham-Algorithmus (Flip-Flop 8-12) in Fig. 8 zeigt an, daß der Ursprung des nächsten gezeichneten Vektors bezogen auf den Ursprung des vorhergehenden gezeichneten Vektors diagonal liegt, was die zweite, oben erwähnte Bedingung für eine Warnung ist, um eine Lückenfüllung durchzuführen. Das zuletzt erwähnte Vorzeichen-Signal wird an das UND-Gatter für den Lückentest in der Zustands-Maschine 37 gegeben.
• Ein Pluszeichen auf der Leitung 28 von der Schaltung für den Bresenham-Algorithmus in Fig. 4 würde anzeigen, daß die Adresse eines nachfolgenden Pixels auf einem gezeichneten Vektor zu einer zuvor erzeugten Adresse diagonal liegt, was die dritte, oben erwähnte Bedingung für eine Warnung ist, um eine Lückenfüllung durchzuführen. Das Vorzeichen-Signal auf der Leitung 28 von der Schaltung in Fig. 4 wird an das UND-Gatter für den Lückentest in der Zustands-Maschine 37 gegeben. Aus Betrachtungen der Fig. 15 wird offenbar, daß alle drei Bedingungen für das Erzeugen einer Lücke bei der Erzeugung des A-Pixels vorliegen. Es werden keine Lücken erzeugt, wenn die B-Pixel berechnet werden, da die zweite Bedingung, d. h. daß der Ursprung des nächsten gezeichneten Vektors zum Ursprung des zuvor gezeichneten Vektors diagonal liegen soll, nicht vorliegt. Der Ursprung 97 des Vektors C liegt nicht diagonal zum Ursprung 99 des Vektors B.
• Da bezogen auf die Erzeugung der A-Pixel in Fig. 15 die drei Warnungs-Bedingungen existieren, sendet die Zustands-Maschine 37 ein Befehls-Signal an PLA 31, das seinerseits die Schaltungen von Fig. 5-7 aktiviert. Das Befehls-Signal von PLA 31 schaltet den Schalter 7-3 auf die "0"-Eingangs-Leitung 7-4 und schaltet den Schalter 6-3 auf die "1"-Eingangs-Leitung 6-12, so daß nur die Adresse auf der Y-Achse erhöht wird. Zusätzlich wird der Schalter 5-4 auf die "0"-Eingangs-Leitung 5-11 geschaltet, so daß der an der Stelle 85 hinzugefügte Pixelwert nicht gezählt wird. Die Schalter 4-1, 4-3 und 4-5 der Schaltung für den Bresenham-Algorithmus in Fig. 4 werden auf ihre "0"-Eingangs- Leitungen geschaltet, um einen neuen Befehl während dem Zeitrahmen, in dem der Pixelwert für die Stelle 85 erzeugt wird, zu verhindern. Im nächsten Zeitrahmen weist die Zustands-Maschine 37 PLA 31 an, den Schalter 7-3 auf die "1"-Eingangs-Leitung 7-12; den Schalter 6-3 auf die "0"-Eingangs-Leitung 6-4; den Schalter 5-4 auf die "1"-Eingangs-Leitung 5-5 und die Schalter 4-1, 4-3 und 4-5 jeweils auf die Akkumulator-Eingangs-Leitung 4-14, die FDX-Eingangs-Leitung 4-7 und die FDY-Eingangs-Leitung 4-9 zu schalten. Folglich wird nur die Adresse längs der X-Achse erhöht und die nächste FX- Adresse ist dort, wo der Wert 101 des A-Pixels liegt. Der Pixelwert 101 wird gezählt und die Bresenham-Schaltung erzeugt neue Adreßerhöhungs-Befehle, um das A-Pixel 103 zu erzeugen.

Claims (13)

1. Ein Transformations-Schaltkreis zum Lesen einer ersten Vielzahl von Pixelwerten, die einem Quellbild aus einem ersten Feld von Adressen in einem Bit-Map-Speicher mit Zeilen und Spalten von Adressen entspricht, und zum Schreiben einer zweiten Vielzahl von Pixelwerten, die einer transformierten Version des Quellbildes entspricht, in ein zweites Feld von Adressen im Bit-Map-Speicher, wobei jede Adresse aus einer eine Spalte im Bit-Map-Speicher kennzeichnenden X-Adreß-Komponente und einer eine Zeile kennzeichnenden Y-Adreß-Komponente besteht und wobei das Quellbild aus einer Vielzahl gleichlanger, paralleler gezeichneter Quell-Vektoren mit Ausgangspunkten längs eines dazu senkrecht stehenden Quell-Ursprungs-Vektors gebildet wird und das transformierte Bild aus einer Vielzahl gleichlanger, paralleler gezeichneter Ziel-Vektoren mit ihrem Ursprung längs eines Ziel-Ursprungs-Vektors gebildet wird, wobei jeder gezeichnete Ziel-Vektor eine Transformation eines entsprechenden gezeichneten Quell-Vektors und der Ziel-Ursprungs-Vektor eine Transformation des Quell-Ursprungs-Vektors darstellt, und wobei jeder Vektor Pixelwerte umfaßt, die an einer Folge von Adressen gespeichert sind, ein mit dem Bit-Map-Speicher verbundener Adreß-Schaltkreis (59), wobei der Adreß-Schaltkreis als Reaktion auf Adreß-Signale eine ausgewählte Adresse im Bit-Map- Speicher anspricht und wobei der Transformations-Schaltkreis folgende Einrichtungen aufweist:

(a) eine Zieladressen-Schaltung (13) für Ursprungs-Vektoren zur Ausgabe einer Folge von Adressen, an denen die den Ziel-Ursprungs-Vektor repräsentierenden Pixelwerte gespeichert werden sollen als Funktion von den X- und Y- Komponenten der ersten Adresse und den X- und Y-Ausdehnungen des Ziel-Ursprungs-Vektors;

(b) eine Zieladressen-Schaltung (15) für gezeichnete Vektoren, die mit der Zieladressen-Schaltung für Ursprungs- Vektoren verbunden ist zur Ausgabe einer Folge von Adressen, an denen die einen gezeichneten Ziel-Vektor repräsentierenden Pixelwerte gespeichert werden sollen als Funktion von der von der Zieladressen-Schaltung für Ursprungsvektoren ausgegebenen Adresse und den X- und Y- Ausdehnungen eines gezeichneten Ziel-Vektors;

(c) eine Quell-Logik-Schaltung (55) zur sequentiellen Ausgabe des ersten Feldes von Adressen;

(d) Schalt-Einrichtungen (29, 31, 53), die mit der Zieladressen-Schaltung für Ursprungs-Vektoren, der Zieladressen- Schaltung für gezeichnete Vektoren und der Quell-Logik- Schaltung verbunden sind zur Ausgabe von Schalt-Signalen, die die Folge der Adressen-Ausgabe durch die Zieladressen-Schaltung für Ursprungs-Vektoren, die Zieladressen- Schaltung für gezeichnete Vektoren und die Quell-Logik- Schaltung bestimmen;

(e) eine Steuerschaltung (37), die mit den Schalt-Einrichtungen, der Zieladressen-Schaltung für Ursprungs-Vektoren und der Zieladressen-Schaltung für gezeichnete Vektoren verbunden ist, zur Ausgabe von Steuer-Signalen an die Schalt-Einrichtungen als Folge von Status-Signalen aus der Zieladressen-Schaltung; und

(f) eine Adreß-Sammel-Schaltung (57), die mit der Quell-Logik-Schaltung (55), der Ziel-Adressen-Schaltung für gezeichnete Vektoren (15) und dem Adreß-Schaltkreis (59) verbunden ist zum Multiplexen der Adressen, die ausgegeben werden von der Quell-Logik-Schaltung und der Zieladressen-Schaltung für die gezeichneten Vektoren an den Adreß-Schaltkreis (59), wobei die zieladressen-Schaltung für den Ursprungs-Vektor weiterhin einschließt eine Schaltung zur Bestimmung der Rotation, die so angeschlossen ist, daß sie die X- und Y-Ausdehnungen des Ziel-Ursprungs-Vektors empfängt und daß sie erste oder zweite status-Signale an die Schalt-Einrichtungen ausgibt als Funktion des Ergebnisses der Verarbeitung der X- und y-Ausdehnungen des Ziel-Ursprungs-Vektors entsprechend einem vorher festgelegtem Algorithmus, wobei die Schalt- Einrichtungen die Zieladressen-Schaltung für Ursprungs- Vektoren veranlassen, eine Folge von Adressen zu erzeugen, die im wesentlichen längs eines Vektors liegen, der bezüglich dem Quell-Ursprungs-Vektor gedreht ist und wobei die Zieladressen-Schaltung für gezeichnete Vektoren weiterhin Schaltkreise aufweist zur Bestimmung der Rotation, die so angeschlossen sind, daß sie die X- und Y-Ausdehnungen eines gezeichneten Ziel-Vektors empfangen und daß sie entweder erste oder zweite status-Signale an die Schalt-Einrichtungen ausgeben als Funktion vom Ergebnis der Verarbeitung der X- und Y-Ausdehnungen eines gezeichneten Ziel-Vektors entsprechend einem vorher festgelegten Algorithmus, wobei die Schalt-Einrichtungen den Zieladressen-Schaltkreis der gezeichneten Vektoren so schalten, daß er eine Folge von Adressen erzeugt, die im wesentlichen längs eines Vektors liegen, der relativ zum gezeichneten Quell-Vektor gedreht ist.

2. Transformations-Schaltkreis nach Anspruch 1, wobei der Ziel-Adressen-Schaltkreis für gezeichnete Vektoren Zählerschaltungen enthält, um eine Zählgröße um eins zu erhöhen als Reaktion auf die Erzeugung einer X-Adresse für einen Pixelwert eines gezeichneten Ziel-Vektors, die verschieden von der X- Adresse ist, die für den vorhergehenden Pixelwert dieses gezeichneten Ziel-Vektors erzeugt worden ist, und um ein Statussignal an den Steuer-Schaltkreis auszugeben, das das Ende des gezeichneten Ziel-Vektors anzeigt als Reaktion auf die Anzahl der Zählvorgänge, wenn diese einen Wert gleich der x-Ausdehnung des gezeichneten Vektors erreichen.

3. Transformations-Schaltkreis nach Anspruch 2, wobei der Ziel-Adressen-Schaltkreis für Ursprungs-Vektoren Zähler-Schaltungen enthält, um eine Zählgröße um eins zu erhöhen als Reaktion auf die Erzeugung einer Y-Adresse für einen Pixelwert des Ziel-Ursprungs-Vektors, die verschieden ist von der Y-Adresse, die für den vorhergehenden Pixelwert des Ziel-Ursprungs-Vektors erzeugt worden ist, und um ein Status-Signal an den Steuerschaltkreis auszugeben, das das Ende des Ziel-Ursprungs-Vektors anzeigt als Reaktion auf die Anzahl der Zählvorgänge, wenn diese den Wert der Y-Ausdehnung des Ursprungs-Vektors erreichen.

4. Transformations-Schaltkreis nach Anspruch 1, wobei der ziel-Adressen-Schaltkreis für Ursprungs-Vektoren weiterhin Bestimmungs-Schaltkreise für die X- und Y-Adressen enthält, die jeweils so angeschlossen sind, daß sie die X- und Y-Komponenten der ersten Adresse empfangen und beide schalt-Signale von den schalt-Einrichtungen erhalten können, wobei die Bestimmungsschaltkreise für die X- und Y-Adressen jeweils die X- und Y-Komponenten einer Folge von Adressen im Bit-Map-Speicher erzeugen, an denen die den Ziel-Ursprungs-Vektor repräsentierenden Pixelwerte gespeichert werden sollen, und wobei die Schalt- Einrichtungen die Bestimmungs-Schaltkreise für die X-Adressen so schalten, daß sie eine unveränderte X-Komponente erzeugen, und die Bestimmungs-Schaltkreise für die Y-Adressen so schalten, daß sie eine auf den neuesten stand gebrachte Y-Komponente als Reaktion auf das erste Status-Signal erzeugen, und die Bestimmungs-Schaltkreise für die X- und Y-Adressen so schalten, daß sie jeweils auf den neuesten stand gebrachte X- und Y-Komponenten erzeugen als Reaktion auf das zweite Statussignal.

5. Transformations-Schaltkreis nach den Ansprüchen 1 oder 3, wobei der vorher festgelegte Algorithmus der Bresenham-Algorithmus ist.

6. Transformations-Schaltkreis nach Anspruch 1, wobei die zieladressen-Schaltung für gezeichnete Vektoren weiterhin Bestimmungs-Schaltkreise für X- und Y-Adressen enthält, die so angeschlossen sind, daß sie jeweils von der Zieladressen Schaltung für Ursprungs-Vektoren ausgegebene X- und Y-Komponenten empfangen, und beide so angeschlossen sind, daß sie schalt-Signale von den Schalt-Einrichtungen erhalten, wobei die Bestimmungs-Schaltkreise für die X- und Y-Adressen jeweils die X- und Y-Komponenten einer Folge von Adressen im Bit-Map- Speicher erzeugen, an denen die den gezeichneten Ziel-Ursprungs-Vektor repräsentierenden pixelwerte gespeichert werden sollen, und wobei die Schalt-Einrichtungen den Bestimmungsschaltkreis für die X-Adressen so schalten, daß er eine auf den neuesten stand gebrachte X-Komponente erzeugt, und daß der Bestimmungs-Schaltkreis für die Y-Adressen eine unveränderte Y-Adresse erzeugt als Reaktion auf das erste Status-Signal, und daß die schalt-Einrichtungen die Bestimmungs-Schaltkreise für die X- und Y-Adressen so schalten, daß sie jeweils auf den neuesten Stand gebrachte X- und Y-Komponenten als Reaktion auf das zweite Status-Signal erzeugen.

7. Transformations-Schaltkreis nach Anspruch 6, wobei der steuer-Schaltkreis (37) ein vorher festgelegtes Steuer-Signal an die schalt-Einrichtungen ausgibt als Reaktion auf den Empfang eines vorher festgelegten Satzes von Status-Signalen von den Zieladressen-Schaltungen (13, 15), das anzeigt, daß eine Lücke vorliegt in der Folge der Adressen, an denen die das transformierte Bild repräsentierenden pixelwerte zu speichern sind, und bei dem die Schalt-Einrichtungen (31) den Bestimmungs-Schaltkreis für die X-Adressen veranlassen, eine unveränderte X-Komponente zu erzeugen, und den Bestimmungs-Schaltkreis für die Y-Adresse veranlassen, eine auf den neuesten Stand gebrachte Y-Komponente zu erzeugen als Reaktion auf das vorher festgelegtes Steuer-Signal.

8. Transformations-Schaltkreis nach Anspruch 1, wobei der Transformations-Schaltkreis weiterhin Skalierungs-Schaltungen (41, 43) enthält, die so angeschlossen sind, daß sie von der Steuer-Schaltung (37) Signale für den skalierungs-Faktor empfangen und Status-Signale an die Steuer-Schaltung (37) ausgeben, wobei die Steuer-Schaltung die Schalt-Einrichtungen als Reaktion auf die von den skalierungs-Schaltungen empfangenen Status-Signale so steuert, daß die Anzahl der Adressen des zweiten Feldes, die für jede von wenigstens einigen Adressen des ersten Feldes erzeugt werden, nicht gleich eins ist, wobei die Anzahl der Adressen des zweiten Feldes, die für jede der Adressen des ersten Feldes erzeugt werden, vom von der Steuerschaltung gelieferten Skalierungs-Faktor abhängt.

9. Transformations-Schaltkreis nach Anspruch 8, wobei die Steuer-Schaltung (37) die Schalt-Einrichtungen (53) als Reaktion auf ein vorher festgelegtes Status-Signal von der Skalierungs- Schaltungen (41, 43) so steuert, daß die nächste Adresse des ersten Feldes von Adressen von der Quell-Logik (55) ausgegeben wird.

10. Transformations-Schaltkreis nach Anspruch 8, wobei der Skalierungs-Faktor einen solchen Wert hat, daß das transformierte Bild größer als das Quell-Bild ist.

11. Transformations-Schaltkreis nach Anspruch 10, wobei der Skalierungs-Faktor einen solchen Wert hat, daß das transformierte Bild um einen nicht-ganzzahligen Faktor größer als das Quell-Bild ist.

12. Transformations-Schaltkreis nach Anspruch 10, wobei der Skalierungs-Faktor einen solchen Wert hat, daß das transformierte Bild kleiner als das Quell-Bild ist.

13. Transformations-Schaltkreis nach Anspruch 10, wobei der Skalierungs-Faktor einen solchen Wert hat, daß das transformierte Bild um einen nicht-ganzzahligen Faktor kleiner als das Quell-Bild ist.