DE3854600T2 - Verfahren zur Verwendung von baryzentrischen Koordinaten wie bei der Vieleckinterpolation. - Google Patents

Description

• Videospiele sind vielleicht die allgemein bekannteste Form einer Vorrichtung zur graphischen Datenverarbeitung bzw. einer Computergraphikvorrichtung (nachfolgend "Computergraphikvorrichtung" genannt). Das Gebiet umfaßt jedoch viele weitere Vorrichtungsformen, wie für Schulung, den Planung, Gestaltung usw. Typischerweise gibt eine solche Vorrichtung dem Betrachter den Eindruck, daß er durch ein Fenster auf ein Bild ähnlich dem eines Fernsehempfängers sieht. Um das Bild zu erzeugen, wählt das System zur graphischen Datenverarbeitung bzw. das Computergraphiksystem (nachfolgend "Computergraphiksystem" genannt) einen Inhalt aus Grundformen (Grundelementen) aus, orientiert die ausgewählten Stücke in bezug auf das Fenster und zeigt sie auf einem Betrachtungsschirm als eine Zusammensetzung an.
• Nach einer Technik wird der Bildinhalt aus Grundelementen wie Polygonen entwickelt, d.h. geschlossene, durch gerade Kanten begrenzte Umrisse. Solche Polygone definieren Umrisse von grauen oder farbigen räumlichen Flächen und werden verbunden, um ein Objekt oder einen Teil eines Objekts in der gewünschten Darstellung zu bilden. Normalerweise sind die Polygone mathematisch im dreidimensionalen Welt-Raum (world space) definiert. Die herkömmliche Grundpraxis umfaßt das Orientieren solcher Polygone in bezug auf einen Standpunkt, das Rastern der Polygone, um Daten für kleine einzelne Bildelemente (Pixel) zu definieren, das Eliminieren von Darstellungen verdeckter Flächen, dann das Darstellen der Pixel in einem Bildbereich auf einem zweidimensionalen Schirm. Im wesentlichen schließt die Rasterumwandlung eines Polygons das Auffinden aller Pixel, die innerhalb jedes Polygons liegen, und entsprechendes Festsetzen der Farbe und Intensität für jedes Pixel ein. Bei einer typischen Anzeige können eine Million Pixel ein Bild zusammensetzen.
• Nach früheren Computergraphiktechniken wird eine Bilddarstellung als Muster binärer Digitalzahlen gespeichert, die einzelne Pixel in einem rechteckigen Bereich darstellen. Die numerischen Daten, die einzelne Pixel darstellen, werden der Reihe nach einer Kathodenstrahlröhrenvorrichtung zugeführt, während der Röhrenbildschirm gerastert wird, um die Pixel in dem rechteckigen Bereich anzuzeigen. Folglich werden die Pixel in einem Rastermuster als eine Folge von Rasterzeilen gezeigt, von welchen jede aus einer Pixelreihe besteht. Das Rastermuster ist bei Fernsehbildschirmen bestens bekannt.
• Wie oben erwähnt, sind Computergraphiksysteme fähig, aus Grundelementen, die die Form ebener Polygone annehmen können, realistische Bilder bereitzustellen. Die Erzeugung solcher Bilder schließt auch das Unterteilen von Polygonen und das Auswählen von Abschnitten solcher Polygone ein, die für den Betrachter nicht versperrt sind und folglich in der Darstellung erscheinen. In dieser Hinsicht sind viele Techniken für verdeckte Flächen wohlbekannt. Zusammenfassend gestattet der gegenwärtige Stand der Technik in der Computergraphik die Erzeugung dynamischer realistischer Darstellungen durch Prozessoren, die die oben beschriebenen Techniken ausnutzen.
• Wenn andere geometrische Grundelemente als ebene Polygone zur Modelldefinition verwendet werden, werden die Grundelemente oft in ebene Polygone zerlegt, die danach zur Verarbeitung weiter in Dreieckpolygone zerlegt werden, um eine bessere Simulation bereitzustellen und verdeckte Flächen zu entfernen. Zum Beispiel kann eine gekrümmte oder parametrische Fläche eines Objekts der Darstellung durch Unterteilung zerlegt werden, wie es im Stand der Technik wohlbekannt ist und in US-Patent 4 646 251, erteilt am 24. Februar 1987, für Hayes, Brown, Jensen und Madsen behandelt wird.
• Während das Definieren ebener Polygonen zum Zusammensetzen eines Bilds erfolgreich ist, liefert die Technik noch ein unrealistisches Bild. Zum Beispiel ist es wünschenswert, daß die Darstellung eines Zylinders als Zylinder erscheint, nicht als eine Anordnung miteinander verbundener, diskreter, ebener Polygone, um einen Zylinder anzunähern. Solche Formen erlangen jedoch einen größeren Realismus, wenn sie über die Fläche verschiedener Polygone gleichmäßig abgetönt bzw. schraffiert (nachfolgend "abgetönt" genannt) sind. Die Technik ist in einem Buch mit dem Titel "Principles of Interactive Computer Graphics", 2. Aufl., Newman & Sproull, McGraw-Hill Book Company, 1979, dargestellt und beschrieben. Verschiedene spezielle Abtöntechniken sind auf dem Gebiet wohlbekannt, und in dieser Hinsicht beschreibt das zitierte Buch Abtöntechniken nach sowohl Gouraud als auch Phong.
• Die Technik nach Gouraud für ein gleichmäßiges Abtönen schließt das Berechnen von Normalen an den Scheitelpunkten bzw. Spitzen (nachfolgend "Scheitelpunkte" genannt) (Ecken) jedes Polygons, dann das Berechnen des genauen Farbtons an jedem der Scheitelpunkte ein. Dann wird eine Interpolation ausgeführt, um den Farbton für jedes das Polygon zergliedernde Pixel zu bestimmen. Herkömmlicherweise wird die Interpolation auf jedem Polygon ausgeführt, wie es im Bild- oder Bildschirmraum vorhanden ist. Das heißt, das Abtönen wird ausgeführt, nachdem Polygone vom Welt-Raum zum Bildraum transformiert wurden. In dieser Hinsicht siehe Kapitel 22 des zitierten Buchs "Principles of Interactive Computer Graphics" auf Seite 339, ein mit "Transformation in Viewing" überschriebener Abschnitt. Eine ähnliche Situation besteht hinsichtlich der Interpolation von Polygonen für das Abtönen nach Phong.
• Etwas zusammenfassend wurden herkömmlich ebene Polygone, wie sie vorhanden sind (zum Bild- oder Bildschirmraum transformiert), zum Abtönen oder Strukturieren interpoliert. Die Transformation von Polygonen vom Welt-Raum zu ihren zweidimensionalen Äquivalenten im Bildraum ist eine nichtlineare Projektion, d.h. dreidimensional zu zweidimensional. Als Folge ist das Interpolieren eines Polygons (zum Abtönen oder Strukturieren) nach der Transformation zum Bildraum ziemlich verschieden vom Interpolieren desselben Polygons im Welt-Raum. Obwohl herkömmlicherweise Polygone im Bildraum interpoliert wurden, ist eine solche Interpolation fehlerhaft und schreckt vom dargestellten Bild ab. In dieser Hinsicht basiert die vorliegende Erfindung auf der Erkenntnis, daß aus der Interpolation im Welt-Raum, das heißt einem Raum, der keiner linearen Verzerrung unterliegt, beträchtlich verbesserte Darstellungen resultieren. Diese Verbesserung kann auch durch Interpolation von Polygonen in anderen Räumen als dem Welt-Raum erhalten werden, welche keiner nichtlinearen Verzerrung des Bildraums unterliegen. Ein Beispiel eines weiteren Raums, der keiner nichtlinearen Verzerrung unterliegt, ist der Blickraum (eye space). In der Vergangenheit wurde jedoch angenommen, daß die Daten für eine solche Interpolation nicht wirtschaftlich verfügbar sind.
• Im allgemeinen ist das System der vorliegenden Erfindung als erfolgreiches Verfahren oder Produkt zum Interpolieren ebener Polygone verkörpert, um ein gleichmäßiges Abtönen (oder Strukturieren) für ein durch die Polygone definiertes Objekt zu erreichen. Eine Interpolation gemäß der vorliegenden Erfindung wird auf ebenen Polygonen ausgeführt, die im Welt-Raum definiert sind, und ermöglicht dadurch verbesserte Darstellungen. Besonders in dieser Hinsicht ermöglicht das System der vorliegenden Erfindung Interpolationen im Welt-Raum durch Verwendung von Daten in unkonventionellen Kombinationen. Wie ausführlich unten offenbart, wurden insbesondere leicht verfügbare Vektoren entdeckt, die einer Verarbeitung als Skalarprodukte und Kreuzprodukte zugänglich sind, um die Interpolation eines Polygons im Welt-Raum auszuführen und folglich aus solchen Polygonen zusammengesetzte Objekte erfolgreich abzutönen oder zu strukturieren.
• Gemäß der vorliegenden Erfindung wird ein Verfahren zum Interpolieren eines graphischen Objekts, wie in Anspruch 1 dargelegt, ein System zum Interpolieren eines graphischen Objekts, wie in Anspruch 8 dargelegt, und ein Verfahren zum Bestimmen von Pixeldaten, wie in Anspruch 9 dargelegt, bereitgestellt.
Kurze Beschreibung der Zeichnungen
• In den Zeichnungen, die einen Teil dieser Beschreibung ausmachen, sind beispielhafte Ausführungsformen dargelegt, die verschiedene Ziele und Merkmale hiervon zeigen, insbesondere ist:
• Fig. 1 eine graphische Darstellung einer gekrümmten Fläche, die in bezug auf eine Polygonzerlegung und Scheitelpunktnormalisierung (vertex normalization) dargestellt ist, wie zum Abtönen in Übereinstimmung hiermit;
• Fig. 2 eine graphische Darstellung, die einen Betrachtungsstumpf, der sich von einem Augenpunkt bzw. Blickpunkt (nachfolgend "Blickpunkt" genannt) aus radial ausbreitet, in bezug auf den Bildraum und den Welt-Raum darstellt, wie hierin behandelt;
• Fig. 3 eine graphische Darstellung, die baryzentrische Koordinaten in bezug auf ein Polygon darstellt, wie hierin entwickelt;
• Fig. 4 eine graphische Darstellung, die Vektoren zur Berechnung baryzentrischer Koordinaten für ein Polygon gemäß der vorliegenden Erfindung darstellt;
• Fig. 5 eine graphische Darstellung, die ein Fünfeckpolygon darstellt, das ein Dreieckpolygon enthält, wie hierin diskutiert;
• Fig. 6 eine graphische Darstellung, die ein Dreieckpolygon in Verbindung mit einer quadratischen Bezier-Fläche darstellt, wie hierin diskutiert;
• Fig. 7 ein Flußdiagramm, die ein Verfahren gemäß der vorliegenden Erfindung darstellt; und
• Fig. 8 ein Blockdiagramm einer Anordnung gemäß der vorliegenden Erfindung.
Beschreibung der erläuternden Ausführungsform
• Hierin ist eine ausführlich erläuternde Ausführungsform der vorliegenden Erfindung offenbart; sie ist jedoch nur repräsentativ in Anbetracht der Tatsache, daß eine breite Vielfalt spezieller Ausführungsformen des offenbarten Systems möglich ist. Dennoch wird die erläuternde Ausführungsform für die gehalten, die zum Zwecke der Offenbarung und zur Bereitstellung einer Basis für die Ansprüche hierin, welche den Schutzumfang der vorliegenden Erfindung definieren, die beste Ausführungsform ist.
• Zuerst ist die Betrachtung einiger graphischer Darstellungen hilfreich, wie sie mit der vorliegenden Entwicklung zusammenhängen, insbesondere hinsichtlich der Zerlegung von Kegelschnitten in ebene Polygone. In Fig. 1 ist eine gekrümmte Außenfläche, die ein Stück 10 eines Zylinders umfaßt, in halbfetten Linien dargestellt. Das zylindrische Stück 10 ist grob durch ein Paar ebener Polygone 12 und 14 simuliert, die in feinen Linien dargestellt sind. Um die Gestalt des Zylinderstücks 10 besser anliegend zu simulieren, könnte eine erhöhte Anzahl ebener Polygone verwendet werden. Für die Zwecke der vorliegenden Erläuterung ist jedoch zu sehen, daß zwei ebene Polygone 12 und 14 eine zylindrische Fläche grob simulieren. Folglich wurde ein wenig Annäherung erreicht. Die relativ großen Polygone 12 und 14 sind für die folgende Erläuterung bequem und nützlich.
• Es ist zu bemerken, daß jedes der Polygone eine gleichmäßige Intensität oder einen Farbton besitzt, die bzw. der die Abtönung für eine Hälfte des gekrümmten Stücks 10 annähert. Bei einer unteren frontalen Beleuchtung der Außenfläche, wie dargestellt, ist das Polygon 12 dunkler abgetönt als das Polygon 14. Techniken eines solchen Abtönens sind in Kapitel 25 des oben zitierten Buchs, "Principles of Interactive Computer Graphics" beschrieben.
• Während ein gleichmäßiges Abtönen der einzelnen, ein Objekt definierenden Polygone einigen Realismus verleiht, neigen solche Darstellungen dazu, als Stückwerk zu erscheinen. Für einen größeren Realismus wurde vorgeschlagen, die Polygone über die gesamte Fläche des simulierten Objekts gleichmäßig abzutönen. Techniken zum Erreichen eines gleichmäßigen Abtönens sind in dem oben zitierten Buch in Kapitel 25 behandelt und können das Interpolieren der Normalen an den Scheitelpunkten jedes Polygons einschließen. Es ist zu bemerken, daß die Flächennormalenvektoren an den Scheitelpunkten der Polygone 12 und 14 allgemein durch Pfeile 16 und 18 angegeben sind. Es ist zu bemerken, daß die Fläche des zylindrischen Stücks 10 an den Polygonscheitelpunkten mit den Polygonen 12 und 14 zusammenfällt.
• Eine gleichmäßige Abtönung kann das Verbinden jedes Polygonscheitelpunktes mit dem entsprechenden Flächennormalenvektor einschließen, wie in Fig. 1 dargestellt. Ein Normalenvektor wird an jedem Punkt auf der Innenseite des Polygons unter Verwendung der mit den Polygonscheitelpunkten verbundenen Flächennormalenvektoren interpoliert. Wie oben erwähnt, wird die Interpolation von Normalenvektoren Abtönung nach Phong genannt. Eine einfachere Technik wird Abtönen nach Gouraud genannt, bei der eher als Normalenvektoren die Helligkeit interpoliert wird. Jedenfalls schließen sowohl diese als auch andere Formen des Abtönens die Interpolation von Polygonmerkmalen ein. Bei einer solchen Interpolation kann die Variation des Farbtons von der Oberkante 20 des Stücks 10 zur Unterkante 22 gleichmäßig sein, was dazu beiträgt, der gekrümmten Fläche eine realistischere Erscheinung zu verleihen.
• Manchmal ist es wünschenswert, andere Größen als Normalenvektoren und Helligkeiten für Polygone zu interpolieren. Zum Beispiel könnte eine Fläche mit einer Struktur bedeckt sein, die in der Darstellung erscheinen soll. Im allgemeinen wird in der Computergraphik das Verfahren des Auflegens solcher Muster auf Flächen "Strukturabbildung" genannt und ist in dem oben zitierten Buch, "Principles of Interactive Computer Graphics", in Kapitel 25 behandelt. Eine Strukturabbildung schließt im wesentlichen das Festsetzen einer Struktur an Polygonen ein und wird durch ein interpolierendes Verfahren ausgeführt, das zum gleichmäßigen Abtönen analog ist.
• Zusammenfassend schließen wiederum sowohl das gleichmäßige Abtönen als auch die Strukturabbildung eine Interpolation von Polygonmerkmalen ein. Das Abtönen nach Gouraud schließt die Interpolation der Helligkeit (Intensität), einer eindimensionalen Größe, ein. Das Abtönen nach Phong schließt die Interpolation von Normalenvektoren, dreidimensionaler Größen, ein. Eine Strukturabbildung schließt eine Interpolation von Strukturmustern ein, die typischerweise in einem X,Y-Koordinatensystem definierte Größen sind. Folglich schließen das Abtönen nach Gouraud, die Strukturabbildung bzw. das Abtönen nach Phong die Interpolation ein-, zwei- und dreidimensionaler Größen ein. Gemäß der vorliegenden Erfindung wird eine verbesserte Interpolation von Polygonen zur Darstellung im die Polgone definierenden, dreidimensionalen Welt-Raum-Koordinatensystem ausgeführt. Eine solche Interpolation vermeidet die nichtlinearen Eigenschaften einer Interpolation in der prespektivischen Projektion. Die Funktion des vorliegenden Systems ist in Fig. 2 dargestellt und wird nun ausführlich betrachtet.
• Ein Polygon 24 in Form eines Dreiecks ist im Welt-Raum dargestellt (Fig. 2, oben links). Nach den herkömmlichen Techniken werden die Scheitelpunkte des Polygons 24 auf einen Ursprung (nicht gezeigt) im Welt-Raum bezogen. Der Ursprung des Welt- Raums wird mit Beziehung zu einem Augenpunkt bzw. Blickpunkt (nachfolgend "Blickpunkt" genannt) O festgelegt (Fig. 2, unten rechts). Unter Verwendung herkömmlicher Verfahren kann das Polygon 24 leicht auf den Blickpunkt O in Form von dreidimensionalen Koordinaten bezogen werden; siehe das zitierte Buch, "Principles of Interactive Computer Graphics", auf Seite 339.
• Wie oben allgemein erläutert wurde, wird, um das Polygon 24 (das eine von mehreren Komponenten einer Darstellung veranschaulicht) von dem Blickpunkt O aus betrachten, das Polygon auf eine Betrachtungsebene oder einen Schirm 28 im zweidimensionalen Bildraum transformiert; siehe das zitierte Buch, "Principles of Interactive Computer Graphics", auf Seite 341. Nach einer Übereinkunft umfaßt der Schirm 28 die Basis eines Betrachtungs-Pyramidenstumpfs 30 mit dem Scheitelpunkt 32 am Blickpunkt O. Gewissermaßen kann der Betrachtungsschirm 28 (an der Basis des Stumpfes 30) zum Schirm einer Fernsehanzeige analogisiert werden, durch welchen Objekte im Welt-Raum (wie das Polygon 24) betrachtet werden.
• Gemäß der wohlbekannten herkömmlichen Praxis ist der zweidimensionale Bildraum des Schirms 28 in kleine Bildelemente oder Pixel zergliedert. Es kann zum Beispiel eine Million Pixel zu einem Feld von eintausend Reihen mit jeweils tausend Pixeln arrangiert werden. Ein repräsentatives Pixel 34 ist an einem zentralen Ort des Schirms 28 dargestellt. Es ist zu bemerken, daß sich ein Strahl 36 vom Blickpunkt O durch den Mittelpunkt des Pixels 34 hindurchgehend zum Punkt P erstreckt. Der Strahl 36 veranschaulicht Tausende solcher Strahlen, die das Bild in Pixel zergliedern. Jeder Betrachtungsstrahl 36 ist durch ein Pixel auf dem Schirm 28 definiert, setzt sich dann über den Schirm 28 (Pixelschnittpunkt) hinaus fort und kann Polygone im Welt-Raum schneiden, der die Grundelemente zum Bilden eines Objekts oder Modells umfaßt. Im vereinfachten Beispiel der Fig. 2 setzt sich der Betrachtungsstrahl 36 nach dem Durchgang durch das Pixel 34 am Punkt C so fort, daß er das Polygon 24 an einem Punkt P schneidet. Es ist an dieser Stelle beachtenswert, daß der Ort des Polygonschnittpunktes P nicht in Form von Koordinaten bekannt ist. Wäre der Punkt P definiert, könnte das Polygon im Welt-Raum interpoliert werden; dies ist jedoch nicht der Fall. In Übereinstimmung hiermit wurde jedoch entdeckt, daß Daten verfügbar sind, um die Interpolation in einem wirtschaftlichen System auszuführen. Eine solche Interpolation ermöglicht ein erfolgreiches gleichmäßiges Abtönen und eine Strukturabbildung.
• In Übereinstimmung hiermit schließt das Behandeln des Punktes P und folglich das Interpolieren des Polygons 24 als Dreieck die Verwendung baryzentrischer Koordinaten ein, wie sie auf dem Gebiet der Computergraphik wohlbekannt sind. Insbesondere sind baryzentrische Koordinaten in einem Dokument mit dem Titel "Representation and Approximation of Surfaces" von Robert E. Barnhill behandelt, das in Mathematical Software III, 1977, von Academic Press, Inc. veröffentlicht, erschien. Es werden nun einige grundlegende Erläuterungen baryzentrischer Koordinaten gegeben, wie sie hierin verwendet werden.
• Fig. 3 zeigt ein Dreieckpolygon 24 in einer ebenen Ansicht. Es wird angenommen, daß die Punkte P&sub1;, P&sub2; und P&sub3; in einem dreidimensionalen Welt-Raum-Koordinatensystem definiert sind. Es ist zu bemerken, daß, wie oben beschrieben, der Punkt P in der Ebene des Polygons liegt. Es ist zu erkennen, daß der Punkt P, durch P&sub1;, P&sub2; und P&sub3; ausgedrückt, unter Verwendung der Gleichung P = b&sub1;P&sub1; + b&sub2;P&sub2; + b&sub3;P&sub3; definiert werden kann, wobei b&sub1;, b&sub2; und b&sub3; die baryzentrischen Koordinaten des Punktes P genannt werden. Es ist zu bemerken, daß der Punkt P durch einen eindeutigen Satz baryzentrischer Koordinaten definiert ist, und ferner, daß die Koordinaten b&sub1; + b&sub2; + b&sub3; = 1 sind. Die Gleichung bedeutet, daß durch Anwendung baryzentrischer Koordinaten der Punkt P als Linearkombination der Punkte P&sub1;, P&sub2; und P&sub3; berechnet werden kann. Wenn zum Beispiel b&sub1;=1, b&sub2;=0 und b&sub3;=0 sind, liegt der definierte Punkt am Scheitelpunkt P&sub1;.
• Wenn als weiteres einfaches Beispiel b&sub1;=1/3, b&sub2;=1/3 und b&sub3;=1/3 sind, liegt der Punkt P im Mittelpunkt des Dreieckpolygons 24.
• Zur weiteren Behandlung baryzentrischer Koordinaten sind die folgenden Definitionen zu betrachten:
• Wie in Fig. 3 dargestellt, ist A die Fläche des Dreiecks P&sub1;P&sub2;P&sub3; (Polygon 24), A&sub1; ist die Fläche des Dreiecks PP&sub2;P&sub3;, A&sub2; ist die Fläche des Dreiecks PP&sub3;P&sub1; und A&sub3; ist die Fläche des Dreiecks PP&sub1;P&sub2;.
• Die baryzentrischen Koordinaten für das Dreieck P&sub1;P&sub2;P&sub3; können berechnet werden als:
• b&sub1; = A&sub1;/A
• b&sub2; = A&sub2;/A
• b&sub3; = A&sub3;/A.
• Wie in dem oben zitierten Dokument von Barnhill offenbart, können, da aus einer Prüfung der Fig. 3 offensichtlich ist, daß
• A = A&sub1; + A&sub2; + A&sub3; ist,
• die baryzentrischen Koordinaten ausgedrückt werden als:
• b&sub1; = A&sub1;/(A&sub1; + A&sub2; + A&sub3;)
• b&sub2; = A&sub2;/(A&sub1; + A&sub2; + A&sub3;)
• b&sub3; = A&sub3;/(A&sub1; + A&sub2; + A&sub3;)
• Bei der Anwendung der obigen Gleichungen ist es beachtenswert, daß, obwohl Fig. 3 den Punkt P innerhalb des Dreiecks P&sub1;P&sub2;P&sub3; (Polygon 24) darstellt, die baryzentrischen Gleichungen anwendbar sind, wenn der Punkt P irgendwo in der Ebene des Dreiecks liegt, sogar wenn der Punkt P außerhalb des Dreiecks liegt. Somit ist die Bestimmung des Punktes P in baryzentrischen Koordinaten zur Ermöglichung einer Interpolation allgemein und kann ebenfalls auf nicht dreieckige Polygone angewendet werden. Es wird zum Beispiel Fig. 5 betrachtet, die ein Fünfeck P&sub1;P&sub2;P&sub3;P&sub4;P&sub5; zeigt. Irgendein Dreieck innerhalb dieses Fünfecks (wie dargestellt), beispielsweise P&sub1;P&sub3;P&sub4;, kann zur Berechnung baryzentrischer Koordinaten b&sub1;, b&sub2; und b&sub3; verwendet werden. Diese baryzentrischen Koordinaten können dann verwendet werden, um das gesamte Polygon zu interpolieren. Weiterhin kann mit der Fähigkeit, jeden der Pixelstrahlpunkte, wie den Punkt P im Polygon 24, unter Verwendung baryzentrischer Koordinaten zu ermitteln, das Polygon abgetönt oder die Struktur abgebildet werden.
• An dieser Stelle sollten einige Übereinkünfte erwähnt werden, die verwendet werden, um der Erläuterung zu folgen.
• Ein Vektor ist durch die Komponenten des Vektors angegeben, die in Klammern gesetzt und durch Kommata getrennt sind. Wenn zum Beispiel der Punkt P (Fig. 3) in einem dreidimensionalen Koordinatensystem definiert wäre, könnte der Vektor vom Ursprung zum Punkt P durch (x,y,z) unter Verwendung der x-, y- und z-Koordinaten des Punktes P dargestellt werden. Die baryzentrischen Koordinaten des Punktes P werden ein wenig analog durch den Vektor (b&sub1;,b&sub2;,b&sub3;) dargestellt.
• Nun wird die Berechnung der baryzentrischen Koordinaten des Polygons 24 in Übereinstimmung hiermit erläutert. In Fig. 4 ist das Dreieck P&sub1;P&sub2;P&sub3; (Polygon 24) im dreidimensionalen Raum mit Strahlen RA gezeigt, die sich vom Blickpunkt 32 zu den Scheitelpunkten P, P&sub1;, P&sub2; und P&sub3; erstrecken. Beim Betrachten der Figur wird eine Vektornotation eingesetzt, bei der dem Ausgangspunkt eines Vektors der Endpunkt folgt, wobei beide Punkte fettgedruckt sind. Folglich ist der Vektor vom Punkt O (Blickpunkt 32) zum Punkt P mit OP bezeichnet.
• Wir denken normalerweise von Punkten als durch Koordinaten in einem Kartesischen Koordinatensystem bestimmt. Wenn jedoch O bei (xo,yo,zo) und P bei (xp,yp,zp) liegt, dann kann OP durch:
• OP = [(xp - xo)(yp - yo)(zp - zo)]
• dargestellt werden.
• Die Handhabung von Vektoren im Zusammenhang mit Computergraphik ist in einem Anhang I des oben zitierten Buchs, "Principles of Interactive Computer Graphics" behandelt. Es sind insbesondere dreidimensionale Vektoroperationen, einschließlich Skalarprodukten und Kreuzprodukten, wie sie unten verwendet werden, erläutert und beschrieben.
• In Fig. 4 geht der Vektor OP (vom Ursprung O oder Blickpunkt 32 zum Punkt P) durch den Punkt C hindurch, der sich in der Ebene des zweidimensionalen Schirms 28 befindet (Fig. 2 und 4). Insbesondere ist der Punkt C (Fig. 4) der Mittelpunkt des Pixels 34. Die Fortsetzung des Vektors OC (über den Punkt C hinaus) schneidet das Polygon 24 am Punkt P, so daß der Vektor OP definiert wird. Da die Koordinaten des Polygons 24 bekannt sind, gelten die folgenden Definitionen:
• V ist das Volumen des Tetraeders OP&sub1;P&sub2;P&sub3; , dessen Basis das Dreieck P&sub1;P&sub2;P&sub3; mit der Fläche A ist,
• V&sub1; ist das Volumen des Tetraeders OPP&sub2;P&sub3; , dessen Basis das Dreieck PP&sub2;P&sub3; mit der Fläche A&sub1; ist,
• V&sub2; ist das Volumen des Tetraeders OPP&sub3;P&sub1; , dessen Basis das Dreieck PP&sub3;P&sub1; mit der Fläche A&sub2; ist,
• V&sub3; ist das Volumen des Tetraeders OPP&sub1;P&sub2; , dessen Basis das Dreieck PP&sub1;P&sub2; mit der Fläche A&sub3; ist.
• Ferner werden die folgenden ergänzenden Definitionen gemacht:
• T ist das Tripelprodukt der Vektoren OP&sub1;, OP&sub2; und OP&sub3;,
• T&sub1; ist das Tripelprodukt der Vektoren OP, OP&sub2; und OP&sub3;,
• T&sub2; ist das Tripelprodukt der Vektoren OP, OP&sub3; und OP&sub1;,
• T&sub3; ist das Tripelprodukt der Vektoren OP, OP&sub1; und OP&sub2;.
• Folglich gelten, aus dem obigen, die folgenden Beziehungen:
• V = T/6
• V&sub1; = T&sub1;/6
• V&sub2; = T&sub2;/6
• V&sub3; = T&sub3;/6
• Diese Beziehungen sind in einem Buch von Paul J. Kelly und Ernst G. Straus mit dem Titel "Elements of Analytic Geometry" (Seiten 144-145), herausgegeben von Scott, Foresman & Co., 1970, diskutiert. Das Buch führt weiterhin die Binsenwahrheit an, daß das Volumen eines Tetraeders gleich einem Drittel des Produktes seiner Grundfläche mal seiner senkrechten Höhe ist. Da die Basen der vier oben genannten Tetraeder einfach die Dreiecke sind, deren Flächen A, A&sub1;, A&sub2; und A&sub3; sind, gelten die folgenden Beziehungen:
• V = hA/3
• V&sub1; = hA&sub1;/3
• V&sub2; = hA&sub2;/3
• V&sub3; = hA&sub3;/3.
• In den obigen Gleichungen ist h die senkrechte Höhe von der Ebene des Dreiecks P&sub1;P&sub2;P&sub3; zum Punkt O. Verbinden der obigen, in V, V&sub1;, V&sub2; und V&sub3; ausgedrückten Gleichungen ergibt:
• A = T/2h
• A&sub1; = T&sub1;/2h
• A&sub2; = T&sub2;/2h
• A&sub3; = T&sub3;/2h.
• Ferner ergibt das Verbinden der baryzentrischen Gleichungen mit den obigen:
• b&sub1; = T&sub1;/(T&sub1; + T&sub2; + T&sub3;)
• b&sub2; = T&sub2;/(T&sub1; + T&sub2; + T&sub3;)
• b&sub3; = T&sub3;/(T&sub1; + T&sub2; + T&sub3;).
• An diesem Punkt ist es wichtig zu erkennen, daß die obigen Gleichungen nützlich wären, mit Ausnahme der Tatsache, daß T&sub1;, T&sub2; und T&sub3; unter Verwendung des Vektors OP berechnet wurden und die Koordinaten des Punktes P (Fig. 4) nicht bekannt sind. Eine Entdeckung der vorliegenden Erfindung überwindet jedoch das Problem. Es kann durch Untersuchung der Fig. 4 gesehen werden, daß der Vektor OP zum Vektor OC proportional ist. Das heißt, OP = qOC, wobei q eine Proportionalitätskonstante oder ein Skalar, wenn auch unbekannt, ist.
• Angesichts des obigen und im Interesse des Vorgehens wird die Definition der folgenden drei Tripelprodukte betrachtet:
• K&sub1; ist das Tripelprodukt der Vektoren OC, OP&sub2; und OP&sub3;,
• K&sub2; ist das Tripelprodukt der Vektoren OC, OP&sub3; und OP&sub1;,
• K&sub3; ist das Tripelprodukt der Vektoren OC, OP&sub1; und OP&sub2;.
• Folglich sind die folgenden Beziehungen wahr:
• T&sub1; = qK&sub1;
• T&sub2; = qK&sub2;
• T&sub3; = qK&sub3;.
• Die obigen Gleichungen sind wahr, weil das Multiplizieren eines der Vektoren in einem Tripelprodukt mit einem Skalar, wie q, im Multiplizieren des Wertes des Tripelprodukts mit demselben Skalar resultiert. Folglich ergibt das Verbinden der Gleichungen für die baryzentrischen Koordinaten das folgende nützliche Ergebnis, bei dem der unbekannte Skalar, q, herausgefallen ist.
• b&sub1; = K&sub1;/(K&sub1; + K&sub2; + K&sub3;)
• b&sub2; = K&sub2;/(K&sub1; + K&sub2; + K&sub3;)
• b&sub3; = K&sub3;/(K&sub1; + K&sub2; + K&sub3;).
• Die besondere Signifikanz der obigen Gleichungen ist die Tatsache, daß K&sub1;, K&sub2; und K&sub3; unter Verwendung bekannter Vektoren OC, OP&sub1;, OP&sub2; und OP&sub3; (Fig. 4) berechnet werden, die alle in den Graphikberechnungen leicht verfügbar sind. Das heißt, daß die Scheitelpunkte P&sub1;, P&sub2; und P&sub3; zusammen mit den Koordinaten des Punktes O und des Punktes C bekannt sind. Während der Ort des Punktes P nicht bekannt ist, wie oben mathematisch entwickelt, kann der Vektor OC eher eingesetzt werden, als der Vektor OP, der unbekannt ist. Somit sind die baryzentrischen Koordinaten für den Punkt P durch die obigen nützlichen Gleichungen festgelegt und können folglich erfolgreich eingesetzt werden, um alle Strahlenpunkte auf dem Polygon 24 für Pixel zu interpolieren.
• Es wird ein spezielles Beispiel betrachtet. Wenn einmal die baryzentrischen Koordinaten b&sub1;, b&sub2; und b&sub3; durch K&sub1;, K&sub2; und K&sub3; ausgedrückt berechnet sind, können sie zur Interpolation und folglich zum gleichmäßigen Abtönen verwendet werden. Es wird zum Beispiel angenommen, daß ein Abtönen nach Gouraud mit der Folge, daß eine Intensität mit jedem der Punkte P&sub1;, P&sub2; und P&sub3; verbunden ist, erwünscht ist (Fig. 4). Die drei Intensitätswerte können durch den Vektor (i&sub1;,i&sub2;,i&sub3;) angegeben werden. Dann kann die Intensität i am Punkt P linear als:
• i = b&sub1;i&sub1; + b&sub2;i&sub2; + b&sub3;i&sub3; interpoliert werden.
• Da die obige Gleichung tatsächlich nur ein Skalarprodukt ist und da die baryzentrischen Koordinaten selbst als ein Vektor dargestellt werden können (wie oben vorgeschlagen), kann alternativ die Gleichung als: i = (b&sub1;,b&sub2;,b&sub3;) (i&sub1;,i&sub2;,i&sub3;) neu geschrieben werden. Folglich kann das Polygon 24 durch Rasterwandlung, um die Orte der Pixel (zum Beispiel des Pixelmittelpunktes C) zu bestimmen, gleichmäßig abgetönt werden; siehe das zitierte Buch, "Principles of Interactive Computer Graphic", in Kapitel 16. Die Farbtonintensität kann dann für jedes Pixel entwickelt werden, indem die Gleichung:
• i = b&sub1;i&sub1; + b&sub2;i&sub2; + b&sub3;i&sub3;
• angewendet wird.
• Das Abtönen nach Phong kann unter Verwendung einer ähnlichen Technik erreicht werden, außer daß anstelle des Interpolierens eines einzigen Intensitätswerts für jedes Pixel, z.B. am Punkt P, die drei Komponenten des Flächennormalenvektors für jedes Pixel gemäß der Abtönungstechnik nach Phong interpoliert werden.
• Baryzentrische Koordinaten können auch für eine Strukturabbildung verwendet werden. Es wird insbesondere die Existenz einer mit jedem der Punkte P&sub1;, P&sub2; und P&sub3; verbundenen x,y-Koordinate der Struktur angenommen (Fig. 4). Diese drei x,y-Koordinaten der Struktur können durch die Vektoren (tx&sub1;,tx&sub2;,tx&sub3;) und (ty&sub1;,ty&sub2;,ty&sub3;) angegeben werden. Die x,y-Koordinaten der Struktur tx und ty am Punkt P können linear interpoliert werden als:
• tx = (b&sub1;,b&sub2;,b&sub3;) (tx&sub1;,tx&sub2;,tx&sub3;)
• ty = (b&sub1;,b&sub2;,b&sub3;) (ty&sub1;,ty&sub2;,ty&sub3;).
• Das Anwenden der obigen Gleichungen für jedes Pixel ordnet für eine konsistente und erfolgreiche Abbildung die Struktur dem Polygon zu. Somit ermöglicht das System der vorliegenden Erfindung Anwendungen der Polygoninterpolation für verbesserte Computergraphikabbildungen.
• Es ist möglich, baryzentrische Koordinaten zu verwenden, um andere Interpolationen als eine Linearinterpolation auszuführen. Zum Beispiel beschrieb die obige Diskussion einer Intensitätsinterpolation eine mittels eines Skalarprodukts erreichte Linearinterpolation. Fig. 6 stellt jedoch eine Intensitätsinterpolation unter Verwendung einer quadratischen Interpolation dar. In Fig. 6 ist das Dreieck P&sub1;P&sub2;P&sub3; (Polygon 24) übereinanderliegend mit einer quadratischen Bezier-Fläche 26 gezeigt, die durch Intensitätswerte i&sub1; bis i&sub6; definiert ist. Die Intensitätswerte i&sub1;, i&sub2; und i&sub3; liegen auf der Fläche, während die Intensitätswerte i&sub4;, i&sub5; und i&sub6; in Übereinstimmung mit der Standarddefinition einer quadratischen Bezier-Fläche nahe der Fläche liegen. Bezier-Flächen sind im Stand der Technik wohlbekannt und in US-Patent 4 646 251, erteilt am 24. Februar 1987 für Hayes, Brown, Jensen und Madsen, behandelt. Die Intensitätsfläche 26 definiert die Weise, in welcher eine quadratische Interpolation der Intensität auf dem Polygon 24 berechnet werden soll. Insbesondere ist die Intensität i am Punkt P auf dem Polygon durch die folgende Gleichung gegeben: i = i&sub1;b&sub1;² + i&sub2;b&sub2;² + i&sub3;b&sub3;² + i&sub4;b&sub2;b&sub3; + i&sub5;b&sub3;b&sub1; + i&sub6;b&sub1;b&sub2;. Bezier-Interpolationsformeln sind im Stand der Technik wohlbekannt und auf Seite 38 eines Dokuments mit dem Titel "A survey of curve and surface methods in CAGD" von Wolfgang Bohm, Gerald Farin und Jurgen Kahmann, erschienen in Computer Aided Geometric Design, 1984, herausgegeben von Elsevier Science Publishers B.V., beschrieben. In einer zu der für die quadratische Bezier-Interpolation gezeigten analogen Weise können baryzentrische Koordinaten verwendet werden, um eine Interpolation eines Grades größer oder gleich Eins auszuführen.
• Typischerweise schließt bei der Berechnung von Bildern, die Algorithmen für verdeckte Flächen anwenden, jedes Polygon verschiedene Pixel ein. In den obigen Gleichungen, die b&sub1;, b&sub2; und b&sub3; durch K&sub1;, K&sub2; und K&sub3; ausgedrückt definieren, sind zum gleichmäßigen Abtönen und zur Strukturabbildung jedes Pixels pro Pixel drei Tripelprodukte nötig. Da ein Tripelprodukt die Determinante einer Drei-mal-drei-Matrix ist, erfordert die Berechnung dreier Tripelprodukte die Berechnung dreier solcher Determinanten; ein beträchtlicher Umfang an Berechnungen. Alternativ ist es jedoch möglich, ein Tripelprodukt als ein Skalarprodukt und ein Kreuzprodukte auszudrücken. In dieser Hinsicht können die Größen K&sub1;, K&sub2; und K&sub3; unter Verwendung von Kreuzprodukten und Skalarprodukten wie folgt ausgedrückt werden:
• K&sub1; = OC [OP&sub2; x OP&sub3;]
• K&sub2; = OC [OP&sub3; x OP&sub1;]
• K&sub3; = OC [OP&sub1; x OP&sub2;].
• Kreuzprodukte und Skalarprodukte sind in Anhang 1 des oben zitierten Buchs, "Principles of Interactive Computer Graphics", behandelt. Es ist zu bemerken, daß für ein bestimmtes Bild der Punkt O am Blickpunkt konstant ist. Für ein bestimmtes Bild sind ebenfalls die Punkte P&sub1;, P&sub2; und P&sub3; für jedes Polygon konstant. Daher sind für jedes Polygon die Vektoren OP&sub1;, OP&sub2; und OP&sub3; konstant und ebenfalls die in den obigen Gleichungen gezeigten Kreuzprodukte dieser Vektoren. Folglich können diese Produkte einmal pro Polygon pro Bild berechnet und gespeichert werden. Danach muß, um ein gleichmäßiges Abtönen und eine Strukturabbildung, eine Interpolation an einem bestimmten Pixel auszuführen, der Vektor OC erzeugt und als Skalarprodukt mit den drei bereits berechneten Kreuzproduktwerten von OP&sub1;, OP&sub2; und OP&sub3; verbunden werden. In dieser Weise werden die baryzentrischen Koordinaten berechnet. Es ist zu bemerken, daß dieser Ansatz erfolgreich die an jedem Pixel erforderliche Berechnung reduziert, indem drei Skalarprodukte anstelle von drei Tripelprodukten ausgeführt werden. Als weiterer Vorteil erfordert das System hierdurch zum Entwickeln der baryzentrischen Koordinaten die gleiche Art von Berechnungen wie die Interpolation, d.h. Skalarprodukte. Eine Reduzierung der erforderlichen Berechnung für jedes Pixel auf eine geringe Anzahl von Skalarprodukten hilft, die Berechnung homogen zu machen und dadurch die für die Berechnung erforderliche Computerhardware zu vereinfachen.
• Es ist oft wünschenswert, den Abstand des Blickpunkts O (Fig. 2) zum Punkt P auf dem Polygon 24 zu berechnen. Zum Beispiel kann der Abstand OP verwendet werden, um einen Schleier als Teil der Berechnung eines gleichmäßigen Abtönens zu simulieren. Ein Verfahren zum Berechnen dieses Abstands ist es, die Gleichungen für K&sub1;, K&sub2; und K&sub3; zu verwenden, um baryzentrische Koordinaten zu berechnen; dann die oben genannte Gleichung P = b&sub1;P&sub1; + b&sub2;P&sub2; + b&sub3;P&sub3; zu verwenden, aus welcher die x,y,z-Koordinaten verwendet werden können, um den Punkt P zu berechnen, nach dem der Vektor OP berechnet werden kann.
• Das Verfahren zum Interpolieren von Polygonen in Übereinstimmung hiermit ist in Fig. 5 dargestellt. Das Verfahren der verdeckten Flächen kann verschieden von oder eng mit dem Interpolationsverfahren verbunden sein, was beides allgemein als Teil der erforderlichen Hardware in Abbildungsprozessoren bzw. Anzeigeprozessoren betrachtet wird. Typischerweise wird die Anordnung verwendet, um räumliche Flächen zu rastern, wobei sie in einzelne Pixel zergliedert werden. Folglich würden mit der vorliegenden Entwicklung die Daten für ein gleichmäßiges Abtönen für die einzelnen Pixel bestimmt und in einen Pufferspeicher eingetragen. Das Verfahren hiervon ist jedoch in Fig. 5 unabhängig von Polygonprioritäten oder dem Lösen von Fragen der verdeckten Oberflächen dargestellt.
• In Fig. 7 ist der erste Block mit "Rufe Polygondaten ab" bezeichnet. Im wesentlichen können Polygone nacheinander behandelt werden, und in dieser Hinsicht können die Polygone in Übereinstimmung mit wohlbekannten Techniken aus dem Stand der Technik auf einzelne Dreiecke reduziert worden sein, und, wie oben angegeben, können die Prioritäten verdeckter Flächen unabhängig behandelt werden.
• Das Polygon wird als Dreieck angenommen, wobei verfügbare Daten der Scheitelpunkte P&sub1;, P&sub2; und P&sub3; bestimmt werden, wie durch Block 52 angegeben.
• Als nächster Schritt, der durch Block 54 dargestellt ist, werden die Vektoren OP&sub1;, OP&sub2; und OP&sub3; berechnet und zum Gebrauch während der ganzen Verarbeitung des gegenwärtigen Dreiecks gespeichert.
• Wie durch den Block 56 angegeben, schließt der nächste Schritt das Berechnen der Scheitelpunktintensitäten aus den Polygondaten ein. Insbesondere werden die Intensitäten i&sub1;, i&sub2; und i&sub3; wie angegeben berechnet. Diese Werte werden zum Gebrauch während der ganzen Verarbeitung des gegenwärtigen Dreiecks registriert.
• Der nächste Schritt schließt eine Verbindung ein, die davon abhängt, ob das Rastern des Polygons beendet ist. Wie angegeben, stellt die Raute 58 die Operation "Wähle durch Rastern das nächste Pixel aus" dar, vorausgesetzt, daß unbehandelte Pixel in dem Polygon verbleiben. Wenn das Polygon vollständig gerastert ist, wie durch Linie 60 angegeben, kehrt das System zu Block 50 zurück, und das nächste Polygon wird abgerufen.
• Es ist zu bemerken, daß die Rasteroperation, wie durch die Raute 58 dargestellt, eine wohlbekannte Technik in der Computergraphik ist. Speziell in dieser Hinsicht ist die Rasterwandlung von Raumflächen insbesondere in Kapitel 16 des oben zitierten Buchs, "Principles of Interactive Computer Graphics", behandelt.
• Bei dem wie in Fig. 7 dargestellten Verfahren wird, falls unverarbeitete Pixel im Polygon bleiben, wie durch die Raute 58 angegeben, das nächste Pixel ausgewählt und das Verfahren fährt wie durch Linie 62 angegeben fort.
• Eine weitere Frage wird von der Raute 64 gestellt, insbesondere "Befindet sich das Pixel in dem Polygon?" Wenn nicht, wie durch Linie 66 angegeben, kehrt das Verfahren zur Raute 58 zurück und das Rasterverfahren sucht das nächste Pixel. Alternativ geht das Verfahren, falls das betrachtete Pixel sich in dem Polygon befindet (wie durch Linie 68 angegeben), weiter zum Schritt des Blocks 70, berechne den Vektor OC.
• Der nächste Schritt in dem Verfahren ist durch Block 72 dargestellt und schließt die Verwendung der Vektoren OC, OP&sub1;, OP&sub2; und OP&sub3; ein, um die Werte von K&sub1;, K&sub2; und K&sub3; zu berechnen. Die Einzelheiten dieser Berechnungen wurden oben behandelt.
• Bei Vervollständigung der Größen K&sub1;, K&sub2; und K&sub3; werden die baryzentrischen Koordinaten b&sub1;, b&sub2; und b&sub3; für das Pixel berechnet, wie durch den Verfahrensblock 74 angegeben. Folglich existiert eine Basis zum Interpolieren des Polygons (Dreieck), um ein gleichmäßiges Abtönen oder eine Strukturabbildung wie oben beschrieben zu erreichen.
• Ausführungen des Systems der vorliegenden Erfindung können das Berechnen der baryzentrischen Koordinaten in Übereinstimmung hiermit für irgendeine einer Vielfalt von Funktionen einschließen. Zusammenfassend schließt die Berechnung die Berechnung der Tripelprodukte der Vektoren OC, OP&sub1;, OP&sub2; und OP&sub3;, gefolgt von der Berechnung der baryzentrischen Koordinaten mit einer Proportionalitätskonstante (die den Vektor OC mit dem Vektor OP in eine Gleichung bringt), die eliminiert wird, ein. Natürlich kann irgendeines einer Vielfalt von Rechennetzwerken oder -einrichtungen eingesetzt werden, um solche Berechnungen nach wohlbekannter Prinzipien aus dem Stand der Technik auszuführen.
• Wie in Fig. 7 bei Block 76 dargestellt, wird die Operation zum gleichmäßigen Abtönen unter Verwendung der Scheitelpunktintensitäten i&sub1;, i&sub2; und i&sub3; zusammen mit den baryzentrischen Koordinaten b&sub1;, b&sub2; und b&sub3; durchgeführt, um einen Wert von Intensitäten i für das spezielle Pixel zu berechnen. Die Operation erzeugt einen Pixelintensitätswert. So kann ebenfalls eine Strukturabbildung wie oben erläutert und wie in durch Block 77 dargestellt ausgeführt werden.
• Die, wie durch die Blöcke 76 und 77 angegeben, berechneten Pixelwerte werden gespeichert, wie durch Block 78 dargestellt. Normalerweise würde die Speicherung als Vorbereitung der Darstellung unter Verwendung wohlbekannter Techniken aus dem Stand der Technik in einem Bildwiederholspeicher vorgenommen werden. Bei Beendigung des Speicherns, wie durch Block 78 dargestellt, kehrt das Verfahren zum Rastern des nächsten Pixels zurück, wie durch Linie 80 angegeben.
• Die Berechnung der baryzentrischen Koordinaten in Übereinstimmung hiermit zur Anwendung auf Computergraphikoperationen ist in Fig. 8 insbesondere in bezug auf eine Strukturabbildung und ein gleichmäßiges Abtönen dargestellt. Diese Operationen wurden oben ausführlich beschrieben, folglich verbindet die folgende Erläuterung eine Anordnung mit dem Verfahren.
• Bezug nehmend auf Fig. 8 empfängt eine Anordnung 100 zur Rasterwandlung von Polygonen (oben links) Polygondaten, wie von einer Transformationshardware in einem Bildprozessor. Im wesentlichen werden nach dem Stand der Technik Grundelementdaten (die Polygone darstellen) vorbereitend für eine weitere Verarbeitung transformiert. Die weitere Verarbeitung kann im wesentlichen das Abtönen und die Strukturdarstellung in Übereinstimmung hiermit beinhalten. Solche Operationen können von der Anordnung, wie sie in Fig. 8 dargestellt ist, ausgeführt werden.
• Das Strukturieren und Abtönen einzelner Polygone wird durch das Beispielsystem in zwei Phasen ausgeführt, d.h. Phase PH&sub1; und Phase PH&sub2;. Für die beiden Phasen PH&sub1; und PH&sub2; bezeichnende Signale werden von einer Steuerung 102 bereitgestellt. Es ist einzusehen, daß die Steuerung 102 zusammen mit der Anordnung 100 zur Rasterwandlung von Polygonen typischerweise in einem Gesamt-Computergraphiksystem beträchtlicher Komplexität beinhaltet wäre. Für die Zwecke der vorliegenden Erfindung, die ein spezielles System zum Erzeugen baryzentrischer Koordinaten für spezielle Funktionen einschließt, ist jedoch die Anordnung von Fig. 8 abgesondert, um eine leicht zu handhabende Darstellung zu bieten.
• Die Steuerung 102 liefert die Signale PH&sub1; und PH&sub2; in einer Weise, daß die Behandlung der Komponenten, wie bei dem System der Fig. 8 dargestellt, sequentiell geordnet wird. In dieser Hinsicht schließt die Phase PH&sub1;, die durch das ebenfalls mit PH&sub1; bezeichnet Signal definiert ist, die vorbereitende Verarbeitung eines neuen Polygons ein. Die zweite Phase PH&sub2;, die durch das Signal PH&sub2; definiert ist, bietet die Berechnung von Intentsitäts- und Strukturwerten für jedes einzelne Pixel, während das gegenwärtige Polygon rastergewandelt wird.
• Die Anordnung 100 zur Rasterwandlung von Polygonen ist mit einem Polygonspeicher 106 und einem Rechennetzwerk 112 verbunden. Der Polygonspeicher 106 empfängt die Polygondaten während der Anfangsphase PH&sub1; und liefert wiederum spezielle Komponenten der Daten an Operationseinheiten während der Phasen PH&sub1; und PH&sub2;. Insbesondere liefert der Speicher 106 die Scheitelpunktdaten O, P&sub1;, P&sub2; und P&sub3; an das Rechennetzwerk 108 während der Anfangsphase PH&sub1;. Mit solchen Daten berechnet das Netzwerk 108 die Vektoren OP&sub1;, OP&sub2; und OP&sub3; unter Verwendung verfügbarer Rechenelemente. Die Darstellungen der berechneten Vektoren werden in einen Speicher 110 gegeben.
• Während der zweiten Phase PH&sub2; des Betriebs liefert die Anordnung 100 zur Rasterwandlung Werte, die zu jedem einzelnen Pixel gehören, an das Rechennetzwerk 112. Insbesondere wird ein den Vektor OC, der mit einem innerhalb des Polygons liegenden Pixel verbunden ist, darstellender Wert von der Anordnung 100 an ein Rechennetzwerk 112 geliefert, das auch mit dem Speicher 110 verbunden ist. Außerdem werden die Intensitätssignale i&sub1;, i&sub2; und i&sub3; vom Polygonspeicher 106 an ein Rechennetzwerk 114 für den Farbton geliefert. Die baryzentrischen Koordinaten, wie durch die Signale b&sub1;, b&sub2; und b&sub3; vom Netzwerk 112 dargestellt, werden ebenfalls an das Rechennetzwerk 114 für den Farbton geliefert. In ein wenig ähnlicher Weise werden die baryzentrischen Koordinaten vom Rechennetzwerk 112 an ein Rechennetzwerk 116 für die Struktur geliefert, das ebenfalls Struktursignale tx&sub1;, tx&sub2;, tx&sub3;, ty&sub1;, ty&sub2; und ty&sub3; vom Polygonspeicher 106 empfängt.
• Den Betrieb des Systems von Fig. 8 betrachtend werden Polygondaten zur speziellen Analyse und Verteilung in der Anordnung 100 empfangen. In dieser Hinsicht wird die Anordnung 100 durch die Steuerung 102 betätigt, die die verschiedenen Phasen sequentiell ordnet und die Operationen steuert.
• Während der Phase PH&sub1; werden die vorbereitenden Daten eines Polygons von der Anordnung 100 zur Rasterwandlung von Polygonen empfangen. Anschließend werden während der Phase PH&sub1; diese Daten an den Polygonspeicher gesendet. Anschließend sendet während der Phase PH&sub1; der Polygonspeicher 106 Punkte P&sub1;, P&sub2;, P&sub3; und O an das Rechennetzwerk 108, das die Vektoren OP&sub1;, OP&sub2; und OP&sub3; berechnet und sie an den Speicher 110 sendet. Anschließend bestimmt während der Phase PH&sub2; die Anordnung 100 zur Rasterwandlung von Polygonen unter Verwendung von Rasterwandlungsoperationen, welche Pixel innerhalb des Polygons liegen, und liefert einen eindeutigen Vektor OC für jedes solche Pixel, der bei Berechnungen zum Abtönen und für die Struktur für jenes einzelne Pixel in Übereinstimmung hiermit verwendet werden soll. Insbesondere wenn jedes Pixel, das innerhalb des Polygons liegt, berücksichtigt ist, wird ein eindeutiger Vektor OC an das Rechennetzwerk gesendet, und die Rechennetzwerke 112, 114 und 116 werden betätigt, um Farbton- und Strukturpixeldaten zu berechnen. Während der Verarbeitung für jedes Pixel werden die baryzentrischen Koordinaten b&sub1;, b&sub2; und b&sub3; für das Pixel berechnet und auf Rechennetzwerke 114 und 116 angewendet. Das Netzwerk 114 erreicht den geeigneten Farbton für das Pixel unter Anwendung der Gleichung i = b&sub1;i&sub1; + b&sub2;i&sub2; + b&sub3;i&sub3;. Wie oben angegeben, könnte die Gleichung auch als i = (b&sub1;,b&sub2;,b&sub3;) (i&sub1;,i&sub2;,i&sub3;) dargestellt werden. Die bestimmten Werte von i (einer für jedes Pixel) werden während des Intervalls PH&sub2; im Bildwiederholspeicher in Übereinstimmung mit dem besonderen Anzeigeformat registriert.
• Gleichzeitig mit den obigen Operationen wird die Strukturabbildungsoperation vom Rechennetzwerk 116 für die Struktur ausgeführt. Die Berechnung schließt insbesondere die Bestimmung der Werte tx und ty durch das Netzwerk 116 unter Ausführung der Gleichungen:
• tx = (b&sub1;,b&sub2;,b&sub3;) (tx&sub1;,tx&sub2;,tx&sub3;)
• ty = (b&sub1;,b&sub2;,b&sub3;) (ty&sub1;,ty&sub2;,ty&sub3;).
• ein.
• Wieder werden die Strukturabbildungswerte für jedes Pixel im Bildwiederholspeicher 120 in Übereinstimmung mit dem Anzeigeformat des Systems registriert.
• Aus dem obigen ist zu sehen, daß das System der vorliegenden Erfindung die Bestimmung baryzentrischer Koordinaten für Polygone ermöglicht, um solche spezifischen Operationen auszuführen, wie gleichmäßiges Abtönen und Strukturabbildung. Wie oben angegeben, können verschiedene andere Computergraphikooperationen ausgeführt werden, um Datensignale für Computergraphikdarstellungen unter Verwendung solcher baryzentrischer Koordinaten zu bieten. Folglich ist aus der obigen Erläuterung leicht einzusehen, daß das System hiervon einer großen Zahl von Modifikationen und Abweichungen innerhalb des Netzwerks nach dem Grundkonzept zugänglich ist. Folglich ist der Schutzumfang hiervon wie in den Ansprüchen unten dargelegt gemeint.

