DE3407983C2 - Mehrprozessorrechnersystem zum Erzeugen von Bildpunktinformationen aus in einer hierarchischen Datenstruktur definierten Objektelementen - Google Patents

Description

Die Erfindung betrifft ein Mehrprozessorrechnersystem zum Erzeugen von Bildpunktinformationen gemäß dem Oberbegriff des Anspruchs 1.

Als allgemeiner Stand der Technik sei das Buch von W.M. Newman und R.F. Sproull "Principles of interactive computer graphics", ISBN 0-07-0463387-7, McGraw Hill, 1981 genannt. Dieses Buch beschreibt u. a. auf Seiten 137 . . . 142 verschieden organisierte Datenstrukturen und in Fig. 10-11 eine hierarchische Datenstruktur. Weiter zeigt Seite 421, Fig. 26-4 ein Mehrprozessorsystem der eingangs genannten Art. u. a. mit einem Zentralprozessor, einem Matrixprodukt­ bild und einem Abbildungsprozessor. Anhang I, Seiten 481 . . . 489, gibt eine Übersicht über Vektoren und Matrizen. Die Seiten 315 . . . 320 geben die Bildung und die Verwendung sog. Bezieher-Kurven an, die nachstehend näher erläutert werden. Unter Objektelementen seien quantitative Modelle räumlicher oder flacher Entitäten wie Flächen, Körper und kompliziertere Strukturen verstanden. Diese Objektelemente werden nachstehend anhand der Fig. 1a . . . 1e näher erläutert. Der Vorteil einer hierarchischen Struktur ist die einfache Modifizierbarkeit eines auf einem niedrigen Pegel der hierarchischen Struktur liegenden Objektelements, ohne daß die Struktur als Ganzes geändert wird, und häufig auch in der mehrfachen Verwendungs­ möglichkeit von Objektelementen auf einem höheren Pegel, die auf einem niedrigeren Pegel definiert sind. Letzteres gilt insbesondere für eine zweidimensionale Situation, weil bei der Visualisierung dieser Situation ausschließ­ lich lineare Transformationen auftreten. Der Haupt­ prozessor liefert nunmehr Räumlichkeitsbeziehungen zwischen den Objektelementen, wie relative oder absolute Positionen. Auch kann der Hauptprozessor neue Objekt­ elemente liefern oder bestehende Elemente entfernen. Es ist nach der bekannten Technik häufig ein Problem, daß erst zu bestimmen ist, welcher Teil der Objektelemente in den Abbildungsrahmen fällt, das sog. "clippen". Es wird sich zeigen, daß nach den nachstehend zu beschreibenden Vorgängen dies erst am Ende der Behandlung des betreffen­ den Punkts bestimmt wird, wobei der betreffende Punkt vorübergehend als das Zentrum eines Koordinatensystems betrachtet wird. In einem einfachen Fall kann die Bildpunkt­ erzeugung synchron mit der Darstellung des Bilds im Dar­ stellungselement erfolgen. Das Darstellungselement kann beispielsweise auf der Basis einer zeilenweise darstellen­ den Fernsehröhre arbeiten; es kann jedoch auch eine Matrix mehrfarbiger LED- oder Plasma-Elemente oder einen Tinten­ strahldrucker betreffen. Die Erfindung beschränkt sich auf vollständig seriell darstellende Darstellungselemente, wobei für jeden Bildpunkt die Entscheidung "Farbe" oder "keine Farbe" zu treffen ist, wenn der betreffende Bild­ punkt an der Reihe ist. Die Erfindung bezieht sich ins­ besondere nicht auf sog. vektorgeformte Bilder, die ganz aus geschriebenen Vektorlinien bestehen und wobei die Reihenfolge der Abtastung der Bildpunkte auf wahlfreie Weise erfolgen kann.

Der Erfindung liegt die Aufgabe zugrunde, eine schnelle Bildpunkterzeugung mit einer Anordnung einfacher Prozessoren zu schaffen, ohne daß ein besonders intensiver Verkehr zwischen dem Hauptprozessor und der Anordnung von Prozessoren bzw. gegenseitig zwischen den Prozessoren erforderlich ist.

Die Aufgabe wird bei dem eingangs angegebenen Mehr­ prozessorrechnersystem erfindungsgemäß durch die im kenn­ zeichnenden Teil des Anspruchs 1 angegebenen Merkmale gelöst.

Der Erfindung liegt die Erkenntnis zugrunde, daß es vor­ teilhaft ist, je Bildpunkt jeweils gleichartige und ein­ fache Berechnungen zu wiederholen, wozu dabei weniger komplizierte und andererseits spezifischere und also schnellere Bausteine verwendet werden können. Außerdem wird die Bearbeitung vom höchsten Pegel der hierarchischen Datenstruktur angefangen; es zeigt sich, daß bei dieser Bearbeitungsrichtung eine einfache Struktur in den Bearbeitungen entsteht. Obiges ist um so verständlicher, da jeder Punktprozessor nur auf eine Gruppe von Bild­ punkten des Gesamtbildes einwirkt, so daß die Paralleli­ sierung zu einem weit fortgeschrittenen Stadium verwirk­ licht und dadurch auch die Verarbeitungsgeschwindigkeit erhöht wird.

Vorteilhafte Ausgestaltungen der Erfindung sind in den Unteransprüchen gekennzeichnet. Dabei ist die Aufteilung der Menge der Punktprozessoren und die Verwendung der Hilfsspeicher besonders günstig. Dadurch wird die Paralle­ lisierung gleichsam in zwei Pegeln durchgeführt, wodurch bei begrenztem Aufwand dennoch eine weitgehende Beschleu­ nigung bewirkt wird. Der von jedem Punktprozessor zu bearbeitende Teil der hierarchischen Datenstruktur ist jetzt begrenzt, so daß die Verarbeitungsgeschwindigkeit der Punktprozessoren stark ansteigt. Durch den begrenzten Umfang des zu bearbeitenden Teils der Datenstruktur kann dies auch ohne Bedenken multipliziert werden: Ein bestimmtes Objektelement kann gleichzeitig in mehreren Hilfsspeichern vorhanden sein. Durch die Einführung von Hilfsspeichern braucht jeder Punktprozessor nur noch selten einen Zugriff auf den Empfangsspeicher auszuführen. Konkurrierende und unvorhersagbare Lesevorgänge von den Punktprozessoren im Empfangsspeicher werden hierdurch vermieden. Auch bedürfen die Punktprozessoren unter­ einander keiner Kommunikation, wodurch die Struktur der Informationsversorgung einfach wird: Es gibt beispiels­ weise keine Unterbrechungsmechanismen zwischen den Punkt­ prozessoren und auch kein Schiedsgericht zwischen ver­ schiedenen Benutzern und mögliche gegenseitige Sperrung zwischen verschiedenen Benutzern.

Durch die Verwendung eines doppelten Bildpufferspeichers ist es möglich, einem Betrachter eine kontinuierliche Abbildung zu geben, weil ein einmal gespeichertes Bild einige Male abgetastet werden kann. Flimmereffekte und derartiges werden dabei vermieden.

Ferner braucht die Verarbeitung der Prioritätsangaben und die Vergleichsprüfung in den Prioritätsprozessoren erst aktiviert zu werden, wenn in den Struktur/Polygon­ prozessoren eine Überlappung zwischen zwei elementaren Objektelementen detektiert wird. Außerdem werden hierbei keine Beschränkungen auferlegt in dem Sinne, daß keine konkaven Polygone oder zum anderen keine einander schneidenden Polygone auftreten dürfen.

Die Erfindung ermöglicht mit einfachen Mitteln bisher schwer zu verwirklichende, punktgerichtete Bearbeitungen in der Praxis, wie beispielweise die Kombination (Mischung) verschiedener Farben nach einer Prioritäts­ vorschrift. In einer zweidimensionalen Situation braucht die Priorität nicht mehr von einer Reihenfolgedefinition bestimmt zu sein, sondern kann unabhängig für jedes elementare Objektelement gewählt werden. In einer drei­ dimensionalen Situation sind keine schwer zu implemen­ tierenden Sortierungsalgorithmen zwischen den Objekt­ elementen insgesamt notwendig, sondern die Prioritäten können von einer punktweise organisierten Berechnung einfach abgeleitet werden. Weiter lassen sich Gegenaliasing- Algorithmen durch Betrachtung einer örtlichen Gruppe von Bildpunkten verwirklichen.

Beschreibung der Ausführungsbeispiele

Die Erfindung wird in Teilen beschrieben, und zwar nach­ einander die hierarchische Datenstruktur der Objektele­ mente die aufeinanderfolgenden phänomenologischen Bearbei­ tungen an diesen Objektelementen, eine allgemeine Beschreibung des Rechnersystems, die Bearbeitungen im Reduktionsprozessor, die Bearbeitungen im Polygon­ prozessor, die Verwirklichung eines Polygonprozessors und Ergänzungen für eine dreidimensionale Situation. Dabei wird das Darstellungselement auch als Abbildungselement bezeichnet.

Es zeigen

Fig. 1a einige Beispiele von geraden Linien begrenz­ ter elementarer Objektelemente,

Fig. 1b-1e Details über die Bildung sog. Bezier- Polygone, deren Seiten durch Bezier-Kurven höherer Ordnung gebildet sein können,

Fig. 2 ein Beispiel eines Abzweigs aus einer hierar­ chischen Datenstruktur von Objektelementen,

Fig. 3 ein erweitertes Beispiel einer hierarchischen Datenstruktur,

Fig. 4 ein symbolisches Schema einer Mehrprozessor­ systems,

Fig. 5 die Organisation eines abzubildenden Bildes in einem zweidimensionalen Abbildungsraum,

Fig. 6 ein detaillierteres Schema eines Mehrprozes­ sorsystems,

Fig. 7a, 7b Flußdiagramme zum Wählen von Objekt­ elementen in einem Reduktionsprozessor,

Fig. 8 ein Programm für die Bearbeitung in einem Polygonprozessor,

Fig. 9a, 9b dabei einige Formeln in Figurform,

Fig. 10a-10f einige Möglichkeiten beim Programm nach Fig. 8,

Fig. 11 ein Blockschaltbild eines Polygonprozessors für aus geraden Linien aufgebauten Bezier-Polygone,

