Universität Koblenz-Landau
Abteilung Koblenz
Fachbereich 4: Informatik
Professor Dr. Ing. Giesen

Perspektivisches Texture Mapping
Vergleich von Algorithmen

Christian Cohnen
[Postanschrift und E-Mail-Adresse entfernt]

November 1996

Vorwort

Die vorliegende Studienarbeit befaßt sich mit einem Thema aus der Computergraphik: dem perspektivisch korrekten Texture Mapping.

In der Computergraphik bezeichnet man das Generieren von Oberflächendetails eines angezeigten Objektes als Texturing. Texturing ist heute eines der bedeutsamsten Verfahren, um Anwendungen der Computergraphik – wie zum Beispiel Virtual-Reality-Anwendungen – sehr realistisch erscheinen zu lassen. Es bietet große Vorteile für den Designer von 3D-Objekten und Umgebungen dadurch, daß es den Modellierungsprozeß deutlich beschleunigt und vereinfacht. Es können vorgefertigte Materialien benutzt oder neue künstlich erzeugte oder digitalisierte Bilder zur detaillierten Wiedergabe von Objekten verwendet werden.

Auch für den Anwender bedeutet Texturing eine gesteigerte Qualität der Computergraphik, da texturierte Objekte einen größeren Realismus erreichen als dies durch eine komplexere Szenenmodellierung effizient möglich wäre. Das Texturieren von Objekten bzw. seiner Flächen ahmt die Oberflächendetails realer Objekte nach und bietet bei korrekter Anwendung zusätzliche Information über die räumliche Tiefe des Objektes.

Diese Studienarbeit soll dazu dienen, dem Entwickler eines Polygonrenderer die Problematik des korrekten perspektivischen Texture Mapping zu erläutern.

Im ersten Teil werden die Grundlagen des Polygon Rendering erklärt und die Probleme des perspektivischen Texture Mapping dargelegt. Darauf aufbauend werden verschiedene Texture Mapping Algorithmen vorgestellt. Dabei ergeben sich verschiedene Wahlmöglichkeiten bezüglich der Effizienz und Genauigkeit der Verfahren.

Im zweiten Teil der Studienarbeit wird ein Programm des Autors vorgestellt, in dem die untersuchten Algorithmen implementiert wurden. Das Programm visualisiert die qualitativen Unterschiede der behandelten Algorithmen und bietet zusätzliche Funktionen zur Veranschaulichung der verwendeten Verfahren.

1  Theorie des perspektivischen Texture Mapping

1.1 Einführung

Es existieren mehrere Verfahren, um ein 3D-Objekt mit Detailelementen (z.B. Türen, Fenster) zu versehen. Eine recht einfache Methode, um dies auf einem gegebenen Basispolygon zu erreichen, sind die sogenannten Surface Detail Polygone (vgl. [Fole90], S. 741). Bei dieser Vorgehensweise wird das Basispolygon als eine einfache Fläche dargestellt, falls es sich in einem ausreichend großen Abstand vom Betrachter befindet. Bei Unterschreitung einer bestimmten Entfernung werden zusätzlich zu dem Basispolygon die Surface Detail Polygone angezeigt. Jedes Surface Detail Polygon liegt dabei auf einer Ebene mit dem Basispolygon. Sollen jedoch sehr detaillierte Oberflächen dargestellt werden, so wird dieses Verfahren relativ ineffizient. Eine alternative Methode stellt die Technik dar, die erstmals von Catmull [Catm74] angewendet und später von Blinn und Newell [BlNe76] erneut definiert wurde: das Texture Mapping. Der Ansatz des Texture Mapping besteht darin, ein Bild (digital oder synthetisch) auf eine Oberfläche abzubilden (Mapping). Das Bild wird dabei als Texture Map und dessen einzelne Elemente als Texel bezeichnet. Bei der Methode des Texture Mapping befindet sich die rechteckige Texture Map in ihrem eigenen Texture-Koordinatenraum (Texture Space), der durch seine Texture-Koordinaten u und v bestimmt wird. Alternativ dazu kann die Texture auch durch eine Funktion beliebiger Dimension definiert werden.

Beim Texture Mapping werden u.a. zwei Ziele verfolgt: Zum einen soll zu einer ebenen Fläche ein vorspezifiziertes Muster hinzugefügt werden. Zum anderen soll eine Fläche mit Unebenheiten versehen werden. Beide Aspekte können als Abbildungsfunktion betrachtet werden, die auf verschiedene Flächen-Attribute angewendet wird. Die Intensität, die Farbe, die Reflexionseigenschaften, der Normalenvektor, die Transparenz, die Beleuchtung und die räumliche Verschiebung (Displacement) sind nur einige von möglichen Attributen. Wird eine Texture simuliert, indem die Farbe der Oberfläche variiert wird, so spricht man von Pattern Mapping. Wird die Geometrie der Oberfläche durch Veränderungen der Normalenvektoren deformiert, spricht man von Bump Mapping.