Claims (9)

1. Verfahren zum Interpolieren eines graphischen Objekts (10), wie für das Abtönen oder Strukturieren, um Pixeldaten in einem Computergraphiksystem zu bestimmen, das die Schritte umfaßt:

Definieren wenigstens eines Teils des genannten Objekts als ebenes Polygon mit wenigstens drei Scheitelpunkten in einem Raum, der keiner linearen Verzerrung unterliegt,

Auswählen der Scheitelpunkte eines Dreiecks (24), das innerhalb des genannten Polygons liegt, wobei die genannten Scheitelpunkte des genannten Dreiecks mit P&sub1;, P&sub2;, P&sub3; bezeichnet werden,

dadurch gekennzeichnet, daß das Verfahren die Schritte umfaßt:

Definieren eines Blickpunktes O in bezug auf das genannte ebene Polygon, um Vektoren OP&sub1;, OP&sub2;, OP&sub3; von dem genannten Blickpunkt zu den genannten Scheitelpunkten aufzulösen,

Definieren einer Bildebene (28) in bezug auf den genannten Blickpunkt und Festsetzen eines Pixelortes (34) in der genannten Ebene, wodurch ein sich von dem genannten Blickpunkt zu dem genannten Pixel erstreckender Strahl einen Vektor OC von dem genannten Blickpunkt zu dem genannten Pixel definiert,

