Fachbereich 4: Informatik

Depth-Peeling mit Hilfe von

Textur-Atlanten

Studienarbeit im Studiengang Computervisualistik

vorgelegt von

Simon Schmitt

Betreuer: Prof. Dr. Stefan Müller, Dipl.-Inform. Niklas Henrich (Institut für Computervisualistik, AG Computergraphik)

Koblenz, im Mai 2010

Erklärung

Ich versichere, dass ich die vorliegende Arbeit selbständig verfasst und keine anderen als die angegebenen Quellen und Hilfsmittel benutzt habe.

Ja Nein

Mit der Einstellung dieser Arbeit in die Bibliothek bin ich einverstanden. □ □

Der Veröffentlichung dieser Arbeit im Internet stimme ich zu. □ □

Ort, Datum Unterschrift

�

1

Inhalt

1. Einführung ................................................................................................................. 2

Was ist Depth Peeling ............................................................................................... 2

Anwendungsbereiche ............................................................................................... 3

Ziel dieser Arbeit ....................................................................................................... 4

Einfacher Ansatz mit Tiefenmap ............................................................................... 4

2. Atlasbasiertes Depth Peeling im Detail ..................................................................... 6

Idee ........................................................................................................................... 6

Implementierung ...................................................................................................... 6

1. Rendern in den Texturatlas ............................................................................... 6

2. Sortierung .......................................................................................................... 8

3. Indexierung ..................................................................................................... 10

4. Darstellung ...................................................................................................... 11

3. Auswertung ............................................................................................................. 13

Vergleich mit Standardverfahren ............................................................................ 13

Texturzugriffe ...................................................................................................... 13

Zeitaufwand ........................................................................................................ 13

Speicheraufwand ................................................................................................ 14

Anwendung unter kontrollierten Bedingungen ...................................................... 15

Was sind kontrollierte Bedingungen ................................................................... 15

Vergleichsbilder ...................................................................................................... 16

Probleme ................................................................................................................. 18

Überabtastung .................................................................................................... 18

Unterabtastung ................................................................................................... 19

Auflösung des Texturatlasses .............................................................................. 20

Mögliche Lösungen ................................................................................................. 21

Interpolation gegen Unterabtastung .................................................................. 21

Überzählige Pixel verwerfen gegen Überabtastung: .......................................... 22

Rendern abhängig vom Blickwinkel .................................................................... 23

Texturatlas erweitern .......................................................................................... 23

4. Zusammenfassung .................................................................................................. 24

Ausblick ................................................................................................................... 24

Fazit ......................................................................................................................... 25

Literaturverzeichnis .................................................................................................... 26

2

1. Einführung

Was ist Depth Peeling

Depth Peeling ist ein Verfahren um bei einem computergenerierten Bild Ebenen darzustellen, welche der Kamera normalerweise durch weiter vorne liegende Elemente verdeckt sind. Zunächst wird eine Szene so dargestellt wie es dem natürlichen Sehen entspricht. Im ersten Depth-Peeling-Schritt wird durch Depth Peeling für jeden Bildpunkt die vom Betrachter aus zweite, dahinterliegende Oberfläche dargestellt; im nächsten Schritt für jeden Punkt die 3. Ebene usw. Die in einer Ebene dargestellten Bildpunkte müssen nicht zum jeweils gleichen Objekt gehören; sie müssen nur an dieser Bildposition nur die gleiche Anzahl an vor ihr liegenden Ebenen haben. Die geschieht solange, bis an einem Bildpunkt keine Ebene mehr vorhanden ist.

Abbildung 1. Einfaches Beispiel für Depth Peeling: die ersten 4 Ebenen mit Blick von der Seite und dem resultierenden Bild.

3

Anwendungsbereiche

Depth Peeling findet in verschiedenen Bereichen der Computergrafik Anwendung.

Eine häufige Anwendung sind Transparenzen. Sie können einfach dargestellt werden, indem mehrere hintereinander liegende Ebenen eines Objekts von hinten nach vorne, mit ihrem Transparenzwert multipliziert, überlagert in der korrekten Reihenfolge dargestellt werden. Dies ist mit Depth Peeling auch möglich, wenn mehrere Flächen nicht in der richtigen Reihenfolge vorliegen, die Rendering-Pipeline nicht sortiert erreichen oder sich schneiden.

Abbildung 2. Transparenzen durch Überlagerung mehrerer Ebenen (aus: [Dua05] )

Es existieren viele weitere Anwendungsmöglichkeiten, in vielen davon werden die Tiefenebenen einer Szene nicht direkt aus der Sicht des Betrachters dargestellt, sondern aus anderen Perspektiven gerendert und weiterverwendet. So kommt Depth Peeling beispielsweise bei der Berechnung weicher Schattenkanten [Dua05] zum Einsatz, auch als Teil einer GPU-basierten Flusssimulation [Flw05] und bei der virtuellen Pyeloskopie [Bor06] , einer Untersuchung des Nierenbeckens [Pye09] , und beim Ray Casting [Tiled] wird es verwendet.

Abbildung 3 (a) und (b). Shadowmap in mehreren Ebenen und der resultierender Schatten. (aus: [Shm08] )

4

Ziel dieser Arbeit

Normales Depth Peeling [Eve01] baut die Darstellung jeder Ebene auf der davor liegenden Ebene auf, erfordert also für jede einzelne weiter von der Kamera entfernt liegende Schicht einen weiteren Renderschritt, in welchem die komplette Geometrie die Rendering-Pipeline durchläuft. Der Rechenaufwand für weit vom Betrachter entfernte Ebenen ist entsprechend hoch. Ziel dieser Arbeit ist es den Aufwand des Depth Peelings zu reduzieren und die Geschwindigkeit zu erhöhen indem die Tatsache ausgenutzt wird, dass die ganze Szene die OpenGL-Rendering-Pipeline bereits bei einem einzigen Rendern durchläuft. Möglichst alle Informationen sollen gespeichert und effizient verwendet werden um daraus einfach einzelne Ebenen zu extrahieren.

