Verfahren zur Festlegung von Gewichtungsfaktoren für die Farbberechnung eines Farbwerts von Texeln für einen Footprint Beschreibung Die vorliegende Erfindung bezieht sich allgemein auf ein Verfahren zur Anzeige von Bildern auf einem durch einen Computer gesteuerten Rasteranzeigesystem. Insbesondere be- zieht sich die vorliegende Erfindung auf einen anisotropen Filtermechanismus und eine entsprechende Vorrichtung, die erforderlich ist, um abgespeicherte, diskrete Bilder, die nachfolgend auch als Texturen bezeichnet werden, mit hoher Qualität auf der Rasteranzeige zu rekonstruieren, zu ska- lieren oder einer perspektivischen Projektion zu unterzie- hen. Insbesondere bezieht sich die vorliegende Erfindung auf ein Verfahren zur Festlegung von Gewichtungsfaktoren für die Farbberechnung eines Farbwertes von Texeln für ei- nen Footprint.

Im Stand der Technik sind anisotrope Filterverfahren be- kannt, z. B. die sogenannte Flächenabtastung"area sampling", um einem Footprint eine Textur zuzuordnen. Im Stand der Technik sind sogenannte gewichtete Flächenabtas- tungen als auch ungewichtete Flächenabtastungen bekannt wo- bei ein Nachteil der im Stand der Technik bekannten Verfah- ren darin besteht, dass hier bei einem Übergang zwischen einer gewichteten und einer ungewichteten Abtastung Diskon- tinuitäten in dem dargestellten Bild mit wahrnehmbaren Ar- tefakten erzeugt werden.

Ein"Footprint"ist die perspektivische Projektion eines Bildelements (Pixel) eines Objekts auf eine gebogene Ober- fläche. Ein"Footprint"kann eine konvexe vierseitige Dar- stellung sein, die das angenäherte Ergebnis der perspekti- vischen Projektion auf ein reguläres Texel-Gitter (Textur- element-Gitter) eines quadratischen Bildelements (Pixel) eines Objekts auf eine gebogene Oberfläche wiedergibt.

Ausgehend von diesem Stand der Technik liegt der vorliegen- den Erfindung die Aufgabe zugrunde, ein verbessertes Ver- fahren zu schaffen, das bei einer Erzeugung von Gewichtun- gen für Texel eines Footprints auf einfache und schnelle Art die Bestimmung von Texeln unter den Kanten des Footprints ermöglicht.

Diese Aufgabe wird durch ein Verfahren nach Anspruch 1 ge- löst.

Die vorliegende Erfindung schafft ein Verfahren zur Festle- gung von Gewichtungsfaktoren für die Farbberechnung eines Farbwertes von Texeln für einen Footprint, der eine Mehr- zahl von Texeln in einem Texel-Gitter überdeckt, in einem Graphiksystem, mit folgenden Schritten : (a) Bestimmen einer Forminformation des Footprints ; (b) Bestimmen der Kanten des Footprints ; (c) Annähern der im Schritt (b) bestimmten Kanten durch eine Treppenfunktion ; (d) Bestimmen der Texel des Texel-Gitters, die durch die Treppenfunktion berührt werden ; und (e) Bestimmen eines Gewichtungsfaktors für jedes Texel, das einen Abschnitt der Treppenfunktion enthält, ab- hängig von der durch den Footprint überdeckten Teil- fläche des jeweiligen Texels.

Gemäß einem bevorzugten Ausführungsbeispiel wird ein durch die Treppenfunktion berührtes Texel basierend auf den An- fangspunkten und/oder Endpunkten der vertikalen Abschnitte der Treppenfunktion bestimmt.

Texeln des Texel-Gitters, die nicht durch die Treppenfunk- tion berührt werden und die von dem Footprint bedeckt wer- den, wird vorzugsweise ein einheitlicher Gewichtungsfaktor zugeordnet, wobei die Gewichtungsfaktoren für jedes Texel einer Datenstruktur zugeordnet werden.

Gemäß einem weiteren bevorzugten Ausführungsbeispiel umfaßt die Treppenfunktion für jede Kante des Footprints eine Mehrzahl von Stufen, eine Mehrzahl von horizontalen Stufen- elementen und eine Mehrzahl von vertikalen Stufenelementen, wobei jede Kante eine Mehrzahl von gleichlangen, aufeinan- derfolgenden Kantenabschnitten umfaßt, wobei eine horizon- tale Kante vorliegt, wenn die Endpunkte der Kantenabschnit- te der Kante ein horizontales Stufenelement der Treppen- funktion schneiden, wobei eine vertikale Kante vorliegt, wenn die Endpunkte der Kantenabschnitte der Kante ein ver- tikales Stufenelement der Treppenfunktion schneiden, wobei eine horizontale Kante eine Anzahl von vertikalen Stufen- elementen umfaßt, die gleich der Anzahl der Stufen der Treppenfunktion ist, wobei eine vertikale Kante eine Anzahl von vertikalen Stufenelementen umfaßt, die um eine zusätz- liches vertikalen Stufenelement größer als die Anzahl der Stufen der Treppenfunktion ist, und wobei das zusätzliche vertikale Stufenelement für eine Berechnung der Gewich- tungsfaktoren einer benachbarten Kante mit gleicher verti- kaler Position herangezogen wird.

Gemäß einem anderen bevorzugten Ausführungsbeispiel ist dem Footprint eine Vergrößerungsverschiebung zugeordnet, wobei nach dem Schritt (a), basierend auf der Vergrößerungsver- schiebung, der Footprint durch Verschieben der Kanten des Footprints nach außen um eine von der Vergrößerungsver- schiebung abhängige Entfernung vergrößert wird, wobei im Schritt (b) die verschobene Kante bestimmt wird, wobei im Schritt (c) die verschobene Kante durch eine Treppenfunkti- on angenähert wird, und wobei im Schritt (e) ein Gewich- tungsfaktor für jedes Texel, das eine verschobene Kante

enthält, abhängig von der durch den vergrößerten Footprint überdeckten Teilfläche des jeweiligen Texels bestimmt wird.

Der Footprint wird dadurch vergrößert, dass die Kantenend- punkte um eine durch die Vergrößerungsverschiebung festge- legte Entfernung in horizontaler Richtung und in vertikaler Richtung verschoben werden. Vorzugsweise werden die sich einstellenden Zwischenräume durch horizontale und vertikale Kanten gefüllt, wobei anschließend weitere Gewichtungsfak- toren für jedes Texel, das eine eingebrachte vertikale Kan- te enthält, bestimmt werden.

Das erfindungsgemäße Verfahren schafft einen neuartigen An- satz für eine anisotrope Filterung, welche es ermöglicht z.

B. die bekannte Filtertechnik des Flächenabtastens"area sampling"auf vierseitige Footprints anzuwenden, welche ein perspektivisch projiziertes quadratisches Bildelement darstellen, welche ein regelmäßiges Texelgitter überlagern.

Genauer gesagt wird erfindungsgemäß ein weiterer Eingangs- parameter, die sogenannte Vergrößerungsverschiebung, ver- wendet, um Aliasing-Artefakte zu steuern. Die Vergröße- rungsverschiebung bestimmt, ob eine gewichtete Flächenab- tastung oder eine ungewichtete Flächenabtastung auf die Fläche des Footprints angewendet werden soll, insbesondere wird hierdurch bestimmt, wie groß der Gewichtungsbeitrag oder der Grad der Gewichtung bei der Flächenabtastung sein soll. Vorzugsweise findet die vorliegende Anmeldung auf verformte Footprints Anwendung, beispielsweise auf kleine und längliche Footprints.

Eine typische Charakteristik und ein wesentliches Merkmal der vorliegenden Erfindung ist darin zu sehen, dass kein Hardware-basierter Schalter, auf der Basis eines Schwellen- wertes, existiert, der entscheidet wann eine gewichtete und wann eine ungewichtete Flächenabtastung durchzuführen ist, welches tatsächlich zu Diskontinuitäten mit erkennbaren Ar- tefakten führen würde. Statt dessen wird vorzugsweise der Betrag des gewichteten Flächenabtastens zunehmend erhöht.

Vorzugsweise erfolgt die zunehmende Erhöhung des Gewich- tungsbeitrags mit kleiner werdendem Footprint, insbesondere während der Footprint kleiner wird als die Ausdehnung eines Texels in die Breite oder in die Höhe.