Fig. 12 ein Blockschaltbild eines Polygonprozessors für Bezier-Polygone, deren Seiten von Bezier-Kurven höchstens dritter Ordnung gebildet werden.

Objektelemente und Datenstruktur

In Fig. 1 sind einige Beispiele elementarer, aus geraden Linien aufgebauter Objektelemente dargestellt:

Der Einfachheit halber wird zunächst ein planarer Zustand beschrieben. Das Element 30 ist ein konvexes Polygon, das in die Datenstruktur als eine Kette von Daten aufgenommen werden kann, die nacheinander folgende Informationen enthält: den Namen des Objekts in Form eines Identifikators, der auch die Anzahl der Eckpunkte gibt, in diesem Fall also "sechs", anschließend eine Reihe von sieben Eckpunkt­ informationen, und zwar nacheinander den Starteckpunkt, den beim Einhalten des Uhrzeigersinns (rechtsherum oder dagegen linksherum) nächsten Eckpunkt und die aufeinanderfolgenden weiteren Eckpunkte, bis der Starteckpunkt als letzter zum zweiten Mal auftritt. Jeder Eckpunkt wird durch seine rela­ tiven Koordinaten in bezug auf einen Referenzpunkt im Objektelement bestimmt, in dem das betreffende elementare Objektelement verbunden ist. Die Art der Informations­ speicherung auf Systempegel im Ursprungsspeicher, beispiels­ weise nach einer Segmentorganisation, ist für die Erfindung nicht spezifisch und wird nicht näher erläutert. Durch die Schraffierung ist angegeben, daß das betreffende Vieleck ein Innengebiet mit einer bestimmten Farbe besitzt. Dabei kann das Außengebiet entweder farblos sein oder eine andere Farbe besitzen. In diesem letzten Fall kann auch gerade das Innengebiet des Polygons die Hintergrundfarbe besitzen. Der Umfang des Polygons wird im Ausführungsbei­ spiel zum Innengebiet gerechnet. An sich ist diese Wahl beliebig. Weiter enthält die Information des betreffenden Polygons noch eine Prioritätsinformation. Wenn zwei Polygone einen Punkt im Innengebiet gemeinsam haben, kann das Polygon mit niedriger Priorität von einem Polygon mit höherer Priori­ tät abgedeckt werden. Es ist jedoch auch möglich, daß eine Mischfarbe entsteht. Es sei darauf hingewiesen, daß nur zwei Farben für das betreffende Polygon relevant sind und daß keine Linien mit gleichsam unendlich kleiner Breite auftreten. Wenn in einem Bild eine Linie angegeben werden muß, wird diese Linie als ein schmales Polygon verwirklicht. Dies bietet den Vorteil, daß bei fortschreitender Maßstab­ verringerung die betreffende Linie automatisch immer dünner wird und schließlich durch Unterabtastung verschwindet, ohne daß ein zusätzlicher Algorithmus für die Behandlung von (Konturen-)Linien erforderlich ist.

Das Element 32 ist auf entsprechende Weise ein Polygon mit acht Ecken und teilweise konkav. Im übrigen gilt das selbe wie hinsichtlich des Elements 30 bemerkt.

Das Element 31 ist eine andere Art von Polygon. Dies kann einerseits als ein Sechseck mit zwei zusammen­ fallenden Eckpunkten bezeichnet sein; dies wird dann auf die gleiche Weise wie die bereits erwähnten Polygone be­ handelt. Zum anderen kann das betreffende Polygon auch als ein Viereck bezeichnet sein, dessen zwei Seiten einander schneiden. Stets bekommt jetzt das Innengebiet einschließ­ lich der Kontur eine andere Farbe als das Außengebiet.

Auf entsprechende Weise kann das Element 33 als ein Fünfeck bezeichnet sein; wie angegeben, ist ein Teil des umschlossenen Gebiets als Nichtinnengebiet dadurch definiert, daß keine Schraffierung dargestellt ist. Gleiches ist beim Element 35 erfolgt. Es ist klar, daß durch einen anderen Algorithmus als der, der in der bevor­ zugten Ausführungsform eingeschlossen ist, auch andere Verabredungen zum Färben derartiger komplizierter Polygone möglich sind. Insbesondere kann die Kontur eines Polygons die Hintergrundfarbe bekommen.

In Fig. 1b . . . 1e sind Details über die Bildung sog. Bezier-Polygone dargestellt, deren Seiten durch Bezier- Kurven höherer Ordnung gebildet sein können. In Fig. 1b ist die Formel derartiger Bezier-Kurven dargestellt, nähere Einzelheiten über das phänomenologische Verhalten dieser Kurven sind in der bereits genannten Literaturstelle ent­ halten. Eine Bezier-Kurve der Ordnung n = 1 ist eine Gerade zwischen den Punkten p0 und p1, die als Endpunkte wirken. In der hier benutzten Begriffsbestimmung sind dies die beschreibenden Punkte dieses Linienabschnitts. Die dritten und vierten Zeilen geben Bezier-Kurven der zweiten bzw. der dritten Ordnung an. Auf der dritten Zeile sind p0 und p2 die Endpunkte einer Parabel, der Punkt p1 liegt nicht auf der Parabel. Auf der vierten Zeile sind p0 und p3 die Endpunkte der Kurve, die Punkte p1 und p2 liegen nicht auf der Kurve. Die Linienabschnitte, die die Endpunkte mit dem folgenden/vorangehenden Punkt verbinden, berühren die Kurve. Es hat sich gezeigt, daß mit den gegebenen Fällen eine große Anzahl von Möglichkeiten verwirklichbar ist.

Fig. 1c zeigt die Bildung einer Bezier-Kurve der ersten Ordnung. Die zwei beschreibenden Punkte sind 300 und 302. Der Linienabschnitt wird vom Punkt 304 in zwei gleiche Teile unterteilt. Die Hälften werden in zwei gleiche Teile von den Punkten 306 bzw. 308 unterteilt. Fig. 1d zeigt die Bildung einer Bezier-Kurve der zweiten Ordnung. Die drei beschreibenden Punkte sind 310, 312 und 314; also bestimmen diese drei Punkte zwei Bezier-Kurven der ersten Ordnung.

Die jeweiligen Linienabschnitte werden von den Punkten 316 und 318 in jeweils zwei gleiche Teile unterteilt. Der von letztgenannten Punkten gebildete Linienabschnitt wird vom Punkt 320 in zwei gleiche Teile unterteilt. Dies läßt sich dadurch beweisen, daß dieser letzte Punkt ein Punkt der betreffenden Bezier-Kurve der zweiten Ordnung ist. Durch die Wiederholung der betreffenden Bearbeitungen kann eine Reihe von Punkten bestimmt werden, die die betreffende Bezier-Kurve in jeweils kleinere Abschnitte unterteilen:

Die Punkte 310, 316 und 320 bilden nämlich die beschrei­ benden Punkte einer Bezier-Kurve, die mit der Bezier-Kurve zusammenfällt, die die Punkte 310, 314 und 312 bestimmen. Fig. 1e zeigt die Bildung einer Bezier-Kurve der dritten Ordnung. Die vier beschreibenden Punkte sind 322, 324, 326 und 328. Die von aufeinanderfolgenden Paaren beschreibender Punkte bestimmten Linienabschnitte werden von den jeweiligen Punkten 330, 332, 334 in zwei gleiche Teile unterteilt. Dieser Vorgang wird von den Punkten 336 und 338 wiederholt. Der von den letzten zwei Punkten beschriebene Linienab­ schnitt wird vom Punkt 340 in zwei gleiche Teile unterteilt. Dies läßt sich dadurch beweisen, daß der letztgenannte Punkt wieder ein Punkt der betreffenden Bezier-Kurve der dritten Ordnung ist und auch dadurch, daß die von den Punktreihen 322, 330, 336, 340 bzw. 340, 338, 334, 328 bestimmten Bezier-Kurven zusammen gleich der von der Punkt­ reihe 322, 324, 326, 328 bestimmten Bezier-Kurve sind. Die Halbierungspunkte der Bezier-Kurven, also in den dar­ gestellten Fällen die Punkte 304, 306, 308, 320 bzw. 340 werden im weiter unten zu erläuternden Polygonprozessor zur Durchführung einer iterativen Bearbeitung benutzt. Aus den beschriebenen Polygonseiten können flache Figuren gebildet werden. Nach dem Vorbild dieser klassischen Polygone nach Fig. 1a werden sie Bezier-Polygone genannt. Diese können also aus Bezier-Kurven untereinander verschiedener Ordnung aufgebaut sein.

Ein Linienabschnitt nach Fig. 1c diagonalisiert ein Parallelogramm, das weiter vollständig bestimmt ist, wenn die Richtungen der Seiten gegeben sind. Auf gleiche Weise erzeugen die beschreibenden Punkte einer Bezier-Kurve nach Fig. 1d/e ebenfalls ein Parallelogramm, wenn die Rich­ tungen der Seiten gegeben sind: Dieses Parallelogramm ist das kleinste, das alle beschreibenden Punkte der betref­ fenden Bezier-Kurve enthält. Dies wird mit erzeugtem Paral­ lelogramm bezeichnet. Es ist einfach ersichtlich, daß alle Punkte einer Bezier-Kurve in dem von ihren beschreibenden Punkten erzeugten Parallelogramm liegen. Beim Spezifizieren einer Polygonseite von den beschreibenden Punkten wird jeweils die Ordnung der Kurve im Empfangsspeicher mitspezi­ fiziert. Es sei darauf hingewiesen, daß die Form der Kurven auch von der Reihenfolge der beschreibenden Punkte abhängig ist. Aus einer Verkettung einer Anzahl von Bezier- Kurven kann ein Bezier-Polygon gebildet werden, wie aus einer Verkettung gerader Linienabschnitte ein herkömmliches Polygon. In der nachstehend beschriebenen bevorzugten Aus­ führungsform wird gefordert, daß die Bezier-Kurven in bezug auf beide Koordinatenrichtungen einen monotonen Verlauf haben. Wenn dies nicht der Fall ist, läßt sich eine Kurve in Abschnitte verteilen, die je die Bedingungen erfüllen. Eine Bezier-Kurve mit höchstens vier beschreibenden Punkten erfüllt die Bedingung, daß alle beschreibenden Punkte in dem von den Endpunkten erzeugten Rechteck liegen. Dies vereinfacht den Algorithmus. Die herangezogene Literatur­ stelle gibt weiter die Bildung möglicherweise gekrümmter Oberflächen gemäß der Beschreibung von zwei Bezier-Polygon­ vorräten.