Da die Grundlage, um eine Oberfläche durch ein Texture Pattern (Oberflächenmuster) zu verfeinern, das Abbilden (Mapping) ist, reduziert sich die Lösung des Texturing Problems auf die Spezifikation einer Transformation von einem Koordinatensystem in ein anderes. Texture Mapping ist definiert als die Transformation des Texture Space (Texture-Koordinatenraum) in den Object Space (Objekt-Koordinatenraum).

1.2 Problematik des perspektivischen Texture Mapping

Eine häufig angewandte Methode für das Texture Mapping ist die Lineare Interpolation der Texture-Koordinaten u und v. Diese Interpolation erfolgt entlang der Kanten des Polygons und über jede Scan-Linie (ähnlich wie bei dem Gouraud- oder Phong Shading, vgl. [Fole90], S. 736-739). Diese Methode ist jedoch unzureichend für perspektivisches Texture Mapping, da die Lineare Interpolation niemals den korrekten Effekt wie die nicht-lineare perspektivische Verkürzung (Foreshorten) erreicht. Statt dessen müssen Abstände mit der Entfernung zueinander kleiner werden. Die Lineare Interpolation ist nicht rotationsinvariant (konstant), und dieser Fehler ist in der Animation geradezu offensichtlich. Eine Lösung besteht darin, jedes Polygon in kleine Polygone zu zerlegen, bis der Fehler ausreichend reduziert ist (Adaptiver Zerteilungs-Algorithmus, vgl. Kapitel 2.3). Die korrekte Lösung ist allerdings, die Lineare Interpolation durch die korrekte Formel zu ersetzen, die für jeden Pixel eine Division vorsieht. Diese Probleme sind bei dem perspektivischen Gouraud Shading und Phong Shading ebenfalls gegeben, da auch dort die Lineare Interpolation angewandt wird. Allerdings sind dort die Fehler so wenig sichtbar, daß sie kaum wahrgenommen werden können.

1.3 Grundbegriffe

In Hinblick auf das Verständnis der im folgenden vorgestellten Algorithmen werden hier einige grundlegende Begriffe der Computergraphik erläutert.

• Rendering:
  Für jeden Pixel des Bildschirms wird die Farbe berechnet. Dies geschieht auf Basis der internen Repräsentation der 3D-Objekte.
• Scan-Linie:
  Eine Zeile von Pixeln.
• Scanline-Order:
  Die Pixel werden in der Reihenfolge ihres Auftretens in einer Scan-Linie betrachtet.
• 2D-Texture Mapping (Bitmap Image Texturing):
  Es wird ein zweidimensionales Bild als Texture benutzt.
• 3D-Texture Mapping (Solid Texture Mapping):
  Es wird ein dreidimensionaler Funktionsraum als Texture benutzt.

1.4 Definitionen

Im folgenden werden verschiedene Koordinatensysteme definiert.

• Der Object Space ist der 3D-Koordinatenraum, in dem jedes Polygon definiert wird. Es können mehrere Object Spaces vorhanden sein.
•  
• World Space ist der Koordinatenraum, der zu jedem Object Space durch 3D-Modellierungs-Transformationen (Translation, Rotation und Skalierung) in Bezug steht.
• Der 3D-Screen Space ist das 3D-Koordinatensystem des Bildschirms. Dieser perspektivische Raum mit Pixel-Koordinaten (x,y) und einer Tiefe z steht durch Kamera-Parameter in Relation zum World Space.
• Der 2D-Screen Space ist der 2D-Unterraum des 3D-Screen Space ohne die Tiefe z.

1.5 Lineare Interpolation

Eine Vorgehensweise des Texture Mapping ist die sogenannte Lineare Interpolation. Diese Methode dient dazu, den Wert eines Parameters an einer beliebigen Stelle in einem Dreieck anhand dessen bekannten Werten an den Eckpunkten zu berechnen.

Sei I der Parameter. An den Eckpunkten des Dreiecks seien die Werte I₁, I₂ und I₃ bekannt.

I_start = I₁ - (I₁ - I₂)(y₁ - y_scan) / (y₁ - y₂)

I_end = I₁ - (I₁ - I₃)(y₁ - y_scan) / (y₁-y₃)

Daraus ergibt sich für I_p:

I_p = I_end - (I_end - I_start)(x_end - x_p) / (x_end - x_start)

Vor dem Zeichnen des Dreiecks werden die Screen Space Koordinaten wie folgt berechnet.

Jeder Eckpunkt des Dreiecks wird mittels einer 4× 4-Matrix in homogene Bildschirmkoordinaten transformiert. Dies liefert die Werte (xw,yw,zw,w) an jedem Eckpunkt.