Definieren eines Raumpunktes (P), wo ein skalares Vielfaches des genannten Vektors OC die Ebene des genannten ebenen Polygons schneidet,

Erzeugen der multiplen Produkte der Vektoren OC, OP&sub1;, OP&sub2;, OP&sub3;, die als K&sub1;, K&sub2;, K&sub3; definiert werden,

Berechnen baryzentrischer Koordinaten für das genannte ebene Polygon als

b&sub1; = K&sub1;/(K&sub1; + K&sub2; + K&sub3;)

b&sub2; = K&sub2;/(K&sub1; + K&sub2; + K&sub3;)

b&sub3; = K&sub3;/(K&sub1; + K&sub2; + K&sub3;) und

Interpolieren, um das genannte Abtönen oder Strukturieren zu erreichen, oder um den genannten Punkt für das genannte Pixel in Übereinstimmung mit den genannten baryzentrischen Koordinaten zu berechnen.

2. Verfahren nach Anspruch 1, bei dem der genannte Schritt des Erzeugens multipler Produkte der Vektoren das Anwenden von Gleichungen als Skalarprodukt und Vektorprodukt umfaßt, wie

K&sub1; = OC [OP&sub2; x OP&sub3;]

K&sub2; = OC [OP&sub3; x OP&sub1;]