Die Objektelemente können Räumlichkeitsbeziehungen (relativen Transformationen) unterworfen sein. Sie gelten in einer zweidimensionalen Situation beispielsweise in bezug auf ein Referenzachskreuz:

• - Translation;
• - Rotation;
• - Maßstabänderung (Vergrößerung oder Verkleinerung);
• - Spiegelung in bezug auf einen Punkt oder einer Geraden.

In Fig. 2 ist ein Beispiel eines Abzweigs einer hierarchischen Datenstruktur von Objektelementen darge­ stellt. Die Darstellung eines jeden Pegels ist symbolisch. Der niedrigste Pegel 36 enthält auf der linken Seite als Objektelement ein gleichschenkliges Dreieck, das als die bereits erwähnte Kette von Eckpunkten gegeben ist. Auf der rechten Seite enthält dieses Objektelement als zusätzliche Information ein umschriebenes Rechteck (bounding box, hier ein Viereck) des gleichschenkligen Dreiecks, das beispiels­ weise als x-Koordinaten und y-Koordinaten der Rechteck­ seiten in bezug auf das Koordinatensystem des Objektelements der nächsthöheren Ordnung gegeben ist, in der es verbunden ist. Das betreffende Rechteck ist nicht einmalig für das Dreieck, denn jede relative Orientation ergibt ein eigenes umschriebenes Rechteck. Es ist nicht notwendig, daß für eine bestimmte Orientierung die kleinste Figur genommen wird, aber dies erspart im allgemeinen einige Rechenzeit. Insbe­ sondere könnte, wenn die Seiten von Bezier-Kurven höherer Ordnung gebildet werden, ein "zu großes" umschriebenes Rechteck benutzt werden. Die Speicherung des elementaren Objektelements kann wieder auf herkömmliche Weise erfolgen. Die Lage des gleichschenkligen Dreiecks im umschriebenen Rechteck ist punktiert angegeben, während das Rechteck gestrichelt dargestellt ist.

Auf dem nächsthöheren hierarchischen Pegel 38 ist das gleichschenklige Dreieck des Pegels 36 mit einer haken­ förmigen Struktur kombiniert, d. h. also ein Polygon mit sehr schmalen Teilen, von denen die Schraffierung nicht dar­ gestellt ist. Diese hakenförmige Struktur ist hier nicht als Teil eines niedrigeren hierarchischen Pegels angegeben. Rechts ist diese Kombination wieder im zugeordneten um­ schriebenen Rechteck (hier wiederum ein Viereck) darge­ stellt. Die Kombination der zwei Elementarobjektelemente läßt sich wieder durch Räumlichkeitsbeziehungen verwirkli­ chen, wie bereits beschrieben wurde. Das umschriebene Recht­ eck der Kombination läßt sich auf elementare Weise bestimmen.

Auf dem nächsthöheren Pegel 40 wird das dargestellte Objektelement des Pegels 38 wieder mit einem Polygon (Fünf­ eck) kombiniert, auch ist ein umschriebenes Rechteck ge­ strichelt dargestellt. In der Datenstruktur sind die Zu­ sammenhänge zwischen den Objektelementen beispielsweise durch Adressenanzeiger im Empfangsspeicher gegeben.

In Fig. 3 ist ein zweites Beispiel einer hierarchi­ schen Datenstruktur von Objektelementen dargestellt. Auf einem überwölbenden Pegel stellt die Raute 66 mit zugeord­ netem umschriebenen Rechteck 42 eine zweidimensionale Zusammenhangstruktur dar; auf den niedrigeren Pegeln sind nur die jeweiligen umschriebenen Rechtecke 44 . . . 64 numeriert und die möglicherweise elementaren Objektelemente nur durch nicht-numerierte Rauten dargestellt. Auf dem nächstniedrige­ ren Pegel besteht die Zusammenhangstruktur aus drei Objekt­ elementen (44, 46, 48). Auf dem dritten Pegel in der Figur besteht das Objektelement 46 aus zusammenstellenden Objekt­ elementen 50 und 52 und das Objektelement 48 aus den Objekt­ elementen 54 und 56. Auf dem vierten Pegel in der Figur besteht das Objektelement 44 aus Objektelementen 58 und 60, das Objektelement 52 aus dem Objektelement 60 und das Objektelement 54 aus den Objektelementen 62 und 64. Die Objektelemente 50 und 56-64 können als elementar betrachtet werden. An sich ist der möglicherweise elementare Zustand eines Objektelements nur durch seine Lage in der hierarchi­ schen Datenstruktur bestimmt, insbesondere wenn in bezug auf dieses Objektelement kein niedrigerer Pegel vorhanden ist. In einer bevorzugten Ausführungsform enthält die Datenstruktur zwei Arten von Unterteilen: erstens gibt es die eigentlichen Objektelemente, und zweitens gibt es sog. Aufrufe: Ein Aufruf gibt die Transformation zwischen dem Referenzrahmen des aufrufenden oder höheren Objektelements und dem aufgerufenen oder niedrigeren Objektelement an.

Nur für die Elementarobjektelemente ist dabei kein Aufruf vorgesehen, weil vorgesehen ist, daß auf diesem niedrig­ sten Pegel die Zusammenhänge meist unveränderlich sind; dies ist also etwas anderes als in Fig. 2, in der auch zwischen den niedrigsten zwei Pegeln Rotation und Maßstab­ änderung auftritt. Der Einfachheit halber werden nach­ stehend die Aufrufe als Teile des niedrigeren Objektelements betrachtet. Der Sinn der genannten Trennung zwischen Auf­ rufen und Objektelementen liegt in der Vereinfachung der mehrfachen Verwendung von Objektelementen.

Allgemeine Beschreibung des Rechnersystems

Die Bearbeitungen an den Objektelementen werden anhand der Fig. 4 beschrieben, die mehr oder weniger symbo­ lisch das Mehrprozessorsystem darstellt. Der Block 68 ist ein Speicher mit wahlfreiem Zugriff, in dem sich die hierar­ chische Datenstruktur befindet, d. h. in einer dreidimensio­ nalen Lage. Zum Beispiel bei einem Flugsimulator für Piloten gibt dieser Zusammenhang die räumliche "Wirklichkeit" an. Eine einfache Situation tritt oft bei "Entwerfen mit Rechner­ hilfe" auf (CAD). Dabei ist oft die perspektivische Ver­ zeichnung vernachlässigbar und wird eine Parallelprojektion benutzt, im Gegensatz zur sogenannten zentralen Projektion perspektivischer Systeme. Der Block 70, der in einem Rechner implementiert ist, symbolisiert die Transformation der Datenstruktur nach einem visuellen Zentrum, wobei die Projektionsart noch nicht berücksichtigt wird. Die Trans­ formationen bestimmen also die relative Lage des betreffen­ den Objektelements in bezug auf das visuelle Zentrum und werden daher ausgedrückt im zugeordneten Augenkoordinaten­ system. Ggf. kann die betreffende Anordnung einen Teil des Hauptprozessors bilden. Im Block 72 wird die Reduktion von der dreidimensionalen zur zweidimensionalen Situation verwirklicht. Auch der Block 72 ist in einem Rechner imple­ mentiert. Darin wird insbesondere die Projektion des Objekt­ elements bestimmt, das Punkt für Punkt direkt aus den Transformationsgleichungen gegeben ist: x(p) - X′′/Z′′, und y(p) = Y′′/Z′′, worin der Doppelakzent die Koordinaten im Augenkoordinatensystem angibt. Diese Projektion wird nun­ mehr als (ein Teil einer) eine zweidimensionale Zusammen­ hangstruktur in den Speicher mit wahlfreiem Zugriff 74 eingeschrieben. I_n zweidimensionalen Fällen, beispielsweise wenn das beschriebene System beim Entwerfen integrierter Schaltungen benutzt wird, enthält dieser Speicher 74 direkt die zweidimensionale hierarchische Datenstruktur der Objekt­ elemente und können die Blöcke 68, 70 und 72 also entfallen. An sich können die Blöcke 68 . . . 72 Teile des Hauptprozessors sein.

Der Block 76 stellt einen Reduktionsprozessor dar, dessen Wirkungsweise näher erläutert wird. Der Block 78 ist eine Anordnung von Punktprozessoren, die mit Hilfe einer nur als eine Linienabzweigung angegebenen Demultiplexer­ struktur an den Reduktionsprozessor 76 angeschlossen sind. In diesem einfachen Beispiel sind nur vier Punktprozessoren dargestellt. Der Punktprozessor 80 besteht aus einem Spei­ cher 88 und dem eigentlichen Prozessor 90. Die Eingabe/- Ausgabesteuerung des Prozessors 80 und eine mögliche Bus­ struktur dafür sind der Einfachheit halber nicht dargestellt.

In Fig. 5 ist die Organisation eines Bilds in einem zweidimensionalen Abbildungsraum dargestellt. Das Fach 100 gibt das Koordinatengebiet an, in dem die überwölbende Zusammenhangstruktur der Objektelemente definiert ist. Das Fach 102 gibt das Koordinatengebiet an, das davon abge­ bildet werden muß. Der Einfachheit halber sind die Haupt­ richtungen der Fächer 100 und 102 entsprechend gewählt. Es sei angenommen, daß das Abbildungselement eine Fernseh­ röhre mit Rasterdarstellung ist, wobei die Zeilenrichtung im Bild horizontal ausgerichtet ist. Das Fach 102 enthält acht Teilfächer 104 . . . 118, die Unterteilung des weiteren Bereichs ist dargestellt, jedoch nicht numeriert.