Eine homogene Division wird durchgeführt, um x = xw/w, y = yw/w und z = zw/w an jedem Eckpunkt zu berechnen (3D-Screen Space Koordinaten).

Das Dreieck[a,b,c] wird gezeichnet:

1. Sortieren der drei Eckpunkte a, b und c des Dreiecks anhand der y-Koordinate, so daß gilt:
   a.y ≤ b.y ≤ c.y
   
2. Das Dreieck wird jetzt gefüllt gezeichnet, indem in jeder y-Zeile zwischen a.y und c.y der x-Wert der linken und der x-Wert der rechten Kante in dieser Zeile berechnet werden. Man berechnet den Schnittpunkt der linken und der rechten Kante mit der Scan-Linie. Vom linken x-Wert wird eine horizontale Linie zum rechten x-Wert gezeichnet. Die Berechnung der x-Werte entlang der Polygonkanten erfolgt durch Lineare Interpolation. Falls beim Zeichnen zusätzliche Parameter (wie etwa die Helligkeit) beachtet werden sollen, so werden diese genau wie die x-Werte entlang der Polygonkanten durch Lineare Interpolation berechnet.

Beispiel:



Abbildung 1.2: Illustration des Scan-Linien-Algorithmus.

Die schwarzen Punkte in Abbildung 1.2 stellen die Eckpunkte des Dreiecks dar. Die Koordinaten dieser Eckpunkte definieren das Polygon. Die dunkelgrauen Punkte werden durch Interpolation über die Kanten berechnet, die hellgrauen Punkte dazwischen ergeben sich durch Ziehen einer horizontalen Linie. Im Falle des Gouraud Shading, Phong Shading oder Texture Mapping werden die Werte der Kanten über die Scan-Linie interpoliert (Scan-Linien-Interpolation), um die Farbe jedes Pixel in der Scan-Linie zu bestimmen. Zusammen bilden die gefüllten Bereiche (Spans) der Scan-Linien (Scanlines) ein ausgefülltes Dreieck.

Die Formel für die inkrementelle Berechnung der x- und y-Werte einer Kante (Kanten-Interpolation) von (x_min,y_min) nach (x_max,y_max) für die nächste Zeile (i+1) lautet:

y_i+1 = y+1

und

x_i+1 = x_i +1/m, falls m ≠ 0, 1/m = (y_max - y_min) / (x_max - x_min)

x_i+1 = x_i, sonst

Ein detaillierter Zwischencode des Algorithmus findet sich in Kapitel 2.1 am Beispiel des Bilinearen Mapping-Algorithmus.

Eine Optimierung des Algorithmus ist möglich, indem die Berechnung der Deltas (Steigungswerte) für die Interpolation von Parametern in einer Scan-Linie nicht für jede Scan-Linie einzeln, sondern einmalig am Anfang durchgeführt wird. Die Deltas sind in einem Dreieck für jede Scan-Linie gleich, da die Steigung einer Ebene konstant ist, und die an den drei Eckpunkten vorliegenden Werte jeweils ihre eigene Ebene definieren. Für jede Scan-Linie fällt eine Division weg. Gerade diese sind bei heutigen Prozessoren am zeitaufwendigsten.

2. Texture Mapping Algorithmen

2  Texture Mapping Algorithmen

In diesem Kapitel werden verschiedene Algorithmen vorgestellt. Zunächst wird dabei der Bilineare Mapping-Algorithmus behandelt. Dieser Algorithmus ist sehr einfach und wird oft verwendet. Er liefert jedoch kein korrektes Ergebnis. Anschließend wird der perspektivisch korrekte Algorithmus vorgestellt. Im Anschluß daran werden verschiedene Kompromißlösungen aufgezeigt.

2.1 Bilinearer Mapping-Algorithmus

Als Basis für den Bilinearen Mapping-Algorithmus dient der in Kapitel 1.6 bereits vorgestellte Rendering-Algorithmus für Dreiecke (Scan-Linien-Algorithmus). Zusätzlich zur Berechnung der x- und y-Schnittwerte an den Scan-Linien durch Interpolation über die Kanten werden die u- und v-Koordinaten an den Schnittpunkten auf dem gleichen Wege berechnet. Für jeden Bildschirmpixel einer Scan-Linie sind die u- und v-Koordinaten des Texel daraus inkrementell wie folgt zu berechnen:

u_i+1 = u_i + Δ u

v_i+1 = v_i + Δ v

Dabei ergeben sich Δ u und Δ v als Differenz der u- und v-Werte an der linken und rechten Kante, geteilt durch die Länge des zu zeichnenden Spans (Differenz der x-Werte). Als Startwerte u₀ und v₀ dienen die aktuellen Werte an der linken Kante (für den Fall, daß von links nach rechts gezeichnet wird). Da für das Texture Mapping zwei Werte linear interpoliert werden, bezeichnet man den Algorithmus als Bilinearen Mapping-Algorithmus.