Gemäß einem weiteren Aspekt der vorliegenden Erfindung wird ein Verfahren zur Festlegung eines Gewichtungsfaktors für die Farbberechnung eines Farbwertes eines Texels für einen Footprint, der sich zumindest teilweise in das Texel er- streckt, in einem Graphiksystem geschaffen, bei dem eine Forminformation des Footprints bestimmt wird und basierend auf einer Vergrößerungsverschiebung der Footprint durch Verschieben der Kanten desselben nach außen um eine von dem Vergrößerungsverschiebung abhängige Entfernung vergrößert wird, so dass derselbe mehrere Texel überdeckt. Dann wird ein Gewichtungsfaktor für jedes Texel, das eine verschobene Kante enthält, bestimmt, abhängig von der durch den vergrö- ßerten Footprint überdeckten Teilfläche des jeweiligen Te- xels.

Gemäß diesem Aspekt der vorliegenden Erfindung wird ermög- licht, für Footprints, welche nur eine geringe Anzahl von Texeln oder sogar nur ein Texel überdecken, die Farbbestim- mung auf eine breitere Basis zu stellen, indem auch Infor- mationen von benachbarten Texeln berücksichtigt wird, durch die Vergrößerung des Footprints. Es ist darauf hinzuweisen, das die Vergrößerung nur zur Bestimmung des Farbwertes er- folgt-der Footprint wird für die spätere Darstellung des Objekts, dem derselbe zugeordnet ist, nicht vergrößert.

Bevorzugte Weiterbildungen der vorliegenden Anmeldung sind in den Unteransprüchen definiert.

Nachfolgend werden anhand der beiliegenden Zeichnungen be- vorzugte Ausführungsbeispiele der vorliegenden Erfindung näher erläutert. Es zeigen :

Fig. 1A und B ein Flussdiagramm eines bevorzugten Ausfüh- rungsbeispiels des erfindungsgemäßen Verfah- rens ; Fig. 2 die Darstellung eines Footprints im Textur- raum ; Fig. 3 eine Darstellung zur Festlegung der Kantenausrichtung eines Footprints ; Fig. 4A und B ein Flussdiagramm, das ein Verfahren zur Kantenberechnung gemäß einem Ausführungsbei- spiel der vorliegenden Erfindung wiedergibt ; Fig. 5A und B zwei Beispiele für eine Filtervergrößerung eines Footprints ; Fig. 6 eine Darstellung der Annäherung von Kanten des Footprints durch eine Treppenfunktion ; Fig. 7 eine Darstellung einer verschobenen Kante in einem Texelgitter mit den zugeordneten Ge- wichtungstabelleneinträgen ; Fig. 8A und B ein Flussdiagramm, das ein Verfahren zum Verarbeiten einer verschobenen Kante gemäß einem Ausführungsbeispiel der vorliegenden Erfindung wiedergibt ; Fig. 9 eine Darstellung eines Footprints und eines vergrößerten Footprints, anhand der der Stu- fenübertrag beschrieben wird ; Fig. 10A und B Darstellungen zur Verdeutlichung der Notati- on einer Scheitelpunktkante und eines Strei- fens (vertikales Stufenelement) ; und

Fig. 11A und B ein Flussdiagramm, das ein Verfahren zur Farbberechnung eines Pixels wiedergibt.

Nachfolgend wird anhand der Fig. 1 ein erstes Ausführungs- beispiel der vorliegenden Erfindung näher beschrieben, wo- bei einzelne Verfahrensschritte in der nachfolgenden Be- schreibung noch detaillierter erläutert werden.

Hinsichtlich der weitergehenden Beschreibung wird darauf hingewiesen, dass für die Beschreibung des Footprints die mathematische Notation von Vektoren verwendet wird (im Text durch FETTDRUCK dargestellt). Die Einheitslänge aller Koor- dinaten und Längen ist die Breite (bzw. die Höhe) eines Te- xels in der Originaltextur oder in der Textur gemäß einer MipMap-Stufe, sofern vorhanden. Kantenattribute und Schei- telattribute umfassen den Index i, der von 0 bis 3 läuft, und alle Ergebnisse von Indexberechnungen, welche i = 0 bzw. i = 3 überschreiten werden auf tatsächliche Kanten zu- rückgerechnet. Dies bedeutet, dass ein Ergebnis von i = 4 zu i = 0 wird und ein Ergebnis von i =-1 wird zu i = 3.

Gemäß einem bevorzugten Ausführungsbeispiel empfängt das erfindungsgemäße Verfahren im Block 100 Eingangsdaten oder Informationen, die die Form, Position und Ausrichtung des vierseitigen Footprints wiedergeben, und die im Block 102 bereitstehen. Genauer gesagt werden im Block 102 die Footprintdaten vlin, die Drehrichtung d des Footprints und die Vergrößerungsverschiebung (Vergrößerungsoffset) r be- reitgestellt. Durch den Empfang des zusätzlichen Eingangs- parameters, nämlich der Vergrößerungsverschiebung r wird es ermöglicht, erfindungsgemäß den Grad des gewichteten Flä- chenabtastens festzulegen, der für kleine oder dünne Footprints, insbesondere kleine oder dünne vierseitige Footprints, erforderlich ist.

Im Block 104 erfolgt eine sogenannte Kantenberechnung. Die- se Kantenberechnung umfasst das Vergrößern des Footprints durch Verschieben der Kanten desselben basierend auf der

empfangenen Forminformation und dem Vergrößerungsparameter r. Im Rahmen der Kantenberechnung 104 werden anschließend vertikale Kanten in die sich aufgrund der Vergrößerung er- gebenden Zwischenräume eingebracht, ein Begrenzungsrechteck wird berechnet, und alle Kanten werden im Block 104 in lin- ke und rechte Kanten sortiert, so dass im Block 106 die Attribute für die vergrößerten Scheitelpunktkanten bereit- gestellt werden, und im Block 108 die der verschobenen Kan- ten zugeordnete Attribute bereitgestellt werden. Genauer gesagt wird im Block 106 die Footprintinformation vi, die Ausrichtung der einzelnen Kanten ai* und die sich einstel- lenden Zwischenräume gi* für den vergrößerten Footprint be- reitgestellt. Im Block 108 werden die Scheitelpunktinforma- tionen vi', eine Ausrichtung der verschobenen Kante ai'so- wie entsprechende Kantenvektoren si'bereitgestellt. Die im Block 108 bereitgestellten Informationen werden dem Block 110 zugeführt, in dem eine Verarbeitung bezüglich der ver- schobenen Kante durchgeführt wird. Im Block 110 wird zum einen eine Stufenübertrag pi* berechnet, welcher im Block 112 bereitgestellt wird. Die im Block 106 und im Block 112 bereitgestellten Parameter werden dem Block 114 zugeführt, in dem eine Verarbeitung der Scheitelpunktkante erfolgt.

Aus den Verarbeitungen der Scheitelpunktkante (Block 114) und der verschobenen Kante (Block 110) resultieren die in den Blöcken 116 und 118 (Fig. 1B) bereitgestellten Gewich- tungstabellen für die Scheitelpunkt-Kanten und die verscho- benen Kanten.

Basierend auf den so erzeugten Tabellen erfolgt im Block 120 eine Farbberechnung, wobei der Block 120 zusätzlich In- formationen bezüglich der Textur vom Block 122 erhält. Die Farbberechnung im Block 122 ergibt dann die Pixelfarbe, die im Block 124 bereitgestellt wird und im Block 126 ausgege- ben wird.

Ist für den Footprint keine Vergrößerung erforderlich oder vorgesehen, so unterbleibt die Verschiebung der Kanten des

Footprints. Das erfindungsgemäße Verfahren wird dann ledig- lich auf die ursprünglichen Kanten ausgeführt. Zusätzlich eingefügte Kanten existieren in diesem Fall nicht, bzw. sind für die Berechnung auf Null gesetzt.

In den Blöcken 110 bis 118 wird eine geeignete Datenstruk- tur für jede der Kanten des Footprints erstellt. Hierbei werden die nachfolgend erläuterten Schritte für jede Kante parallel durchgeführt. Zunächst wird eine Kante durch eine geeignete Anzahl von einfachen Treppenstufen angenähert, und alle Texel, welche durch eine Treppenfunktion einer linken Kante berührt werden, werden gesucht. Jedem aufge- fundenen Texel wird dann ein Gewichtungswert zugeordnet, der den Bruchteil der verbleibenden Texelfläche, die rechts von der Stufenfunktion liegt, entspricht. Analog werden al- le Texel, die unter der darzustellenden Struktur liegen, und die durch die Treppenfunktion einer rechten Kante be- rührt werden, gesucht. Den so aufgefundenen Texeln wird dann jeweils ein Gewichtungsfaktor zugeordnet, der dem Bruchteil der verbleibenden Fläche jedes Texels entspricht, die links von der Treppenfunktion angeordnet ist. Anschlie- ßend werden alle Koordinaten und entsprechenden Gewichtun- gen in einer geeigneten, einzigartigen Datenstruktur ge- speichert, die der Kante des Footprints zugeordnet ist.