Der Reduktionsprozessor 76 führt jetzt folgende Reduktion durch. Wenn beispielsweise die Farbinformation des Teilfachs 104 zu berechnen ist, wird vom höchsten Pegel der hierarchischen Datenstruktur ausgehend von allen Objektelementen untersucht, ob das umschriebene Rechteck des betreffenden Objektelements einen Punkt mit dem betref­ fenden Teilfach gemeinsam hat. Nur wenn dies so ist, werden vom betreffenden Objektelement die zusammenstellenden, als Objektelemente gegebenen Einzelteile der gleichen Unter­ suchung unterworfen. Wenn es keinen gemeinsamen Punkt gibt, werden das betreffende Objektelement sowie die zusammen­ stellenden Objektelemente weiter vernachlässigt. Wenn ein elementares Objektelement tatsächlich einen Punkt mit dem Teilfach gemeinsam hat, wird von diesem Objektelement sowie von allen Objektelementen eines hierarchisch höheren Pegels, in dem dieses Elementarobjektelement verbunden ist, die Information dem Punktprozessor zugeführt, der das betref­ fende Teilfach oder einen Teil dieses Teilfachs bearbeiten muß. Die Verbindung wird dadurch verwirklicht, daß das betreffende Objektelement als Teil einer Räumlichkeitsbe­ ziehung auftritt. Ein Ablaufdiagramm dieser Bearbeitungen ist in Fig. 7a und 7b angegeben und wird näher erläutert.

In Fig. 6 ist ein Schema eines Mehrprozessorsystems mit weiteren Einzelheiten dargestellt. Der Block 160 stellt einen zyklisch aktivierbaren Demultiplexer dar, der über den an der linken Seite angegebenen Pfeil vom Reduktions­ prozessor gespeist wird. An den Demultiplexer sind sechzehn Teilspeicher angeschlossen, von denen nur der erste (162) und der letzte (164) angegeben sind. Analog der Fig. 5 ist das Fernsehbild in sechzehn vertikale Streifen eingeteilt; jeder Streifen ist in eine feste Anzahl, beispielsweise 16, übereinander liegender Teilfächer unterteilt. Es gibt also 256 Teilfächer, von denen jeweils ein horizontaler Streifen von sechzehn Teilfächern zusammen bearbeitet wird. In einer ersten Teilbearbeitung wird die für die Bearbeitung der jeweiligen Teilfächer relevante Information aus der Daten­ struktur auf den betreffenden Teilspeicher übertragen. Wenn der Streifen von Teilfächern bearbeitet ist, wird die Information für den folgenden Streifen von Teilfächern bestimmt und in die Teilspeicher eingeschrieben. Das Ele­ ment 166 ist ein sekundärer Demultiplexer, der den Inhalt des Teilspeichers 162 einer Anzahl von vier Punktprozessoren (168-174) zur Verfügung stellt. Es gibt also insgesamt 64 Prozessoren für ein vollständiges Bild. In jedem Teil­ fach ist jeder Punktprozessor für vorangehende Bildpunkte wirksam, in einer vorteilhaften Ausführungsform werden in einem Teilfach jeweils zwei Fernsehzeilen bearbeitet, d. h. der Punktprozessor 168 bearbeitet den linken Teil der höchsten Zeile, der Punktprozessor 170 den rechten Teil der höchsten Zeile, der Punktprozessor 172 den linken Teil der nächsten Zeile und der Punktprozessor 174 den rechten Teil dieser folgenden Zeile. Wenn alle Punktprozessoren mit den ihnen auf diese Weise zugeordneten Zeilenabschnitten fertig sind, ist also die gesamte Farbinformation zweier Fernseh­ zeilen bestimmt. Das Element 176 ist ein zyklisch abtast­ barer Multiplexer, der dabei zunächst alle Punktprozessoren abtastet, die einen Teil der ersten Fernsehzeile bearbeitet haben, und danach die Punktprozessoren, die einen Teil der zweiten Fernsehzeile bearbeitet haben. Die Information wird auf den Empfangsteil des Bildspeichers übertragen. Wenn die Information in der richtigen Reihenfolge zugeführt wird, kann der Bildspeicher (Element 92/94 in Fig. 4) seriell organisiert sein, beispielsweise mit ladungsüber­ tragenden Elementen oder magnetischen Domänen. Wenn alle Streifen des Bilds bearbeitet worden sind, wird das Bild nach Bedarf erneut bearbeitet, während im Abbildungsspei­ cher Empfangsteil und Ausgabeteil die Funktion wechseln. Selbstverständlich ist dies nur sinnvoll, wenn sich das Bild dadurch ändert, beispielsweise dadurch, daß das visu­ elle Zentrum die Stelle wechselt (sog. Panning), dadurch, daß der Vergrößerungsfaktor geändert wird (sog. Zooming), oder dadurch, daß in der Datenstruktur eines oder mehrere Objektelemente durch Verschiebung, durch Ersatz oder durch Entfernung geändert werden. Bei einem ungeänderten Bild braucht es nur einmalig bestimmt zu werden.

Die Bearbeitungen im Reduktionsprozessor

In Fig. 7a und 7b sind Ablaufdiagramme zum Wählen der Objektelemente dargestellt, wie dies im Reduktions­ prozessor erfolgt, und wie dies auf nahezu gleiche Weise erfolgen kann, wenn der Punktprozessor als Strukturprozes­ sor arbeitet. Im Block 130 wird die Operation gestartet, beispielsweise werden in einem Programmspeicher der be­ treffende Vorgang aufgerufen und die Variablen vereinbart. Im Block 132 werden die Koordinaten des linken Rands XL, des rechten Rands XR, des oberen Rands YB und des unteren Rands YO eingestellt: es sind die Koordinaten, die auf dem niedrigsten Pegel der hierarchischen Datenstruktur (die Applikationskoordinaten)die mögliche Relevanz des betref­ fenden Objektelements bestimmen. Es sind also die Koordi­ naten der Eckpunkte des umschriebenen Rechtecks. Im Struktur­ prozessor werden hier die Koordinaten des betreffenden Punkts ausgefüllt. Im Block 134 wird die Speicheradresse der zu bearbeitenden hierarchischen Datenstruktur aufge­ rufen, dies ist also die Adresse der überwölbenden Zusammen­ hangstruktur. Alle Objektelemente besitzen ein Relevanzbit: alle diese Relevanzbits werden nunmehr zurückgestellt. Im Block 136 wird ein allgemein zugreifbarer Stapel geschaffen. Im Block 138 wird der rekursive Vorgang "examine" aufge­ rufen, der die eigentliche Untersuchung der Objektelemente auf möglicherweise vorhandene Relevanz durchführt. Wenn das System das zuerst aufgerufene Exemplar dieser Vorgänge wieder verläßt, folgt im Block 140 der Abschluß. Dabei werden alle Objektelemente, deren Relevanzbits gesetzt sind, auf den betreffenden Teilspeicher übertragen. Bei der Ver­ wirklichung des Strukturprozessors werden die relevanten elementaren Objektelemente darauf im Polygonprozessor be­ handelt.

Fig. 7b zeigt den Vorgang "Examine". Im Block 142 wird der Vorgang gestartet. Im Block 144 wird detektiert, ob das zu untersuchende Teilfach eine Überlappung mit dem aktuellen Objektelement hat. Zunächst ist das Objektelement die in Fig. 7a aufgerufene überwölbende Zusammenhangstruktur. Wenn es keine Überlappung gibt, kehrt das System zum Programm zurück, aus dem der betreffende Vorgang aufgerufen wurde: Block 184. Wenn es tatsächlich eine Überlappung gibt, wird die Adresse des aktuellen Objektelements auf dem allge­ meinen Stapel geschrieben: Block 146. Außerdem wird die Hilfsvariable BRA auf Null gestellt. Diese gibt die Nummer des nächsten, zu untersuchenden Objektelements an, es sind also die zusammenstellenden Objektelemente des nächst­ niedrigeren Pegels; sie sind nach den natürlichen Zahlen numeriert. Im Block 148 wird die Variable BRA inkrementiert, und es wird im Block 150 detektiert, ob es eine Überlappung gibt. Wenn das nicht der Fall ist, wird im Block 180 detek­ tiert, ob dies vom aktuellen Objektelement das letzte zu­ sammenstellende Objektelement auf nächstniedrigerem Pegel war.

Wenn das der Fall war, wird im Block 182 die zuletzt emp­ fangene Information vom allgemeinen Stapel abgenommen und weiter nicht behandelt. Wenn in diesem Fall der allgemeine Stapel völlig leer war, ist dies eine blinde Operation. Im Block 184 geht das System zum Vorgang zurück, den das momentane Exemplar des Vorgangs "Examine" aufgerufen hatte. Unter bestimmten Umständen ist dies also der Vorgang nach Fig. 7a. Wenn im Block 150 tatsächlich eine Überlappung detektiert wurde, wird die Adresse des aktuellen, zusammen­ stellenden Objektelements auf den allgemeinen Stapel ge­ schrieben. Im Block 154 wird detektiert, ob letzteres ein elementares Objektelement war. Wenn das der Fall ist, wird die ganze Information vom allgemeinen Stapel herangezogen und von allen darin referierten Objektelementen das Relevanz­ bit gesetzt. Danach geht das System zum Block 180 weiter.

Wenn im Block 154 kein elementares Objektelement in Bearbeitung war, werden im Block 186 die örtlichen Variablen auf der Prozeßumgebung (ein sog. run-time stack) aufgefrischt. Es sind zumindest die Koordinaten des Fensters (Block 132) bzw. die mittels der durchgeführten Transforma­ tionen davon abgeleiteten Koordinaten und der aktuelle Wert der Variable BRA im betreffenden Exemplar des Vorgangs "Examine". Im Block 188 werden die Fensterkoordinaten mittels der Umkehrung der Räumlichkeitsbeziehungen für das betreffende Objektelement zum nächsthöheren Objektelement neu berechnet, dabei eingeschlossen die inzwischen daran ausgeführten Transformationen (dieses letzte Element war also zum Zeitpunkt des Eintritts in den Vorgang im Block 142 aktuell). Anschließend wird im Block 190 der Vorgang "Examine" wieder aufgerufen. Bei Rückkehr aus dem Block 190 entspricht der Block 192 dem Block 182, und das System geht zum Block 180 weiter.

Wenn alle Objektelemente behandelt sind, müssen diejenigen, deren Relevanzbits gesetzt sind, weiter erläu­ tert werden. In einer einfachen Verwirklichung durchläuft das System alle Objektelemente und untersucht jeweils das Relevanzbit. Es läßt sich auch mit einem zweiten umkehr­ baren Vorgang verwirklichen: "Proceß"; dieser Vorgang wird nur kurz erläutert. Statt einer Überlappung detektiert er das Relevanzbit. Statt des Blocks 156/158 werden die be­ treffenden Objektelemente auf den Teilspeicher übertragen. Der Block 188 entfällt, und im übrigen wird nahezu der Verlauf nach Fig. 7b verwirklicht.