K&sub3; = OC [OP&sub1; x OP&sub2;].

3. Verfahren nach Anspruch 1 oder 2, bei dem der genannte Interpolierschritt die Interpolation der Intensität des genannten Pixels (34) in Übereinstimmung mit den genannten baryzentrischen Koordinaten umfaßt.

4. Verfahren nach Anspruch 3, bei dem die genannte Interpolation der Intensität i durch eine Form der Gleichung i = b&sub1;i&sub1; + b&sub2;i&sub2; + b&sub3;i&sub3; erreicht wird.

5. Verfahren nach einem der vorhergehenden Ansprüche, bei dem der Interpolierschritt die Interpolation multipler Komponenten eines Flächennormalenvektors am Raumpunkt (P) umfaßt.

6. Verfahren nach einem der vorhergehenden Ansprüche, bei dem der genannte Interpolierschritt die Interpolation der Struktur für das genannte Pixel (34) umfaßt.

7. Verfahren nach Anspruch 6, bei dem Strukturkoordinaten für die genannten Scheitelpunkte als Vektoren (tx&sub1;,tx&sub2;,tx&sub3;) und (ty&sub1;,ty&sub2;,ty&sub3;) bezeichnet werden und die Struktur des genannten Raumpunktes (P) interpoliert wird als:

tx = (b&sub1;,b&sub2;,b&sub3;) (tx&sub1;,tx&sub2;,tx&sub3;)

ty = (b&sub1;,b&sub2;,b&sub3;) (ty&sub1;,ty&sub2;,ty&sub3;).

8. System zum Interpolieren eines graphischen Objekts (10), wie für das Abtönen oder Strukturieren von Pixeln, bei dem das genannte Objekt in einem Raum, der keiner linearen Verzerrung unterliegt, wenigstens teilweise durch ein ebenes Polygon (24) mit definierten Scheitelpunkten P&sub1;, P&sub2;, P&sub3; dargestellt wird, und bei dem weiterhin ein Blickpunkt O zusammen mit einer Bildebene (28) festgesetzt wird, um Vektoren OP&sub1;, OP&sub2;, OP&sub3; von dem genannten Blickpunkt O zu den genannten Scheitelpunkten und einen Vektor OC von dem genannten Blickpunkt zu einem Pixel (23) in der genannten Bildebene aufzulösen, wobei das genannte System umfaßt:

Mittel zum Erzeugen multipler Produkte der Vektoren OC, OP&sub1;, OP&sub2;, OP&sub3;, um Darstellungen von K&sub1;, K&sub2;, K&sub3; bereitzustellen,

Mittel (112) zum Berechnen baryzentrischer Koordinaten für das genannte ebene Polygon unter Verwendung einer Form der Gleichung

