DE69112434T2 - Kurvengenerator. - Google Patents

Description

Hintergrund der Erfindung
• Die vorliegende Erfindung betrifft einen Kurvengenerator und insbesondere einen Kurvengenerator, der eine freie Kurve aus einer Gruppe von gegebenen Kontrollpunkten in einer graphischen Anzeige generiert, welche Zeichen oder graphische Figuren an einen CRT oder einen Drucker abgibt.
• Als ein typisches mit Graphiken verbundenes Gerät, das mit Zeichen oder Graphiken zu tun hat, sind PC und EWS (Engineer Work Stations - Technische Arbeitsstationen) zu nennen, und diese haben breite Verwendung gefunden. Graphiken, die allgemein in diesen Geräten verwendet werden können, basieren auf geraden Linien oder Kreisbögen, und komplizierte Graphiken werden durch eine Kombination aus denselben dargestellt. Solche Geräte weisen daher Hardware auf, die eine gerade Linie und einen Kreisbogen zeichnen kann, um die Leistung desselben zu verbessern. Es existieren jedoch andere Graphiken als die gerade Linie und der Kreisbogen, die auch häufig verwendet werden. Eine von diesen ist eine freie Kurve, und als eine Bezier-Kurve und eine Spline-Kurve bezeichnete freie Kurven werden oft verwendet. Jede dieser freien Kurven kann eine stetige Kurve darstellen und ist daher nicht nur zweckdienlich für CAD (Computer Aided Design - Computerunterstütztes Entwerfen), welches verschiedene Arten von Produkten mit einem Computer entwerfen kann, sondern ist weiter für den Ausdruck von Zeichen zu verwenden, der als "Outline Font" (Konturschrift) bezeichnet wird, welcher in letzter Zeit große Beachtung geschenkt wurde.
• Die Konturschrift bedeutet, daß ein Zeichen durch Koordinatenwerte von Endpunkten auf Liniensegmenten definiert wird, die die Konturen des Zeichens zeichnen. Um das Zeichen anzuzeigen oder zu drucken, wird eine innere Fläche der Kontur desselben ausgefüllt. Die Kontur des Zeichens weist eine Mischung aus geraden Linien und Kurven auf. Die Kurven sind allgemein freie Kurven eher als Kreisbögen. Ein gekrümmter Anteil der Kontur kann mit kurzen Liniensegmenten angenähert werden, was jedoch eine äußerst hohe Anzahl von Liniensegmenten pro Zeichen zur Folge hat. Die Nachteile hierbei bestehen darin, daß die notwendige Information zum Definieren des Zeichens sehr groß wird, und daß, wenn das Zeichen vergrößert wird, die Qualität desselben schlecht wird, da der mit Liniensegmenten angenäherte gekrümmte Anteil desselben in Form einer Gruppe von geraden Linien erscheint. Daher wird allgemein eine als Bezier-Kurve bezeichnete Kurve für die Konturschrift verwendet.
• Gemäß des Bezier-Kurven-Verfahrens (bekannt z. B. aus EP-A-0 349 182 und "Proceedings of the IEEE, 1989, Custom integrated circuits conference", Mai 1989, New York, Seiten 24.6.1. - 24.6.4; N.Kai et al: "A high speed outline font rastering LSI") kann, wenn einige Kontrollpunkte gegeben sind, die stetige Kurve einer Bezier-Kurve in der Nähe der Punkte interpoliert werden. Eine häufig verwendete Kurve ist eine Bezier-Kurve dritter Ordnung. Wenn vier Punkte als Kontrollpunkte gegeben sind, kann die Bezier-Kurve dritter Ordnung nicht nur für die vier Punkte interpoliert werden, sondern kann weiter eine äußerst stetige Kurve sein, da, wenn eine Bezier-Kurve neu für vier Punkte gezeichnet wird, die aus einem neu angegebenen Punkt und drei der vier Ausgangspunkte außer dem Anfangspunkt derselben bestehen, die Differentialquotienten der ersten und der zweiten Ordnung der ersten Bezier-Kurve mit denen der zweiten Bezier-Kurve an einem Verbindungspunkt der beiden Kurven übereinstimmen. Die freie Kurve weist, wie oben erwähnt, den Vorteil auf, daß der Umfang der Informationen, die eine Form der Kurve definieren, klein ist, und daß, wenn die Konturschrift eines Zeichens zum Anzeigen oder Drucken vergrössert oder verkleinert wird, die Qualität der Zeichen nicht verschlechtert wird.
• Im folgenden wird ein Algorithmus zum Erzeugen einer Bezier-Kurve erläutert. Es ist allgemein ein Algorithmus bekannt, der die Kurve durch Berechnung des Anfangspunkts derselben ermittelt. In diesem Falle ist die Berechnungsgeschwindigkeit bei Verwendung eines Mehrzweckcomputers jedoch langsam, da zahlreiche Multiplikations- und Divisionsberechnungen durchgeführt werden müssen. Daher wird gewöhnlich ein Algorithmus verwendet, der zum Ermitteln der Kurve geometrisch verarbeitet werden kann.
• Fig. 1 ist ein Koordinatenschaubild zur Erklärung des geometrischen Algorithmus, der die Bezier-Kurve der dritten Ordnung erzeugt. Zuerst sollten für die als Kontrollpunkte gegebenen vier beliebigen Punkte mittlere Punkte E, F und G der Liniensegmente AB, BC und CD ermittelt werden. Der Mittelpunkt kann durch die Berechnung ermittelt werden, bei der Koordinatenwerte der Kontrollpunkte auf dem Liniensegment miteinander addiert werden und anschließend durch zwei geteilt werden. Als nächstes sollten die Mittelpunkte H und I der Liniensegmente EF und FG ermittelt werden, und dann sollte ein Mittelpunkt J eines Liniensegments HI ermittelt werden. Dieser Punkt J befindet sich auf der Bezier-Kurve der dritten Ordnung. Als nächstes wird, wenn die oben genannte Methode für die Punkte A, E, H und J als Kontrollpunkte durchgeführt wird, ein nächster Punkt Q auf der Kurve ermittelt. Wie oben erläutert wird die Rekursivmethode, nachdem der Punkt auf der Kurve ermittelt wurde, wiederholt für einen neuen Kontrollpunkt durchgeführt, um einen nächsten Punkt auf der Kurve zu ermitteln.
• Wenn die obengenannte Methode wiederholt durchgeführt wird, nähert sich der ermittelte Punkt auf der Kurve nach und nach und unendlich dem Anfangspunkt A an. Daher ist es notwendig, den Prozess anzuhalten, wenn sich der ermittelte Punkt im wesentlichen dem Anfangspunkt annähert, und den Prozess zu ändern, um einen neuen Punkt zu ermitteln. In anderen Worten sollten die nächsten Kontrollpunkte J, I, G und D sein, wenn die Entfernung zwischen dem Punkt A und dem ermittelten Punkt Q auf der Kurve, wie in Fig. 1 gezeigt, kleiner als ein vorbestimmter Wert ist.
• Zum Generieren der oben genannten freien Kurve gibt es einen herkömmlichen Apparat, bei dem, da derselbe den Prozess mittels Software ausführt, die Verarbeitungszeit lang ist. Gemäß dem herkömmlichen Apparat ist es erforderlich, dar ein Mehrzweckcomputer die Prozesse von mehreren hundert Taktimpulsen durchführt, um einen Punkt auf der Kurve zu ermitteln. Um einen X-Koordinatenwert eines Mittelpunkts zu ermitteln, müssen zweimaliges Laden von Daten, eine Addition, ein Verschieben (d. h. Division durch zwei) und ein Laden durchgeführt werden. Um X-Koordinatenwerte und Y- Koordinatenwerte von 6 Punkten zu ermitteln, sind daher Arbeitsgänge erforderlich, die mindestens 60 Schritte umfassen. Um den Befehl eines Schritts auszuführen, werden 4 Taktperioden benötigt, da der Befehl abgerufen, ein Operand gelesen, der Arbeitsgang ausgeführt und das Ergebnis desselben gespeichert werden muß. Dieses hat zur Folge, daß mehrere hundert Taktimpulse erforderlich sind, um einen Punkt auf der Kurve zu ermitteln. Darüberhinaus sind die Prozesse erforderlich, in denen zum Beispiel die Entfernung zwischen dem Kontrollpunkt und dem Punkt auf der Kurve berechnet wird, um mit dem vorbestimmten Wert verglichen zu werden, und in denen Daten ausgetauscht werden, wenn die Entfernung kleiner als der vorbestimmte Wert ist, so daß die Verarbeitungsgeschwindigkeit langsamer wird.
Zusammenfassung der Erfindung
• Eine Aufgabe der vorliegenden Erfindung besteht daher in der Überwindung der bestehenden Probleme bei der herkömmlichen Anordnung und in der Schaffung eines verbesserten Kurvengenerators.
• Eine andere Aufgabe der vorliegenden Erfindung besteht in der Schaffung eines Kurvengenerators, der eine freie Kurve bei hoher Geschwindigkeit generieren kann.
• Eine weitere Aufgabe der vorliegenden Erfindung besteht in der Schaffung eines Kurvengenerators, der mittels einer exklusiven Hardware die Verarbeitung eines Algorithmus zum Generieren der Kurve realisiert.
• Bei der Erfüllung der oben genannten und anderer Aufgaben der vorliegenden Erfindung in einer Form wird ein verbesserter Kurvengenerator geschaffen, der für eine Kurve in der Nähe einer Vielzahl bestimmter Kontrollpunkte durch Berechnen von Koordinatenwerten von Mittelpunkten zwischen den Kontrollpunkten auf der Basis von Koordinatenwerten der Kontrollpunkte interpoliert, der aufweist:
• ein erstes Speichermittel, das, nachdem die Vielzahl von Kontrollpunkten und die Mittelpunkte in zwei Gruppen geteilt worden sind, eine Gruppe der Koordinatenwerte der Vielzahl von Kontrollpunkten und der Mittelpunkte speichert;
• ein zweites Speichermittel, das die andere Gruppe der Koordinatenwerte der Mittelpunkte speichert und einen Zeiger aufweist, der eine Adresssteuerung ausführt;
• ein Operationsmittel, das Koordinatenwerte eines Mittelpunktes zwischen vorbestimminten zwei Punkten berechnet, deren Koordinatenwerte in wenigstens einem der ersten und zweiten Speichermittel gespeichert sind, und bewirkt, daß der berechnete Koordinatenwert des Mittelpunkts in einem der ersten und zweiten Speichermittel gespeichert wird;
• einen Komparator, der eine Entfernung zwischen den Kontrollpunkten berechnet und diese Entfernung mit einem vorbestimmten Wert vergleicht; und
• ein Mittel, das ein Ausgangssignal des Komparators empfängt, welches Mittel den Zeiger hochschaltet, wenn die Entfernung größer ist als der vorbestimmte Wert, aus dem zweiten Speichermittel ausgelesene Koordinatenwerte zum ersten Speichermittel überträgt und auch den Zeiger runterschaltet, wenn die Entfernung kleiner ist als dieser Wert.
• Gemäß der vorliegenden Erfindung können das erste und das zweite Speichermittel ein oder mehrere Register, Registerfiles oder Speicher mit wahlfreiem Zugriff aufweisen.
Kurze Beschreibung der Zeichnungen
• Fig. 1 ist ein Koordinatenschaubild für die Erklärung eines Algorithmus, der eine allgemeine Bezier- Kurve generiert;
• Fig. 2 zeigt ein Blockschaltbild eines Kurvengenerators als eine erste erfindungsgemäße Ausführungsform;
• Fig. 3 ist ein Ablaufdiagramm, das den Betrieb des in Fig. 2 gezeigten erfindungsgemäßen Kurvengene rators veranschaulicht;
• Fig. 4 ist ein Schaubild zum Erklären des Inhalts der Register in dem in Fig. 2 gezeigten erfindungsgemäßen Kurvengenerator; und
• Fig. 5 zeigt ein Blockschaltbild eines Kurvengenerators als eine zweite erfindungsgemäße Ausführungsform.
Bevorzugte Ausführungsformen der Erfindung
• In der folgenden Erläuterung verweisen ähnliche Bezugssymbole oder -ziffern auf die gleichen oder ähnliche Elemente in allen Figuren der Zeichnungen.
• Nun werden die Ausführungsformen der vorliegenden Erfindung detailiert unter Bezugnahme auf Fig. 2 bis 5 beschrieben.
• Fig. 2 zeigt ein Blockschaltbild eines Kurvengenerators als eine erste erfindungsgemäße Ausführungsform. Der Kurvengenerator umfaßt Register 1-4, Registerfiles 5-7, ein Entfernungsregister 8, eine Verarbeitungseinrichtung 9, eine Verschiebeeinrichtung 10, eine Folgesteuerungseinheit 11, einen Zeiger 12 und einen Komparator 13, wobei die betreffenden Elemente über Datenbusse 20 - 24 und 33 verbunden sind. Die beteiligten Signale umfassen ein Verarbeitungssteuersignal 30, ein Zeigersteuersignal 31, ein Registersteuersignal 32 und ein Vergleichssignal 34.
• Gemäß der ersten erfindungsgemäßen Ausführungsform werden Koordinatenwerte von 4 Punkten in dieselbe eingegeben und anschließend wird der Punkt auf der Bezier-Kurve der dritten Ordnung nahe eines Anfangspunkts ermittelt. Das Abtasten der Kurve wird fortgesetzt, bis sowohl ein X-Koordinatenwert zwischen benachbarten Punkten als auch ein Y-Koordinatenwert zwischen denselben in einem Koordinatensystem kleiner als ein vorbestimmter Wert werden. Ein Koordinatenwert wird durch ein 16-Bit Festkomma dargestellt und der X-Koordinatenwert und der Y-Koordinatenwert werden kombiniert verarbeitet, so daß das Register, der Registerfile, der Datenbus, die Verarbeitungseinrichtung und so weiter jeweils eine Wortlänge von 32 Bits aufweisen. Die Verarbeitungseinrichtung 9 und die Verschiebeeinrichtung 10 weisen jeweils zwei Teile auf, von denen jeder eine Wortlänge von 16 Bits umfaßt und für den X-Koordinatenwert oder der Y-Koordinatenwert verwendet wird, die jedoch ihre Verarbeitungsergebnisse in Kombination mit den Koordinaten ausgeben, so daß Ausgangssignale derselben eine Wortlänge von 32 Bits aufweisen. Kurz gesagt sind der Prozess der X-Koordinatenwerte und der der Y-Koordinatenwerte voneinander unabhängig, aber die Abfolgen der beiden Prozesse sind gleichzeitig, so daß die Ergebnisse der Prozesse miteinander mittels Hardware kombiniert werden können.
• Die Realisierung der Hardware hängt von den Eigenschaften ab, daß:
• (i) Laden der Koordinatenwerte, Addieren, Verschieben und Speichern der Ergebnisse während einer Taktperiode ausgeführt werden kann;
• (ii) die X-Koordinatenwerte und die Y-Koordinatenwerte in einzelnen Verarbeitungseinrichtungen zur gleichen Zeit verarbeitet werden können;
• (iii)die Entfernung zwischen Kontrollpunkten auf der Basis der Unterschiede zwischen X-Koordinatenwerten der Punkte und zwischen Y-Koordinatenwerten derselben bestimmt wird;
• (iv) alle Abfolgen der Prozesse durch die Hardware gesteuert werden können, so daß ein Abrufzyklus eines Befehlskodes nicht benötigt wird; und
• (v) die Prozesse zyklisch mittels der Hardware ausgeführt werden, die durch Berechnung einen Punkt auf der Kurve ermittelt.
• Wenn die Hardware die oben genannten Eigenschaften aufweist, ist es möglich, während einer Laufzeit von 7 Taktperioden einen Punkt auf der Kurve zu ermitteln und die Leistung derselben zu erreichen, die mehrere Zehnfache der Zeit beträgt, die der herkömmlichen Kurvengenerators benötigt, bei dem die Prozesse durch Software ausgeführt werden.
• Gemäß der vorliegenden Erfindung ist die Hardware, insbesondere um die Eigenschaft (v) zu realisieren, so ausgeführt, daß die Abfolge derselben einfach wird. Es sind Speichermittel vorgesehen, in denen die Kontrollpunkte und neue Kontrollpunkte, die aus unter den Kontrollpunkten ermittelten Mittelpunkten generiert werden, in zwei Gruppen aufgeteilt und gespeichert werden, so daß es möglich ist, die Gruppe von Kontrollpunkten leicht auszutauschen, wenn die Entfernung zwischen dem generierten Kontrollpunkt und dem benachbarten Punkt innerhalb des vorbestimmten Wertes fällt.
• Nun wird der Inhalt der Register unter Bezugnahme auf Fig. 4 erklärt. Fig. 4(a) veranschaulicht den Anfangszustand des Inhalts desselben. Die Koordinatenwerte eines ersten Kontrollpunkts (ein Anfangspunkt der Kurve, zum Beispiel der in Fig. 1 gezeigte Punkt A), eines zweiten Kontrollpunkts (zum Beispiel der in der Figur gezeigte Punkt B), eines dritten Kontrollpunkts (zum Beispiel der in derselben gezeigten Punktes C) und eines vierten Punkts (ein Endpunkt der Kurve, zum Beispiel der in derselben gezeigte Punkt D) werden auf die Register 1, 2, 3 und die Adresse 0 des Registerfiles 5 festgelegt. Dieses Festlegen wird durch die Steuerung von einer externen Einheit ausgeführt. Die Fig. 4(b) bis 4(e) veranschaulichen Veränderungen bei dem Inhalt der Register und Registerfiles. Fig. 4(b) veranschaulicht den Inhalt zu der Zeit, wenn der Punkt J auf der Kurve berechnet wird. Die Koordinatenwerte der ermittelten Mittelpunkte J, I und G werden in den Adressen 1 der Registerfiles 5 - 7 gespeichert. Die Register 2 - 4 löschen den vorhergehenden Inhalt und speichern den Inhalt der Punkte E, H und F. Fig. 4(c) veranschaulicht das Ergebnis einer neuen Berechnung, die auf 4 Kontrollpunkten der Register 1 - 3 und der Adresse 1 des Registerfiles 5 basiert. Der Prozess aus den Fig. 4(b) bis 4(c) ähnelt dem in den Fig. 4(a) bis 4(b) gezeigten, außer dar jeder Zeiger des Registers um eine Einheit hochschaltet. Fig. 4(d) veranschaulicht eine Änderung in dem Inhalt des Registers und des Registerfiles, wenn die Entfernung zwischen dem Punkt Q auf der Kurve, der bei der in Fig. 4(c) gezeigten Stufe ermittelt wurde, und dem Anfangspunkt A kleiner als der vorbestimmte Wert wird. Der in den Registerfiles 5 - 7 bei der in Fig. 4(c) gezeigten Stufe gespeicherte Inhalt wird jeweils auf die Register 1 - 3 übertragen, und jeder Zeiger der Registerfiles 5 - 7 schaltet um eine Einheit runter. Dieser Zustand ähnelt dem in Fig. 4(a) gezeigten Anfangszustand. Fig. 4(e) veranschaulicht den Zustand, in dem der Punkt auf der Kurve durch die Berechnung auf der Basis von in Fig. 4(d) gezeigten Daten ermittelt wird, und der Prozess endet, wenn die berechnete Entfernung kleiner als der vorbestimmte Wert wird. In anderen Worten, wenn der Zeiger sich in dem Zustand "0" befindet und die Entfernung kleiner als der verbestimmte Wert ist, ist der Prozess für alle zu ermittelnden Punkte beendet.
• Als nächstes wird der zeitliche Ablauf von Arbeitsgängen in dem erfindungsgemäßen Kurvengenerator unter Bezugnahme auf Fig. 3 beschrieben. Diese Figur veranschaulicht Eingangsauswahl der Register 1 - 4 und der Registerfiles 5 - 7 und veranschaulicht Speicherstellen der Verarbeitungsergebnisse. Wie in dieser Figur gezeigt wird, wird ein Punkt auf der Kurve während der Laufzeit von 7 Taktsignalen berechnet. Die Abfolge der Berechnung wird mittels der Folgesteuerungsein heit 11 gesteuert. Zuerst wird der Inhalt des Registers 2 in einen b-Seiten-Eingangsanschluß der Verarbeitungseinrichtung 9 eingegeben und der Inhalt des Registers 3 wird in einen a-Seiten-Eingangsanschluß desselben eingegeben, und ihr Ergebnis wird in dem Register 4 gespeichert. Als nächstes wird der Inhalt der Register 1 und 2 jeweils in die a-Seiten- und die b-Seiten-Eingangsanschlüsse der Verarbeitungseinrichtung 9 eingegeben, und ihr Ergebnis wird in dem Register 2 gespeichert. Der gleiche Prozess wird entsprechend auf das folgende angewandt, so daß jeder der in Fig. 1 gezeigten Mittelpunkte berechnet wird. Die Koordinatenwerte des Punkts auf der Kurve werden in dem Registerfile 5 zum Zeitpunkt des sechsten Taktsignals gespeichert. Bei dem Zyklus des siebten Taktsignals wird die Entfernung zwischen dem Anfangspunkt auf der Kurve (gespeichert in dem Register 1) und der anhand desselben berechnete Punkt (gespeichert in dem Registerfile 5) berechnet, und das Ergebnis des Vergleichs zwischen der Entfernung und dem vorbestimmten Wert wird ausgegeben.
• Nun wird der Aufbau der Hardware erläutert, die den oben beschriebenen Arbeitsgang durchführt. Die Register 1 - 4 und die Registerfiles 5 - 7 sind über einen Datenbus 20 oder 21 mit dem a-Seiten- und dem b-Seiteneingangsanschluß der Verarbeitungseinrichtung 9 verbunden, und die Verarbeitungsergebnisse werden durch die Verschiebeeinrichtung 10 und den Datenbus 22 in den Registern und den Registerfiles gespeichert.
• Die Folgesteuerungseinheit 11 steuert eine ganze Prozessabfolge, dieselbe führt nämlich einen im wesentlichen in Fig. 4 gezeigten Steuerfluß des Prozesses aus. Um diesen Fluß auszuführen, generiert die Folgesteuerungseinheit 11 als ein Steuersignal 32 ein Steuersignal, das ein Register oder einen Registerfile auswählt, der Daten aufweist, die in die Verarbeitungseinrichtung 9 eingegeben wurden, oder ein Steuersignal, das ein Register oder einen Registerfile auswählt, um ein Verarbeitungsergebnis zu speichern, und gibt als ein Steuersignal 30 ein Signal aus, das die Art der Arbeitsgänge auswählt, die in der Verarbeitungseinrichtung 9 durchgeführt werden sollen. Die Folgesteuerungseinheit 11 verändert darüberhinaus den Prozess gemäß dem Ergebnis aus dem Entfernungsvergleich. In dem Komparator 13 werden der X-Koordinatenwert und der Y-Koordinatenwert des Inhalts in dem Entfernungsregister 8 unabhängig voneinander mit denen des Ausgangsinhalts aus der Verarbeitungseinrichtung 9 verglichen. Wenn mindestens einer des X-Koordinatenwerts und des Y-Koordinatenwerts des Inhalts in dem Entfernungsregister 8 kleiner ist als die Werte des Ausgangsinhalts aus denselben, ist das Vergleichssignal 34 inaktiv, so dar die Folgesteuerungseinheit 11 den in Fig. 1 gezeigten Fluß fortsetzt. Im gegenteiligen Fall, wenn sowohl der X-Koordinatenwert als auch der Y-Koordinatenwert des Inhalts in dem Entfernungsregister 8 größer als die des Ausgangsinhalts sind, wird das Vergleichssignal 34 aktiv. Dies bedeutet, daß der Inhalt der Registerfiles 5-7 durch die Verarbeitungseinrichtung 9 und die Verschiebeeinrichtung 10 ohne jegliche Datenverarbeitung auf dem Datenbus 22 zu den Registern 1-3 übertragen wird. Die Übertragung endet daher während einer Laufzeit von 3 Taktsignalen. Der Komparator 13 umfaßt die Funktion, die, in dem Fall, daß ein Wert des Verarbeitungsausgangssignals einen negativen Wert aufweist, denselben in den absoluten Wert verändert.
• Nun wird im folgenden die Zeigersteuerung auf Registerfiles erklärt, die in dem Zeiger 12 durchgeführt wird. Es sind Zeiger für Lesen und Schreiben vorhanden, und die Anfangswerte des Lesezeigers und des Schreibzeigers sind "0" bzw. "1". Diese Werte des Lese- und des Schreibzeigers werden über den Zeigerdatenbus 33 an die Registerfiles 5-7 ausgegeben. Der zeitliche Ablauf für Ergänzung des Zeigers 12 ist wie folgt. Zuerst, wenn das Vergleichssignal 34 infolge des Entfernungsvergleichs inaktiv ist, werden sowohl der Lesezeiger als auch der Schreibzeiger um eine Einheit (+1) hochgeschaltet. Im gegenteiligen Fall, wenn das Vergleichssignal 34 aktiv ist, wird der Inhalt der Registerfiles 5-7 zu den Registern 1-3 übertragen, und dann werden sowohl der Lesezeiger als auch der Schreibzeiger um eine Einheit runtergeschaltet (-1).
• Die Folgesteuerungseinheit 11 bestimmt die Beendigung des Prozesses. Die Bedingung für die Beendigung ist, daß das Vergleichssignal 34 aktiv ist und der Lesezeiger "0" ist.
• Wenn diese Bedingung erfüllt ist, hält die Folgesteuerungseinheit 11 an.
• Was die Gradation der Hardware betrifft, sind ein Arbeitsspeicher von einigen zehn Wörtern, zwei Verarbeitungseinrichtungen, eine Folgesteuerungseinheit, Zeiger und so weiter für die Hardware erforderlich, so daß die Hardware bei niedrigen Kosten mittels neuer LSI-Technologie hergestellt werden kann. Die erforderliche Kapazität des Arbeitsspeichers wird in der folgenden Art und Weise ermittelt. Wenn eine Bezier-Kurve von dem linken Ende zu dem rechten Ende auf dem Rahmenspeicher mit einer Auflösung von 1024 x 1024 gezeichnet wird, werden Berechnungen zum Ermitteln der Mittelpunkte zehnmal durchgeführt, und anschließend können die Koordinatenwerte des Punkts auf der Kurve, der sich neben dem linken Endpunkt auf derselben befindet, ermittelt werden&sub1; da 1024 gleich 2¹&sup0; ist. In dieser Auflösung ist es daher für den Arbeitsspeicher ausreichend, die Koordinatenwerte von 10 Mittelpunkten zu speichern. In dieser Auflösung kann eine Berechnung darüberhinaus ohne jeglichen Fehler durchgeführt werden, wenn die Präzision 10 Bits für den integren Teil der Daten und auch 10 Bits für den Dezimalteil derselben ist, nämlich 20-Bit Festkomma. Da ein Fehler hinter dem Dezimalkomma jedoch zu einem gewissen Maße ignoriert werden kann, ist die Präzision von 16-Bit Festkomma für den praktischen Gebrauch noch tragbar.
• Fig. 5 zeigt ein Blockschaltbild einer zweiten erfindungsgemäßen Ausführungsform. Bei dieser Ausführungsform wird in der Hardware ein RAM (random access memory - Speicher mit wahlfreiem Zugriff) verwendet, um die in der ersten Ausführungsform verwendeten Register und Registerfiles zu integrieren und um die Kosten zu senken. Da die für einen RAM-Aufbau notwendige Fläche als ein Speicherelement kleiner als die für eine Gruppe von einzelnen Registern ist, das die gleiche Kapazität aufweist, können die Kosten für den Datenspeicheranteil umfassend gesenkt werden. Da jedoch eine Vielzahl von Elementen in dem selben Speicher integriert sind, sollte die Steuerung zum Abrufen eines Inhalts von jedem Element in gewissem Maße verändert werden. Der Unterschied zwischen dieser Ausführungsform und der ersten liegt in einer Zugriffssteuerung auf den RAM, so daß nur dieser Unterschied im folgenden erklärt wird.
• Fig. 5 veranschaulicht RAM 40 und 41, einen Basiszeigerbus 42, ein Steuersignal 43 eines RAM, ein Entfernungsregister 8, eine Verarbeitungseinrichtung 9, eine Folgesteuerungsein heit 11, einen Zeiger 12, einen Komparator 13, Datenbusse 20-24, ein Verarbeitungssignal 30, ein Zeigersteuersignal 31, einen Zeigerdatenbus 33 und ein Vergleichssignal 34.
• Der RAM 40 entspricht der Kombination der in Fig. 2 gezeigten Register 1, 3, 4. Was ein Eingangssignal zu dem a-Seiteneingangsanschluß der Verarbeitungseinrichtung 9 in der ersten Ausführungsform betrifft, gibt die Folgesteuerungs einheit 11 das individuelle Auswahlsignal als das Registersteuersignal 32 an die Register aus. Die Folgesteuerungsein heit 11 der zweiten Ausführungsform verwendet jedoch eine Adresssteuerung durch Anwenden eines RAM-Aufbaus. Die Folgesteuerungseinheit 11 gibt nämlich an Stelle des Registersteuersignals eine RAM-Adresse als ein RAM-Steuersignal aus.
• Andererseits unterscheidet sich die Steuerung auf dem RAM 41, die ein Eingangssignal in den b-Seiteneingangsanschluß der Verarbeitungseinrichtung 9 eingibt, in einem gewissen Maße von der auf dem RAM 40. Die Kombination von einem durch den Zeiger 12 generierten Zeiger und einem durch die Folgesteuerungseinheit 11 ausgegebenen Basiszeiger wird für eine Adresse des RAM 41 verwendet. Aus diesem Grunde wird eine Adresse von 6 Bits, die sowohl Zeigerinformation von 4 Bits durch den Zeigerdatenbus 33 als auch durch den Basiszeigerbus 42 ausgegebene Basiszeigerinformation von 2 Bits umfaßt, in den RAM 41 eingegeben.
• Bei der zweiten Ausführungsform wird mit Koordinatenwerten mittels eines 16-Bit Festkommas verfahren. Die vorliegende Erfindung ist jedoch nicht auf dieses Bitkomma begrenzt. Gemäß der vorliegenden Erfindung kann der Prozess auch in dem Fall, daß die Kurve keine Bezier-Kurve der dritten Ordnung ist, mit hoher Geschwindigkeit durchgeführt werden, wenn die Kurve auf der Grundlage von Berechnung von Mittelpunkten generiert wird. Der Unterschied zwischen dem Fall einer Bezier-Kurve der zweiten, vierten oder höheren Ordnung zum Beispiel und dem der Kurve der dritten Ordnung besteht nur in der Anzahl von Mittelpunkten, die durch Berechnung zu ermitteln sind. In Spline-Kurven ist es bekannt, daß diese Kurve an eine Bezier-Kurve mittels eines Vorprozesses angenähert werden kann, der einen gegebenen Kontrollpunkt auf einer Spline-Kurve in den auf einer Bezier-Kurve umwandelt. Aus diesem Grunde kann die vorliegende Erfindung auch auf solche Spline-Kurven angewandt werden.
• Was den Speicherbereich betrifft, in dem Kontrollpunkte und Mittelpunkte gespeichert werden, kann der Bereich, wie bei der ersten Ausführungsform erklärt, auf eine Vielzahl von Registern verteilt werden oder auf einen einzelnen Speicher, wobei die wie bei der zweiten Ausführungsform gezeigte Zeigersteuerung verwendet werden kann. In jedem Fall birgt die vorliegende Erfindung den Vorteil, daß die Änderung von Kontrollpunkten leicht durchgeführt werden kann und die Abfolge des Prozesses einfacher wird.
• Wie oben erwähnt, bestehen die Vorteile der vorliegenden Erfindung darin, daß es möglich ist, die Verarbeitungszeit zu erhalten, die zehnmal schneller als die Geschwindigkeit des durch Software durchgeführten Prozesses ist und aufgrund des einfachen Aufbaus in der Hardware eine Reduzierung der Kosten zu erzielen.
• Während die vorliegende Erfindung in ihren bevorzugten Ausführungsformen beschrieben wurde, sollte zur Kenntnis genommen werden, daß die Wörter, die verwendet wurden, eher Wörter der Beschreibung als der Begrenzung sind und daß Veränderungen an der Erfindung durchgeführt werden können, ohne von dem durch die folgenden Patentansprüche definierten Umfang derselben abzuweichen.