Schritte des Bilinearen Mapping-Algorithmus:

1. Jedem Eckpunkt des Polygons wird eine Parameterliste zugeordnet. Diese enthält die u- und v- Koordinaten, ggf. auch noch zusätzliche Parameter zur Schattierung.
2. Die Objekt-Koordinaten jedes Eckpunktes werden mittels einer 4× 4-Matrix in homogene Bildschirmkoordinaten transformiert. Diese Transformation liefert die Werte (xw, yw, zw, w) an jedem Eckpunkt.
3. Eine homogene Division wird durchgeführt, um x = xw/w, y = yw/w und z = zw/w an jedem Eckpunkt zu berechnen.
4. Die Scan-Konvertierung wird durchgeführt, indem die an den Eckpunkten anliegenden Parameter jeweils linear interpoliert werden.

Der Bilineare Mapping-Algorithmus liefert ein korrektes Ergebnis, wenn das Polygon parallel zur Ebene des Betrachters liegt. Im einfachsten Fall bedeutet dies, daß die transformierten Koordinaten der Eckpunkte die gleiche z-Tiefe besitzen.

Der Algorithmus wird sehr oft wegen seiner Einfachheit in Bezug auf die Berechnung der Texture-Koordinaten verwendet. Auf heutigen Prozessoren kann die inkrementelle Berechnung durch sehr wenige und wenig Prozessorzeit kostende Operationen durchgeführt werden. Dies gilt vor allem dann, wenn die innere Schleife oder der ganze Algorithmus direkt in Maschinensprache codiert wird. Dabei wird häufig auf Floating-Point-Arithmetik verzichtet und statt dessen die schnelle Integer-Fixed-Point-Arithmetik verwendet. Die Texture Map hat meist 2er-Potenz-Maße (z.B. 64x64 Pixel), da so mittels einfachen Bitoperationen die Speicheradresse eines Texel aus u und v berechnet werden kann.

Zusätzliche Anwendungsgebiete des normalen Pattern Mapping sind das Environment Mapping und damit auch Phong Shading mit festen Lichtquellen. Beim Environment Mapping wird ein Bild der Umgebung auf ein Objekt texturiert. Dabei werden die Normalenvektoren der Eckpunkte als Bezugspunkte in die Texture Map interpretiert. Bei diesen Verfahren ist die perspektivische Verzerrung kaum wahrnehmbar. Das schon angesprochene Bump Mapping kann ebenfalls einfach realisiert werden. Meist werden auch direkt mehrere Flächen-Attribute über verschiedene Mappings verändert. Zum Beispiel findet häufig eine Kombination von Gouraud Shading und Texture Mapping statt (hier werden u, v und die Helligkeit interpoliert).

2.2 Korrektes perspektivisches Mapping

2.2 Korrektes perspektivisches Mapping

Eine korrekte Lösung des perspektivischen Texture Mapping Problems lieferte Paul Heckbert [Heck83]. Er beschreibt eine Methode, die eine inkrementelle Interpolation der homogenen Texture-Koordinaten vorsieht. Dabei ergibt sich ein Aufwand von drei Additionen, zwei Divisionen und einem Texture Zugriff [Heck89]. Paul Heckbert bezifferte den Aufwand, um für ein Polygon die Projektionsmatrix zu berechnen, mit 133 arithmetischen Operationen.

Henry P. Moreton beobachtete, daß die homogenen Texture-Koordinaten, die zum Linearen Interpolieren im Bildschirm-Koordinatenraum geeignet sind, einfach durch Division der Texture-Koordinaten durch w gewonnen werden können. Die Texture-Koordinaten an einem Pixel werden wiedergewonnen, indem u/w und v/w durch 1/w geteilt werden. Jeder im Objekt-Koordinatenraum definierte Parameter kann in dieser Weise korrekt interpoliert werden. Diese neue Methode und der zugehörige Beweis der Korrektheit finden sich in einem Artikel über Texture Mapping von Paul Heckbert und Henry Moreton [HeMo91].

Schritte beim korrekten perspektivischen Mapping Algorithmus:

1. Jedem Eckpunkt des Polygons wird eine Liste mit n Parametern
   (r₁, r₂, ..., r_n) zugeordnet. Diese enthält die u- und v-Koordinaten, ggf. auch noch zusätzliche Parameter zur Schattierung.
2. Die Objekt-Koordinaten jedes Eckpunktes werden mittels einer 4× 4-Matrix in homogene Bildschirm-Koordinaten transformiert. Dies liefert die Werte
   (xw, yw, zw, w) an jedem Eckpunkt.