Die Wirkung der Punktprozessoren

Anschließend wird die Wirkung der Anordnung von Punktprozessoren erläutert, wobei der Einfachheit halber von Fig. 4 ausgegangen wird. Wenn der Hilfsspeicher 88 im Prozessor 80 die relevante reduzierbare Datenstruktur für das behandelte Teilfach enthält (diese Datenstruktur ist wieder auf gleiche Weise hierarchisch geordnet), kann die Bearbeitung der Information anfangen. Der Punktprozessor durchläuft nacheinander für jeden behandelten Bildpunkt die gleiche Reihenfolge und arbeitet für diesen Bildpunkt nacheinander als Strukturprozessor, als Polygonprozessor und als Prioritätsprozessor. Im Prinzip können diese Be­ arbeitungen auch im anderen Zusammenhang durchgeführt werden. So können die Polygonbearbeitungen für ein bestimmtes Poly­ gon anfangen, wenn es von den Strukturprozessorbearbeitungen vollständig behandelt worden ist. Die Bearbeitungen für den Prioritätsprozessor können hinsichtlich der Polygone anfangen, wofür die Bearbeitungen zum Bestimmen der "Innen"- bzw. "Außeninformation" völlig durchgeführt sind. In diesem Zusammenhang kann der Prozessor 90 also auch aus mehreren Teilprozessoren aufgebaut sein, die je einen Teil der Be­ arbeitungen durchführen, je nach der Verfügbarkeit der dazu erforderlichen Daten. An sich sind Multiprozessor­ systeme bekannt und werden der Kürze halber nicht näher erläutert. Die Bearbeitungen für die Funktion als Struktur­ prozessor erfolgen auf gleiche Weise wie die Bearbeitungen im Reduktionsprozessor, d. h. für ein aus einem einzigen Punkt bestehendes Teilfach. Dadurch braucht auch nur ein einziges Koordinatenpaar (statt 2) transformiert und in dem genannten "run-time-stack" aufgehoben zu werden. Außerdem braucht dabei im Punktprozessor auch keine Aus­ richtung mit den Achsen des neuen Koordinatensystems zu er­ folgen, weil es sich um nur einen einzigen Punkt handelt.

Schließlich brauchen im Punktprozessor nur relevante Elementarobjektelemente (die Adressen relevanter elementarer Objektelemente) für den Polygonprozessor einschließlich der möglichen Prioritätsinformation für den Prioritäts­ prozessor kopiert zu werden.

Die Bearbeitungen hinsichtlich des Polygonprozessors werden nachstehend erläutert. Die Bearbeitungen für den Prioritätsprozessor sind häufig einfach. In einer zwei­ dimensionalen Umgebung ist jedes zu färbende Polygon mit einer eigenen Prioritätszahl versehen, und bei einer Über­ lappung wird einfach die Farbe der höchsten Prioritäts­ zahl als "gewinnbringend" angezeigt. Wenn mehrere Polygone Farben mit gleicher Prioritätszahl besitzen, wird eine Mischfarbe erzeugt. An sich ist die Bildung von Mischfarben bekannt. Wenn die zu erzeugende Farbe für einen bestimmten Punkt bestimmt ist, wird der folgende Bildpunkt des von dem betreffenden Punktprozessor zu bearbeitenden Teilfachs be­ handelt. Wenn alle Punkte eines Teilfachs bearbeitet sind, wird der Reduktionsprozessor 76 neu aktiviert und liefert die Information eines folgenden Teilfachs. Die so gebildete Farbinformation wird einem Doppelpufferspeicher 92/94 zuge­ führt. Der Teil 92 ist ein Empfangsteil und daher der Ein­ fachheit halber wie ein serieller Speicher, beispielsweise mit 300 kBits Moduln aufgebaut, von denen eine Anzahl zur Speicherung einer Mehrbitinformation pro Bildpunkt parallel angeordnet sind. Für jeden Bildpunkt wird beispielsweise ein Achtbit-Byte zum betreffenden Punktprozessor parallel erzeugt. Der Teil 94 ist ein Abbildungsteil und besitzt die gleiche Kapazität wie der Empfangsteil. Wenn alle Bild­ punkte des Fachs 102 behandelt sind, werden die Funktionen des Abbildungsteils und des Empfangsteils ausgetauscht. Das Abbildungselement 96 ist beispielsweise ein herkömm­ liches Gerät auf der Basis einer Fernsehröhre mit 600 Bild­ zeilen, auf denen je 1000 Bildpunkte berechnet werden. Das Ausgangsnetz zwischen den jeweiligen Punktprozessoren und dem Doppelpufferspeicher enthält eine Multiplexorgani­ sation, so daß die Information der von den Punktprozessoren bestimmten Farben in der Reihenfolge abgegeben wird, in der die betreffenden Punkte am Bildschirm abgebildet werden müssen. Die punktweise Berechnungen benötigen nicht für jeden Punkt gleich viel Zeit, und außerdem müssen die Punktprozessoren zyklisch abgetastet werden, um die Informa­ tion in der richtigen Reihenfolge abzugeben. Deshalb ent­ hält der Ausgang eines Punktprozessors also eine Zwischen­ puffermenge, in der bereits bestimmte Farbinformationen gespeichert sind, bis sie am Doppelpufferspeicher zur Verfügung gestellt werden müssen.

Die Bearbeitungen im Polygonprozessor

In Fig. 8 sind in einer algorithmischen Rechner­ sprache die vom Polygonprozessor zu implementierenden Be­ arbeitungen dargestellt, wobei also für einen bestimmten Bildpunkt und für ein bestimmtes Polygon die Teilfarben­ information "innen oder nicht-innen" bestimmt wird. Dabei vereinbart Fig. 9b einige Anfangsgrößen, d. h. einen Vorrat mit Punktenpaaren, wobei in einem "Vorrat" das gleiche Punktenpaar mehrmals auftreten darf, drei Boole-sche Variab­ len und zwei Ganzzahlen. Ein Bildpunkt ist ein Element einer Menge von Ganzzahlpaaren: Punkt P hat die Koordinaten (xp, yp). Der gegenseitige Abstand "d" zwischen zwei Punkten wird als der absolute Wert des größten Abstands in einer Koordinatenrichtung (x oder y) bestimmt. Eine Kurve wird als eine Reihe von Punkten mit gegenseitigem Abstand jeweils gleich "1" gebildet; die Anzahl der Punkte der Kurve ist in dieser Begriffsbestimmung mit "Länge" bezeichnet. Ein Abstand "1" entspricht also einer Länge "2". Das um­ schreibende Rechteck zweier Punkte P, Q enthält alle Bild­ punkte mit (x - xp) x (x - xp) < 1, und entsprechend für die y-Koordinaten (faktisch muß das Produkt höchstens gleich Null sein). Die Summe zweier Kurven mit zusammen­ fallendem Endpunkt ist die Verkettung der Kurven mit ein facher Zählung dieses Endpunkts. Eine sog. Kurvenzeichnungs­ funktion (line drawing function) der Punkte P, Q: "f(P, Q)" bildet die Punkte P und Q auf den Endpunkten einer Kurve ab, von welcher Kurve jede Teilkurve alle Punkte in dem von den Endpunkten dieser Teilkurve bestimmten umschreibenden Rechteck hat. Es erfüllen diese Bedingungen also die in Fig. 1c . . . 1e dargestellten Bezier-Kurven. Als Funktion des x-Koordinaten ist die Funktion des y-Koordinaten ent­ weder "nicht ansteigend", oder "nicht-abfallend"; gleiches gilt für den x-Koordinaten als Funktion des y-Koordinaten. Beim hier beschriebenen Algorithmus sind nicht alle Bezier- Kurven zulässig, beispielsweise nicht immer solche, bei denen ein zwischenliegender beschreibender Punkt nicht in dem von äußersten beschreibenden Punkten bestimmten um­ schriebenen Rechteck liegt. Wenn derartige Kurven auftreten, ist es eine einfache Lösung, die keine Annäherungen der Kurve enthält, eine Bezier-Kurve in Teile zu unterteilen, bei denen für die Teile einzeln das Problem nicht auftritt. Es sei noch bemerkt, daß die gestellte Bedingung weniger schwer ist als die, die lautet, daß alle beschreibenden Punkte einer Bezier-Kurve in dem von den Endpunkten be­ schriebenen Rechteck liegen müssen. Ein Polygon "G" ist eine Reihe von Punkten, die die Endpunkte zusammenfallend besitzt, ohne daß weitere Einschränkungen für die anderen gegeben sind. Die Kurve eines Polygons unter einer Kurven­ zeichnungsfunktion ist die Summe der von aufeinanderfolgen­ den Seiten des Polygons bestimmten Kurven unter diesen Kurvenzeichnungsfunktionen. Wenn ein Polygon nur aus einem einzigen Punkt besteht, ist diese Kurve diesem einen Punkt gleich. Für jedes Tripel der Größen Polygon G, Kurven­ zeichnungsfunktion f und Punkt P werden nunmehr ein erstes Prädikat ATSIDE und ein zweites Prädikat INSIDE definiert, die je "wahr" oder "unwahr" sein können. Das erste Prädikat ist "wahr", wenn der betreffende Bildpunkt mit einem von der betreffenden Kurvenzeichnungsfunktion als Seitenpunkt des Polygons angezeigten Punkt zusammenfällt. Das Prädikat INSIDE ist "wahr", wenn die Anzahl der Schnittpunkte einer beliebigen quasiunendlichen Geraden vom betreffenden Punkt mit einigen der Polygonseiten ungerade ist. In der be­ schriebenen Ausführungsform hat diese quasiunendliche Gerade die negative x-Richtung. Das Prädikat INSIDE ist als Formel in Fig. 9a gegeben. Ein Schnittpunkt wird durch zwei notwendige Bedingungen definiert. Die erste ist, daß zwei Punkte k, k+1 der Polygonseite auf der nächsthöheren bzw. der nächstniedrigen y-Koordinaten in bezug auf dem Ursprungspunkt P liegen, so daß das Produkt der Unter­ schiede der y-Koordinaten den Wert "-1" hat. Die zweite Bedingung ist, daß für alle Punkte der Polygonseite zwischen den Punkten k und k+1 die x-Koordinate kleiner als der des Ursprungspunkts P und die y-Koordinate gleich dem des Punkts P ist. In diesem Zusammenhang zeigt Fig. 10a also eine Situation, in der ein Schnittpunkt zwischen den Punkten k und k+1 gegeben ist, während in der Situation nach Fig. 10b kein Schnittpunkt gegeben ist. Die Gesamt­ zahl der Schnittpunkte der quasiunendlichen Geraden mit einigen der Polygonseiten muß dabei für eine "Innen"- Situation ungeradzahlig sein. Im Ausdruck wird das Vor­ zeichen für Modulo-x-Addierung benutzt, wobei x den Wert n hat. Wenn auf der dritten Zeile nach Fig. 9a das Vorzeichen "kleiner als" benutzt wird, verläuft die betreffende quasi­ unendliche Gerade in der positiven x-Richtung. Wenn die Anzahl der Schnittpunkte ungeradzahlig ist, gilt das Prädikat INSIDE. Schließlich wird die Farbinformation positiv ge­ rechnet, wenn das Prädikat ATSIDE oder das Prädikat INSIDE wahr ist: Dies ist das Prädikat INCLUDES. Bei gegebenem Polygon, Punkt und gegebener Kurvenzeichnungsfunktion muß dabei der Wert des Prädikats INCLUDES bestimmt werden.