Ferner wird allen Texeln ein Gewichtungswert von < +1 bzw. von 2-1 zugeordnet, und zwar Texeln, die sich rechts von einer linken Kante bzw. einer rechten Kante-durch diese jedoch nicht berührt werden-und links von der rechten Kante des Begrenzungsrechtecks liegen. Diese Informationen werden zu der Datenstruktur hinzugefügt.

Vorzugsweise werden die so erzeugten Datenstrukturen gemäß einem bevorzugten Ausführungsbeispiel der vorliegenden Er- findung auf eine effizientere Art und Weise beurteilt, so dass jedes Texel, das durch den Footprint bedeckt wird, di- rekt durch die gespeicherten Koordinaten angesprochen wer- den kann, so dass nachfolgend dessen entsprechende Farbe mit dessen zugeordnetem Gewicht multipliziert (gewichtet)

werden kann. Es wird darauf hingewiesen, dass jeder Gewich- tungsfaktor die Summe der Gewichtungen derjenigen Kanten ist, welche in dem betrachteten Texel enthalten sind.

Im Block 120 in Fig. 1B wird eine Farbberechnung durchge- führt, wie sie im Stand der Technik an sich bekannt ist.

Für diese Farbberechnung werden alle Gewichtungsfaktoren gesammelt und ebenso werden alle gewichteten Texel, welche durch den Footprint verwendet werden, gesammelt und an- schließend wird die gesammelte Farbe durch die gesammelten Gewichtungsfaktoren geteilt. Das Ergebnis stellt das aus der Texturabbildung wiedergewonnene und gefilterte Bild- fragment dar, welches dem Pixel zugeordnet ist, das auf das Texturbild abgebildet bzw. projiziert werden sollte.

Hinsichtlich der in Fig. 1 wiedergegebenen Werte vi', ail und si'bzw. vi*, ai*, gi wird darauf hingewiesen, dass sich die mit Apostroph versehenen Werte auf die verschobenen Kanten beziehen, wohingegen sich die mit einem Sternchen versehenen Werte auf die Scheitelpunkt-Kanten beziehen.

Der Vorteil der vorliegenden Erfindung besteht darin, dass das erfindungsgemäße Verfahren inhärent die Möglichkeit schafft, einen hohen Grad von Parallelität bei dessen Aus- führungen in einer konkreten Hardware-Implementierung zu verwenden. Ferner ermöglicht das erfindungsgemäße Verfahren dessen Implementierung in einer Hardware-Pipeline, so dass gemäß einem bevorzugten Ausführungsbeispiel der vorliegen- den Erfindung die oben beschriebenen Verfahrensschritte hardwaremäßig in unterschiedlichen Pipeline-Stufen reali- siert sind. Vorzugsweise sind diejenigen Verfahrensschrit- te, die oben beschrieben wurden und die die Datenstruktur für jede Kante erzeugen, typischerweise als Hardwaremodul implementiert, und werden für jede Kante parallel instanti- iert (aufgerufen). Diese parallel instantiierten Module stellen selbst wieder eine Pipeline-Stufe der gesamten Hardware-Pipeline dar.

Der grundsätzliche Prozess zur Wiedergewinnung der Pixel- farbe von einem Texel-Array, welches durch einen vierseiti- gen Footprint bedeckt wird, besteht darin, eine nicht- gewichtete Flächenabtastung bezüglich dieses Footprints durchzuführen. Dies bedeutet, dass die Farbkomponenten des Texels zunächst über den Footprint integriert werden, und anschließend das Ergebnis durch die summierte Fläche des Footprints geteilt wird. Das Berechnen des Integrals erfor- dert das vorherige Multiplizieren jedes Texels durch einen geeigneten Gewichtungsfaktor. Der Gewichtungsfaktor beträgt 1,0 für diejenigen Texel, welche vollständig unterhalb des Footprints angeordnet sind. Erfindungsgemäß wird jedes Te- xel, welches nur teilweise durch den Footprint bedeckt wird, also am Rand des Footprints liegt, ein Gewichtungs- faktor zugeordnet, welcher proportional zur Größe der be- deckten Fläche ist.

Somit erfüllt das erfindungsgemäße Verfahren die folgenden zwei Aufgaben, die bisher beschrieben wurden, nämlich die Identifizierung aller Texel, welche vollständig oder teil- weise durch den vierseitigen Footprint bedeckt sind, und die Berechnung eines Gewichtes für jedes Texel und die Zu- ordnung dieses Gewichtungsfaktors zu dem entsprechenden Te- xel.

Ferner wird erfindungsgemäß ein Überblenden realisiert, welches durch den zusätzlichen Parameter, den Vergröße- rungsparameter r gesteuert wird, um ein Überblenden von ei- ner ungewichteten in eine gewichtete Flächenabtastung durchzuführen.

Der Hintergrund des gerade beschriebenen Aspekt ist darin zu sehen, dass eine ungewichtete Flächenabtastung in dem wiedergewonnenen Bild dann erkennbare Aliasing-Artefakte erzeugt, wenn der Footprint stark verformt, z. B. Formen aufweist, welche lediglich sehr dünne und sehr längliche Flächen umfassen. Dies ist ebenfalls der Fall, wenn die Fläche, welche durch den Footprint bedeckt wird, wesentlich

kleiner wird als die Fläche eines quadratischen Texels des Texelgitters.

Um die gerade erwähnten Artefakte in diesen Fällen zu ver- meiden, wird erfindungsgemäß die Fläche des Footprints durch Verschieben der vier Kanten, welche die Grenze des Footprints wiedergeben, erweitert. In den oben beschriebe- nen Fällen nähert dies einen Footprint an, welcher als die Projektion eines Filterkernels interpretiert werden kann, der die Charakteristik eines gewichteten Flächenabtastens erfüllt, wobei der Filterkernel seine Nachbarn überlappt und eine bilinear ähnliche Verteilung aufweist.

Bei der oben dargelegten Beschreibung des bevorzugten Aus- führungsbeispiels der vorliegenden Erfindung gemäß Fig. 1 wird darauf hingewiesen, dass das erfindungsgemäße Verfah- ren im wesentlichen die Blöcke 100 bis 118 umfasst, welche dann die erforderlichen Daten für eine im wesentlichen her- kömmliche Farbberechnung bereitstellen. Ferner wird hin- sichtlich der Fig. 1 angemerkt, dass alle rechteckigen Blö- cke die Hauptverarbeitungsschritte wiedergeben, welche nachfolgend für bevorzugte Ausführungsbeispiel der vorlie- genden Erfindung im Detail beschrieben werden. Die Ergeb- nisse der Verarbeitungsschritte sind in Datenstrukturen ge- speichert, die in Fig. 1 in den parallelogrammförmigen Blö- cken wiedergegeben sind. Diese Ergebnisse werden als Ein- gänge für die nächsten Verarbeitungsstufen herangezogen.

Die in Fig. 1 im Block 100 eingegebenen Daten und im Block 102 bereitgestellten Daten umfassen die Informationen be- züglich des Footprints vi, welcher gemäß einem bevorzugten Ausführungsbeispiel konvex ist und bei dem die Höhe und die Breite keiner der Kanten einen vorbestimmten maximalen Wert Emax überschreiten darf. Ferner wird eine Drehrichtung d für den Footprint eingegeben, wobei d = +1 für eine Drehrich- tung im Uhrzeigersinn und d =-1 für eine Drehrichtung ent- gegen dem Uhrzeigersinn steht. d wird auf 0 gesetzt, wenn die Drehung aufgrund der Verformung des Footprints nicht

mehr festgestellt werden kann. Ferner wird die Vergröße- rungsverschiebung r eingegeben, welche vorzugsweise auf ei- nen Wert zwischen 0,0 und 0,5 beschränkt ist.