3. An jedem Eckpunkt werden die homogenen Bildschirm-Koordinaten, die Parameter r_i und die Zahl 1 durch w geteilt. Dies liefert die Variablenliste (x, y, z, s₁, s₂, ...., s_n+1), wobei s_i = r_i / w für alle i ≤ n und s_n+1 = 1/w.
4. Rendering des Dreiecks im 2D-Screen Space durch Lineare Interpolation aller Parameter. An jedem Pixel wird r_i = s_i / s_n+1 für alle n Parameter berechnet. Diese Parameter werden zum Texturieren und Schattieren verwendet.

Dieser Algorithmus liefert ein perfektes Ergebnis.

Die inkrementelle Berechnung der u- und v-Koordinaten ergibt drei Additionen und zwei Divisionen, um für einen Pixel die Texel-Koordinaten zu berechnen. Da bei den meisten heutigen Prozessoren die Division sehr viel Rechenzeit beansprucht, ist dieser Algorithmus entsprechend rechenintensiv.

2.3 Adaptiver Zerteilungs-Algorithmus

Der Adaptive Zerteilungs-Algorithmus stellt eine Erweiterung zum Bilinearen Mapping-Algorithmus dar. Bei dem Adaptiven Zerteilungs-Algorithmus (Triangle Decomposing Algorithm, Triangle Subdivision Algorithm) werden alle drei Kanten des Dreiecks auf perspektivische Verzerrung getestet. Ist diese an einer Kante größer als ein vorgeschriebener Faktor, so muß das Dreieck an dieser Kante unterteilt werden. Auf dieser Kante wird der Unterteilungspunkt so berechnet, daß dieser genau im Mittel der Verzerrung liegt. Auf die dabei entstehenden Dreiecke wird solange rekursiv der Unterteilungstest angewandt, bis keine Unterteilung mehr notwendig ist (d.h. bis die Abweichung ausreichend minimal ist). Dies geschieht mit dem Ziel, die Verzerrung, die beim Texturieren mit dem Bilinearen Mapping-Algorithmus entstehen würde, bis auf ein vertretbares Maß zu reduzieren.

Es ergeben sich für ein Dreieck acht verschiedene Fälle:

1. Alle drei Kanten müssen unterteilt werden.

Es entstehen vier Dreiecke:

Dreieck[a,b,c]

⇒ Dreieck[a,ab,ac] + Dreieck[ab,b,bc] + Dreieck[ac,bc,c] + Dreieck[ab,bc,ac]

2. - 4. Zwei Kanten müssen unterteilt werden.

Es entstehen drei Dreiecke:

Dreieck[a,b,c] ⇒ Dreieck[ab,b,bc] + Dreieck[a,bc,c] + Dreieck[a,ab,bc]
oder Dreieck[a,b,c] ⇒ Dreieck[a,ab,ac] + Dreieck[ab,b,c] + Dreieck[ac,ab,c]
oder Dreieck[a,b,c] ⇒ Dreieck[ac,bc,c] + Dreieck[a,b,ac] + Dreieck[ac,b,bc]

5. - 7. Eine Kante muß unterteilt werden.

Es entstehen zwei Dreiecke:

Kante ab wird unterteilt: Dreieck[a,b,c] ⇒ Dreieck[a,ab,c] + Dreieck[ab,b,c]
oder Kante bc wird unterteilt: Dreieck[a,b,c] ⇒ Dreieck[a,b,bc] + Dreieck[a,bc,c]
oder Kante ac wird unterteilt: Dreieck[a,b,c] ⇒ Dreieck[ac,b,c] + Dreieck[a,b,ac]

8. Keine Unterteilung.

Das Dreieck [a,b,c] wird gezeichnet.

Zum Zeichnen wird der Bilineare Mapping-Algorithmus verwendet, da der Fehler, der durch die perspektivische Verzerrung entsteht, unterhalb eines Grenzwertes liegt.

Die Genauigkeit des Algorithmus ist beliebig über einen Parameter einstellbar. Der Parameter legt fest, ab welcher Abweichung des Bildmittelpunktes einer Kante von dem perspektivischen Mittelpunkt dieser Kante, die Kante unterteilt werden muß. Wählt man als Parameter 1, so liefert dieser Algorithmus ein perfektes Ergebnis.

Sinnvoll ist allerdings nur eine Parameter Einstellung größer 1, da sonst der korrekte perspektivische Mapping Algorithmus schneller ist. Zu groß sollte der Parameter dagegen auch nicht gewählt werden, da sonst keine Unterteilung und somit auch keine Verbesserung erzielt wird. Dagegen wird zusätzliche Zeit zum Testen der Kanten auf Unterteilung benötigt. Weiterhin ist die Einstellung des Parameters von der gewählten Auflösung abhängig: je höher die Auflösung, desto mehr Abweichung ist für das menschliche Auge akzeptabel.