b&sub1; = K&sub1;/(K&sub1; + K&sub2; + K&sub3;)

b&sub2; = K&sub2;/(K&sub1; + K&sub2; + K&sub3;)

b&sub3; = K&sub3;/(K&sub1; + K&sub2; + K&sub3;)

um baryzentrische Signale bereitzustellen, und Mittel (114, 116) zum Interpolieren des genannten Polygons für das genannte Pixel in Übereinstimmung mit den genannten baryzentrischen Koordinaten, um Pixelsignale bereitzustellen.

9. Verfahren zum Bestimmen von Pixeldaten zur Verwendung bei Computergraphiksystemen, um eine Hervorhebung bereitzustellen und bei dem dreieckige ebene Flächen zu einzelnen Pixeldaten für die genannte Hervorhebung rastergewandelt werden, welches umfaßt:

Definieren der Scheitelpunkte P&sub1;, P&sub2;, P&sub3; einer der genannten dreieckigen ebenen Flächen (24) als dargestellte Computergraphikelemente,

dadurch gekennzeichnet, daß das Verfahren die Schritte umfaßt:

Definieren eines Blickpunktes O in bezug auf eine der genannten dreieckigen ebenen Flächen (24) und Berechnen von Vektoren OP&sub1;, OP&sub2;, OP&sub3; als dargestellte Computergraphikelemente,

Definieren einer Bildebene (28) in bezug auf den genannten Blickpunkt und Festsetzen eines Pixelortes (34) in der genannten Ebene, wodurch ein von dem genannten Blickpunkt ausgehender Strahl sich zu dem genannten Pixel erstreckt und folglich einen Vektor OC von dem genannten Blickpunkt zu dem genannten Pixel definiert,

Definieren eines Raumpunktes (P), wo ein skalares Vielfaches des genannten Vektors OC die Ebene der genannten dreieckigen ebenen Fläche schneidet,

Erzeugen der multiplen Produkte der Vektoren OC, OP&sub1;, OP&sub2;, OP&sub3;, die als K&sub1;, K&sub2;, K&sub3; definiert werden,

Berechnen baryzentrischer Koordinaten für das genannte ebene Polygon als

b&sub1; = K&sub1;/(K&sub1; + K&sub2; + K&sub3;)

b&sub2; = K&sub2;/(K&sub1; + K&sub2; + K&sub3;)

b&sub3; = K&sub3;/(K&sub1; + K&sub2; + K&sub3;) und

Anwenden der Darstellungen der genannten baryzentrischen Koordinaten, um Daten für die genannte Hervorhebung zu erreichen.