Einfacher Ansatz mit Tiefenmap

1. Beim einfachen Ansatz um Depth Peeling durchzuführen [Eve01] wird die Szene zunächst normal, mit aktiviertem Tiefenpuffer gerendert. Die Tiefenwerte des entstandenen Bildes werden in eine Tiefenkarte eingetragen, welche für jeden Bildpunkt den vordersten Tiefenwert (im Bereich 0-1.0) enthält, welcher durch den Tiefenpuffer automatisch geliefert wird.

Abbildung 4. Beispielszene in Realfarben und mit Tiefenwerten.

2. Um nun die erste tiefe Ebene des Bildes darzustellen, wird die Szene erneut

gerendert und durchläuft komplett die Rendering-Pipeline. Am Ende der Pipeline werden die Tiefenwerte der entstandenen Bildpunkte mit den Werten in der Tiefenmap verglichen, Vertices/Bildpunkte mit Tiefenwerten kleiner oder gleich der Tiefenmap werden dabei verworfen, zum Beispiel im Fragement-Shader eines OpenGL-Programms.

3. Für jede weitere Ebene werden die vordersten Tiefenwerte des entstandenen Bildes erneut als Tiefenkarte gespeichert. Die Szene durchläuft wieder die komplette Rendering-Pipeline. Wieder werden alle Vertices/Bildpunkte mit kleineren oder gleichen Tiefenwerten verworfen.

5

Abbildung 5. 1. Tiefenebene der Szene mit ihrer Tiefenkarte. Es sind zwei Renderschritte nötig um dieses Ergebnis zu erhalten. Die Tiefenkarte kann als Vergleichseingabe für die 2. Tiefenebene dienen.

Das Problem bei diesem Verfahren ist, dass für jede Ebene die komplette Szene neu die Rendering-Pipeline durchläuft und auf Basis der davor liegenden Ebene Vertices verworfen werden. Um die i. Ebene darzustellen wird die Szene i+1-mal gerendert, was durch den linearen Aufwand zu einer entsprechend niedrigen Performance in tieferen Ebenen führt.

Abbildung 6. Für jeden Renderschritt dient die Tiefenkarte aus dem vorherigen Durchgang als Eingabe.

6

2. Atlasbasiertes Depth Peeling im Detail

Idee

In dieser Arbeit setze ich eine Idee von Niklas Henrich um. Der von mir verfolgte Ansatz ermöglicht es, jede einzelne Ebene einer Szene in vier Schritten mit gleichem Aufwand darzustellen. Dazu wird die Farbinformation jeder Fläche in der Szene bereits beim ersten Renderschritt in einem Texturatlas gespeichert und mit zusätzlichen Ortsinformationen versehen. Der Texturatlas wird sortiert und indexiert, um zur Darstellung effizient ausgelesen werden zu können.

Um mehrere Schichten der gleichen Szene gleichzeitig darzustellen, z.B. für Transparenzeffekte müssen drei der vier Schritte des Verfahrens nur einmal ausgeführt werden. Lediglich der letzte mit wenig Aufwand verbundene Schritt muss für jede Ebene einmal durchgeführt werden.

Implementierung

Im Folgenden beschreibe ich die Umsetzung meiner Implementierung des Verfahrens in OpenGL 2.0 mit GLSL-Shadern.

1. Rendern in den Texturatlas

Jede Oberfläche der Szene wird mit einem GLSL-Shader-Programm, im Texturatlas an der vom Programm übergebenen Texturkoordinate abgelegt. Die Position im Kamera-3D-Raum wird im Vertex Shader berechnet und per Varying Variable an den Fragment-Shader weitergegeben.

Für jedes Pixel im Texturatlas werden im Fragment-Shader zusätzlich weitere Informationen abgespeichert: die letztendlich darzustellende Farbe, welche aus einem beliebigen Beleuchtungsverfahren stammen kann, sowie die Pixelkoordinaten und der Tiefenwert im Kamerakoordinatensystem. Dies wird in meinem Ansatz mit Texturen im Format2 D 32-Bit RGBA gelöst. Der Texturfilter wird auf GL_NEAREST gesetzt, da keine Interpolation zwischen den diskreten Einträgen gewünscht wird.

Textur A: RGB

enthält die letztendliche Farbe in der ein Pixel dargestellt wird.

Textur B: XYZI

enthält zu jedem Pixel die Bildschirmkoordinate X,Y und die Tiefe Z im 3D-Raum.

X und Y sind diskrete Werte im Bereich 0 – Viewport-Breite/-Höhe,

Z ist ein Fließkommawert im Bereich -1.0 – 1.0.

I wird zunächst mit „-1“ initialisiert und erhält im 3. Schritt den Index.

In Textur A bleibt einer der vier Wert ungenutzt, welcher z.B. verwendet werden kann um Transparenzen, Normalen oder andere je nach Anwendung benötigte Werte zu speichern. Nicht genutzte Bereiche des Texturatlasses werden in Textur A und B komplett mit „-1“ gefüllt.

7

In dem Texturatlas sind nun alle für die Darstellung nötigen Informationen der gesamten Szene gespeichert.

Die Größe des Texturatlasses muss nicht der Größe des Viewports entsprechen, sie muss nur Platz bieten, um alle Flächen der Szene Pixelgenau zu speichern und mindestens die Größe des Viewports haben, damit der Index (Schritt 3) eingetragen werden kann. Um optimal sortiert werden zu können, sollte die Gesamtpixelzahl einer Zweierpotenz entsprechen.