Bei der oben erwähnten maximalen Kantenlänge Ejax handelt es sich vorzugsweise um einen Hardware-codierten Wert, der ei- ne Potenz von 2 sein sollte, wobei hier der Wert 8 bevor- zugt wird. Höhere Werte werden den Rasterprozess, also die Verarbeitungsgeschwindigkeit des Graphiksystems, signifi- kant verlangsamen und die erforderlichen Datenstrukturen deutlich vergrößern. Würde keine 2er Potenz verwendet, wä- ren die mit Emax verbundenen Berechnungen in Hardware nur aufwendig zu realisieren.

Fig. 2 zeigt ein Beispiel für eine Darstellung eines Footprints im Texturraum. Der Texturraum ist bei dem darge- stellten Beispiel durch die Koordinaten x und y aufge- spannt. Der Footprint ist durch die vier Scheitelpunktvek- toren vo bis V3 sowie die vier Kantenvektoren so bis S3 de- finiert. Ferner ist durch die Richtung der Kantenvektoren so bis S3 die Drehrichtung d des Footprints festgelegt.

Fig. 2 zeigt die typische Form eines Footprints in dem Tex- turraum. Der Footprint ist durch dessen Umgrenzung defi- niert, die wiederum aus den vier Kanten so bis S3 besteht, und daher oft auch als vierseitiges Element bezeichnet wird. Die vier Scheitelpunkte vo bis V3, die durch die vier in Fig. 2 gezeigten Vektoren im Texturraum positioniert sind, definieren die Kanten so bis S3.

Wie nachfolgend noch näher beschrieben wird, besteht ein Hauptaspekt der vorliegenden Erfindung darin, dass horizon- tale und vertikale Stufenfunktionen angewandt werden, um jede der Kanten anzunähern. Um jedoch einen konsistenten und einzigartigen Gewichtungsalgorithmus zu erhalten, der für alle Kanten so bis 83 parallel abgearbeitet werden kann, wird für die weitergehende Berechnung angenommen, dass die Kanten lediglich Beiträge zu denjenigen Texeln liefern, welche rechts von einer Kante angeordnet sind. So-

mit werden Werte von linksseitigen Kanten zu dem effektiven Gewichtungsfaktor, der sich für alle Kanten ergibt, ad- diert, und Werte von rechtsseitigen Kanten werden von dem effektiven Gewichtungsfaktor, der von allen Kanten resul- tiert abgezogen. Die Kantenattribute links, rechts, unten und oben sind in Fig. 3 dargestellt.

Wie ferner aus Fig. 3 zu entnehmen ist, werden Kanten, die als unten links bzw. oben rechts liegend eingestuft werden, durch vertikale Stufenelemente angenähert, wohingegen Kan- ten, welche als unten rechts bzw. oben links liegend ange- sehen werden durch horizontale Stufenelemente angenähert werden. Die gerade beschriebenen horizontalen und vertika- len Stufen werden nachfolgend noch detaillierter beschrie- ben.

Zunächst wird anhand der Fig. 4 ein erster Hauptverarbei- tungsschritt des erfindungsgemäßen Verfahrens nach einem bevorzugten Ausführungsbeispiel näher erläutert, nämlich die in Fig. 1A im Block 104 allgemein angegebene Kantenbe- rechnung. Im Block 128 empfängt das Verfahren zur Kantenbe- rechnung die hierfür erforderlichen Daten, nämlich die Footprintdaten vlin und die Vergrößerungsverschiebung r, welche in den Blöcken 130 und 132 der weiteren Verarbeitung bereitgestellt wird. Die Kantenberechnung erzeugt die ange- näherte Fläche des Footprints, wobei eine positive Filter- vergrößerung, angezeigt durch den Vergrößerungsverschiebung r, mit r 2 0, mit einbezogen wird. Jede Kante des ursprüng- lichen Footprints wird von dem Mittelpunkt weg bewegt, durch Hinzufügen einer Verschiebung mit der Größe r. Diese Kanten werden im weiteren als verschobene Kanten bezeich- net. Als ein Ergebnis dieser"Explosion"ergeben sich hori- zontale und vertikale Zwischenräume zwischen den ursprüng- lichen Scheitelpunkten des Footprints. Horizontale Zwi- schenräume können bei dem erfindungsgemäßen Verfahren gemäß dem beschriebenen Ausführungsbeispiel ignoriert werden, vertikale Zwischenräume werden jedoch einfach durch verti-

kale Kanten, die sogenannten Scheitelpunktkanten aufge- füllt.

Um die Berechnung der Kanten-und Scheitelpunktattribute zu vereinfachen und hinsichtlich der erforderlichen Hardware- Implementierung weniger aufwendig zu gestalten, werden im Block 134 Footprints, welche eine Drehrichtung entgegen dem Uhrzeigersinn aufweisen, stets in Footprints mit einer Drehrichtung im Uhrzeigersinn umgewandelt (siehe Fig. 2).

Die Umwandlung erfolgt gemäß der nachfolgend wiedergegebe- nen Berechnungsvorschrift : vö 1, z, 3 wenn d >_ 0 lV2103 wennd<0 2, 1, 0, 3 vo, 1, 2, 3 n im Block 128 empfangene Eingangsdaten.

Die gemäß der obigen Berechnungsvorschrift erhaltenen Footprintdaten vo, 1, 2,3 werden im Block 136 zur weiteren Ver- arbeitung bereitgestellt.

Basierend auf der im Block 136 bereitgestellten Footprin- tinformationen vi ergeben sich die Kantenvektoren gemäß der nachfolgenden Berechnungsvorschrift : s, =v-v, Ferner werden die sogenannten Ausrichtungsvektoren ai für die Kanten berechnet, um die entsprechenden Kanten in lin- ke/rechte und obere/untere Kanten zu klassifizieren. Basie- rend auf der in Fig. 3 gezeigten Einteilung wird für jede Kante bestimmt, in welchem Quadrat dieselbe liegt. In der nachfolgenden Tabelle sind die Werte für die zwei Komponen- ten des Kantenorientierungsvektors ai, nämlich für die Kom- ponenten ai, x und ai, y wiedergegeben für verschiedene Vorzei- chen der Komponenten si, x bzw. si, y des Kantenvektors si. Vorzeichen (si,x) Vorzeichen (si,y) ai,x ai, #0 <0 -1 -1 >0 20 +1-1 <O >O +1 +1 <0 : go-1 +1 0000

In der obigen Tabelle zeigt ein Wert von +1 eine Ausrich- tung nach rechts entlang der x-Achse und nach unten in Richtung der y-Achse in dem in Fig. 3 aufgespannten Textur- raum wieder. Ein Wert von-1 zeigt eine Ausrichtung nach links in Richtung der x-Achse und eine Ausrichtung nach o- ben in Richtung der y-Achse. Horizontale Kanten und verti- kale Kanten werden die gerade genannten Werte zugeordnet.

Eine"0-Kante" (in einem Punkt verformte Kante) resultiert zu einem Vektor a = 0 bzw. zu einem Wert für a = 0.

Die in der Tabelle wiedergegebenen Orientierungen werden verwendet, um die Richtung einer Vergrößerungsverschiebung festzustellen. Der Footprint wird auf vier verschobenen Kanten vi', si'erweitert, abhängig von der Größe des be- schränkten Vergrößerungsparameters r. Tatsächlich wird je- der der ursprünglichen Scheitelpunkte auf die in Fig. 5A und 5B beschriebene und wiedergegebene Art und Weise um den Vergrößerungsparameter r verschoben, wodurch sich die ver- schobenen Kanten si'einstellen. Nachdem alle Kanten von links nach rechts abgetastet werden sollten, müssen der Startpunkt und der Endpunkt für diejenigen Kanten, welche als unten liegend festgestellt wurden, vertauscht werden, was gemäß der nachfolgend wiedergegebenen Berechnungsvor- schrift durchgeführt wird : -5 i-i ã'; =ã ; s ; _-a ; y s ; , ã +tvi wenn a ; y<0 v ; =rä ; + v ; +, sonst

Die gerade beschriebenen Berechnungen erfolgen in Fig. 4A zum einen im Block 138, worauf sich die Kantenvektoren si ergeben, die im Block 140 bereitgestellt werden. Basierend auf diesen Informationen werden im Block 142a die verscho- benen Kantenvektoren si'berechnet und im Block 142b für die Ausgabe im Block 150 bereitgestellt. Basierend auf die- sen Informationen wird im Block 142 die Ausrichtung der Kanten berechnet, und anschließend im Block 144 (Fig. 4B) zur weiteren Verarbeitung bereitgestellt. Im Block 146 wer- den basierend auf den im Block 144 bereitgestellten Aus- richtungen ai', basierend auf den im Block 136 bereitge- stellten Footprintdaten vi sowie basierend auf dem im Block 132 bereitgestellten Vergrößerungsparameter r die Verschie- bung für die verschobenen Kanten berechnet, so dass im Block 148 die verschobenen Kanteninformationen vil bereit- gestellt werden und im Block 150 ausgegeben werden.