Abbildung 2.6: Würfel als Liniengitter. Keine Zerteilung.	Abbildung 2.7: Bilinear texturierter Würfel. Keine Zerteilung.
Abbildung 2.8: Würfel als Liniengitter mit Zerteilungsfaktor 100.	Abbildung 2.9: Bilinear texturierter Würfel mit Zerteilungsfaktor 100.
Abbildung 2.10: Würfel als Liniengitter mit Zerteilungsfaktor 10.	Abbildung 2.11: Bilinear texturierter Würfel mit Zerteilungsfaktor 10.
Abbildung 2.12: Würfel als Liniengitter mit Zerteilungsfaktor 1.	Abbildung 2.13: Bilinear texturierter Würfel mit Zerteilungsfaktor 1.

Die Geschwindigkeit des Adaptiven Zerteilungs-Algorithmus hängt stark von dem gewählten Abweichungsparameter ab. Der Unterteilungstest sowie die Berechnung der Teilungspunkte erfordert Rechenaufwand. Hinzu kommt, daß zunehmend mehr Kanten entstehen, die interpoliert werden müssen. Die entstehenden, aneinander liegenden Kanten werden von zwei Dreiecken eingenommen und sogar doppelt interpoliert.

Der Adaptive Zerteilungs-Algorithmus findet in heutigen Software Rendering Lösungen häufig Anwendung. Er kann bestehende Rendering Systeme sehr einfach erweitern, da er auf den Bilinearen Mapping-Algorithmus aufsetzt. Dies gilt sowohl für Software Systeme, und auch insbesondere als Aufsatz für Hardware Systeme, die meist einen einfachen nicht-perspektivisch korrekten Mapping-Algorithmus unterstützen.

2.4 Scanline-Subdivision-Algorithmus

Der Scanline-Subdivision-Algorithmus (Scan-Linien-Unterteilung) ist eine Erweiterung des korrekten perspektivischen Mapping Algorithmus. Um den Rechenaufwand für die korrekte Berechnung zu verringern und so die Ausführungsgeschwindigkeit stark zu erhöhen, verzichtet man auf einen Teil der Genauigkeit des perspektivischen Mapping und führt die korrekte perspektivische Berechnung der u- und v-Koordinaten in einer Zeile (Scan-Linie) statt für jeden Pixel nur alle n Pixel aus. In der Regel wählt man n = 16, also 16er Schrittweite. Bei den dazwischenliegenden Pixeln ermittelt man die Texture-Koordinaten durch Lineare Interpolation der u- und v-Koordinaten wie bei dem Bilinearen Mapping-Algorithmus. Die Implementation erfordert somit zusätzlichen Programmcode.

• Die Lineare Interpolation der Texture-Koordinaten eines n-Pixel-Abschnittes kann auf modernen Prozessoren gleichzeitig mit der Berechnung der Interpolations-Deltas für den nächsten Abschnitt durchgeführt werden (z.B. auf dem Pentium Prozessor: Lineare Interpolation mit der Integer Einheit und Berechnung der Deltas mit der FPU Einheit).

• Statt den Span in festen Schrittweiten zu unterteilen, werden die u(x) und v(x) Funktionen auf Nicht-Linearität getestet und adaptiv unterteilt. Der Unterteilungstest muß in diesem Fall sehr einfach und schnell sein, um den Vorteil der wenigeren Divisionen nicht zu verlieren. In einer Newsgroup (vgl. [CSGA]) wurde vorgeschlagen, die Subdivision abhängig von der Größe der Division von der Differenz des linken und rechten Wertes von 1/w und der Differenz der x-Werte durchzuführen: je größer Δ (1/w)/Δ x, desto feiner die Subdivision. Zusätzlich ist zu bedenken, daß bei nicht-fester Schrittweite keine automatische Loop-Unrolling-Optimierung vom Compiler stattfindet. Diesen Nachteil kann man aber bei Maschinensprachecodierung wieder ausgleichen, indem man an die richtige Position der ausgerollten Schleife springt.

Im folgenden werden einige Aspekte aufgezeigt, die für eine Anwendung des Scanline-Subdivision-Algorithmus sprechen.

• Es handelt sich um eine Software-Implementierung.
• Der korrekte Algorithmus ist nicht schnell genug.
• Die Fehler des Bilinearen Mapping-Algorithmus sind für die Anwendung nicht tragbar.
• Es steht keine optimierte Version (z.B. in Hardware) des Bilinearen Mapping-Algorithmus zur Verfügung.
• Die bei Varianten angesprochenen Punkte können ausgenutzt werden.

2.5 Linien mit konstantem Z-Wert