Abbildung 7 (a) und (b). Beispielszene aus Kamerasicht (links) und von der Seite gesehen mit Tiefenwerten der drei Rechtecke

Abbildung 8. Neu erstellter Texturatlas der Beispielszene: X,Y Koordinaten in der jeweils oberen Zeile, der Tiefenwert Z darunter. Die Farbe aus Texturatlas Teil B entspricht der dargestellten.

8

2. Sortierung

Der Texturatlas wird auf der GPU mit absteigender Priorität nach X- und Y-Bildschirmkoordinate und dem Tiefenwert Z sortiert. Der Texturatlas wird dabei als linear (von 0 – Texturbreite*-höhe) angesehen. Angewendet wird hier das Sortiernetz Bitonic Merge Sort [Sed02] [Sor10] , welches sehr gut für parallele Anwendung auf einer Grafikkarte geeignet ist und optimale Geschwindigkeit verspricht. Es hat einen konstanten Aufwand von O(n log(n)2) unabhängig von den Eingabedaten. Auf Texur-Teil A und Teil B werden basierend auf den Informationen aus Teil B parallel die gleichen Sortieroperationen angewendet.

In mehreren Schritten läuft ein Fragment-Shader dabei über die Textur und sortiert diese. Da in einem Fragment-Shader nur je ein Pixel - das gerade aktuelle - geschrieben werden kann, muss der Vergleich zweier Pixel aus der Eingabetextur in jedem Sortierschritt immer zweimal stattfinden, einmal mit dem Vergleich „>“ einmal

mit „<“. Der größere Vergleichswert wird rechts in den Texturatlas geschrieben, der

niedrigere entsprechend links.

Der jeweilige Vergleichswert wird in bis zu drei Abfragestufen gesucht:

Erst wird die gespeicherte Bildschirmkoordinate X überprüft. Unterscheiden sich diese wird X als Vergleichswert verwendet, ist diese gleich, wird Bildschirmkoordinate Y verglichen und bei unterschiedlichen Werten verwendet. Ist auch der Y-Wert gleich, wird der Tiefenwert Z verglichen. Sollte auch dieser Fließkommawert wiedererwartend gleich sein, bedeutet dies, dass beide Pixel an der exakt gleichen Stelle im 3D-Raum liegen und ein sinnvoller Vergleichswert nicht vorhanden ist. Das im Texturatlas linke Pixel wird nun im aktuellen Sortierschritt an der linken Position eingetragen, das rechte an der anderen. Welcher der beiden Pixel-Farbwerte im letztendlichen Bild vorne dargestellt wird bleibt dabei abhängig von der ursprünglichen Position im Texturatlas dem Zufall überlassen.

Abbildung 9. Zwei identische Ebenen (grün und blau) und ihre Anzeige in einer Ebene. In der nächsten Ebene sind blaue und grüne Pixel vertauscht. In der dritten Ebene wird keine der beiden Flächen mehr angezeigt.

Abbildung 10. Bitonic Merge Sort Sortierschema (aus: [Srt05] )

9

Resultat

Im Texturatlas liegen, auf die leeren Bereiche folgend, hintereinander alle Pixel mit gleichen Bildschirmkoordinaten mit aufsteigendem Tiefenwert: Erst alle mit gleichem X-Wert aufsteigend, innerhalb dieser alle mit gleichem Y-Wert aufsteigend und innerhalb dieser schließlich alle mit aufsteigendem Z-Wert.

Abbildung 11. Sortierter Texturatlas. Alle leeren Pixel sind komplett mit „-1“ gefüllt.

Im einfachsten Fall muss zum finalen Rendern einer i.-Schicht nun nur noch das i.-Pixel gefunden werden, welches die passenden Bildschirmkoordinaten hat. Dies benötigt jedoch viele Texturzugriffe, wenn der Texturatlas für jedes darzustellende Pixel durchlaufen wird, welche in OpenGL teuer sind. Für jedes Bildschirmpixel muss der Texturatlas zunächst bis zum ersten Pixel mit passender Bildschirmkoordinate durchlaufen werden und pro Ebene ein weiterer Texturzugriff stattfinden.

10

3. Indexierung

Um die Zahl der Texturzugriffe im letzten Schritt zu minimieren wird für den Texturatlas ein Index erstellt, welcher für jedes Bildschirmpixel die Information enthält an welcher Position im Texturatlas die zugehörigen Pixel beginnen.

Ein Fragment-Shader läuft über jedes Pixel des Texturatlasses und trägt die Startposition s im vierten Platz des Texturatlasses Teil B als eine natürliche Zahl ein. Der Texturatlas wird auch hier als eindimensional angesehen. Die Startposition wird somit als natürliche Zahl im Bereich 0 – (Texturbreite * -höhe) gespeichert. Ist für ein Bildschirmpixel keine Fläche in der Szene vorhanden, so wird der Index mit „-1“ als

leer gekennzeichnet.

Die Indexierung benötigt in einem OpenGL-Programm wieder extrem viele Texturabfragen, ist aber nicht anders lösbar, da in OpenGL nicht beliebig auf Pixelwerte zugegriffen werden kann. Innerhalb eines einzelnen Renderdurchgangs kann nicht auf andere gerade geschriebener Texturpunkte zugegriffen werden. Daher wird sich der zusätzliche Aufwand durch die Indexierung erst beim Zugriff auf mehrere Ebenen lohnen.

Abbildung 12. Indexeinträge in kursiv. Die referenzierten Pixel sind durch fette Umrandung hervorgehoben. Alle übrigen Indexeinträge sind "-1"

11

4. Darstellung

Jede einzelne beliebige Ebene wird nun mit nur drei Texturzugriffen (a-c) auf den Texturatlas pro Bildschirmpixel dargestellt.