Claims (4)

1. Kurvengenerator, der für eine Kurve in der Nähe einer Vielzahl bestimmter Kontrollpunkte durch Berechnen von Koordinatenwerten von Mittelpunkten zwischen den Kontrollpunkten auf der Basis von Koordinatenwerten der Kontrollpunkte interpoliert, dadurch gekennzeichnet, daß der Kurvengenerator aufweist:

ein erstes Speichermittel (1-4), das, nachdem die Vielzahl von Kontrollpunkten und die Mittelpunkte in zwei Gruppen geteilt worden sind, eine Gruppe der Koordinatenwerte der Vielzahl von Kontrollpunkten und der Mittelpunkte speichert;

ein zweites Speichermittel (5-7), das die andere Gruppe der Koordinatenwerte der Mittelpunkte speichert und einen Zeiger (12) aufweist, der eine Adresssteuerung ausführt;

ein Operationsmittel (9), das Koordinatenwerte eines Mittelpunktes zwischen vorbestimmten zwei Punkten berechnet, deren Koordinatenwerte in wenigstens einem der ersten und zweiten Speichermittel gespeichert sind, und bewirkt, daß der berechnete Koordinatenwert des Mittelpunktes in einem der ersten und zweiten Speichermittel (1-4; 5-7) gespeichert wird;

einen Komparator (13), der eine Entfernung zwischen den Kontrollpunkten berechnet und diese Entfernung mit einem vorbestimmten Wert vergleicht; und

ein Mittel (11), das ein Ausgangssignal des Komparators (13) empfängt, welches Mittel den Zeiger (12) hochschaltet, wenn die Entfernung größer ist als der vorbestimmte Wert, aus dem zweiten Speichermittel ausgelesene Koordinatenwerte zum ersten Speichermittel überträgt und auch den Zeiger runterschaltet, wenn die Entfernung kleiner ist als dieser Wert.

2. Kurvengenerator nach Anspruch 1, bei dem das erste Speichermittel ein Register (1-4) aufweist und das zweite Speichermittel ein Registerfile (5-7) aufweist.

3. Kurvengenerator nach Anspruch 1, bei dem jedes der ersten und zweiten Speichermittel (1-4; 5-7) einen Speicher mit wahlfreiem Zugriff (40;41) aufweist.

4. Kurvengenerator nach Anspruch 1, bei dem das Mittel, das ein Ausgangssignal des Komparators empfängt, eine Folgesteuerungseinheit (11) ist.