Einen völlig anderen Weg geht der "Constant Lines of Z"-Algorithmus. Statt das Polygon durch horizontale Linien (Scan-Linien-Algorithmus) zu zeichnen, werden schräge Linien verwendet. Diese werden so gewählt, daß die Pixel einer Linie auf gleichem Z-Wert liegen. Dadurch ergibt sich in diesen Linien keine perspektivische Verzerrung, da auch im Texture-Space eine konstante Schrittweite vorliegt. Das Problem bei diesem Algorithmus besteht darin, die Linien so zu zeichnen, daß keine "Pixel-Löcher" im Dreieck entstehen.

Innerste Schleifen beim "Constant Lines of Z"-Algorithmus:

• Der Algorithmus liefert ein korrektes Ergebnis.
• Es entsteht nur ein geringer Rechenaufwand pro Pixel.

• Der Algorithmus hat ein schlechtes Cache-Verhalten, da die Pixel nicht in "Scanline-Order" bearbeitet werden.
• Der Algorithmus ist schwierig zu implementieren.

2.6 Ausblick: Quadratische Interpolation

Ein Algorithmus, der hier keine genauere Betrachtung findet, ist der Quadratische Interpolations-Algorithmus. Dieser verwendet beim Zeichnen der Scan-Linien keine lineare, sondern eine quadratische Interpolation (der u- und v- Texture-Koordinaten), um die perspektivische Verzerrung zu approximieren. Da über diesen Algorithmus wenig Literatur zur Verfügung steht, wurde von einer genaueren Untersuchung des Algorithmus abgesehen. Er liefert definitionsgemäß kein korrektes Ergebnis.

Die innerste Schleife beim Quadratischen Interpolations-Algorithmus kommt ohne Divisionen aus. Mit vier Additionen ist sie nur unwesentlich langsamer als der "normale" bilineare Algorithmus (zwei Additionen). Für die Berechnung der Delta-Werte ist zusätzlicher Rechenaufwand nötig. Dort ist auch die kritische Implementationsstelle. Es sollte sehr viel Sorgfalt darauf gelegt werden, die Berechnung so zu gestalten, daß in allen Fällen eine gute Approximation der nicht-linearen Steigung der u- und v-Koordinaten erreicht wird.

Eine ausführlichere Betrachtung des Quadratischen Interpolations-Algorithmus findet sich in [Wolb90].

Innerste Schleife beim Quadratischen Interpolations Algorithmus:

3  Programm

Als Entwicklungs-Plattform für das in dieser Studienarbeit zu erstellende Programm wurde NEXTSTEP gewählt, welches auf verschiedenen Hardware-Plattformen unterstützt wird, wie z.B. Sparc, Intel-PC oder NEXT-Rechner.

Das Programm wurde mit dem ProjectBuilder entwickelt und ist in der Programmiersprache Objective-C geschrieben. Ziel des Programms ist eine Visualisierung der Unterschiede zwischen den vorgestellten Algorithmen.

3.1 Objektdiagramm

Die Pfeile zeigen die Interaktion der Objekte RenderControl, Object3D und RenderView. Wie die obige Abbildung verdeutlicht, steuert das RenderControl Objekt sowohl das Object3D wie auch den RenderView. Es folgt eine detaillierte Beschreibung der Funktion der drei Objekte.

3.2 Die Objekte

Im folgenden werden die einzelnen Objekte vorgestellt. Die allgemeine Aufgabenzuordnung wird erklärt, und in einer Auflistung werden die implementierten Methoden beschrieben.

3.2.1 RenderControl

Behandelt die Aktionen der Benutzerschnittstelle und kontrolliert das Rendering der 3D-Objekte anhand von Parametern.

Keine.

3.2.2 Object3D

Stellt die interne Repräsentation eines 3D-Objektes dar. Beinhaltet Methoden zur Rotation und Projektion des 3D-Objektes, sowie die Ausgabe einer Ansicht des Objektes als Menge von Polygonen in sortierter Reihenfolge.

typedef struct

{
float x;
float y;
float z;
} _Point3D;

Die Datenstruktur beinhaltet die 3D-Koordinaten eines Punktes.

typedef struct

{
int p1,p2,p3;
float u1,u2,u3;
float v1,v2,v3;
}_Triangle;

Ein Dreieck besitzt die folgenden Attribute:

p1,p2,p3: Referenzen auf die Punkte des Dreiecks
u1,u2,u3: u-Koordinaten der drei Eckpunkte
v1,v2,v3: v-Koordinaten der drei Eckpunkte

3.2.3 View

Der View kontrolliert das Rendering in den Framebuffer und die Ausgabe des Framebuffers auf dem Bildschirm sowie die Verwaltung der Texture. Die Zeichen- und Texture Mapping Algorithmen sind hier implementiert.

3.3 Renderingvorgang