Um die Farbe für den aktuellen Ausgabepixels x,y in Ebene e zu erhalten sind folgende Schritte nötig:

a) Im Index I in Textur B wird zunächst die Pixel-Startpositon i abgefragt. Ist der gefundene Wert i =„-1“ so befindet sich in der Szene an dieser Stelle kein Objekt; die Hintergrundfarbe wird dargestellt und weitere Texturzugriffe für dieses Bildschirmpixel sind nicht nötig.

b) Auf den gefundenen Wert wird die gewünschte Ebene e hinzuaddiert (e+i), um die gesuchte Position im Texturatlas zu erhalten. An dieser Position e+i wird in Texurteil B die Bildschirmposition X,Y gelesen. Diese wird mit den aktuell gewünschten Bildschirmkoordinaten x,y verglichen. Sind x,y und X,Y gleich, so ist hier die gewünschte Position gefunden.

Sind die Bildschirmkoordinaten nicht die gewünschten, existiert in der Szene kein Objekt dieser Ebene mehr, in diesem Fall wird die Hintergrundfarbe dargestellt, Texturzugriff c ist nicht nötig.

c) Der an dieser Position e+i in Teil A liegende Farbeintrag RGB wird abgefragt und dargestellt bzw. kann weiter verwendet werden, zum Beispiel um Transparenz darzustellen.

Abbildung 13 (a) und (b). Kamerasicht und die verwendeten Pixelpositionen der Ebenen 0 (links) und 1 (rechts). In der 1. Ebene wird an der umrandet hervorgehobenen Bildschirmkoordinate Pixel 57 gefunden. Da die dort gespeicherten Koordinaten (4,3) nicht mit den Bildschirmkoordinaten übereinstimmen, wird keine Farbe dargestellt.

12

Zugriff auf mehrerer Ebenen

Sind mehrere Ebenen e gleichzeitig abzufragen sinkt die maximale Anzahl der Texturzugriffe auf 1 + e * 2 da die Startposition i im Index nur einmal pro Bildschirmpixel gelesen werden muss. Es muss somit nur noch einmal die Startposition und je gewünschter Eben e ein Pixel i + e überprüft werden.

Finden die Abfragen der Ebenen mit der tiefsten Ebene beginnend statt, ist sogar noch kleine Optimierung möglich, wenn der X,Y/x,y-Vergleich in aufeinanderfolgenden Ebenen emin bis emax umgekehrt stattfindet. Mit der entferntesten Schicht emax beginnend, wird die passende Farbe nacheinander bei Startposition i + emax beginnend absteigend gesucht. Für jedes Pixel findet der Vergleich der gesuchten Pixelposition mit der gespeicherten statt. Sobald ein solcher Eintrag mit X,Y = x,y gefunden wird, ist dieser Abfrage bei jedem weiteren Pixel unnötig. Im Texturatlas sind nur noch Pixel mit den gewünschten Koordinaten zu erwarten. So bleibt pro gesuchtem Pixel nur je ein einziger Texturzugriff auf die Farbe.

Abbildung 14. Ausschnitt aus einem sortierten Texturatlas mit optimalem Zugriff auf die Ebenen 2 bis 8 an den Koordinaten 25,5. Der Indexeintrag dort ist 55. Bei den Position 63-61 müssen nur die Koordinaten überprüft werden, bei Position 60 stimmen diese erstmals. Bei 59-57 muss nur noch die Farbe gelesen werden.

13

3. Auswertung

Vergleich mit Standardverfahren

Zum Vergleich habe ich auch den Standard Ansatz in OpenGL 2.0 implementiert und beide Verfahren miteinander verglichen.

Texturzugriffe

In OpenGL sind Texturzugriffe verglichen mit anderen Vorgängen in der Rendering-Pipeline aufwändig. Das texturatlasbasierte Verfahren benötigt in der Vorarbeit (Schritte 2-3) jedoch sehr viele Texturzugriffe. Bitonic Merge Sort wird der Texturatlas je Sortierschritt komplett gelesen und erneut geschrieben. Die Indexierung (Schritt 3) benötigt einmalig noch mehr Texturzugriffe. Für jede zu einer einzelnen Ebene zusätzlich benötigte Ebene ist die Anzahl der Texturzugriffe jedoch sehr gering, der Aufwand sinkt somit. Die Indexierung mit seinen vielen Texturzugriffen ist damit der langsamste Teil des Verfahrens.

Zeitaufwand

Im Vergleich mit einem Standardansatz ist der Zeitaufwand für die erste Ebene zunächst deutlich höher, da je ein zusätzlicher relativ aufwändiger Sortier- und Indexierungs-Schritt durchgeführt werden muss. Der Sortiervorgang ist auf der Grafikkarte mit Sortiernetz Bitonic Merge Sort [Sed02] relativ schnell und hat mit O(n log(n)2) einen konstanten Aufwand. Peter Kipfer und Rüdiger Westermann [Srt05] haben mit ihrer stark optimierten Implementierung schon auf einer Nvidia GeForce 6800 Ultra aus dem Jahr 2004 bei einer 256² großen Textur 90 komplette Sortiervorgänge/sec erreicht. Bei einer Texturgröße von 1024² sinkt dieser Wert auf 3,6 Sortiervorgänge/sec. Im atlasbasierten Verfahren müssen zwei (Teil A und B) statt nur einer Textur sortiert werden, welche je 4 32-Bit-Werte enthalten, während Kipfer und Westermann 16-Bit-Werte sortiert haben. Da die Leistung heutiger Grafikkarten jedoch deutlich höher ist und mit jeder Generation weiter steigt, ist zu erwarten, dass eine Sortierung in für Echtzeitanwendung geeigneter Geschwindigkeit mit aktuelleren Grafikkarten in greifbare Nähe rückt und bald sicher erreichbar ist. Der Zugriff auf den sortierten Texturatlas oder dessen Indexierung ist jedoch extrem teuer! Der Aufwand ist allerdings für jede beliebige einzelne Ebene konstant. Für weitere gleichzeitig darzustellende Ebene ist er mit maximal 2 Texturzugriffen je Bildschirmpixel und Ebene minimal.