Zwischenräume, die sich aufgrund der Verschiebung jedes Scheitelpunkts des Footprints ergeben, werden durch die vertikalen Scheitelpunkt-Kanten gehandhabt. Die Verschie- bung dieser Kanten hängt von der Ausrichtung der zwei be- nachbarten Kanten, die eine Länge von größer 0 aufweisen ab. Diese Kanten werden mit j indiziert, abhängig von dem Scheitelpunktindex i, gemäß der nachfolgend wiedergegebenen Berechnungsvorschrift : i + 2 wenn a, = a, + = O j+ (i) =4ill wenn a = 0 i sonst i-3 wenn aí l =a'2 =O j (i) = i-2 wenn aí l = ° i-1 sonst Unter Verwendung dieser Indexübersetzung ergibt sich der modifizierte Ausrichtungsvektor ai*und die Zwischenraumflag Si wie folgt : r aj-(i),x aj-(i),y aj+(i),x aj+(i),y ai,x* ai,y* <0 <0 <0 <0-1-1 0 <0 <0 >0 <0 x x 0 <0 <0 >0 >0 +1 +1 1 >0 <0 >0 <0 +1 -1 0 >0 <0 <0 >0 +1 01 1 >0 <0 >0 >0 +1 -1 1 <0 >0 <0 <0-1 +1 1 <0 >0 >0 <0 -1 +1 1 <0 >0 <0 >0-1 +1 0 >0 >0 <0 <0-1-1 1 >0 >0 <0 >0 x x O >0 >0 >0 >0 +1 +1 0 sonst x

X steht für einen Wert, der keine Auswirkungen auf folgende Berechnungen hat und daher beliebig sein kann. Der Basis- punkt für die Scheitelpunktkante und die Größe des Vergrö- ßerungszwischenraums ergibt sich dann gemäß der nachfolgend wiedergegebenen Berechnungsvorschrift : Vi =Vi +r-ai * _ 0 wenn a ; = 0 gi t-2r sonst Die Bedingung ai = 0, woraus folgt gi* = 0, stellt sicher, dass eine"0-Kante", die zwei benachbarte und auch identi- sche Scheitelpunkte mit den gleichen Attributen aufweist, lediglich eine Zwischenraumkante für die nachfolgende Te- xelgewichtung erzeugt. Die oben beschriebenen Berechnungs- schritte erfolgen zunächst im Block 152, in dem basierend auf der im Block 144 bereitgestellten Ausrichtung ai'und basierend auf dem Vergrößerungsparameter r eine Ausrichtung der Scheitelpunkt-Kanten berechnet wird, die dann im Block 154 bereitgestellt wird. Ferner wird der Vergrößerungszwi- schenraum gi* im Block 156 bereitgestellt, der ebenfalls durch die Berechnung im Block 152 erzeugt wurde.

Basierend auf den Ausrichtungen ai*, die im Block 154 be- reitgestellt wurden, erfolgt im Block 156 die Berechnung der Verschiebung für die Scheitelpunktkanten vi*, die dann im Block 158 bereitgestellt werden. Im Block 150 werden dann die verschobenen Scheitelpunktkanten vi*, die Ausrich- tungen ai*, der Vergrößerungszwischenraum gi*, die im Block 144 bereitgestellte Ausrichtung ai', die verschobenen Kan- tenvektoren si'sowie die verschobenen Scheitelpunktinfor- mationen vi'ausgegeben, wie dies in Fig. 1A in den Blöcken 106 und 108 wiedergegeben ist.

Basierend auf den ausgegebenen Attributen vi', si'und ai' erfolgt nachfolgend in einem zweiten Hauptverarbeitungs- schritt die Verarbeitung der verschobenen Kanten, welche in Fig. 1A im Block 110 angegeben ist. Für die Verarbeitung der verschobenen Kanten werden dieselben durch eine Anzahl von Stufen approximiert, wobei die Anzahl der Stufen von der Größe der verschobenen Kante abhängt. An dieser Stelle sei darauf hingewiesen, dass 0-Kanten mit einem Wert ai = 0 ausgelassen werden. Ferner soll die Breite und die Höhe ei- ner Stufe einen Wert von 1,0 nicht überschreiten. Zunächst muss also die Anzahl der Schritte nstufe pro Kante bestimmt werden. Dies erfolgt gemäß der nachfolgenden Berechnungs- vorschrift : , sm =maxs ;, X, Is ;, yl ni, Stufe-I Smax 1 =2ngzcs, o1 i, Stufa Bevorzugt wird das mit 2) bezeichnete Berechnungsverfahren, da dieses durch den hartcodierten Maximalwert für die Kan- tenlängen Emax signifikant vereinfacht werden kann und fer- ner aufwendige Teiler durch einfache Schiebeoperationen in der nachfolgenden Berechnung der Stufenvektoren qi ersetzt.

Die Stufenvektoren qi berechnen sich gemäß der nachfolgend wiedergegebenen Berechnungsvorschrift :

1, qi ='si ni, Stufe Um das gleiche Gewichtungsverfahren bei allen Scheitelpunk- ten zu erhalten, sind zwei unterschiedliche Stufen- Verfahren erforderlich. Die Stufenausrichtung Si'ist 0, also horizontal, für oben rechts liegende Kanten und unten links liegende Kanten. Die Stufenausrichtung Si'ist 1, ist also vertikal, für oben links liegende Stufen und für unten rechts liegende Stufen. Horizontale Stufen beziehen sich auf horizontale Schnittpunkte einer Treppenfunktion mit der entsprechenden Kante am Ende des Stufenvektors qi. Ebenso beziehen sich vertikale Stufen auf vertikale Schnittstellen der Stufenfunktion mit der jeweiligen Kante am Ende des Stufenvektors qi, wie dies aus Fig. 6 zu entnehmen ist. Ein Streifen ist ein vertikales Stufenelement, welches verwen- det wird, um die Gewichtungen der Texel zu bestimmen. Für die Stufenausrichtung Si'gilt die folgende Berechnungsvor- schrift : 1 wenn ( (a,, < o) und (a,, > o)) oder ( (a > o) und (a,, < o)) '0 sonst Nachdem die Kanten mit einer Stufenausrichtung Si'gleich 1 ein vertikales Element mehr aufweisen als die Anzahl der Stufen ni, stufen wäre ein zusätzlicher Gewichtungszyklus er- forderlich. Statt dessen kann dieser jedoch auf die Verar- beitung einer benachbarten Scheitelpunkt-Kante mit dersel- ben x Position verschoben werden, was im Zusammenhang mit der vorliegenden Erfindung als Stufenübertrag (step propa- gation) bezeichnet wird, und nachfolgend anhand der Fig. 9 noch näher erläutert wird.

Eine Streifenverarbeitungsschleife ist für jede Kante vor- gesehen, und verarbeitet eine Streife pro Zyklus, wie dies nachfolgend noch detaillierter anhand der Fig. 8 beschrie- ben wird. Jeder Zyklus kann ein oder zwei Texel gewichten,

wobei die Eingangsparameter für die Verarbeitungsschleife v', q, nstufe, a'y und 31 sind. Die Schleife erzeugt eine Datenstruktur und füllt diese mit entsprechenden Daten, die in der nachfolgenden Tabelle wiedergegeben sind : y' ofs y ist die ganzzahlige Koordinate einer Texelrei- he k = 0. Dies ist die oberste Reihe für Kanten für die gilt # = 1, und ansonsten die unterste Reihe. y num Anzahl der Texelreihen Xf kl x ist die ganzzahlige Koordinate des am meisten links liegenden gewichteten Texels in dieser Reihe x'num[k] Anzahl der gewichteten Texel dieser Reihe w'ofs[k] Gewichtungsindex 1 für das am meisten links lie- gende Texel wrprop [k] Gewichtungsfaktor für Texel in dieser Reihe, die außerhalb des am weitesten rechts liegenden und gewichteten Texels liegen w'tex [1] Texelgewichtung = 0,0 bis 1,0 In Fig. 7 sind die in der obigen Tabelle wiedergegebenen Einträge graphisch dargestellt. Der höchstmögliche Wert für k und 1 hängt bei dem bevorzugten Ausführungsbeispiel von der maximal zulässigen Kantenerstreckung Emax ab, so dass gilt : k = 0,..., EmaX, und 1 = 0, ..., 2 Emax.