1. Aus den x-, y-, z-Rotationsparametern und dem Zoomfaktor wird die Transformationsmatrix berechnet.
2. Die Punkte des 3D-Objektes werden anhand der Transformationsmatrix transformiert.
3. Die Flächen des transformierten 3D-Objektes werden auf Rückflächenunterdrückung getestet.
4. Die anzuzeigenden Flächen werden sortiert.
5. Die Flächen werden in sortierter Reihenfolge gezeichnet (übernimmt RenderView).

4  Benutzen des Visualisierungsprogramms

Im letzten Kapitel wird die Bedienung des NEXTSTEP Programmes beschrieben. Der Benutzer sollte mit der allgemeinen Bedienung der NEXTSTEP Oberfläche vertraut sein.

4.1 Das Hauptmenu (Dock)

Das Programm wird aus dem Workspacemanager mit Doppelklick gestartet. Danach erscheinen das Hauptmenu und der View.

4.1.1 Info...

Zeigt ein Info-Fenster an. Dieses gibt Auskunft über das Programm und den Autor. Das Info-Fenster kann über den Close-Button des Fensters wieder geschlossen werden.

Es erscheint eine File-Select-Box zur Auswahl einer Bilddatei. Unterstützt werden TIFF-Dateien in beliebiger Größe.

4.1.3 Load Object

Dieser Menupunkt dient zum Laden von 3D-Körpern. Es erscheint eine File-Select-Box zum Selektieren einer Datei. Diese Datei wird dann geladen.

4.1.4 Hide

Versteckt das DOCK-Fenster auf der NEXT-Oberfläche.

4.1.5 Quit

Das Programm wird beendet.

4.2 Der View

4.2.1 Einstellen des Mapping Algorithmus

Über die Radio Buttons kann der zu benutzende Polygon-Zeichen-Modus ausgewählt werden. Neben den vorgestellten Algorithmen stehen auch zusätzliche Modi zur Verfügung, die zur Verständlichkeit beitragen sollen.

4.3 Render Button

Die Betätigung des Buttons hat ein Neuzeichnen des Bildes mit dem aktuell eingestellten Algorithmus und Parametern zur Folge.

4.3.1 Einstellen der X-Y-Z Rotation und des Zoomfaktors

Das Einstellen der Rotationsfaktoren, um die das anzuzeigende Objekt rotiert werden soll, erfolgt über die Slider oder direkt über die Eingabefelder. Der Zoomfaktor zum raumlichen Heranholen und Distanzieren des Objektes kann auch über den Slider und das Eingabefeld eingestellt werden. Zulässige Werte liegen zwischen 0 und 1.

4.3.2 Einstellen des Abweichungsfaktors des Zerteilungs-Algorithmus

In dem dazugehörigen Eingabefeld (Decomposing Value) kann der Abweichungsfaktor eingestellt werden, der beim Dreiecks-Zerteilungs-Algorithmus verwendet werden soll. Diese Einstellung gilt sowohl für den Texture Mapping Algorithmus als auch für die veranschaulichende Darstellung des Objektes Linien Gitter der entstehenden Dreiecke.

Abbildungsverzeichnis

Abbildung 1.1: Interpolation entlang Polygonkanten und Scan-Linien.
Abbildung 1.2: Illustration des Scan-Linien-Algorithmus.
Abbildung 2.1: Perspektivisch korrekt texturierter Würfel.
Abbildung 2.2: Wirkung einer Zerlegung an der Kante ab auf den Parameter u.
Abbildung 2.3: Zerteilung in 4 Dreiecke.
Abbildung 2.4: Zerteilung in 3 Dreiecke.
Abbildung 2.5: Zerteilung in 2 Dreiecke.
Abbildung 2.6: Würfel als Liniengitter. Keine Zerteilung.
Abbildung 2.7: Bilinear texturierter Würfel. Keine Zerteilung.
Abbildung 2.8: Würfel als Liniengitter mit Zerteilungsfaktor 100.
Abbildung 2.9: Bilinear texturierter Würfel mit Zerteilungsfaktor 100.
Abbildung 2.10: Würfel als Liniengitter mit Zerteilungsfaktor 10.
Abbildung 2.11: Bilinear texturierter Würfel mit Zerteilungsfaktor 10.
Abbildung 2.12: Würfel als Liniengitter mit Zerteilungsfaktor 1.
Abbildung 2.13: Bilinear texturierter Würfel mit Zerteilungsfaktor 1.
Abbildung 2.14: Approximation von u(x) beim Scanline-Subdivision.
Abbildung 2.15: Texturierter Würfel (Scanline-Subdivision-Algorithmus).
Abbildung 4.1: Dock.
Abbildung 4.2: Info-Fenster.
Abbildung 4.3: View.

Literaturverzeichnis