Im Standardverfahren steigt der Aufwand dagegen linear mit der relativen Tiefe der darzustellenden Ebene, da für jede Ebene alle davor liegenden Ebenen die komplette Szene Rendering-Pipeline einmal durchlaufen muss.

Bei großen Szenen, mit vielen gleichzeitig darzustellenden Ebenen, wird somit irgendwann der Punkt erreicht, an dem atlasbasiertes Depth Peeling einen deutlichen Geschwindigkeitsvorteil bringt.

14

Abbildung 15. Aufwand des Standardverfahrens im Vergleich zum atlasbasierten für eine Ebene (links) und für mehrere Ebenen gleichzeitig (rechts).

Der Geschwindigkeitsunterschied des atlasbasierten Verfahrens ist selbst bei Zugriff auf 10 Ebenen einer Szene gleichzeitig zu gering um im Rahmen der Messgenauigkeit feststellbar zu sein, da die Vorarbeit, bestehend aus Sortieren und Indexieren, den weit größten Teil ausmacht. Der Zugriff auf die einzelnen Ebenen ist im Verhältnis dazu sehr einfach und viel zu schnell.

Speicheraufwand

Der Speicheraufwand des atlasbasierten Verfahrens ist vergleichsweise gering und unabhängig von der Anzahl der benötigten Ebenen. Mit zwei Texturen und je 4 32-Bit-Werten liegt er je Texturpixel bei 256 Bit. Das Standardverfahren muss dagegen je Ebene eine große Textur in der Größe des Viewports vorhalten. Sie liegt je Pixel im Viewport bei 4 * 32 Bit, also 128 Bit.

Der Vergleich des atlasbasierten Verfahrens mit einem 512² großen Texturatlas und des Standardverfahrens mit einem 512² großen Viewport zeigt folgenden Speicherbedarf:

Texturatlasbasiert:

0. Ebene: 512 (Breite) * 512 (Höhe)* 32 Bit * 4 (RGBA) * 2 (A und B) = 67 108 864

Er bleibt bei allen Ebenen identisch.

Standardverfahren

0. Ebene: 512 (Breite) * 512 (Höhe) * 32 Bit * 4 (RGBA) = 33 554 432

Wenn die jeweils davor gespeicherten Ebenen vorgehalten werden steigt der Speicheraufwand linear:

1. Ebenen: 67 108 864 Bit

2. Ebenen: 100 663 296 Bit

10. Ebenen: 301 989 888 Bit

15

Zunächst ist der Speicheraufwand des atlasbasierten Verfahrens also doppelt so große, ist jedoch bereits bei der 1. Ebene identisch. Ab der 2. Ebene wird der Speichervorteil zunehmend größer.

Abbildung 16. Speicherbedarf des Standardverfahrens und des atlasbasierten Depth Peelings.

Anwendung unter kontrollierten Bedingungen

Was sind kontrollierte Bedingungen

Die Darstellungsgröße in Pixeln jeder Fläche im Texturatlas, entspricht in horizontaler und vertikaler Richtung exakte der Darstellung im letztendlich angezeigten Bild. Je Ausgabepixel einer Fläche existiert genau ein zugehöriges Pixel im Texturatlas. Die Fläche im Atlas kann dabei beliebig gedreht oder aufgeteilt sein, solange die Pixelzuordnung des Bildschirms und des Texturatlasses exakt erhalten bleibt.

In diesem kontrollierten Fall funktioniert Depth Peeling mit Texturatlas gut, wenn auch für eine einzelne Ebene langsamer als das Standardverfahren. Die Darstellung geschieht ohne Artefakte, die Ergebnisse entsprechen exakt denen im Standardverfahren.

16

Vergleichsbilder

Abbildung 17. Beispielszene schematisch von der Seite

Abbildungen 18 (a-b).

17

Abbildungen 18 (c-h). Beispielszene atlasbasiert (links) und im Standardverfahren (rechts) in den

Ebenen 0-3. Die Auflösung im atlasbasierten Verfahren ist hier geringer.

18

Auch Transparenzen werden identisch dargestellt:

Abbildung 19. Transparente Szene mit 4 Ebenen mit 50% Transparenz

Nur eine Berechnung

Die Farbe jedes Punktes wird im texturatlasbasierten Verfahren nur einmal berechnet und zwar im ersten Schritt bei der Erstellung des Texturatlasses. Sie ist somit für alle Ebenen identisch, auch wenn davor liegende Ebenen entfernt werden. Da nicht wirklich die Geometrie entfernt wird, sondern lediglich ausgeblendet, können Schatten von verschwundenen Objekten somit weiterhin vorhanden sein, auch wenn davor liegende Ebenen entfernt werden. Gleiches gilt für indirektes Licht und globale Beleuchtung vorderer Objekte.

Dieser Effekte unterscheidet sich im Detail vom Standardverfahren, indem die Farbe für jede Ebene erneut berechnet wird. Zwar wird auch hier die Szenengeometrie nicht tatsächlich entfernt, dennoch sind Möglichkeiten denkbar, die Farbe abhängig von der Anzahl der davor liegenden Ebenen oder der Sichtbarkeit zu beeinflussen. Er grenzt jedoch die Anwendungsbereiche des texturatlasbasierten Verfahrens möglicherweise ein, kann jedoch auch gewünscht sein oder je nach Anwendung keine Rolle spielen. Ein Beispiel sind mit Depth Peeling berechnete Schatten, indem nur die Sichtbarkeit einzelner Ebenen untereinander getestet wird, jedoch keine Farbe benötigt wird.