Für den Stufenübertrag gilt die folgende Berechnungsvor- schrift : pi*=#i'##|Qi,y|

Anhand der Fig. 8 wird nachfolgend ein bevorzugtes Ausfüh- rungsbeispiel der oben erwähnten Streifenverarbeitungs- schleife näher erläutert.

Hinsichtlich der nachfolgenden Beschreibung einer Streifen- verarbeitungsschleife in Fig. 8 wird darauf hingewiesen, dass hier auf die explizite Angabe des Index i verzichtet wurde, da dieser bei allen Werten auftauchen würde. Be- schrieben wird lediglich der Vorgang für eine Kante, wobei das anhand der Fig. 8 beschriebene Verfahren dann im Regel- fall für alle Kanten parallel durchgeführt wird. In Fig. 8 ist ferner der Index 1 angegeben, der für die Verarbeitung der Streifen lediglich die Anzahl der durch eine Kante ge- troffenen Texel (siehe Fig. 7) zählt.

In einem anfänglichen Abschnitt 160 werden die Koordinaten für den ersten Streifen (Slice), siehe auch die Vektoren ui, o in Fig. 9, initialisiert. In dem Block 162 werden die Koordinaten des Anfangspunktes ux, uyo sowie die Höhe duy (siehe Fig. 10B) festgelegt, wobei die tatsächlichen Koor- dinaten des ersten Streifen vom Beginn der betrachteten Kante, was durch den entsprechenden Anfangsscheitelpunkt v angezeigt ist, und von der Orientierung der Kante, was durch 31 bzw. ay angezeigt wird, abhängen. Daher wird zur Festlegung des tatsächlichen Anfangspunktes zunächst im Block 164 bestimmt, ob für den betrachteten, im Block 162 festgelegten Punkt eine horizontale Stufenausrichtung % 91 existiert oder nicht. Ist die Stufenorientierung horizon- tal, so geht das Verfahren zum Block 166, in dem die Koor- dinate ux des Anfangspunktes um den Wert qx/2 erhöht wird.

Die übrigen im Block 162 festgelegten Koordinaten bzw. Pa- rameter bleiben gleich.

Handelt es sich bei der im Block 164 festgestellten Stufen- ausrichtung nicht um eine horizontale sondern um eine ver- tikale Ausrichtung, so geht das Verfahren zum Block 168, in dem zunächst die Ausrichtung ay der betrachteten Kante be- stimmt wird. Handelt es sich bei der betrachteten Kante um

eine obere Kante, so geht das Verfahren zum Block 170, in dem der Koordinatenwert ux um den Wert qx erhöht wird. E- benso wird im Block 170 der Koordinatenwert uyo um den Wert qy/2 erhöht.

Wird im Block 168 festgestellt, dass die betrachtete Kante eine untere Kante ist, so geht das Verfahren zum Block 172, in dem die Höhe duy halbiert wird.

Die so festgelegten Anfangskoordinaten für den betrachteten Streifen werden dann dem Block 174 bereitgestellt. Im Block 174 werden zunächst die verwendeten Indizes initialisiert, wobei k die Texelreihen zählt, 1 die Texel insgesamt zählt, und n die Streifen/Slices zählt. Die Koordinate der ersten Texelreihe y'of s entspricht dem Texel unter dem Slice- Anfangspunkt, wobei in der zweiten Zeile im Block 174 be- züglich des Anfangskoordinatenwertes uyo die sogenannte Floor-Funktion angezeigt ist, welche den nächsten ganzzah- ligen Wert in Richtung-oo ausgehend von dem angegebenen Wert für uyo wiedergibt.

Die Anzahl der betroffenen Reihen und der betroffenen Texel bei der Bearbeitung des Streifens wird in der ersten Reihe aus 1 initialisiert, wie dies durch y'n"m-x'n"m [0)-1 wiedergegeben ist. Ferner wird die x Koordinate x'of 5 des Beginns der ersten Reihe gleich der Slice-Position ux sein, wobei hier wieder der nächste ganzzahlige Wert ausgehend von ux in Richtung-gewählt wird. Ferner wird die Gewich- tungsinformation w' ofx für die erste Reihe und das erste Te- xel zum Wert 0 initialisiert.

Basierend auf den im Block 174 initialisierten Werten fährt das Verfahren bei Block 176 in Fig. 8B fort. Im Block 176 wird überprüft, inwieweit sich die zur Zeit betrachtete x- Position aufgrund späterer Berechnungen geändert hat. Aus- gehend vom Block 174 wird festgestellt, dass die zwei im Block 176 angegebenen Parameter gleich sind, so dass das Verfahren in diesem Fall zum Block 178 weiter geht, in dem

das erste Texel gewichtet wird. Im Block 178 erfolgt eine Bestimmung der Gewichtungen für das erste von dem Streifen getroffene Texel, was gemäß den im Block 178 wiedergegebe- nen Berechnungsvorschriften bestimmt wird. Im Block 178 wird zunächst der Streifen-Endpunkt uyl berechnet, und an- schließend die dazugehörige ganzzahlige Texel-Koordinate ylint, basierend auf dem nächsten ganzzahligen Wert von uyi in Richtung-oo. Anschließend wird der Texel-Bruchteil wx berechnet, der sich durch den vertikalen Schnitt ergibt, wie dies in Fig. 7 dargestellt ist. Ferner wird der Bruch- teil wyo berechnet, der sich durch den horizontalen Schnitt ergibt. Die angegebene Fallunterscheidung berücksichtigt, welche Richtung der Streifen aufweist (siehe Fig. 10B) und ob ein oder zwei Texel getroffen sind.

Basierend auf den so bestimmten Informationen betreffend die Bruchteile des horizontalen und vertikalen Schnittes wird im Block 178 der Gewichtungsbeitrag w'tex [1] des Strei- fens zum aktuellen Texel bestimmt, in dem der existierende Wert um das Produkt aus wx mal wyo erhöht wird. Abschließend wird noch der an das rechts liegende Texel weitergegebene Gewichtungsbeitrag w'p", p bestimmt, in dem der existierende Wert für w'prop um den Wert wyo erhöht wird.

Wurde im Block 176 festgestellt, dass sich die x Position durch eine spätere Berechnung geändert hat, also ein neues Texel in der gleichen Reihe betrachtet wird, so werden zu- nächst der Index 1 und die Anzahl der bereits bearbeiteten Texel in dieser Reihe x'num inkrementiert. Ferner wird die Gewichtung für das neue Texel w'tex [l] auf w'prop [k] gesetzt, so dass die Gewichtungsbeiträge der vorhergehenden Texel weitergegeben werden.

Vom Block 180 geht das Verfahren dann zu Block 178, in dem dann eine entsprechende Gewichtung des neuen Texels auf die oben beschriebene Art und Weise durchgeführt wird.

Wurde die Berechnung der Gewichtung eines Texels im Block 178 abgeschlossen, so geht das Verfahren zu Block 182 in dem festgestellt wird, ob der Endpunkt des Streifens in ei- ner anderen Reihe liegt als der Anfangspunkt. Ist dies der Fall, so geht das Verfahren zum Block 184 in dem ein neues Texel in einer neuen Reihe festgelegt wird, also verfah- renstechnisch in die nächste zu betrachtende Reihe gesprun- gen wird, so dass zunächst die Reihenanzahl y'nmr der Rei- henindex k und der Texelindex 1 inkrementiert werden. Fer- ner wird die Texelanzahl x'num [k] neu auf den Wert 1 initia- lisiert und die Koordinate des ersten Texels in der neuen Reihe x'of 5 wird bestimmt. Zusätzlich wird der Index für das wtex-Array, bei dem das Gewicht für das erste Texel dieser Reihe gespeichert ist, festgelegt.

Vom Block 184 geht das Verfahren zum Block 186, in dem die Gewichtung für das zweite von dem Streifen getroffene Texel berechnet wird, ähnlich wie im Block 178, so dass auf die dortige Beschreibung verwiesen wird.

Nach dem Block 186 geht das Verfahren zum Block 188 in dem die x-Position der gerade betrachtete Streifen gespeichert wird und der Index n inkrementiert wird, um zum nächsten Streifen zu gelangen. Im Block 190 wird bestimmt, ob der Wert n kleiner ist als der Wert nstufe und wenn dies nicht der Fall ist, wird festgestellt, dass der letzte Streifen überarbeitet wurde. In diesem Fall endet das Verfahren.