Es läßt sich beweisen, daß obige Prädikate, wobei INCLUDES schließlich die Innen/Außeninformation liefert, sich wie folgt berechnen lassen. Dazu sind zunächst zwei Hilfsprädikate wie folgt zu definieren. Das Prädikat INBOX1 zwischen zwei Punkten Q, R und einem zu untersuchenden Punkt P ist wahr, wenn der betreffende Punkt in dem von Q und R bestimmten umschriebenen Rechteck umfaßt ist:

(xP - xQ) × (xP - xR) × 1; (yP - yQ) × (yP - yR) < 1;

faktisch muß das Produkt höchstens gleich Null sein. Das Prädikat INBOX2 ist wahr, wenn das von den Punkten Q und R bestimmte umschriebene Rechteck zwei Punkte A und B enthält, für die gilt, daß der Punkt A links auf den selben y-Koordinaten wie der Punkt P liegt, und der Punkt B als Nachbar des Punkts A auf der nächsthöheren Y-Koordinaten.

Das bedeutet u. a.: Der Punkt P liegt weder auf der linken noch auf der oberen Seite des umschriebenen Rechtecks. Fig. 10d . . . . 10f zeigen einige Möglichkeiten für ein von A und B beschriebenes Rechteck; für eine jede dieser Möglich­ keiten ist das Prädikat INBOX2 "wahr", wobei einige ver­ schiedene Positionen des Punkts P jeweils angegeben sind. Auf diese Weise ist das Prädikat INSIDE sehr leicht prüfbar, wobei die gewählten Bedingungen der Kurvenzeichnungsfunktion gegeben sind.

Beim Auftragsverzeichnis nach Fig. 8 wird von einem Vorrat von Punktpaaren B ausgegangen, wobei gegebenenfalls doppelte auftreten dürfen. Weiter gibt es drei zweiwertige Hilfsgrößen in, at, und stop und sind q und r als natürliche Zahlen definiert. Das Auftragsverzeichnis nach Fig. 8 ent­ hält folgende Aufträge. Auf der Zeile 200 wird das betref­ fende Polygon vereinbart. Auf der Zeile 201 wird die Anzahl der Punktpaare als jeweils von einer jeweiligen Polygon­ seite bestimmt vereinbart, während die Größen in at, unwahr werden. Auf der Zeile 202 werden die Operationen gestartet und fortgesetzt, bis alle Punktpaare B aus dem Vorrat be­ arbeitet sind oder die Größe "at" in "wahr" übergegangen ist. Auf der Zeile 203 werden zwei Punkte Q, R dem Vorrat von Punktpaaren B entzogen. Auf der Zeile 204 wird detektiert, ob der Punkt P in dem von Q und R bestimmten Rechteck liegt. Wenn das nicht so ist, folgt das System die dort anfangende vertikale Gerade, die auf der Zeile 230 endet. Auf gleiche Weise geben die weiteren vertikalen Geraden eine Iterations­ struktur (nest) an. Auf der Zeile 205 wird detektiert, ob der Punkt P mit dem Punkt Q oder mit dem Punkt R zusammen­ fällt. Wenn das so ist, wird die Größe "at" "wahr". Wenn die Prüfung ein negatives Ergebnis hat, wird auf der Zeile 208 eine Reihe von m Punkten mit Hilfe der in Q und R enden­ den Kurve unter der Kurvenzeichnungsfunktion f, benannt. Eine Hilfsgröße "stop" wird "unwahr" gemacht, und die Rangnummern q, r werden einem ersten bzw. letzten Punkt der Kurve gegeben. Solange die Größe "stop" noch "unwahr" ist, geht das System weiter. Auf der Zeile 210 wird die Größe p dem Unterschied zwischen q und r angeglichen.

Es gibt nun zwei Fälle. Wenn p gleich 0 oder 1 ist, sind die Punkte Eq und Er Nachbarn und enthält das von ihnen bestimmte umschriebene Rechteck vier Bildpunkte: Das sog. elementare Rechteck, das hier durch die frühere Prüfung auf der Zeile 205 vier Punkte enthält. Auf der Zeile 213 wird angegeben, daß in jedem Fall gestoppt wird. Auf der Zeile 214 wird geprüft, ob keiner der Punkte Eq, Er rechts vom Punkt P liegt, während zumindest 1 der originalen End­ punkte Q und R in der y-Richtung über dem Punkt P liegt. Wenn das so ist, wird der Wert der binären Variablen "in" geändert. Einige Möglichkeiten dazu sind in Fig. 10d-10f dargestellt. Wenn jedoch der Abstand zwischen Eq und Er größer ist, wird auf der Zeile 217 die Linie zwischen Eq und Er in zwei Abschnitte geteilt, beispielsweise unter Berücksichtigung der Abrundung halbiert. Wenn der Punkt P mit diesem Zwischenpunkt Et zusammenfällt, wird auf der Zeile 219 gestoppt, wobei festgestellt ist, daß der be­ treffende Punkt auf der Polygonseite liegt. Wenn die voran­ gehende Prüfung ein negatives Ergebnis hat, wird auf den Zeilen 224 geprüft, ob der Punkt P in einem der vom Punkt Et bzw. einem der Punkte Eq bzw. Er diagonalisierten Rechteck liegt. Wenn das so ist, kehrt das System zur Zeile 209 (while) zurück, wobei das immer vorhandene andere Rechteck - der Punkt kann bei dieser Prüfung nie gleichzeitig in beiden Rechtecken liegen - abgelehnt wird und der Punkt Et die Stelle eines der Punkte Eq, Er für den nächsten Itera­ tionsschritt einnimmt. Wenn der Punkt P nicht in einem der zwei umschriebenen Rechtecke liegt, wird gestoppt, aber es wird noch geprüft, ob der Punkt hinsichtlich des Zwischen­ punkts und eines der Endpunkte das Prädikat INBOX2 viel­ leicht wahr machen würde. Dieses Prädikat unterscheidet sich von INBOX1 und prüft, ob die Linie, die die Diagonal­ punkte des Rechtecks als Enden hat, ganz links vom Punkt P liegt, mindestens einen Punkt mit einem größeren Y-Koordi­ naten und mindestens einen Punkt mit dem gleichen Y-Koordi­ naten wie der Punkt oder einen kleineren enthält. Wenn das Prädikat INBOX2 "wahr" ist, wird der Wert der Größe "in" geändert. Wenn der Punkt P nicht INBOX1 (Q, R) auf Zeile 204 entspricht, erreicht das System die Zeile 230 und wird die Prüfung INBOX2 noch an den Endpunkten Q, R durchgeführt (Zeile 231). Schließlich wird in 233 das Ergebnis des Algorithmus, insbesondere der Wert der Größe "at" zurück­ gegeben. In Fig. 10c ist eine Anzahl von mit gestrichelten Linien angegebener, umschreibender Rechtecke dargestellt; der Einfachheit halber werden hier Bezier-Kurven der ersten Ordnung erläutert. Beim Teilen einer Polygonseite (Polygon­ seitenteil) braucht eine Vielzahl von Bildpunkten nicht mehr mitgenommen zu werden. Mit anderen Worten: durch das logarithmische Einteilungsverhalten konvergiert für viele Bildpunkte der Algorithmus schon nach einem oder einigen Verarbeitungsschritten. Es sei noch darauf hingewiesen, daß der in Fig. 8 angegebene Algorithmus für Bezier-Kurven der ersten Ordnung anwendbar ist, und nur dabei besteht die Freiheit in der Wahl des Teilungsfaktors, der ungleich 1/2 sein kann. Die Bildung der Teilpunkte bei Bezier-Kurven höherer Ordnung ist bei Fig. 1d, 1e beschrieben. Der Algorith­ mus der Fig. 8 braucht für derartige Bezier-Kurven höherer Ordnung nur an diesem Punkt angepaßt zu werden, wobei also immer einige beschreibende Hilfspunkte zu merken sind.

Verwirklichung eines Polygonprozessors

In Fig. 11 ist eine Blockschaltung eines Polygon­ prozessors für ein Polygon dargestellt, dessen Seiten von Bezier-Kurven erster Ordnung gebildet werden. Eine derartige Schaltung kann in einem Spezialzweckprozessor verwirklicht werden. Nur der Teil in bezug auf die X-Koordi­ naten ist angegeben. Für die Y-Koordinaten ist eine ent­ sprechende Anordnung vorgesehen bzw. wird die gleiche Anordnung in Zeitverschachtelung benutzt. Die Programm­ steuerung ist der Einfachheit halber nicht angegeben, sondern nur die Datenwege. Zunächst werden die Register 240 und 242 mit der X-Koordinaten eines beschreibenden Punkts (hier mit dem Endpunkt) der betreffenden Polygonseite bzw. mit dem des betreffenden zu untersuchenden Punkts geladen. Bei den Datenwegen ist jeweils die Breite in Bits angegeben. Die Koordinaten der Punkte bestehen aus N Bits; dies wird durch die Abmessungen des Arbeitsfelds 100 in Fig. 5 bestimmt.