Probleme

Wird der Texturatlas nicht optimal auf den aktuellen Viewport passend erstellt, führt dies zu Über- oder Unterabtastung, welche jeweils Artefakte und Fehler auslösen.

Überabtastung

Eine Oberfläche wird im Texturatlas größer, das heißt mit mehr Pixeln, eingetragen, als sie später in der Szene zu sehen ist. Da die X,Y-Koordinaten der Bildpunkte diskret als letztendliche Bildschirmkoordinaten x,y gespeichert werden, entstehen für eine Oberfläche im Texturatlas mehrere Pixel mit gleichen Bildschirmkoordinaten. Die entstandenen Tiefenwerte sind jedoch nicht diskret, werden damit also nur in

19

Ausnahmefällen gleich sein und zwar, wenn die Oberfläche senkrecht zur Blickrichtung liegt. Da jedes Pixel aus dem Texturatlas jedoch zwingen in einer Ebene Verwendung findet, wird eine Oberfläche in so vielen Ebenen dargestellt, wie Punkte im Texturatlas mit gleichen Bildkoordinaten vorhanden sind. Die selbe Oberfläche ist nun mehrfach in hintereinander liegenden Ebenen am gleichen Bildschirmpunkt zu sehen. Diese zusätzlichen Punkte verdecken in weiteren Schichten die dahinterliegenden Flächen, welche somit auch erst in weiter entfernten Ebenen dargestellt werden. Dies setzt sich weiter nach hinten in jede weitere Ebene fort. Im endgültigen Bild entstehen daher durch Unterabtastung an manchen Stellen mehr Tiefenebenen als in der Szene vorhanden sind.

Abbildung 20. Die gelbe und orange Fläche sind zu klein im Texturatlas eingetragen. In Ebene 0 (links) haben sie daher Lücken. In Ebene 1 (rechts) setzen sich diese auf die dahinterliegenden, korrekten Flächen fort.

Unterabtastung

Eine Oberfläche wird im Texturatlas kleiner eingetragen, als sie später in der Szene zu sehen ist. Dadurch sind im Texturatlas weniger Pixel vorhanden, um die benötigten Informationen zu speichern, als für die Darstellung nötig sind. In den diskreten X,Y-Koordinaten der Bildpunkte entstehen Sprünge. Im sortierten Texturatlas werden für einige Bildpunkte x,y daher keine zu der Fläche gehörenden Pixel mit passenden Koordinaten X,Y gefunden. Das Objekt wird an diesen Stellen nicht dargestellt. Möglicherweise wird jedoch ein Pixel mit passenden Koordinaten X,Y gefunden, welches zu einer anderen, dahinter liegenden Fläche gehört, in diesem Fall wird diese Fläche dargestellt, obwohl sie eigentlich noch verdeckt sein sollte. Es entstehen Lücken in Oberflächen, an denen dahinterliegende Flächen sichtbar werden. Diese Lücken setzen sich nach hinten über alle Ebenen fort. So enthält das endgültige Bild an verschiedenen Stellen weniger Tiefenebenen als eigentlich vorhanden sind.

20

Abbildung 21. Die orange und gelbe Fläche sind zu groß in den Texturatlas eingetragen. Sie verschwinden daher auch in Ebene 1 (links) und 2 (rechts) nicht vollständig.

Selbstverständlich können Über- und Unterabtastung auch in einer Oberfläche gleichzeitig auftreten, wenn der Eintrag einer Fläche im Texturatlas in eine Richtung gestaucht und die andere gestreckt ist oder an unterschiedlichen Stellen gestreckt oder gestaucht ist.

Abbildung 22. Ebene 0 von vorne (links) und um 45° gedreht. An der grünen Fläche tritt mit der Drehung Unterabtastung auf . An der Orangenen Fläche verschwindet die Unterabtastung, Überabtastung ist in tieferen Ebenen erkennbar.

Auflösung des Texturatlasses

Auch eine unterschiedliche Auflösung des Texturatlas bei ansonsten gleicher Szene und passendem Viewport kann zu Artefakten an Rändern von Flächen führen. Dies geschieht, da in OpenGL Texturen üblicherweise im Bereich 0.0 – 1.0 an Flächen gebunden werden, ihre Positionen im Texturatlas jedoch mit diskreten Werten im Bereich 0 – Bildschirmbreite/-Höhe gespeichert werden. Der Eintrag im Texturatlas kann sich daher durch Rundungen verschieben. Auch ein größerer Texturatlas kann

21

gegenüber einem kleineren diesen Effekt zeigen, während die Darstellung im kleineren korrekt ist.

Abbildung 23. Zwei Ebenen des gleichen Objekts. Links korrekt mit Texturauflösung 128², rechts mit 256². Die höhere Auflösung führt zu Artefakten an den Rändern.

Den Texturatlas soweit zu vergrößern, bis die Artefakte vernachlässigbar sind, ist daher nicht zielführend.

Mögliche Lösungen

Interpolation gegen Unterabtastung

Zwischen den Bildpunkten könnten interpolierte Farbwerte dargestellt werden, dies ist jedoch mit mehreren Problemen verbunden.

Interpolation nach dem Sortieren im Texturatlas:

An dieser Stelle ist im Texturatlas nicht mehr bekannt, welche Bildpunkte zur gleichen Fläche gehören. Da trotz fehlender Pixel einer Fläche häufig ein Pixel einer anderen Fläche mit den gleichen Koordinaten gefunden wird, lässt sich anhand dieser Information nicht mehr entscheiden, ob interpoliert werden muss oder sich dort wirklich eine Lücke befindet. Befindet sich dort eine Lücke in der Geometrie der Szene darf nicht interpoliert werden, sondern die nächste Ebene muss dargestellt werden.

Könnte dies entschieden werden, bliebe es noch problematisch die zusätzlichen Pixel an der korrekten Position im Texturatlas zu speichern. Dazu müsste entweder für jedes eingefügte Pixel der restliche Texturatlas um eine Position verschoben werden um Platz zu schaffen, oder der Texturatlas erneut sortiert werden. Beide Möglichkeiten sind mit Leistungsverlusten verbunden.

Vor dem sortieren im Texturatlas interpolieren:

Auch hier ist nicht mehr bekannt, welche Pixel zur gleichen und ununterbrochenen Fläche gehören. Würde die Zuordnung zu Objekten vom Programm mit an den Shader übergeben, so ist dadurch auch noch nicht die Form von Objekten bekannt. So kann eine mit einer Textur versehene Fläche eines konkaven Objekts durchaus mehrfach an den gleichen Bildschirmkoordinaten zu sehen sein.

22

In beiden Fällen ist nicht einfach zu entscheiden, welche Farbe und welchen Tiefenwert das eingefügte Pixel erhält. Das Hinzufügen vieler weiterer Pixel, kann außerdem möglicherweise dazu führen, dass die Größe des Texturatlas überschritten wird.

Überzählige Pixel verwerfen gegen Überabtastung:

Pixel mit mehreren gleichen Koordinaten können verworfen werden, wobei Information aus dem Texturatlas verloren gehen.

Im sortierten Texturatlas:

Hier ist die Zuordnung zu Ebenen oder Objekten nicht mehr verfügbar. So könnte ein Objekt mehrfach mit gleicher X,Y-Koordinate aber unterschiedlichem Z-Wert vorhanden sein. Es kann durchaus korrekt sein, ein Objekt mehrfach darzustellen, schon die Vorder- und Rückseite eines Objekts, führen dazu, dass das Objekt für jedes Bildschirmpixel zweimal eingetragen wird. Aus den im Texturatlas gespeicherten Werten lässt sich nicht schließen ob ein Pixel verworfen werden muss. Zudem müsste der Texturatlas für jedes einzelne entfernte Pixel eine Position nach links verschoben werden, was diesen Schritt teuer macht. Alternativ könnte der Texturatlas erneut sortiert werden, was jedoch ebenfalls teuer ist. Pixel im Texturatlas als „leer“ zu markieren, würde den bewusst einfachen Schritt 4 des Verfahrens jedoch komplizierter machen, da er auf leere Pixel entsprechend reagieren muss.

Im unsortierten Texturatlas:

Auch Pixel vor dem Sortieren des Texturatlasses weg zu werfen ist nicht einfach möglich, da auch hier die Zuordnung zu Objekten nicht bekannt ist. Wie beim Interpolieren müssten genaue Informationen vom Programm übergeben werden, wobei konkave Objekte durchaus mehrfach an der gleichen Bildschirmposition vorhanden sein könnten und damit tatsächlich mehrfach eingetragen werden müssen.

Könnte entschieden werden, ob ein Pixel verworfen wird, müsste zusätzlich entschieden werden, welches der Pixel verworfen wird, wenn diese unterschiedliche Farben oder Tiefenwerte haben, oder wie aus den Werten ein geeigneter neuer generiert werden könnte.

Sowohl die Interpolation als auch das Verwerfen von Pixeln würden natürlich beide nicht das jeweils andere Problem lösen und die Entscheidung, welche der beiden Möglichkeiten zum Einsatz kommt ist kaum zu treffen, da schon in den beiden einzelnen Fällen kaum erkennbar ist, ob Über-/Unterabtastung auftritt.

23

Interpolation oder das Entfernen von Pixeln erst bei der Darstellung würden – könnte hier diese Entscheidung getroffen werden – den einfachen vierten Schritt komplexer machen und damit den Vorteil bei mehreren gleichzeitig verwendeten Ebenen verringern.

Rendern abhängig vom Blickwinkel

Flächen im ersten Schritt vom Blickwinkel abhängig in den Texturatlas zu rendern wäre ebenfalls nur in kontrollierten Szenen in denen alle Parameter bekannt sind möglich. Informationen über die Geometrie und Ausrichtung der Fläche und die Szene müssen den Shadern bei der Erstellung exakt bekannt sein. Ungenauigkeiten wegen der Umrechnung der Texturkoordinaten im Bereich 0.0 – 1.0 in die diskreten gespeicherten X,Y-Bildschirmkoordinaten sind zu erwarten. (siehe „Auflösung des

Texturatlasses“)

Texturatlas erweitern

Es ist denkbar, im Texturatlas mehr Informationen über die Geometrie und die Zugehörigkeit einzelner Flächen zueinander zu speichern, um in weiteren Schritten mehr Entscheidungsgrundlagen über Interpolation oder das Verwerfen von Pixeln zu erhalten. Jede Erweiterung des Texturatlasses um benötigte Informationen würde seine Größe erhöhen und somit den Speichervorteil verringern. Es würde auch zu mehr Texturzugriffen führen und Geschwindigkeit verringern.

24

4. Zusammenfassung

Ausblick

Das texturbasierte Verfahren ist ausbaufähig, falls die vorhandenen Probleme gelöst werden. Die Performance des Sortiervorgangs bleibt kaum zu verbessern und ist mit steigender Grafikkartenleistung mit Bitonic Merge Sort sicher bald auf ausreichend großen Texturatlanten in Echtzeit durchführbar.