Wird jedoch festgestellt, dass noch nicht der letzte Strei- fen bearbeitet wurde, geht das Verfahren zum Block 192, in dem die Koordinaten für den nächsten Streifen berechnet werden. Hierfür wird die Koordinate ux um den Wert qx er- höht, und ebenso wird die Koordinate uyo um den Wert qy er- höht. Die Fallunterscheidung bei der Betrachtung von duy berücksichtigt den in Fig. 9 bezüglich der Kanten s2 und S3 gezeigten Fall, gemäß dem der letzte Streifen nur die halbe Länge aufweist. Bei den Kanten so und si ist dies bereits der erste Streifen, was bereits bei der anfänglichen Initi- alisierung im Block 160 berücksichtigt wurde.

Basierend auf den im Block 192 festgelegten Daten werden im Block 194 die Texelkoordinaten des Anfangspunkts neu be- rechnet, und dann ein neuer Gewichtungsberechnungsdurchlauf für diesen Streifen durchgeführt.

Nachfolgend wird die in Fig. 1A im Block 114 angegebene Scheitelpunkt-Kanten-Verarbeitung näher beschrieben, welche die vertikalen Kanten behandelt, die hinzugefügt werden, um die vertikalen Zwischenräume auszufüllen.

Grundsätzlich stellen die Gewichtungstabellen für die Scheitelpunkt-Kanten die gleichen Parameter bereit, wie sie für die verschobenen Kanten herangezogen werden. Die Imple- mentierung dieser Gewichtungstabellen ist jedoch weniger aufwendig, da die Anzahl der möglichen Reihen wesentlich niedriger ist, und die Indizierung der Gewichtungen und Reihen sich nicht unterscheiden, nachdem die Ausrichtung der betrachteten Kanten stets vertikal ist.