Im arithmetischen Element 244 wird zunächst der Unterschied der zwei x-Koordinaten bestimmt. Der betreffende Datenweg hat eine Breite von N Bits, erweitert um 1 Zeichenbit. Wenn der Unterschied den Wert +1,0, oder -1 hat, kann es sein, daß der betreffende Punkt mit dem betreffenden End­ punkt der Polygonseite zusammenfällt oder anders in einem von diesem Endpunkt bestehenden elementaren umschriebenen Rechteck liegt. Für einen jeden der erwähnten drei Fälle enthält das Register 250 eine Bitsposition. Weiter wird in einer zweiten Bearbeitung das Ergebnis der Bearbeitung zusammen mit dem Inhalt des Registers 248 über einen Daten­ weg mit der Breite N+4 Bits auf das Register 250/252 über­ tragen: Es enthält also die relative x-Koordinate des ersten Endpunkts der betreffenden Polygonseite. Anschließend wird die gleiche Bearbeitung für den anderen Endpunkt der betreffenden Polygonseite wiederholt, deren Ergebnis in das Register 254/256 eingeschrieben wird. Auf gleiche Weise werden die y-Koordinaten der Endpunkte der betreffenden Polygonseite behandelt. Eine nicht dargestellte Detektions­ schaltung kann nunmehr die in Fig. 8 auf den Zeilen 204, 205 und 212 angegebenen Prüfungen durchführen. In vorkom­ menden Fällen kann damit die Behandlung des betreffenden Punkts beendet sein, insbesondere wenn der betreffende Punkt außerhalb des von der Polygonseite diagonalisierten Recht­ ecks liegt oder wenn direkt eine Entscheidung über die Innen/Außen-Information getroffen werden kann. Zum Durch­ führen der weiteren Zeilen nach Fig. 8 werden anschließend die Multiplexer 258 und 260 für die Inhalte der Register 250 . . . 256 durchlässig gemacht, die um ein unbedeutsamstes "1"-Bit ergänzt sind, wie es aus einer nicht dargestellten Signalquelle erhalten wird. Anschließend wird die Mitte der betreffenden Polygonseite bestimmt: die relativen x-Koordinaten werden dem Addierelement 270 zugeführt. Die Summe wird im Register 272 zwischengespeichert, die Summe ist wieder ein relativer Wert. Der Block 274 entspricht funktionsmäßig dem Block 256, weiter steuert das Ergebnis der Prüfung auf der Zeile 221 in Fig. 8, nach welchem der zwei Register 262-268 durchgelassen werden muß. Der zu behandelnde Punkt muß dabei wieder in dem vom Polygon­ seitenteil diagonalisierten Rechteck liegen. Sowohl die x-Koordinaten als auch die y-Koordinaten der beiden End­ punkte dieses Teils müssen dabei entgegengesetzte Vorzeichen haben. So schreitet die Bearbeitung weiter fort, bis das Ende des Auftragsverzeihnisses nach Fig. 8 erreicht ist.

Fig. 12 zeigt eine Blockschaltung eines Polygon­ prozessors für Bezier-Polygone, deren Seiten durch Bezier- Kurven höchstens dritter Ordnung gebildet werden. Die Informationsquelle ist ein Speicher 350 mit wahlfreiem Zugriff, beispielsweise der betreffende Hilfsspeicher, in dem die relevanten Elementarobjektelemente eines Relevanz­ bits für den betreffenden Polygonprozessor vorgesehen sind, wobei das Relevanzbit vom Strukturprozessor eingestellt ist. Bei einer großen und komplizierten Datenstruktur kann auch hier diese Datenstruktur als Wegzeiger genommen werden: Nur Objektelemente, die selbst ein Relevanzbit besitzen, können auf einem niedrigeren Pegel in der Hierarchie auf ein Objektelement verweisen, das mit einem derartigen Relevanzbit versehen sein kannte. Wenn mehrere Punktprozes­ soren mit der gleichen Datenstruktur arbeiten, wird zunächst ein Auszug zur Speicherung in den Hilfsspeicher gemacht. Anschließend machen die jeweiligen Punktprozessoren je ihre eigene Kopie dieses Auszugs und kann der Reduktions­ prozessor einen neuen Auszug machen, während die Punkt­ prozessoren ihre Arbeit machen. Das Register 354 liefert die Koordinate des betreffenden Bildpunkts. Das Addier­ element 352 entspricht dem Element 244 in Fig. 11. Die relativen Koordinaten des Anfangspunkts Q und des End­ punkts R der betreffenden Polygonseite gelangen an eines der Register 356 und 358. Die logische Schaltung 420 prüft, ob der zu untersuchende Bildpunkt mit einem der zwei End­ punkte zusammenfällt (Fig. 8, Zeile 205, dies wird also für zwei Koordinaten zusammen bestimmt), und wenn dies zutrifft, wird die Größe "at" eingestellt und ist das be­ treffende Polygon fertig. Dabei wird nötigenfalls das folgende Polygon im Speicher 350 adressiert. Weiter wird, wenn der Bildpunkt außerhalb des beschriebenen Rechtecks liegt (Zeile 204), ein Steuersignal dem Fortschrittssteuer­ element 422 zum Adressieren der folgenden Seite des be­ treffenden Polygons zugeführt. Weiter prüft die logische Schaltung 418 die Bedingung INBOX2 (Q, R), Fig. 8, Zeile 231. Ggf. wird dabei die Größe "in" "wahr". Weiter werden die relativen Koordinaten der höchstens vier beschriebenen Punkte nacheinander den Registern 360-366 zugeführt. Die Elemente 368 . . . 374 sind Multiplexer mit 2-4 Eingängen. Die Elemente 376 . . . 382 sind Register entsprechend den Elementen 250/2 und 254/6. Die Blöcke 384 . . . 394 stellen eine Baumstruktur von Akkumulatoren dar, die einen oder mehrere beschreibende Punkte des Polygonseitenteils bestimmen. Das Element 404 ist ein Multiplexer, der die von der Ordnung der betreffenden Bezier-Kurve gegebene Ausgangszahl (Et) durchläßt. Für eine Kurve der ersten Ordnung ist dies das Element 384 usw. Das Element 396 ist ein Multiplexer zum Durchlassen des Koordinaten des letzten beschreibenden Punkts. Dabei ist der Block 402 eine logische Schaltung zum Zuführen der rich­ tigen Information von Et an weitere logische Schaltungen (400, 408). Gleiches gilt für die logischen Schaltungen 406 und 398 hinsichtlich der zwei Endpunkte der Polygonseite (des Polygonseitenteils). Die Koordinaten des ersten und des letzten beschreibenden Punkts gelangen so an die Logik­ schaltungen 406 bzw. 398. Die logische Schaltung 400 prüft INBOX1. (Eq, Et) bzw. INBOX1 (Er, Et). Wenn einer dieser beiden "wahr" ist, werden die Multiplexer 368, 370, 372, 374 für die Inhalte der Akkumulatoren durchlässig, die die Daten der danach relevanten beschreibenden Punkte enthalten (Prüfung in Zeile 222, 224). Die logische Schaltung 410 prüft (Zeile 212), ob die zwei beschreibenden Punkte ein elementares umschreibendes Rechteck bilden, so daß ggf. die Situation nach Fig. 10d, e, f auftreten kann (Zeile 212). Die logische Schaltung 408 prüft, ob der neu gefundene Punkt Et mit dem betreffenden Bildpunkt zusammenfällt: Die gleiche Prüfung wie in der Logikschaltung 420. Wenn der betreffende Bildpunkt außerhalb der zwei von Endpunkten und vom neuen Mittelpunkt beschriebenen Rechteck liegt, führt die logische Schaltung 412 die Prüfung der Zeile 228 durch, wodurch ggf. die Information "in" geändert werden kann. Die dazu er­ forderliche Information hinsichtlich der Punkte Q, R wurde bereits von den Registern 356, 358 mit Hilfe selektierender logischer Schaltungen 424 und 426 empfangen. Die Elemente 414 und 416 bilden Register dafür.

Ergänzungen für einen dreidimensionalen Zustand

In einer dreidimensionalen Situation können zunächst alle Objektelemente immer noch als flache Polygone gegeben sein, von denen alle beschreibenden Punkte also eine dritte Koordinate besitzen, die dabei ebenfalls in den Speicher 68 nach Fig. 4 eingeschrieben ist. Nach der Transformation mit Hilfe des Elements 70 wird dabei der Vergleich dieser Fläche bestimmt und werden die Parameter des Vergleichs dieser Fläche nach Art von Prioritätsinformation bei den mit Hilfe des Elements 72 transformierten Objektelementen in den Speicher 74 eingeschrieben. Bei der Verarbeitung durch den Reduktionsprozessor wird die ganze Information der relevanten Objektelemente in den betreffenden Hilfsspeicher einge­ schrieben. Wenn nunmehr nach den bereits beschriebenen Be­ arbeitungen im Strukturprozessor und im Polygonprozessor festgestellt wird, daß zwei oder mehrere Polygone einen bestimmten Bildpunkt überlappen, wird das Einfärbungsproblem wie folgt gelöst: Dabei sei bemerkt, daß dies bei einer Parallelprojektion dadurch genau erfolgen kann, daß nur die beschreibenden Punkte der betreffenden Polygone in die zweidimensionale Situation übertragen werden, wonach der beschriebene Polygonvorgang durchgeführt wird. Die zwei Flächen, in denen die Polygone sich befinden, sind durch die Parameter des Parametervergleichs der Flächen a, b, c, d, bzw. a′, b′, c′, d′ gegeben, während von der ersten Fläche der Vergleich wie folgt ist: ax + by + cz + d = 0, und von der zweiten a′x + b′y + c′z + d′ = 0, während die Vorzeichen von d und d′ gleich sind (dies ist keine faktische Beschrän­ kung). Der aktuelle Bildpunkt wird durch seine Koordinaten C, D, T gegeben, das ist also die Durchschneidung der Schaulinie und der projektiven Ebene, so daß der Wert von T für alle Bildpunkte fest ist. Dabei sind in diesem Augen­ koordinatensystem die Gleichungen der Projektionsgeraden für den aktuellen Bildpunkt wie folgt: Bei Parallelprojektion:

x=C, y=D, z=kT (k kann jeden Wert haben),

so daß für die jeweiligen Polygone die Parameterwerte von k für die Durchschneidungspunkte mit der Schaulinie wie folgt gefunden wurde:

k = (-d - a × C - b × D)/(c × T), und

k′= (-d′- a′ × C - b′ × N D)/(c′ × T).

Bei zentraler Projektion:

x=kC, y=kD, z=kT (k kann jeden Wert haben):

k = (-d)/(a × C + b × D + c × T), und

k′= (-d′)(a′ × C + b′ × D + c′ × T).

Nur die relativen Werte des Parameters k sind jedoch wichtig, und unter anderem dadurch, daß immer für einen positiven Wert des Koeffizienten d gewählt wurde, kann diese Bestimmung nach Ausmultiplikation der obigen Be­ ziehungen erfolgen (so daß also keine Teilung erforder­ lich ist). Der kleinste Wert von k bzw. k′ zeigt das Polygon an, für das die "Innen"-Information die höchste Priorität besitzt und für das also die Einfärbung zu verwirklichen ist. Wenn mehr als zwei Polygone für den betreffenden Bildpunkt relevant sind, wird die Entscheidung nacheinander paarweise für alle Polygone durchgeführt, wobei immer nur das rele­ vanteste der zwei in der weiteren Bearbeitung behalten wird.

In obiger Beschreibung sind flache Bezier-Figuren beschrieben. Die Erweiterung nach drei Dimensionen erfolgt dadurch, daß dabei die Bezier-Kurven in zwei Bündeln verlaufen, die als ein Doppelprodukt vorstellbar sind, wo sie in Fig. 1b nur ein einziges Produkt erforderlich machen.

Claims (9)

1. Mehrprozessorsystem zum Erzeugen von Bildpunktinforma­ tionen, insbesondere Farbinformationen, für ein Darstellungselement mit rasterförmiger Darstellung aus Objektelementen, die in einem elementaren Pegel einer hierarchischen Datenstruktur mit mehreren hierarchischen Pegeln angegeben sind, mit einem Empfangsspeicher mit einem Anschluß, an dem die Information der Objektelemente von einem Hauptprozessor zur Speicherung im Empfangs­ speicher empfangen wird, sowie einem vom Empfangsspeicher gespeisten Punktprozessorsystem, das aus der Datenstruktur der Objektelemente die Bildpunktinformationen zum Zuführen an einen Anschluß für ein Darstellungselement berechnet, dadurch gekennzeichnet, daß die Objektelemente auf dem elementaren Pegel als ausschließlich von Punkten ihrer Polygonseiten definierte Bezier-Polygone angegeben sind, die in jedem nächsthöheren hierarchischen Pegel durch Räumlichkeitsbeziehungen (relative Transformationen) zu hierarchisch höheren Elementen verbunden sind, bis auf einem höchsten hierarchischen Pegel eine zweidimensionale Zusammenhangstruktur entsteht, die in Form von Objekt­ elementen und planaren Räumlichkeitsbeziehungen im Empfangsspeicher gespeichert ist, daß das Punktprozessor­ system eine Anordnung parallelgeschalteter Punkt­ prozessoren (80, 82, 84, 86) enthält, die mit dem Empfangsspeicher gekoppelt sind und von denen jeder Punkt­ prozessor die Bildpunktinformation für jeweils eine Gruppe von Bildpunkten erzeugt, wobei jeder Bildpunkt einem der Punktprozessoren zugeordnet ist und die Gruppen von Bild­ punkten im Bild eine regelmäßige Anordnung bilden, daß jeder Punktprozessor einerseits als Strukturprozessor arbeitet, der für einen vorgegebenen Bildpunkt nachein­ ander vom höchsten hierarchischen Pegel der Datenstruktur pegelweise die diesem Bildpunkt zugeordneten Applika­ tionskoordinaten in den Objektelementen bestimmt, bis entweder festgestellt wird, daß dem jeweiligen Bild­ punkt keine Applikationskoordinaten des betreffenden Objektelements zugeordnet sind oder bis der niedrigste hierarchische Pegel eines oder mehrerer elementarer Objekte erreicht ist, daß jeder Punktprozessor zum anderen für die als Polygone angegebenen elementaren Objekt­ elemente als Polygonprozessor arbeitet, der bei jedem vorgegebenen Bildpunkt für jedes relevante Polygon eine binäre Information als eine Inneninformation bzw. Außen­ information zur Bildung eines für diesen Bildpunkt bestimmten Verzeichnisses elementarer Objektelemente und zugeordneter Farbinformationen berechnet, für welche Objektelemente die "Innen"-Information gilt, und daß jeder Punktprozessor ferner als Prioritätsprozessor arbeitet, der aus dem Verzeichnis mit Hilfe für jedes elementare Objektelement gültiger Prioritätsinformation die für diesen Bildpunkt zu erzeugende Farbinformation bestimmt, und daß dem Anschluß für das Darstellungselement ein Multiplexer (176) vorgeschaltet ist, der die von den Punktprozessoren gebildeten Farbinformationen zyklisch abtastet und diesem Anschluß zuführt.

2. Mehrprozessorsystem nach Anspruch 1, dadurch gekennzeichnet, daß im Punktprozessor beim Arbeiten als Polygonprozessor für jede Polygonseite eines Polygons eine iterative Entscheidung durchgeführt wird, wobei je Iterationsschritt ein von einer zumindest teil­ weise im Bild liegenden Polygonseite bzw. von einem Poly­ gonseitenteil erzeugtes Parallelogramm mit der Stelle des aktuellen Bildpunktes verglichen wird, über die zu ent­ scheiden ist, daß mit dem Bildpunkt im Parallelogramm die Polygonseite bzw. der Polygonseitenteil geteilt wird, bis in einem Iterationsschritt das Zusammenfallen des Bild­ punktes und der Diagonale festgestellt wird (ATSIDE) oder anderenfalls mit dem aktuellen Bildpunkt außerhalb des betreffenden Parallelogramms bzw. beim Nichtzusammenfallen des Bildpunktes und der Diagonale in einem elementaren Iterationsschritt die Anzahl der Schnittpunkte aller Poly­ gonseiten des betreffenden Polygons mit einer quasiunend­ lichen Geraden durch den aktuellen Bildpunkt gezählt und bei einer ungeraden Zahl eine "umschlossene" Information (INSIDE) für diesen Bildpunkt gebildet und aus der "umschlossenen Information die "Innen"-Information gebildet wird.

3. Mehrprozessorrechnersystem nach Anspruch 2, dadurch gekennzeichnet, daß aus dem Zusammenfallen außer­ dem die "Innen"-Information, ansonsten die "Außen"-Infor­ mation gebildet wird.

4. Mehrprozessorsystem nach Anspruch 2 oder 3 für ein Darstellungselement, für das die Bildpunkte in einer rechteckigen Matrix von Zeilen und Spalten organisiert sind, dadurch gekennzeichnet, daß die Seiten des genannten Parallelogramms parallel zu Zeilen bzw. Spalten und die erwähnte quasiunendliche Gerade parallel zu einer der Seiten verlaufen.

5. Mehrprozessorrechnersystem nach Anspruch 3, dadurch gekennzeichnet, daß die Menge der Punktprozessoren in Teilmengen (166/174) mit je einem Hilfsspeicher (162) unterteilt ist und in einer Teilmenge die Punktprozessoren auf ein gemeinsames Teilbild einwirken, daß zwischen dem Empfangsspeicher und den damit über einen zyklisch abtast­ baren Demultiplexer verbundenen Hilfsspeichern ein Reduktionsprozessor (76) geschaltet ist, der aus der hier­ archischen Datenstruktur nacheinander vom höchsten hier­ archischen Pegel jeweils pegelweise die Relevanz des betreffenden Objektelements für das betreffende Teilbild bestimmt, bis eine Irrelevanz detektiert wird bzw. bis die Elementarobjektelemente erreicht sind, um nur jenen Teil der Datenstruktur, für den zumindest ein darin verbundenes elementares Objektelement als relevant detektiert wurde, einschließlich des Vorrats der als relevant detektierten elementaren Objektelemente auf den entsprechenden Hilfs­ speicher zu übertragen.

6. Mehrprozessorrechnersystem nach Anspruch 5, dadurch gekennzeichnet, daß die Relevanz zumindest teil­ weise durch ein Zusammenfallen des betreffenden Teilbilds und durch ein je Objektelement der Datenstruktur im Empfangsspeicher geschriebenes und dieses Objektelement umschließendes Rechteck gesteuert wird.

7. Mehrprozessorrechnersystem nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, daß zwischen der Menge der Punkt­ prozessoren und dem Darstellungselement ein doppelter Bildpufferspeicher (92/94) mit einem Empfangsteil zum Empfangen von Farbinformation für ein vollständiges Bild aus den Punktprozessoren und mit einem Ausgabeteil zum Aufnehmen der Farbinformation für ein vollständiges Bild und zum Abgeben an das Darstellungselement geschaltet ist, bis der Empfangsteil nach vollständiger Ausfüllung mit der Information eines Bilds als Ausgabeteil umgeschaltet und der bis dann wirkende Ausgabeteil als Empfangsteil umge­ schaltet wird.

8. Mehrprozessorrechnersystem nach Anspruch 1, dadurch gekennzeichnet, daß im Empfangsspeicher jedes Elementarobjektelement mit einer Prioritätsangabe versehen ist.

9. Mehrprozessorrechnersystem nach Anspruch 8 zum Darstellen einer dreidimensional organisierten Daten­ struktur in einer Zentralprojektion oder in einer Parallelprojektion, dadurch gekennzeichnet, daß für die darin als Polygone definierten Elementarobjektelemente eine implizite Priori­ tätsangabe durch die Vergleichsparameter des umschließen­ den Rechtecks gegeben ist, das stellenweise das betreffen­ de Elementarobjekt enthält, und daß bei nach der Projek­ tion auf die Szene stellenweise überlappenden Polygonen die Parameterwerte der Schnittpunkte der örtlich zugeord­ neten umschließenden Rechtecke mit der parameterisierten Geraden entlang der Projektionsrichtung und durch den betreffenden Projektionspunkt beim Vergleich dazwischen die relative Priorität explizit angeben.