Die Anzahl der Texturzugriffe durch die Indexierung ist jedoch sehr hoch. Der Zugriff auf den Texturatlas muss also überdacht werden. Dieses Problem ist sicher lösbar, zum Beispiel indem die Indexierung von der GPU auf die CPU mit freierem Texturzugriff ausgelagert wird.

Die Erstellung des Texturatlas ist sicher die größte Herausforderung, da der Texturatlas festen Vorgaben entsprechen muss um für das Verfahren geeignet zu sein. Das Eintragen der Szene in den Texturatlas muss trotz unterschiedlicher Koordinatensysteme und Umrechnungen Pixelgenau und universell gelöst werden. Auf spezielle Aufgaben angewendet kann dies unter kontrollierten Bedingungen allerdings auch gelöst werden.

25

Fazit

Anhand meiner Implementierung des texturatlasbasierten Depth Peelings in OpenGL 2.0 mit GLSL habe ich die Eigenschaften des Verfahrens im Detail untersucht.

Mit dem ebenfalls auf der GPU implementierten Standardverfahren konnte ich Vergleiche durchgeführt und die Unterschiede untersuchen.

Festgestellt habe ich, dass das texturatlasbasierte Verfahren für eine einzelne Ebene der Szene einen deutlich höheren Rechenaufwand hat als das Standardverfahren. Er ist jedoch für jede Ebene identisch und für weitere gleichzeitig benötigte Ebene minimal. Der texturatlasbasierte Ansatz kann daher bei komplexen Szenen Vorteile bieten, wenn viele Ebenen gleichzeitig dargestellt werden müssen. Es sollten dabei jedoch kontrollierte Bedingungen herrschen, damit das Verfahren einwandfrei funktioniert.

Transparenzdarstellung ist eine wichtige Anwendung des Depth Peelings, bei der mehrere Ebenen gleichzeitig dargestellt werden müssen. Hier kann das texturatlasbasierte Verfahren Vorteile zeigen. Bereits Everitt [Eve01] hat 2001 allerdings Transparenzen mit Depth Peeling verglichen und für eine seiner Testszene angemerkt: „good enough after three layers“. Wie viele Transparenzebenen in der Praxis wirklich für den Betrachter erkennbar sind, ist daher eingeschränkt. Andere Anwendungen als Transparenzen können weit mehr Ebenen der Szene zur Weiterverarbeitung benötigen und damit ein geeigneter Einsatzbereich dieses Verfahrens sein.

Auch wenn der Grafikspeicher mit jeder Grafikkartengeneration weiter steigt und die vielen vorgehaltene Ebene des Standardverfahrens je nach Anwendung kein großer Nachteil sein müssen, ist der Speicherbedarf des texturatlasbasierten Depth Peelings doch dessen größter Vorteil. Er ist für beliebig viele Ebenen konstant und schon bei wenigen Ebenen geringer als im Standardverfahren.

26

Literaturverzeichnis [Cod10] codeworx. Lektion 6: Texture Mapping. [Online] http://www.codeworx.org/opengl_tut6.php.

[Bor06] David Borland, John P. Clarke, and Russell M. Taylor II. 2006. Volumetric depth peeling for virtual arthroscopy. North Carolina : University of North Carolina, 2006.

[Dgl09] DGL Wiki. [Online] http://wiki.delphigl.com/.

[Eve01] Everitt, Cass. 2001. Interactive Order-Independent Transparency. s.l. : NVIDIA Corporation, 2001.

[Tiled] Fabio F. Bernardon, Christian A. Pagot, Joao L. D. Comba, Cláudio T. Silva. GPU-based Tiled Ray Casting using Depth Peeling. s.l. : Universidade Federal do Rio Grande do Sul, University of Utah.

[Gd101] 1999-2010. gamedev.net. OpenGL FrameBuffer Object 101. [Online] Rob Jones, 1999-2010. http://www.gamedev.net/reference/programming/features/fbo1/.

[Gd201] 1999-2010. gamedev.net. OpenGL FrameBuffer Object 201. [Online] Rob Jones, 1999-2010. http://www.gamedev.net/reference/programming/features/fbo2/.

[Lig09] Lighthouse 3D. GLSL Tutorial. [Online] http://www.lighthouse3d.com/opengl/glsl/.

[Dua05] Louis Bavoil, Kevin Myers. 2005. Order Independent Transparency with Dual Depth Peeling. [book auth.] Matt Pharr. GPU Gems 2. Amsterdam : Addison-Wesley Longman, Amsterdam, 2005.

[Shm08] Louis Bavoil, Steven P. Callahan, and Claudio T. Silva. 2006. Robust Soft Shadow Mapping with Backprojection and Depth Peeling. Utha : Scientific Computing and Imaging Institute, University of Utah, 2006.

[Srt05] Peter Kipfer, Rüdiger Westermann. 2005. Improved GPU Sorting. [Buchverf.] Matt Pharr. GPU Gems 2. Amsterdam : Addison-Wesley Longman, 2005.

[Pye09] 2007-2009. Pyeloskopie - Medizinlexikon. imedo.de. [Online] Elsevier GmbH, München, 2007-2009. http://www.imedo.de/medizinlexikon/pyeloskopie.

[Sed02] Sedgewick, Robert. 2002. Algorithmen. s.l. : Pearson Studium, 2002.

[Sor10] Sortiernetze. Odd-even Mergesort. [Online] Prof. Dr. Hans Werner Lang, FH Flensburg. http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/networks/oem.htm.

[Flw05] Wei Li, Zhe Fan, Xiaoming Wei,Arie Kaufman. 2005. GPU-Based Flow Simulation with Complex Boundaries. [book auth.] Matt Pharr. GPU Gems 2. Amsterdam : Addison-Wesley Longman, 2005, 47.