Die nachfolgende Tabelle gibt die Gewichtungen für die Scheitelpunkt-Kanten wieder. Y*ofs y-Ganzzahlkoordinate der Texelzeile k = 0 x*ofs x-Ganzzahlkoordinate der Texelreihe k = 0 Y*num Anzahl der Texelzeilen w*tex [k] Texelgewichtung im Bereich von 0,0 bis 1,0 w*prop [k] Gewichtungen für die Texel in dieser Reihe, wel- che rechts des gewichteten Texels liegen, wel- ches am weitesten rechts angeordnet ist Der Vergrößerungszwischenraum g und der Stufenübertrag p werden zu der Gesamtlänge einer Scheitelpunkt-Kante ad- diert, wie dies in Fig. 10A dargestellt ist, so dass die Koordinaten (Anfangspunkt und Endpunkt) einer Scheitel- punkt-Kante gemäß der nachfolgenden Berechnungsvorschrift ergeben : (O r-p ;, v,. y + g ; wenn a ; y < 0 (Vjy-givviy+pi) sonst sonst x = Vi, x '. y"Sii, y+Pj sonst x=v

Die Kantenlänge ist g + p = 2'r + p, mit max. Wert für r und p = 0, 5. Aus der obigen Berechnungsvorschrift ergibt sich eine maximale Länge von 0, 5-1, 0 + 2'0, 5 = 1,5, was die Anzahl von Texelreihen auf 3 begrenzt. Die Tabellenele- mente für k = 0, 1, 2 für eine Scheitelpunkt-Kante i werden gemäß der nachfolgenden Berechnungsvorschrift bestimmt : Yint Yofs LYJ Yint LY j Xint-Xofs-X Ynum Yínt Yint + 1 s num-'mt-'mt w"", [k] = min (y", t + k + 1, y)-max (yinl+ k, y) Wtex [k] =wprop [k]-(xint+l-x) Nachdem nun alle Gewichtungstabellen für die entsprechenden Kanten, also die Scheitelpunkt-Kanten und die verschobenen Kanten bestimmt wurden, und gemäß Fig. 1B in den Blöcken 116 und 118 bereitgestellt werden, kann nun die abschlie- ßende Farbberechnung gemäß Block 120 in Fig. 1B erfolgen.

Nachfolgend wird ein Beispiel für den letzten, verbleiben- den Verarbeitungsschritt aus Fig. 1, nämlich den Block 120 näher beschrieben. Diese Farbberechnung besteht hauptsäch- lich aus einer Schleife, welche die Datenstrukturen, welche auf die oben beschriebene Art und Weise für jede verschobe- ne Kante und jede vertikale Kante erzeugt und gespeichert wurden, beurteilt. Genauer gesagt wird bei dieser Farbbe- rechnung auf alle Texel Bezug genommen, welche durch den vergrößerten Footprint berührt oder überdeckt werden, für jedes dieser Texel wird eine Gewichtung bestimmt. Für ein Texel (x, y) berechnet sich der Gewichtungsfaktor w E [0,0, 1.0] zu der Summe aller Kantenbeiträge, die aus den Gewich-

tungstabellen ausgelesen werden. Der Prozess zur Berechnung der sich ergebenden Pixelfarbe hängt im Detail von der das Pixel umgebenden Region ab, z. B. von der Organisation des Zugriffs auf den Texturspeicher. Nachfolgend wird ein funk- tionelles Beispiel für die Farbberechnungsprozedur anhand der Fig. 11 näher erläutert, wobei die in Fig. 11 darge- stellte Prozedur eine Schleife ist, welche mehrfach durch- laufen wird, um alle betroffenen Texel abzuarbeiten. Hin- sichtlich der Fig. 11 wird darauf hingewiesen, dass der In- dex i die Parallelität der angegebenen Rechnungen für vier Kanten beschreibt. Gleichungen, in denen i auf beiden Sei- ten des Gleichheitszeichens vorkommt, beschreiben vier Gleichungen, eine für jede Kante (i = 0, 1, 2,3). i- indizierte Werte als Funktionsargument beschreiben vier Ar- gumente. Der Index 1 gibt die durch eine Kante getroffenen Texel innerhalb einer Reihe an.

In Fig. 11A werden im Block 200 zunächst alle Farbkomponen- ten und die Summe aller Texelgewichte auf 0 initialisiert.

Bei den Farbkomponenten handelt es sich im allgemeinen um RGB-Komponenten und die a-Komponente, wobei die Gleichun- gen eine Berechnung nur für eine abstrakte Komponenten Far- bepix zeigen. Nachfolgend zu der Initialisierung der Farb- komponenten und der Summe aller Texelgewichte wird im Block 202 eine unterste und eine oberste Texelreihe bestimmt, wo- bei die kleinste und die größte y-Koordinate aller Texel, die durch die Werte in den oben beschriebenen zwei Tabellen beschrieben werden, ermittelt werden muss. Zunächst werden ein minimaler und ein maximaler Wert jeweils einer Kante (Y'i, min und y'i, max) bestimmt, und zwar aus der oben wieder- gegebenen Tabelle betreffend die verschobenen Kanten. Durch die angegebene Gleichung werden acht Gleichungen beschrie- ben, nämlich für die Bestimmung von ymin und ymax für jeweils vier Kanten. Die angegebene Fallunterscheidung in der Zu- weisung berücksichtigt, ob die Tabelle in Richtung steigen- der oder fallender y-Koordinaten aufgebaut wurde.

Ferner wird im Block 202 basierend auf der oben genannten Tabelle für die Scheitelpunkt-Kantenverarbeitung die mini- malen und die maximalen Werte einer Kante y*i, min und y*i, max bestimmt. Anschließend wird aus den für die Scheitelpunkt- Kanten und die verschobenen Kanten bestimmten minimalen Werten acht minimale Werte ymin bestimmt, und ebenso werden aus den bestimmten maximalen Werten für die verschobenen Kanten und die Scheitelpunkt-Kanten acht Maximalwerte ymax bestimmt. Nachdem die Bestimmung der untersten und der o- bersten Texelreihe auf diese Art und Weise durchgeführt wurde, geht das Verfahren zum Block 204, in dem der Schlei- fenwert y, welcher eine Texel-Reihe beschreibt, auf den Wert Yon initialisiert wird. Die Schleife wird für y Werte von Yin bis ymax durchlaufen.

Anschließend werden im Block 206 die in den oben beschrie- benen Tabellen angegebenen Werte herangezogen, um die in diesen enthaltene Verschiebung zu kompensieren. So wird zu- nächst der Schleifenparameter k'i festgelegt, der für die verschobenen Kanten gilt. Die Werte der entsprechenden Ta- belle enthalten lediglich Werte für xn Reihen, beginnend bei der ganzzahligen y Koordinate der Texelreihe 0 (yofs)- Diese Verschiebung wird von dem Schleifenwert abgezogen, um den Reihenindex kti innerhalb der Tabelle für die verscho- benen Kanten zu erhalten. Ähnlich wie oben bezüglich des Blocks 202 beschrieben wurde, muss auch hier berücksichtigt werden, ob die zugrundeliegende Tabelle die y Koordinaten in aufsteigender oder absteigender Reihenfolge enthält.

Anschließend erfolgt eine entsprechende Entfernung der Ver- schiebung für die Werte aus der Scheitelpunkt- Kantentabelle, um so den Reihenindex k*i zu erhalten. Fer- ner werden die Werte der Flags Ai und A*i bestimmt, welche anzeigen, ob eine betrachtete Kante über dem aktuellen y liegt, also einem Beitrag zu den Texel-Gewichten liefern wird.

Anschließend werden im Block 208 das am meisten links lie- gende und das am meisten rechts liegende Texel in der be- trachteten Reihe bestimmt. Für die aktuelle Reihe wird nun die kleinste und größte x-Koordinate aller Texel bestimmt, die durch die Tabellen gewichtet werden, also die x Koordi- naten x'i, min und x'i, max für die verschobenen Kanten und die Koordinaten x*i, min und x i, max für die Scheitelpunkt-Kanten.

Kanten, die keinen Beitrag liefern, für die also die im Block 206 festgelegte Flag A*i oder Api 0 sind, werden bei der entsprechenden Bestimmung der minimalen und maximalen x Werte nicht berücksichtigt, was durch die -oo-Beiträge formal beschrieben ist.

Aus den für die verschobenen Kanten und die Scheitelpunkt- Kanten bestimmten minimalen x-Koordinaten wird dann der mi- nimale Wert xi, ausgewählt. Ebenso wird aus den für die verschobenen Kanten und die Scheitelpunkt-Kanten bestimmten maximalen x Koordinaten der maximale Wert xmax ausgewählt.

Anschließend geht das Verfahren zum Block 210 (Fig. 11B).

Im Block 210 wird der Schleifenwert x, welcher ein Texel innerhalb der betrachteten Reihe angibt auf den Wert xmin initialisiert. Dieser Schleifenwert läuft von xin bis xax.

Anschließend geht das Verfahren zum Block 212 in dem aus den bereitgestellten Tabellen die Gewichtungsbeiträge für die verschobenen Kanten ausgelesen werden. Hier werden die Beiträge aller acht Kanten zur Gewichtung des Texels bei den Koordinaten x, y bestimmt.

Zunächst wird der Index li des Texels innerhalb der Reihe für eine entsprechende Kante betrachtet (siehe Fig. 7). An- schließend wird der Gewichtungsbeitrag w'i für die Verscho- bene-Kante betrachtet, wobei hier für jede Kante vier Fälle zu unterscheiden sind. Das Texel kann entweder oberhalb o- der unterhalb der Kante liegen, wobei in diesem Fall der Wert Ai 0 ist, so dass das betreffende Texel keinen Bei- trag liefert. Ferner kann das Texel links von der Kante liegen, wobei in diesem Fall der Index 1 kleiner als 0 ist, und in diesem Fall auch kein Beitrag des Texels zu der Ge-

samtgewichtung geliefert wird. Liegt das Texel jedoch rechts von der Kante, also dass 1 xnum ist, so wird der in der entsprechenden Tabelle bereitgestellte Wert w'prop ge- wählt. Liegt das Texel auf der Kante, so wird der in der Tabelle bereitgestellte Wert w'tex bereitgestellt. Der Fak- tor ati, X negiert das Ergebnis für rechte Kanten.

Parallel zum Block 212 wird im Block 214 eine entsprechende Auslesung der Tabellen hinsichtlich der Gewichtungsbeiträge der Scheitelpunkt-Kanten durchgeführt, wobei auch hier der entsprechende Beitrag w*i bestimmt wird. Wie im Block 212 gilt auch hier dass vier Fälle zu unterscheiden sind. Im ersten Fall liegt das Texel oberhalb oder unterhalb der Kante, der entsprechende Wert A*i ist somit 0. In diesem Fall liefert das Texel keinen Beitrag zur Gesamtgewichtung.

Liegt das Texel links von der Kante, so trägt dieses eben- falls nicht zur Gewichtung bei. Ist das Texel rechts von der Kante, x > x*i, ofs, so wird der in der Tabelle betreffend die Scheitelpunkt-Kanten festgelegte Wert w*prop ausgewählt.

Liegt das Texel auf der Kante, so wird der entsprechende Wert w*tex ausgewählt. Auch hier wird das Ergebnis für rech- te Kanten mittels des Faktors a*i, x negiert.

Nachdem in den Blöcken 212 und 214 die jeweiligen Beiträge für die verschobenen Kanten und die Scheitelpunkt-Kanten zur Gewichtung bestimmt wurden, geht das Verfahren zum Block 216, in dem alle Beiträge summiert werden, und die Texelfarbe gewichtet wird. Zunächst werden die in den Blö- cken 212 und 214 berechneten acht Beiträge aufsummiert, um den summierten Gewichtungswert w zu erhalten. Der so erhal- tene Gewichtungswert w wird mit den Farbkomponenten Farbe- tex (x, y) des Texels multipliziert und zur Farbe des Pixels Farbepix addiert. Für eine spätere Normalisierung der Farbe wird ferner die Gesamtsumme wgum der Texelgewichtungen durchgeführt. Genauer gesagt wird der Wert zum um den im Block 216 bestimmten Wert w erhöht.

Anschließend geht das Verfahren zum Block 218, in dem zum einen der Schleifenwert x um 1 inkrementiert wird und fer- ner bestimmt wird, ob der Wert x den maximalen Wert xmax ü- berschreitet. Ist dies nicht der Fall, so sind noch zu be- arbeitende Texel in der betrachteten Reihe enthalten, und das Verfahren geht vom Block 218 zurück zu den Blöcken 212 und 214. Es erfolgt folglich ein Sprung um ein Texel nach rechts, und eine entsprechende Überarbeitung bezüglich die- ses Texels wird durchgeführt. Wird im Block 218 bestimmt, dass alle Texel einer Reihe abgearbeitet wurden, so geht das Verfahren zum Block 220, in dem der Schleifenwert y und 1 inkrementiert wird und überprüft wird, ob der Schleifen- wert y den maximalen y Wert Ymax übersteigt. Ist dies nicht der Fall, so wird in die nächste Reihe gesprungen, und das Verfahren geht zurück zum Block 206. Wird festgestellt, dass die letzte Texelreihe bearbeitet wurde, so geht das Verfahren vom Block 220 zum Block 222. Im Block 222 wird dann die tatsächliche Farbe des Pixels Farbepix bestimmt, wobei für den Fall, dass eine Gewichtung existiert, also Wsum ungleich 0 ist, was anzeigt, dass zumindest ein Texel durch die betrachtete Kante berührt wurde, der Farbpixel- wert basierend auf der summierten Gewichtung ws"m normali- siert wird, also Farbepix/sum festgelegt wird. Bei einer so- genannten Nullgewichtung, wenn also der Footprint zu einem Punkt entartet und eine Vergrößerungsverschiebung einen Wert von 0 aufweist wird die Farbe des Texels unter dem Scheitelpunkt 0 des Footprints unverändert übernommen (nächstliegendes Filter). Dies bedeutet, dass das Texel was am nächsten zu den Punktkoordinaten liegt ausgewählt wird und eine konstante Gewichtung von 1,0 zugeordnet bekommt.

Obwohl die vorliegende Erfindung bei der obigen Beschrei- bung der bevorzugten Ausführungsbeispiele auf der Grundlage eines Footprints mit vier Seiten beschrieben wurde, kann der erfindungsgemäße Ansatz grundsätzlich auf beliebige Footprints erweitert werden.

Ferner wird darauf hingewiesen, dass die vorliegende Erfin- dung nicht auf die obigen Ausführungsbeispiele beschränkt ist, bei denen eine anfängliche Vergrößerung des Footprints durchgeführt wurde. Ist keine solche Vergrößerung er- wünscht, ist dem empfangenen Footprint z. B. keine Vergröße- rungsverschiebung zugeordnet, so arbeitet das erfindungsge- mäße Verfahren bezüglich des ursprünglichen Footprints und führt bei diesem zu einer beschleunigten Verarbeitung des- selben, aufgrund der erfindungsgemäßen Schritte zur Auffin- dung von Texeln unter Kanten.