Globale Beleuchtung Im Bildraum Unter Besonderer Berücksichtigung ...

Fachbereich 4: Informatik
Globale Beleuchtung im Bildraum
unter besonderer Berücksichtigung
der Sichtbarkeitsbestimmung
Studienarbeit
im Studiengang Computervisualistik
vorgelegt von
Sinje Thiedemann
Betreuer:
Prof. Dr. Stefan Müller, Dipl.-Inform. Niklas Henrich
Institut für Computervisualistik, AG Computergraphik
Koblenz, im September 2009

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 der Arbeit in die Bibliothek bin ich einverstanden.
Der Veröﬀentlichung dieser Arbeit im Internet stimme ich zu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(Ort, Datum)
(Unterschrift)

Inhaltsverzeichnis
1
Einführung
1
2
Beleuchtung
4
2.1
Lokale Beleuchtungsmodelle . . . . . . . . . . . . . . . . . . .
4
2.2
Globale Beleuchtungsmodelle . . . . . . . . . . . . . . . . . .
4
2.3
Ambient Occlusion . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3.1
Deﬁnition . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3.2
Berechnung . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3.3
Bent Normal . . . . . . . . . . . . . . . . . . . . . . .
7
2.3.4
Monte-Carlo-Integration . . . . . . . . . . . . . . . . .
8
2.3.5
Existierende Verfahren . . . . . . . . . . . . . . . . . .
9
2.4
Obscurances . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3
Voxelisierung mit der GPU
14
3.1
Einführung
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.2
Oberﬂächenvoxelisierung . . . . . . . . . . . . . . . . . . . . .
14
3.2.1
Die Voraussetzungen . . . . . . . . . . . . . . . . . . .
14
3.2.2
Der Ablauf . . . . . . . . . . . . . . . . . . . . . . . .
16
3.3
Körpervoxelisierung . . . . . . . . . . . . . . . . . . . . . . . .
17
3.4
Erstellung von Slicemap-Mipmaps
. . . . . . . . . . . . . . .
19
4
Sichtbarkeit
22
4.1
Problemstellung . . . . . . . . . . . . . . . . . . . . . . . . . .
22
4.2
Sichtbarkeitstest im Objektraum (Referenzlösung)
. . . . . .
23
4.3
Sichtbarkeitstest im Bildraum (Screen-Space) . . . . . . . . .
23
4.4
Sichtbarkeitstest im Voxelraum (Voxel-Space) . . . . . . . . .
27
4.5
Bildraum vs. Voxelraum . . . . . . . . . . . . . . . . . . . . .
29
5
Implementierung
31
5.1
Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
5.2
G-Buﬀer erzeugen . . . . . . . . . . . . . . . . . . . . . . . . .
32
5.3
Ambient Occlusion und indirektes Licht . . . . . . . . . . . .
34
5.3.1
Sampling
. . . . . . . . . . . . . . . . . . . . . . . . .
34
5.3.2
Gewichtung der Samples . . . . . . . . . . . . . . . . .
38
5.3.3
Screen-Space AO und Screen-Space GI . . . . . . . . .
39
5.3.4
Voxel-Space AO und Hybrid-GI . . . . . . . . . . . . .
41
5.4
Blur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
5.5
Finale Kombination
. . . . . . . . . . . . . . . . . . . . . . .
44
6
Ergebnisse
45
6.1
Qualität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
6.2
Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
6.3
Erweiterungsmöglichkeiten . . . . . . . . . . . . . . . . . . . .
55
i

6.4
Ausblick: Strahlschnitttest im Voxelraum
. . . . . . . . . . .
55
6.5
Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
Literaturverzeichnis
58
ii

1
Einführung
“I am sure that at some point we will be ray tracing complex
scenes on our palm pilots. Until then we’ll continue to create
eﬃcient cheats and tricks to get the visual advantages of global
illumination without the time and expense.”
Hayden Landis, Industrial Light & Magic [Lan02, S. 97 ﬀ.]
Die fotorealistische Bildsynthese beschäftigt sich mit der Frage, wie die Aus-
breitung und Interaktion von Licht in einer virtuellen Szene so simuliert
werden kann, dass ein menschlicher Betrachter das entstandene Bild nicht
von einem Foto unterscheiden kann. Der Entstehungsprozess wird Rendering
genannt. Rendering ist die Abbildung der dreidimensionalen Objekte einer
virtuellen Szene mit all ihren deﬁnierten Eigenschaften auf ein zweidimen-
sionales Bild. Hierbei sind folgende Faktoren zu berücksichtigen: Licht, Ma-
terialien, Geometrie, Kamera bzw. Betrachter.
Insbesondere die Simulation des Lichts ist dafür ausschlaggebend, ob ei-
ne Szene realistisch oder unrealistisch wirkt, selbst bei sehr detaillierter Mo-
dellierung der in ihr beﬁndlichen Objekte. Es gibt zahlreiche Modelle und
Verfahren, um die Beleuchtung eines Punktes in der Szene zu berechnen. Je
nachdem, welche Informationen für diese Beleuchtung genutzt werden, han-
delt es sich um eine lokale oder globale Beleuchtung. Global ist sie dann,
wenn außer den lokal für den aktuell betrachteten Punkt vorhandenen In-
formationen wie Position und Oberﬂächennormale auch Informationen über
alle anderen Punkte mit in die Berechnung eingehen. Da andere Oberﬂächen-
punkte je nach ihrer Materialeigenschaft jedoch auch wieder Licht reﬂektie-
ren und damit andere Punkte beleuchten können, handelt es sich bei der
Berücksichtigung solcher Interreﬂexionen um ein rekursives Problem: Um
einen Punkt korrekt beleuchten zu können, müssen andere Punkte bereits
beleuchtet sein [AMHH08, S. 379].
Entsprechend hoch ist der nötige Rechenaufwand, um eine globale Be-
leuchtungssimulation durchzuführen, vor allem bei physikalisch korrekten
oder basierten Ansätzen. Für statische Szenen mit nicht-verformbaren Ob-
jekten, die sich ebenso wie alle Lichtquellen nicht bewegen, lassen sich die
Beleuchtungsinformationen vorberechnen, in geeigneten Datenstrukturen ab-
legen und später für die Darstellung wieder abrufen.
Dies ist jedoch für dynamische Szenen nur unter bestimmten Voraus-
setzungen und nur teilweise möglich. In voll dynamischen Umgebungen mit
sich bewegenden und animierten Objekten oder sich bewegenden Lichtquel-
len muss die Lichtsimulation fortlaufend neu berechnet werden.
Auch auf heutiger Hardware sind die von Hayden Landis im Eingangszi-
tat genannten „Tricks“ und vereinfachende Annahmen erforderlich, um dy-
namische Szenen interaktiv oder sogar in Echtzeit global zu beleuchten.
Akenine-Möller et al. deﬁnieren Rendering als interaktiv ab einer Bilder-
1

zeugungsrate von 6 Frames pro Sekunde (fps), Echtzeit als 15 fps aufwärts
[AMHH08, S. 1]. Nicht nur Anwendungen wie Spiele, in denen Echtzeit zwin-
gend erforderlich ist, proﬁtieren von Verfahren, die die Berechnung einer glo-
balen Beleuchtung beschleunigen. Neben den komplett computergenerierten
Animationsﬁlmen kommen in immer mehr Kinoﬁlmen Spezialeﬀekte zum
Einsatz. Die Produktionsﬁrmen sparen durch eine Beschleunigung des Ren-
derings – selbst mit ihren Renderfarmen – Zeit und damit Geld.
Die Vereinfachungen und Näherungen sind immer ein Kompromiss zwi-
schen der dadurch erzielten höheren Performance und der Bildqualität. Je
nach Anwendung sind darüber hinaus wichtige Kriterien, ob ein ggf. zeitin-
tensiver Vorverarbeitungsschritt notwendig ist oder ob komplizierte Daten-
strukturen während des Renderings zu verwalten sind. Daraus ergibt sich
auch, wie ﬂexibel ein Verfahren ist und ob die Szenengeometrie zum Beispiel
in spezieller Form vorliegen muss. Je nachdem, wie stark die Vereinfachung
ist, sind Artefakte möglich, die das menschliche Auge stören oder gar nicht
wahrgenommen werden. Auch hier ist es anwendungsabhängig, ob kleinere
Fehler akzeptabel sind.
Verfahren im Objektraum arbeiten direkt auf der Szenengeometrie und
sind abhängig von ihrer Komplexität. Eine Möglichkeit zur Beschleunigung
ist daher, die tatsächliche Geometrie durch einfachere Geometrie anzunä-
hern.
Um die Lichtberechnungen von der Szenenkomplexität zu entkoppeln,
entstanden Algorithmen im Bildraum, die als grobe Szenenrepräsentation
den Tiefenpuﬀer nutzen, d. h. die Tiefenwerte aller von der Kamera aus sicht-
baren Objekte. Zudem beschränkt man sich in der Regel auf einen Radius,
innerhalb dessen andere Szenenelemente berücksichtigt und außerhalb lie-
Abbildung 1: Links: Lokale Beleuchtung mit konstantem ambienten Licht und
Shadow Mapping. Rechts: Angenäherte globale Beleuchtung im
Voxel- und Bildraum.
2

gende ignoriert werden.
Für das Rendering mit globaler Beleuchtung sind Sichtbarkeitsanfragen
essentiell: Können sich zwei Elemente der Szene sehen? Wird ein Punkt
aus einer bestimmten Richtung verdeckt? Im Bildraum ist diese Informa-
tion zwar nur begrenzt verfügbar, da er von der Kamera aus nicht sichtbare
Teile nicht erfasst. Trotzdem können ansprechende Resultate bei gleichzei-
tiger Echtzeitfähigkeit erzielt werden. Eine viel benutzte Charakterisierung
der Ergebnisse solch vereinfachender „Fake“-Verfahren ist „plausibel für die
menschliche Wahrnehmung“. Sehr populär ist ein Verfahren namens Ambient
Occlusion, das in dieser Studienarbeit eine wesentliche Rolle spielt. Mithilfe
von Ambient Occlusion lassen sich sehr weiche Schatten und eine globale
Beleuchtung annäherungsweise berechnen.
Diese Studienarbeit befasst sich mit zwei Arten der Szenenrepräsentati-
on (Bildraum und Voxelraum) und wie diese für eine Sichtbarkeitsbestim-
mung genutzt werden können. Dafür wurden bekannte Ambient-Occlusion-
Verfahren untersucht und zwei ausgewählte Techniken implementiert. Die-
se wurden anschließend auf „Fake“-GI erweitert, das heißt, indirektes Licht
wurde berücksichtigt (erste Indirektion). Die Umsetzung geschah im Kontext
eines Deferred Shadings, das sich für bildraumbasierte Eﬀekte anbietet. Für
die Implementierung wurden OpenGL und die OpenGL Shading Langua-
ge (GLSL) genutzt, sowie Qt für die Benutzeroberﬂäche der entstandenen
Anwendung.
3

2
Beleuchtung
2.1
Lokale Beleuchtungsmodelle
Die direkte Beleuchtung bildet die Grundlage für jede weiterführende Be-
leuchtung. „Direkt“ heißt, dass nur die deﬁnierten Lichtquellen herangezo-
gen werden, um die Szene zu beleuchten. Unter die direkte Beleuchtung fällt
auch die Berechnung von Schatten, die durch Verdeckung der Lichtquellen
entstehen.
Für Punktlichtquellen gilt: Entweder ist die Lichtquelle von einem Punkt
aus gesehen verdeckt (Punkt liegt im Schatten) oder sichtbar (kein Schatten).
Dieses binäre Ergebnis produziert harte Schattenkanten. In der Realität gibt
es keine Punktlichtquellen außer der Sonne, die aber auch nur näherungsweise
als eine solche betrachtet werden kann aufgrund ihrer großen Entfernung. Um
realistische Schatten zu erzeugen, werden ﬂächige Lichtquellen eingesetzt,
durch deren Abtastung Halbschatten und weiche Schattenverläufe möglich
sind.
Ist der Punkt unverdeckt oder wird die Sichtbarkeit der Lichtquelle nicht
beachtet, wird ein lokales Beleuchtungsmodell für die Beleuchtung des Punk-
tes herangezogen. Dieses beschreibt, wie das Material bei Interaktion mit
Licht reagiert: Wie stark wird das Licht beim Auftreﬀen auf eine Oberﬂäche
absorbiert, reﬂektiert oder transmittiert (und dabei vermutlich gebrochen)?
Lokal bedeutet, dass jeder Punkt „für sich“ beleuchtet wird, unabhängig von
den anderen Punkten in der Szene. Nur die Informationen über die Licht-
quellen (Typ, Position, Lichtfarbe) und über die eigene Position, Oberﬂä-
chennormale und Materialeigenschaften gehen in die Auswertung des lokalen
Beleuchtungsmodells mit ein.
Materialien lassen sich mit Hilfe der Bidirectional Reﬂectance Distribu-
tion Function (BRDF) modellieren. Diese gibt für jeden Einfalls- und Aus-
fallswinkel an, wie das Verhältnis zwischen einfallender Beleuchtungsstärke
und reﬂektierter Leuchtdichte ist, kann aber noch von weiteren Größen wie
dem betrachteten Ort auf der Oberﬂäche abhängig sein. Sie lässt sich durch
geschlossene mathematische Formeln oder durch Tabellen ausdrücken, in de-
nen die jeweiligen Werte durch meist tausende Messungen erfasst wurden.
Für ideal diﬀuse Materialien (Lambert-Strahler ) ist die BRDF konstant.
Sie hängt nur von dem Reﬂexionsgrad des Materials ab. Für jede Einfalls-
richtung wird die gleiche Leuchtdichte in alle Richtungen reﬂektiert, sodass
das Material aus allen Richtungen betrachtet gleich hell erscheint. Ein wei-
teres klassisches Beleuchtungsmodell ist das Phong-Beleuchtungsmodell, das
zusätzlich zur diﬀusen Reﬂexion Spiegelungen bzw. Glanz mit einbezieht.
2.2
Globale Beleuchtungsmodelle
In der Realität können Bereiche, die durch die direkte Beleuchtung dunkel
bleiben, von ihrer (nahen) Umgebung beleuchtet werden. Licht, das auf eine
4

diﬀuse farbige Fläche – zum Beispiel eine rote Wand – fällt, wird in alle
Richtungen reﬂektiert und beleuchtet somit indirekt andere Objekte in der
Szene. Objekte in der Nähe der Wand erscheinen demnach leicht rötlich.
Lokale Beleuchtungsmodelle berücksichtigen solche indirekten Phänomene
nicht.
Die einfachste Möglichkeit, ein nicht näher deﬁniertes indirektes Licht
(gestreutes Umgebungslicht) zu simulieren, ist das Aufaddieren einer für die
gesamte Szene konstanten Farbe. Dieser ambiente Term ist die gröbste Art
der Annäherung einer globalen Beleuchtung (engl. global illumination = GI).
Das Ergebnis ist jedoch weit von Wirklichkeitstreue entfernt.
Zwei klassische Ansätze zur globalen Beleuchtungssimulation sind Radi-
osity-Systeme und Path Tracing. Bei einer Radiosity-Simulation darf die
Szene nur aus diﬀusem Material bestehen. Sie wird in viele kleine Flächen-
elemente (Patches) geteilt, zwischen denen Strahlungsaustausch stattﬁndet.
Path Tracing geht über das klassische Ray Tracing hinaus, indem viele Strah-
len durch jedes Pixel geschossen werden, allerdings pro Strahl nur ein einziger
– zwar zufällig ausgewählter, gleichwohl aber vom jeweiligen Auftreﬀpunkt
abhängiger – „Weg“ durch die Szene verfolgt wird. Um ein rauschfreies Er-
gebnis zu erhalten, sind sehr viele Strahlen pro Pixel nötig, entsprechend
hoch ist die nötige Rechenleistung.
2.3
Ambient Occlusion
2.3.1
Deﬁnition
Ambient Occlusion (AO, deutsch: Umgebungsverdeckung) ist ein viel genutz-
tes Verfahren zur Annäherung globaler Beleuchtung. Es deckt zwar nur eine
Untermenge der globalen Eﬀekte ab, kann aber dennoch den Realismusgrad
eines Bildes beträchtlich steigern.
Das Verfahren modelliert, wie stark ein Punkt von der ihn umgebenden
Geometrie verdeckt wird. Diesem Verdeckungsgrad entsprechend erreicht ihn
viel oder wenig Licht eines imaginären diﬀusen Umgebungslichts, das die Sze-
ne aus allen Richtungen gleichmäßig beleuchtet (wie ein komplett bewölkter
Himmel). Für die verdeckenden Objekte hat sich der Begriﬀ Occluder einge-
bürgert.
Es ist ein Verfahren, das rein geometrisch basiert arbeitet und somit voll-
ständig von der Beleuchtung durch die Lichtquellen einer Szene entkoppelt
ist. Beide Berechnungen werden unabhängig voneinander ausgeführt und
am Ende kombiniert, zum Beispiel durch eine einfache Multiplikation des
Verdeckungsgrades mit der Farbe des lokal beleuchteten Punktes. Alterna-
tiv können die für jeden Oberﬂächenpunkt der Szene bestimmten Ambient-
Occlusion-Werte als variierender ambienter Term angesehen werden.
Für Schatten, die durch Verdeckung der Lichtquellen entstehen, muss ein
ergänzendes Schattenverfahren wie z. B. Shadow Mapping eingesetzt werden.
5

Abbildung 2: AO am Beispiel des Stanford Bunnys
Das Ergebnis von Ambient Occlusion sind zum einen extrem weiche
Schatten (siehe Abbildung 2 (rechts), der Boden unter dem Bunny), die Kon-
taktstellen zwischen nahen Objekten und somit die räumliche Anordnung
der Objekte verdeutlichen können. Zum anderen wird für einzelne Objekte
durch Selbstverdeckung erkennbar, ob Stellen gewölbt oder gekrümmt sind.
Die Heuristik „Vertiefungen sind dunkler als Erhebungen“ („dark means deep“
[LB99]) wird von Menschen zwar nicht alleine zur Erkennung von Oberﬂä-
chenbeschaﬀenheiten herangezogen, spielt jedoch eine nicht außer Acht zu
lassende Rolle.
2.3.2
Berechnung
Der Verdeckungsgrad wird für jeden Punkt P wie folgt bestimmt [AMHH08,
S. 375]:
1
AO(P, n) =
V (P, ω)
·
(ω ◦ n)
dω
(1)
π
ω∈Ω
Sichtbarkeit
= Cosinus des Win-
kels zwischen Nor-
male n und Rich-
tung ω
[BS09, S. 426] weisen darauf hin, dass die Berechnung auch ohne Cosinus-
Gewichtung möglich ist. In dem Fall lautet die Formel
1
AO(P, n) =
V (P, ω) dω.
(2)
2π Ω
Im Allgemeinen kommt jedoch die Variante mit Cosinusgewichtung zum Ein-
satz. Welche optischen Unterschiede sich ergeben, kann Abbildung 23 auf S.
35 in Abschnitt 5.3.1 Sampling entnommen werden.
6

Abbildung 3: Ambient Occlusion Prinzip in 2D: An der Normalen n ausgerich-
tete Hemisphäre Ω um einen Punkt P, innerhalb welcher der Ver-
deckungsgrad an Punkt P bestimmt wird. Rote Richtungen sind
verdeckt, grüne unverdeckt.
AO(P, n) nimmt Werte aus [0, 1] an, die prozentuale Verdeckung der He-
misphäre des Punktes P. Ein Wert von 1 bedeutet, dass der Punkt komplett
unverdeckt („oﬀen“) ist, bei einem Wert von 0 ist der Punkt komplett ver-
deckt. Aufgrund dieser Art der Berechnung (größerer Ergebniswert bedeutet
weniger Verdeckung), ist ein häuﬁger Einwand gegen die Bezeichnung Am-
bient Occlusion, dass eigentlich der Grad der „Oﬀenheit“ bestimmt wird –
allerdings hat sich der Name Ambient Occlusion eingebürgert.
Oft wird statt des gesamten vorderen Halbraums die an der Normalen
eines Punktes ausgerichtete Hemisphäre betrachtet, also eine Halbkugel mit
festem, endlichen Radius. Ohne Beschränkung auf einen Radius wären ge-
schlossene Räume schwarz, da hier jeder Punkt in allen Richtungen verdeckt
wäre. Ein anderer Ansatz, um dieses unerwünschte Ergebnis zu vermeiden,
ist die Abschwächung des Verdeckungsgrades (siehe Abschnitt 2.4 Obscuran-
ces, S. 12). Der geeignete Radius muss manuell pro Szene bestimmt werden.
2.3.3
Bent Normal
Während der Berechnung kann auch die sogenannte Bent Normal (deutsch:
geneigte Normale) durch Mittelung aller unverdeckten Richtungen bestimmt
werden. Sie zeigt die Richtung, in der sich im Durchschnitt die wenigsten oder
keine Occluder beﬁnden. Im Allgemeinen zeigt die Bent Normal potentiell
in eine andere Richtung als die eigentliche – zuvor deﬁnierte – Oberﬂächen-
normale. Sie kann für eine spätere Beleuchtung genutzt werden, häuﬁg in
Kombination mit einer diﬀusen Environment Map. Abbildung 4 zeigt den
Unterschied zwischen den Normalen.
Es gibt allerdings Konstellationen, in denen die Ausrichtung der Bent
Normal nicht deﬁniert ist (mathematisch zwar schon, der Bedeutung nach
aber nicht). Somit kann es passieren, dass sie in eine eigentlich verdeckte
7

Richtung zeigt. Wenn zum Beispiel über dem Punkt oben mittig in der He-
misphäre ein Occluder schwebt, und der Punkt ringsherum in den ﬂachen
Richtungen unverdeckt ist, heben sich diese im Durchschnitt auf. Die Bent
Normal wird wieder der ursprünglichen Oberﬂächennormalen ähneln, obwohl
genau diese Richtung verdeckt ist.
Abbildung 4: Links: die deﬁnierten Normalen; rechts: Bent Normals, berechnet
mit SSAO (Ray Marching)
2.3.4
Monte-Carlo-Integration
Das Ambient-Occlusion-Integral kann nicht analytisch gelöst werden. Daher
wird oftmals Monte-Carlo-Integration zur Annäherung der Lösung einge-
setzt, also die diskrete Abtastung der Hemisphäre mittels zufällig generierter
Richtungen (= Stichproben oder Samples). Die allgemeine Formulierung für
das Abschätzen eines Integrals mittels Monte-Carlo-Integration zeigt Glei-
chung (3). Der rechte Teil der Gleichung wird auch als Monte-Carlo-Schätzer
bezeichnet.
b
N
1
f (Xi)
f (x)dx ≈
(3)
N
p(Xi)
a
i=1
mit
N
Anzahl der Samples
Xi
i-tes Sample
p(Xi) Dichtefunktion
Die Ambient-Occlusion-Formeln (1) und (2) integrieren jeweils über eine
Hemisphäre Ω mit Raumwinkel 2π. Für die Monte-Carlo-Integration müs-
sen als Samples zufällige Richtungen innerhalb der Hemisphäre ausgewählt
werden, die jeweils einen gewissen Raumwinkel repräsentieren.
8

Die Samples für eine Einheits-Hemisphäre mit Radius = 1 sind in Ku-
gelkoordinaten ausgedrückt zweidimensional, nämlich ein Winkelpaar (φ, θ)
(genannt Azimut- und Polarwinkel). Sie beschreiben im dreidimensionalen
Raum innerhalb einer Kugel oder einer Hemisphäre eine Richtung und kön-
nen in kartesische Koordinaten (x, y, z) umgerechnet werden.
Es bietet sich an, die Dichtefunktion ähnlich dem Integranden des Inte-
grals zu wählen (Importance Sampling ). Zur Generierung der Samples für die
Abschätzung des Integrals (2) ist eine konstante Dichtefunktion p(φ, θ) = 1
2π
sinnvoll, die in einem uniformen Sampling in Bezug auf den Raumwinkel der
Hemisphäre resultiert. Jede Richtung wird also mit gleicher Wahrscheinlich-
keit erzeugt. Für die Abschätzung des Integrals (1) ist dagegen ein cosinusge-
wichtetes Sampling mit der Dichtefunktion p(φ, θ) = cosθ (mehr Samples in
π
Richtung der Normalen) zweckmäßig. Der Cosinus-Term des Integrals nimmt
dann hohe Werte an, wenn der Winkel zwischen Normale und Richtung klein
ist. Bei sehr großem Winkel würde ein Sample nicht viel zur Summe beitra-
gen.
In beiden Fällen werden die Ergebnisse der Sichtbarkeitstests aufaddiert
und durch die Anzahl der Samples geteilt:
N
1
V (Xi)
N i=1
2.3.5
Existierende Verfahren
Es gibt zahlreiche Algorithmen zur Berechnung des Verdeckungsgrades. Sie
werden kategorisiert in Inside-out -Verfahren und Outside-in-Verfahren. Die
Bezeichnung weist darauf hin, aus welchem Blickwinkel die Berechnung des
Verdeckungsgrads geschieht. Inside-out heißt, dass der Punkt von sich aus
nach außen in die Umgebung „schaut“. Dieser Betrachtungsweise entspricht
auch die sehr rechenaufwändige Referenzlösung mittels Ray Tracing. Jene
wird daher nur im Oﬄine-Rendering eingesetzt. Outside-in bedeutet, dass
der betreﬀende Punkt von außen betrachtet wird. Das Umgebungslicht (re-
präsentiert durch mehrere imaginäre Lichtquellen, von denen aus die Szene
gerendert wird) „testet“, wieviel es von dem Punkt sieht.
Seit Hayden Landis das Konzept von Ambient Occlusion im Jahr 2002
veröﬀentlichte, welches damals in einem Oﬄine-Renderer zum Einsatz kam,
wurde die Technik rasch populär. Die Tendenz ging und geht immer mehr
hin zu Verfahren, die AO in Richtung Interaktivität und sogar Echtzeit in
voll dynamischen Szenen bewegen.
Martin Knecht unterscheidet in seinem „State of the Art Report on Am-
bient Occlusion“ aus dem Jahr 2007 [Kne07] zwischen objektbasierten, ver-
texbasierten und bildbasierten Methoden. Erstere arbeiten auf ganzen Ob-
jekten, zweitere betrachten einzelne Vertices und letztgenannte nutzen den
blickwinkelabhängigen Bildraum. Im Jahr 2009 stellten Reinbothe et al. das
9

voxelbasierte „Hybrid Ambient Occlusion“ vor [RBA09]. Sie nutzen den vo-
xelisierten Objektraum und den Bildraum für ein intelligentes Hochskalieren
der nicht vollaufgelösten Ambient-Occlusion-Textur.
Vertexbasiert ist zum Beispiel ein von Michael Bunnell 2005 vorgestell-
tes Verfahren [Bun05], das die Geometrie in Form vieler Scheiben an-
nähert. Jede Scheibe ist an einem Vertex zentriert und gemäß der
Normalen dieses Vertex ausgerichtet. Das Verfahren ist auf eine aus-
reichend hohe Auﬂösung der Meshes angewiesen, da die Annäherung
durch Scheiben ansonsten zu grob ist.
Bildbasierte Verfahren nutzen den Tiefenpuﬀer bzw. eine Vielzahl an Tex-
turen, die zusammen oft als G-Buﬀer bezeichnet werden (von Geome-
trie-Buﬀer). Abbildung 5 zeigt Beispiele für mögliche Texturen bzw.
Texturkanäle.
Abbildung 5: Beispiele für G-Buﬀer-Texturen bzw. Kanäle; von links nach rechts:
Farbe/Material, Beleuchtungsstärke, Normalen, Tiefe, Kamerako-
ordinaten
Exkurs: G-Buﬀer und Deferred Shading
Deferred Shading bezeichnet das Prinzip, zunächst die Szene in Texturen
zu rendern und anschließend auf diesen Texturen zu arbeiten, um das
fertige Bild zu erzeugen.
Der G-Buﬀer wird beim Deferred Shading im ersten Pass erzeugt.
Alle nötigen Informationen (Tiefe, Kamerakoordinaten oder Weltkoordi-
naten; Normale; Farbe; Material) werden im Fragment Shader in dafür
zuvor angelegte Texturen (= Render Targets eines Framebuﬀers) ge-
schrieben.
Dabei fallen – je nach Bildauﬂösung – große Datenmengen an, wes-
halb eine möglichst geschickte Anordnung und Nutzung aller Kanäle in
den Texturen angestrebt wird. Bei einer späteren Weiterverarbeitung,
die den Zugriﬀ auf die Texturen benötigt, können Graﬁkkarten mit we-
nig Texturspeicher und Bandbreite ausgebremst werden.
Vor diesen eben beschriebenen ersten Render-Pass kann ein „Early-
Z“-Pass geschoben werden. Währenddessen wird alles außer dem Schrei-
ben der Tiefenwerte in den Tiefenpuﬀer deaktiviert. Beim anschließenden
10

Rendern der Szene werden über den Tiefentest frühzeitig nicht-sichtbare
Pixel aussortiert, sofern die Hardware „Early-Z“ unterstützt, d. h. das
Verwerfen eines Fragments früh in der Pipeline, vor dem Fragment Sha-
der. Es ist zu bedenken, dass die Geometrie doppelt gerendert werden
muss – auch wenn der „Nur-Tiefen“-Pass schnell ist, kostet dieser Zeit.
Deshalb ist diese Vorgehensweise nur dann sinnvoll, wenn der anschlie-
ßende Pass extrem komplizierte Berechnungen im Fragment Shader bein-
haltet.
Das erste Mal wurde Ambient Occlusion im Bildraum im Kontext des
Deferred Shadings in Cryteks CryEngine 2 bzw. ihrem Computerspiel Crysis
unter dem Namen Screen Space Ambient Occlusion (SSAO) vorgestellt
[Mit07], Details in: [Kaj09]. Die Idee ist, nur den Tiefenpuﬀer als Grundlage
für eine Per-Pixel-Verdeckungsberechnung im Fragment Shader zu nutzen.
Der Tiefenpuﬀer stellt eine grobe Repräsentation der Szenengeometrie dar.
Das Verfahren spannt um jeden Punkt eine Kugel mit gewissem Radius auf,
in der Samples (Punkte) generiert werden. Für jedes Sample wird getestet, ob
es von dem betrachteten Punkt aus sichtbar oder verdeckt ist. Die Ergebnisse
werden akkumuliert, wobei die Hälfte der Samples als ungültig angenommen
wird, da sich diese im hinteren Halbraum des Punktes beﬁnden. Wie die
Sichtbarkeit im Bildraum bestimmt werden kann, ist in Abschnitt 4.3 (S. 23
ﬀ.) beschrieben. Ein allgemeines Problem besteht dabei darin, dass von der
Kamera aus nicht-sichtbare Objekte nicht erfasst sind.
Seit dieser „Geburtsstunde“ erfreuen sich AO-Verfahren im Bildraum
großer Beliebtheit. Solche sind äußerst ﬂexibel und können auf alles ange-
wendet werden, was in einen Tiefenpuﬀer rasterisiert werden kann. Es gibt
weder Einschränkungen für die Geometrie noch die Notwendigkeit spezielle
Datenstrukturen zu nutzen oder langwierige Vorverarbeitungsschritte durch-
zuführen.
Screen-Space Directional Occlusion wurde 2009 von Ritschel et al.
[RGS09] vorgestellt. Es bietet die interessante Neuerung, die Entkopplung
von direkter Beleuchtung und ambienter Verdeckung aufzuheben und statt-
dessen beides zeitgleich durchzuführen. Es entstehen dadurch potentiell ge-
richtete und farbige Verschattungen, die im Worst Case genauso aussehen
wie „normales“ Ambient Occlusion.
Im Rahmen von NVIDIA’s Image-Space Horizon-Based Ambient
Occlusion [BSD08] (Details in: [BS09]) stellen die Autoren das Ray Mar-
ching als Referenzlösung für Ambient Occlusion im Bildraum vor. Die Werte
des Tiefenpuﬀers der Szene repräsentieren ein Höhenfeld (height ﬁeld ). Ray
Marching ist ein Brute-Force Algorithmus, der jeden für die Annäherung des
Ambient-Occlusion-Integrals erzeugten Strahl schrittweise daraufhin testet,
ob und an welcher Stelle er das Höhenfeld schneidet. Der erste Sample-Punkt,
der unterhalb des Höhenfeldes liegt, wird als Schnittpunkt angenommen.
Ray Marching wird ebenfalls in dem bereits erwähnten Hybrid Am-
11

bient Occlusion eingesetzt. Anstelle des Tiefenpuﬀers als grobe Szenenre-
präsentation nutzen Reinbothe et al. eine dynamische Voxelisierung der
Szene, die ebenfalls in nur einer 2D-Textur speicherbar ist. Auch hier wird
jeder Strahl auf den ersten Schnittpunkt mit der Szene getestet. Dies ist der
erste Sample-Punkt, der innerhalb eines vollen Voxels liegt. Die Voxelisie-
rung (genaueres dazu in Abschnitt 3 auf S. 14 ﬀ.) wird pro Frame in nur
einem einzigen anfänglichen Pass durchgeführt. Der Vorteil besteht darin,
dass nicht nur von der Kamera aus sichtbare Objekte, sondern die gesamte
Geometrie von der „Voxelisierungskamera“ erfasst wird und für die Ambient-
Occlusion-Berechnung genutzt werden kann.
2.4
Obscurances
Ambient Occlusion ist eine Vereinfachung von Obscurances (engl. to obscure
= verdecken), die zum ersten Mal 1998 von Zhukov et al. vorgestellt wurden
[ZIK98]. Sie deﬁnieren Obscurance als geometrische Eigenschaft, die angibt,
wie oﬀen ein gegebener Oberﬂächenpunkt ist.
Der einzige wesentliche Unterschied ist, dass bei Obscurances der Ab-
stand zum ersten Occluder berücksichtigt wird. Der binäre Visibilitätsterm
aus dem Ambient-Occlusion-Integral wird ersetzt durch eine Distanzabbil-
dungsfunktion, die von dem Abstand zum ersten Occluder in der unter-
suchten Richtung abhängig ist. Das heißt, es muss nicht mehr nur ermittelt
werden, ob eine Richtung verdeckt ist, sondern welches der erste Occluder
ist bzw. wo sich der erste Schnittpunkt in dieser Richtung beﬁndet. Das
Sichtbarkeitsergebnis wird pro Sample berechnet, indem die stetige Distanz-
abbildungsfunktion auf den Abstand angewendet wird.
1
Obsc(P, n) =
ρ(d(P, ω, dmax)) · (ω ◦ n) dω
(4)
π
ω∈Ω
Distanz-
abbildungs-
funktion
mit
d(P, ω, dmax) Abstand zum ersten Schnittpunkt in Richtung ω
maximaler Abstand von Punkt P, innerhalb dessen nach
dmax
Schnittpunkten gesucht wird
ρ() hat einen Wertebereich von [0,1] (siehe Abbildung 6), d() liegt in-
nerhalb [0, dmax]. Die Annahme ist, dass nahe Objekte einen Punkt stärker
verdecken als weit entfernte. Der Wert von ρ() ist dann 1, wenn der ers-
te gefundene Schnittpunkt einen Abstand ≥ dmax hat. Aus diesem Grunde
kann die Schnittpunktsuche direkt auf einen Radius von dmax beschränkt
werden. Im Falle keines Fundes innerhalb dieses Bereichs ist d() = dmax. Es
ist natürlich auch möglich, dmax = ∞ zu setzen, falls keine solche Einschrän-
kung des Suchradius gewünscht ist. Je nachdem, welche Abmessungen die
12

Szene hat, muss ein passender Wert für dmax manuell bestimmt werden, um
ansprechende Ergebnisse zu erzielen.
Abbildung 6: Beispiel-Plot einer Distanzabbildungsfunktion nach [ZIK98, S. 47]
Viele Verfahren nennen sich zwar Ambient Occlusion, da dies der popu-
lärere Begriﬀ ist. Sie nutzen für die Berechnung aber eigentlich die Formel
für Obscurances, sofern der für die Formel benötigte Abstand zum ersten
Schnittpunkt bekannt ist. Die Abbildung 25 auf S. 39 zeigt verschiedene
Funktionen und die Ergebnisse.
Durch eine Erweiterung des Obscurance-Algorithmus können die Farb-/
Materialinformationen an den Schnittpunkten zum Einsammeln von farbi-
gem indirektem Licht genutzt werden [Mén07, S. 47 ﬀ.] (Color Bleeding, siehe
Abbildung 7).
Abbildung 7: Links: Ambient Occlusion, rechts: Obscurances mit Color Bleeding.
Bilder entnommen aus [Mén07, S. 31]
13

3
Voxelisierung mit der GPU
3.1
Einführung
Der Begriﬀ Voxel ist an das Kunstwort Pixel (von Picture Element) ange-
lehnt und bezeichnet ein diskretes Volumenelement. Die zweidimensionalen
Pixel entstehen durch Diskretisierung eines kontinuierlichen Bildes, die drei-
dimensionalen Voxel durch die Diskretisierung eines Raumes und der darin
beﬁndlichen Objekte. Im Normalfall handelt es sich bei der Zellenstruktur,
in der die Voxel angeordnet sind, um ein reguläres Gitter. Sie können belie-
bige Daten enthalten. Ebenso wie bei Bildern und Pixeln ist die Auﬂösung
des dreidimensionalen Gitters ein wichtiges Kriterium dafür, wie gut die dis-
kreten Voxel die kontinuierlichen Objekte annähern.
In der Medizin werden Volumendatensätze zum Beispiel mit Computer-
tomographen (CT) generiert.
Aber auch außerhalb der medizinischen Bildverarbeitung bieten Voxel
interessante Möglichkeiten. Anwendungsbeispiele aus der Computergraﬁk
sind Partikelsimulationen, Berechnungen von Schnittvolumen zweier Objek-
te, Kollisionserkennung oder auch Sichtbarkeitsanfragen für beispielsweise
Ambient Occlusion.
Da die virtuellen Objekte in der Computergraﬁk aber in aller Regel als
Polygonnetze vorliegen, müssen diese zunächst in eine geeignete Voxelreprä-
sentation überführt, d. h. voxelisiert, werden.
Das in diesem Abschnitt beschriebene Verfahren zur Voxelisierung von
Meshes auf der GPU wurde von Eisemann und Décoret vorgestellt. 2006 ver-
öﬀentlichten sie das Paper Fast Scene Voxelization and Applications [ED06],
zwei Jahre später Single-Pass GPU Solid Voxelization for Real-Time App-
lications [ED08]. Das zweite modiﬁzierte das erste Verfahren so, dass Voxel
nicht nur für die Meshoberﬂächen generiert werden, sondern auch für das
Innere eines geschlossenen Objektes.
Ziel dieser Voxelisierung ist es, die Information zu erfassen, ob sich an
einer bestimmten diskreten Stelle in der Szene etwas beﬁndet, also eine binäre
Angabe über die Existenz von Objekten in einer Szene.
Im Folgenden wird zunächst die Oberﬂächenvoxelisierung (boundary vo-
xelization) erläutert, danach die Körpervoxelisierung (solid voxelization), auf
die sich der Algorithmus durch minimale Änderungen übertragen lässt.
3.2
Oberﬂächenvoxelisierung
3.2.1
Die Voraussetzungen
Das Verfahren arbeitet mit bitweisen logischen Operationen und beruht dar-
auf, dass seit Shader Model 4.0 der Datentyp (Unsigned) Integer auf der
GPU verfügbar und der Zugriﬀ auf (Unsigned) Integer Texturen möglich ist.
14

Bei Verwendung von OpenGL ist mindestens Version 2.0 erforderlich, da erst
ab dieser Version das interne Texturformat für Unsigned Integer unterstützt
wird.
Eine Voxelisierung mit OpenGL und GLSL benötigt:
• ein Framebuﬀer-Objekt mit einer 2D-Textur als Render Target,
internalFormat = GL_RGBA32UI_EXT,
pixelFormat = GL_RGBA_INTEGER_EXT,
pixelType = GL_UNSIGNED_INT
• eine 1D-Textur (bitmask ), deren Texel den gleichen Datentyp wie jene
des Render Targets haben
(Aufbau der Textur: siehe Abbildung 9 auf S. 17)
• eine Graﬁkkarte, die Shader Model 4.0 unterstützt
• das zu voxelisierende 3D-Modell
Abbildung 8: Slicemap mit Auﬂösung 8 × 8: Die beispielhaft herausgegriﬀene
Schicht besteht aus 8 × 8 Bits, welche jeweils anzeigen, ob sie ein
volles (1, hier: dunkelgrau) oder leeres (0, hier: hellgrau) Voxel re-
präsentieren. Ein Texel der Slicemap hat 128 Bits, es gibt also 128
solcher Schichten.
Die gesamte voxelisierte Szene wird in der 2D-Unsigned-Integer-Textur
abgespeichert. Diese Voxel-Textur wird als Slicemap (slice = Schicht) be-
zeichnet und im Folgenden so genannt. Das Prinzip ist in Abbildung 8 sche-
matisch dargestellt. Alle k-ten Bits der Texel der Slicemap bilden zusammen
eine Schicht.
15

Ein Bit entspricht einem Voxel und enthält die Information, ob dieser
voll (1) oder leer (0) ist. Ein Texel mit dem internen Format GL_RGBA32UI_EXT
enthält 128 Bits (= 4 Kanäle · 32 Bits pro Kanal). Dies entspricht 128
Voxel-Schichten in z-Richtung.
3.2.2
Der Ablauf
Die Slicemap ist das Render Target des zum Zeitpunkt der Voxelisierung
genutzten Framebuﬀer-Objekts. Um ein reguläres Voxelgitter zu erhalten, in
dem die Voxel würfel- bzw. quaderförmig sind, ist eine Voxelisierungskame-
ra mit orthographischer Projektion zu setzen. Das Frustum dieser Kamera
umfasst die Szene bzw. den Teil der Szene, der voxelisiert werden soll. Die
Auﬂösung der Slicemap in x- und y-Richtung entspricht der Auﬂösung des
zum Zeitpunkt der Voxelisierung gesetzten Viewports. Die Auﬂösung in z-
Richtung ist die Anzahl der Bits pro Texel, also 128 bei dem beschriebenen in-
ternen Format. Eine Slicemap der Auﬂösung 512×512 enthält 512×512×128
Voxel. Die Auﬂösung in z-Richtung kann durch den Einsatz von Multiple
Render Targets erhöht werden. Mit zwei Slicemaps, also zwei Render Tar-
gets, beträgt die Auﬂösung in z-Richtung folglich 256.
Beim Rendern der gesamten Geometrie dürfen weder Vertices durch Cul-
ling noch Fragments am Ende der Pipeline verworfen werden. Das Culling
wird ausgeschaltet mit glDisable(GL_CULL_FACE) und es wird kein Render-
Buﬀer für den Tiefentest an das Framebuﬀer-Objekt gehängt. Somit gelangt
jeder innerhalb des Voxelisierungsfrustums gelegene und rasterisierte Vertex
zum Fragment Shader und jedes Fragment in den Framebuﬀer.
Listing 1: Voxelisierung: GLSL Vertex Shader
1
# v e r s i o n 120
2
v a r y i n g f l o a t m a p p e d Z ;
3
4
v o i d m a in ()
5
{
6
// f i x e d f u n c t i o n p i p e l i n e
7
g l _ P o s i t i o n
= f t r a n s f o r m () ;
8
// map z - c o o r d i n a t e to [0 ,1]
9
m a p p e d Z = ( g l _ P o s i t i o n . z + 1 . 0 ) / 2 . 0 ;
10
}
Jeder Punkt wird mit ftransform() ( = gl_ModelViewProjectionMatrix *
gl_Vertex) in homogene Koordinaten transformiert. Bei einer orthographi-
schen Projektion entspricht dies bereits dem kanonischen Volumen mit Ko-
ordinaten von -1 bis 1 in allen drei Raumrichtungen. Der z-Wert kann des-
halb direkt in Fensterkoordinaten umgerechnet und an den Fragment Shader
weitergereicht werden (siehe Listing 1).
Der lineare z-Wert mappedZ zwischen 0 und 1 wird im Fragment Shader
genutzt, um zu bestimmen, an welcher Stelle der 128 Bits des aktuellen
16

Abbildung 9: Bitmaske für die Oberﬂächenvoxelisierung
Texels in der Slicemap ein Bit auf 1 gesetzt wird (voller Voxel). Dafür wird
die Bitmaske (1D-Textur) benutzt.
Ein Lookup in der Bitmaske mit Texturkoordinate = mappedZ ermittelt
die dem z-Wert entsprechende Bitposition.
Listing 2: Voxelisierung: GLSL Fragment Shader
1
# v e r s i o n 120
2
// S h a d e r M o d e l 4.0 for I n t e g e r A r i t h m e t i c s
3
# e x t e n s i o n G L _ E X T _ g p u _ s h a d e r 4 : r e q u i r e
4
5
v a r y i n g f l o a t m a p p e d Z ;
6
v a r y i n g out u v e c 4 r e s u l t ;
7
8
u n i f o r m u s a m p l e r 1 D b i t m a s k ;
9
10
v o i d m a i n ()
11
{
12
r e s u l t = t e x t u r e 1 D ( bitmask , m a p p e d Z ) ;
13
}
Die Bits werden am Ende der Pipeline mit den bereits im Framebuﬀer
vorhandenen Werten durch eine logische Operation verodert. Die OpenGL-
Befehle zum Einschalten und Deﬁnieren der logischen Operation lauten
glEnable(GL_COLOR_LOGIC_OP) und glLogicOp(GL_OR).
Auf diese Weise werden alle Flächen voxelisiert. Problematisch sind aller-
dings Flächen, die parallel oder nahezu parallel zur Blickrichtung der Kamera
verlaufen, weil diese nicht oder kaum erfasst werden (Abbildung 10).
3.3
Körpervoxelisierung
Bei der Oberﬂächenvoxelisierung bleibt das Innenleben der Objekte leer. Vor
allem bei der Bestimmung, ob sich etwas an einer Stelle in der Szene beﬁndet,
ist es sinnvoll, auch die Voxel innerhalb eines Meshes zu füllen. Liegt bei
der Frage „Beﬁndet sich etwas an Position xy in der Szene?“ die Position
innerhalb eines Objektes, sollte die Antwort eigentlich „ ja“ lauten, weil das
Objekt die Position umschließt. Im Falle der Oberﬂächenvoxelisierung wäre
die Antwort jedoch „nein“, da alle Voxel im Objektinneren leer sind.
17

Abbildung 10: Zur Kamerablickrichtung parallele Flächen werden bei der Ober-
ﬂächenvoxelisierung kaum erfasst. Oben links: Das zu voxelisieren-
de Stanford Bunny. Oben rechts: Oberﬂächenvoxelisierung, Voxel
dargestellt als Quader. Die Farben symbolisieren, in welchem Ka-
nal (Rot, Grün, Blau oder Alpha) das Voxel abgespeichert wurde.
Unten links: Die im Bild oben links mit dem roten Pfeil markierte
Oberseite des Bunny-Kopfes weist in der Voxelrepräsentation eine
große Lücke auf. Unten rechts: Bei der Körpervoxelisierung tritt
dieses Problem nicht auf.
18

Mit einer kleinen Änderung des obigen Algorithmus wird das Objektin-
nere gefüllt. Es muss lediglich eine andere Bitmaske und eine andere logische
Operation verwendet werden, nämlich das Exklusiv-Oder glLogicOp(GL_XOR).
Die 128 Bits der Bitmasken-Texel folgen dem Muster:
[11111...1], [01111...1], [00111...1],... , [0000...01].
Abbildung 11: Veranschaulichung des Prinzips der Körpervoxelisierung. Die Gra-
ﬁk zeigt von links nach rechts die Füllschritte für ein Texel (eine
Voxelspalte) der Slicemap. Das Texel hat der Einfachheit halber
nur 8 Bits, ebenso der Framebuﬀer, welcher anfangs leer ist (alle
Bits sind 0). In der Graﬁk bedeutet weiß = 0, grau = 1. Bei dem
Ergebnis (ganz rechts) ist ein Detail zu erkennen: Die Voxel sind
um etwa eine halbe Voxellänge in z-Richtung relativ zur Geometrie
verschoben. Durch einen Oﬀset lassen sich Geometrie und Voxel
zur Deckung bringen. (Abbildung nach [ED08, S. 3], dort ﬁndet
sich auch eine mathematische Begründung für die Voxelisierung
via XOR-Operation.)
Das Mesh muss die Anforderung erfüllen, watertight zu sein (anschaulich:
„wasserdicht“ = keine Löcher). [ED08, S. 3] deﬁnieren ein Modell als water-
tight, wenn für jeden zusammenhängenden Bereich im Raum gilt, dass all
seine Punkte entweder innenliegend oder außenliegend sind. Gemäß des Jor-
dan Theorems liegt ein Punkt im Inneren, wenn für jeden beliebigen Strahl,
dessen Ursprung dieser Punkt ist, die Anzahl der Schnittpunkte mit dem Mo-
dell ungerade ist. Analog liegt er außen, wenn die Anzahl der Schnittpunkte
gerade ist. Abbildung 12 veranschaulicht diesen Sachverhalt.
Löcher im Mesh würden zu einer fehlerhaften Voxelisierung führen, die
in Abbildung 13 gezeigt wird.
3.4
Erstellung von Slicemap-Mipmaps
Aktuelle Graﬁkkarten unterstützen die automatische Erzeugung von Mip-
maps bei Integer-Texturen nicht. Da aber ohnehin die volle Kontrolle über
die Art der Reduzierung gegeben sein muss, wird ein eigener Fragment Sha-
der zum sukzessiven Zusammenführen der Voxelspalten eingesetzt. Räumlich
gesehen handelt es sich um eine Reduzierung in x- und y-Richtung, nicht je-
doch in z-Richtung, da die Texel ihr Format von 128 Bits behalten. Somit
entsteht eine Datenstruktur, die als Quadtree angesehen werden kann (statt
des üblichen Octrees für Voxelhierarchien). Um einen echten Octree zu er-
19

Abbildung 12: Links: Jordan Theorem: Beim Szenario „Kleine Box in großer Box“
wird der Zwischenraum der Boxen als „Innen“ angenommen: Aus-
gehend von dem Punkt im Inneren des Objekts (dunkelblau) ha-
ben alle Strahlen eine ungerade Anzahl an Schnittpunkten mit
den Objektgrenzen. Rechts: Geometrie, die nicht watertight ist,
da Innen und Außen nicht wohldeﬁniert ist (nach [ED08, S. 2])
Abbildung 13: Beispiel einer fehlerhaften Voxelisierung: Das Original-Mesh des
Stanford Bunnys ist nicht watertight. Die Tonﬁgur hatte unten
Öﬀnungen. Die Voxelisierungskamera blickt durch die Löcher auf
die eigentliche Rückseite, interpretiert diese aber als Vorderseite
eines dort beginnenden Objektes und füllt den Raum dahinter ent-
sprechend mit Voxeln. So entstehen die herausragenden „Säulen“
im rechten Bild.
20

halten, müssten die Voxel auch in z-Richtung zusammengeführt werden.
Die bei der Voxelisierung erzeugte Slicemap muss eine quadratische Auf-
lösung von 2n × 2n haben. Der Mipmap-Level 0 hat die Auﬂösung 2n × 2n,
der höchste Mipmap-Level n die Auﬂösung 1 × 1. Ausgehend von Mipmap-
Level 0 wird in jedem Schritt die Auﬂösung in jeder Dimension halbiert,
indem jeweils eine Gruppe von 2 × 2 Voxelspalten zu einer Voxelspalte zu-
sammengeführt wird. Dies geschieht durch einfache Veroderung der Bits der
vier Texel des nächstniedrigeren (im vorherigen Schritt erzeugten) Levels.
Abbildung 14: Voxel-Mipmaps des Dragons von Level 0 bis maximales Level 7.
Initiale Slicemap-Auﬂösung: 128 × 128 (27)
Im Rahmen dieser Studienarbeit wurde versucht, die Mipmaps für einen
verbesserten Sichtbarkeitstest im Voxelraum zu nutzen; genaueres dazu in
Abschnitt 6.4 Ausblick, S. 55.
21

4
Sichtbarkeit
4.1
Problemstellung
Je nach zu lösendem Problem hat der Begriﬀ Sichtbarkeit (Visibilität) in der
Computergraﬁk eine andere Bedeutung.
Bei der Rasterisierung stellt sich die Frage: Was ist auf dem Bildschirm
sichtbar? Am Ende der Rendering-Pipeline muss für jeden Punkt, der die
Viewport-Transformation (Abbildung in Bildschirmkoordinaten) durchlau-
fen hat, entschieden werden, ob er dargestellt werden soll. Nur für die Kamera
sichtbare Punkte werden dargestellt, alle verdeckten verworfen. Ein bekann-
tes Verfahren zur Lösung dieses Problems ist der Z-Buﬀer-Algorithmus. Um
zu ermitteln, ob ein Punkt verdeckt oder sichtbar ist, wird der Tiefenpuﬀer
(Z-Buﬀer) herangezogen, in dem die Tiefenwerte all jener zuvor gerenderten
Objekte, die am weitesten „vorne“ (nah an der Kamera) liegen, gespeichert
sind. Ist der Tiefenwert des zu prüfenden Punkts größer als der aktuell an
seiner Bildschirmkoordinate eingetragene Tiefenwert, ist er weiter von der
Kamera entfernt, somit verdeckt, und wird nicht dargestellt. Diese Art der
Sichtbarkeit bezieht sich also darauf, welches der in der Szene beﬁndlichen
Polygone an einem Bildpunkt (Pixel) dargestellt werden muss.
Die in dieser Studienarbeit relevante Art der Sichtbarkeitsanfrage bezieht
sich auf Sichtbarkeit innerhalb einer virtuellen Szene. Dabei werden Punkt-
paare (zum Beispiel zwei Oberﬂächenpunkte) auf gegenseitige Sichtbarkeit
oder eine Richtung von einem Punkt aus auf Unverdecktheit untersucht. Die
Sichtbarkeitsinformation ist jeweils binär: Entweder sehen sich die Punkte
oder nicht, entweder ist die Richtung unverdeckt oder nicht - eine teilwei-
se Verdeckung ist nicht möglich. Zwei Punkte sehen sich dann nicht, wenn
ein Objekt ihre Verbindungslinie schneidet. Ein solches verdeckendes Objekt
wird Occluder genannt.
1
falls die Punkte P und Q sich sehen können
V (P, Q) =
(5)
0
sonst
Eine Richtung ω ist von Punkt P aus gesehen dann unverdeckt, wenn
sich kein Occluder in dieser Richtung beﬁndet.
1
falls Richtung ω unverdeckt
V (P, ω) =
(6)
0
sonst
Betrachtet man statt Punkten inﬁnitesimal kleine Flächenelemente, die
eine Normale haben, können von vornherein alle Punkte als nicht sichtbar
(alle Richtungen als verdeckt) klassiﬁziert werden, die im hinteren Halbraum
des betrachteten Elements liegen. Potentiell sichtbare Elemente müssen im
vorderen Halbraum liegen bzw. als unverdeckte Richtungen werden nur sol-
che in Erwägung gezogen, die in den vorderen Halbraum zeigen.
22

In Abschnitt 2.3.2 wurde der Visibilitätstest als zentrales Element des
Ambient-Occlusion-Integrals vorgestellt. Auch hierbei wird nur der vorde-
re Halbraum betrachtet bzw. sogar nur eine durch einen endlichen Radius
begrenzte Hemisphäre.
Ein weiteres Anwendungsbeispiel sind Schattenfühler beim Ray Tracing.
Zu beachten ist: Die erste Anfrage des Ray Tracers „Finde den ersten Schnitt-
punkt des Strahls“ ist komplexer als ein reiner Sichtbarkeitstest, bei dem
danach gefragt wird, ob es überhaupt einen Schnitt des Strahls gibt.
4.2
Sichtbarkeitstest im Objektraum (Referenzlösung)
Im Objektraum liefert ein Ray Tracer die Referenzlösung des Sichtbarkeits-
tests. Schneidet der Strahl Ray(t) = P + t · ω mit t ∈]0..R] und beliebigem
Suchradius R die Szene, so ist die Richtung ω verdeckt. Dabei ist es irrele-
vant, an welcher Stelle des Strahls der Schnittpunkt gefunden wurde, es muss
nicht der vorderste sein. Sobald ein Schnittpunkt gefunden wurde, kann die
Suche beendet werden. Im schlimmsten Fall (kein Schnittpunkt und unend-
licher Suchradius) müssen alle Objekte getestet werden, bis feststeht, dass
wirklich kein Schnittpunkt zu ﬁnden ist. Durch Beschleunigungsstrukturen
kann die Suche jedoch auf bestimmte Objekte begrenzt werden.
4.3
Sichtbarkeitstest im Bildraum (Screen-Space)
Der Sichtbarkeitstest im Bildraum hat als Grundlage den Tiefenpuﬀer oder
Kamerakoordinaten-Puﬀer.
Wenn nur die Tiefenwerte gespeichert wurden anstelle vollständiger Ka-
merakoordinaten (x, y, z), können die Kamerakoordinaten rekonstruiert wer-
den. Eine mögliche Rekonstruktionsmethode ist es, den Shadern Informatio-
nen über das Kamerafrustum beim Zeichnen eines bildschirmfüllenden Vier-
ecks zu geben:
• Die Tiefenwerte müssen in der Form |z| /zF ar) vorliegen (z in Kamera-
Koordinaten).
• Beim Zeichnen des bildschirmfüllenden Quads wird jeder der vier Ecken
ein Sichtstrahl von der Kamera aus (0,0,0) zu der entsprechenden Ecke
der Far-Plane1 mitgegeben (z. B. als Normale oder selbst deﬁniertes
Attribut an den Vertex Shader).
• Die Sichtstrahlen werden (nicht normalisiert) an den Fragment Shader
weitergereicht, also interpoliert für jeden Pixel.
• Im Fragment Shader wird über (Tiefe·Sichtstrahl) die Kamerakoordi-
nate ermittelt, die an dieser Pixelposition im Bild zu ﬁnden ist.
1Formeln hierfür siehe OpenGL Lighthouse 3D: View Frustum Culling Tutorial http:
//www.lighthouse3d.com/opengl/viewfrustum/index.php?gaplanes
23

Die beschriebene Rekonstruktionsmethode wurde in dieser Studienarbeit wäh-
rend der Implementierung getestet, um den G-Buﬀer um eine Textur zu ver-
kleinern. Sie brachte jedoch keinen erkennbaren Performance-Vorteil, sodass
der Einfachheit halber die Variante des Abspeicherns vollständiger Kamera-
koordinaten gewählt wurde.
Abbildung 15: Visualisierung des Kamerakoordinaten-Buﬀers. Links die Szene,
wie die Kamera sie sieht. Rechts drei Ansichten des als Triangle-
Strip gerenderten Kamerakoordinaten-Buﬀers. Deutlich ist zu se-
hen, wie der Dragon in die Tiefe ragt.
Der Ray Marching-Algorithmus im Bildraum startet bei Kamera-
koordinate P und läuft schrittweise entlang eines Strahls. Für jeden Schritt
wird geprüft, ob Geometrie geschnitten wurde.
Abbildung 16: Ray Marching im Bildraum: Blau dargestellt ist das Höhenfeld.
Die Sample-Positionen auf dem Strahl sind unverdeckt (grün) oder
verdeckt (rot). Die weiß dargestellten Positionen auf dem Höhen-
feld ergeben sich aus dem auf S. 25 beschriebenen Projektionsver-
fahren. Der Vergleich zwischen diesen Positionen und den Strahl-
Samples liefert das Ergebnis, ob verdeckt oder unverdeckt.
Abbildung nach [BS09, S. 430]
Für jede Sample-Position P + t · Ray soll also ermittelt werden, ob der
Strahl an dieser Stelle unterhalb oder oberhalb des Höhenfeldes verläuft. Da
die Suche einen begrenzten Radius hat, ist ein Endpunkt E auf dem Strahl
bekannt. Das Abtasten des Strahls und die Generierung der Samples kann
24

auf zwei Wegen geschehen [BS09, S. 430]. Beide Methoden liefern identische
Ergebnisse:
1. 3D-Samples in Kamerakoordinaten Samplecam = Pcam+t·Raycam
mit einem 3D-Strahl der Länge Radius. Jedes 3D-Sample wird mit
der zum Zeitpunkt des G-Buﬀer-Renderings gesetzten Projektionsma-
trix und anschließender manueller Transformation in Texturkoordina-
ten überführt. Mit dieser Texturkoordinate wird auf die Tiefentextur
zugegriﬀen und die „reale“ Tiefe an der Stelle ermittelt. Der Vergleich
von Samplecam.z und RealPoscam.z zeigt, ob sich der Sample-Punkt auf
dem Strahl unter- oder oberhalb des Höhenfeldes beﬁndet. In OpenGL
blickt die Kamera nach der View-Transformation entlang der negati-
ven z-Achse, also sind alle Tiefenwerte negativ. Ein größerer Tiefenwert
bedeutet demnach „näher an der Kamera“. Ein Schnitt liegt vor, wenn
RealPoscam.z > Samplecam.z, denn die Geometrie liegt näher an der
Kamera als der Punkt auf dem Strahl. Somit beﬁndet sich der Strahl
bereits innerhalb der Geometrie.
Anders formuliert: Bewegt sich die Position auf dem Strahl durch die
Projektion2 von der Kamera weg, war an der Stelle keine Geometrie.
Wenn sie sich zur Kamera hin bewegt, war an der Stelle Geometrie
[RGS09].
oder
2. 2D-Samples in Texturkoordinaten Sampleuv = Puv + t · Rayuv
mit einem 2D-Strahl durch vorherige Projektion des Start- und End-
punktes in Texturkoordinaten. In diesem Fall muss nicht mehr jedes
Sample projiziert werden, sondern nur noch jeder Strahl. Folglich gibt
es weniger Matrix-Multiplikationen im Shader. Das 2D-Sample wird di-
rekt zum Texturzugriﬀ benutzt, um RealPoscam zu ermitteln. Für den
Vergleich zwischen dieser 3D-Position mit einer 3D-Strahl-Position ist
es nötig, parallel zum 2D-Sample auch das 3D-Sample zu berechnen
gemäß obiger Methode.
Ein Problem ist, dass nur der erste von der Kamera aus sichtbare Punkt
pro Pixel bekannt ist – alles, was dahinter liegt, aber nicht. Es ragt sozusagen
alles, was vorne nah an der Kamera ist, unendlich tief in die Szene hinein
und wird dort als Geometrie erkannt. Das heißt, der Test kann ergeben,
dass sich zwei Punkte nicht sehen, obwohl sich zwischen ihnen eigentlich
kein Occluder beﬁndet, im Screen-Space aber ein vorderes Objekt imaginär
bis nach hinten ragt. Dadurch entstehende Artefakte bei Ambient Occlusion
sind in Abschnitt 6 (Ergebnisse) geschildert.
2von Kamerakoordinaten in Texturkoordinaten und Auslesen der realen Kamerakoor-
dinaten an dieser Texturkoordinate
25

Eine Lösung des Problems ist Depth Peeling. Dabei werden durch mehrfa-
ches Rendering Schichten (Texturen) erzeugt, die den herkömmlichen Tiefen-
puﬀer durch Tiefen ergänzen, die hinter dem vordersten Pixel liegen. Außer
Tiefen können natürlich auch noch andere Informationen pro Schicht gespei-
chert werden, aber der Speicherbedarf ist enorm.
Wie kann mit zwei Schichten der Sichtbarkeitstest im Bildraum verbes-
sert werden? Angenommen, die Geometrie ist so beschaﬀen, dass die Ober-
ﬂäche eindeutig das Objektinnere vom Objektäußeren trennt. Dann gehört
der Tiefenwert z1 der ersten Schicht zu einer Vorderseite und der Tiefenwert
z2 der dahinter liegenden zweiten Schicht zu der zugehörigen Rückseite. Für
einen Sample-Punkt muss daher ausgewertet werden, ob er sich hinter z1,
aber vor z2 beﬁndet, also im Inneren eines Objektes [RGS09, S. 3 f.]. Dieser
Ansatz kann mit weiteren Schichtenpaaren fortgeführt werden.
Abbildung 17: Sichtbarkeitstest und Depth Peeling mit 2 Schichten: Das Sample
S (rot) ist von Punkt P aus gesehen eigentlich unverdeckt. Es
würde aber bei nur einer Schicht als verdeckt angenommen, da es
sich aus Sicht der Kamera hinter einem Occluder beﬁndet. Mit 2
Schichten ergibt die Auswertung des z-Werte-Paars (gelb), dass
das Sample unverdeckt ist, da es sich nicht zwischen den beiden
Werten beﬁndet. Graﬁk nach [RGS09, S. 4]
Ein anderer Ansatz ist das Rendern der Szene aus zusätzlichen Kame-
rapositionen und -blickwinkeln. [RGS09, S. 4] beschreiben die Details einer
möglichen Umsetzung. Ein nennenswerter Vorteil gegenüber Depth Peeling
besteht darin, dass so auch Informationen über Polygone gewonnen wird, die
ganz oder nahezu parallel zur Standard-Kamera verlaufen. Außerdem erfas-
sen die zusätzlichen Kameras Objekte, die außerhalb des mit der Standard-
Kamera gerenderten Bildes liegen. Somit lassen sich Probleme am Bildrand
lösen, die daher stammen, dass es über die außerhalb der Tiefentextur lie-
gende Geometrie keine Information gibt.
26

4.4
Sichtbarkeitstest im Voxelraum (Voxel-Space)
Die geschilderten Probleme im Bildraum entspringen immer einer mangeln-
den Information über im Bild nicht erfasste Geometrie.
Im Voxelraum werden sämtliche Objekte von einer Voxelisierungskamera
erfasst. Anders als bei der Nutzung des Tiefenpuﬀers (1 Layer, keine zusätz-
lichen Kameras) liegt hier auch Information über die Szenengeometrie vor,
die von der Kamera aus nicht direkt sichtbar ist. Dies ist Geometrie, die
von vorderen Objekten verdeckt wird oder gar außerhalb des rasterisierten
Bereichs der darstellenden Kamera liegt.
Die voxelisierte Szene (eine Slicemap, Körpervoxelisierung) wird unter-
stützend zum G-Buﬀer herangezogen. Zur Voxelisierung und zur ﬁnalen Dar-
stellung der Szene kann jeweils eine eigene Kamera benutzt werden:
Voxelisierungskamera zur Voxelisierung mit orthographischer Projektion
und eigener View-Transformation. Im Folgenden wird nur eine einfache
statische View-Transformation betrachtet, sodass das quaderförmige
Frustum die gesamte Szene umschließt. Komplizierter wird es, wenn
die Voxelisierungskamera dynamisch so positioniert wird, dass ihr Fru-
stum immer mindestens so viel von der Szene umschließt wie jenes der
Darstellungskamera.
Darstellungskamera zum Rendering des G-Buﬀers mit perspektivischer
Projektion und eigener (von der View-Transformation der Voxelisie-
rungskamera abweichender) View-Transformation zum dynamischen
Bewegen.
Wie lassen sich im Screen-Space erfasste Kamerakoordinaten der Darstel-
lungskamera und Voxel-Space in Einklang bringen?
Die Projektion der Kamerakoordination der Darstellungskamera in Slice-
map-Texturkoordinaten ist komplexer als im bildbasierten Fall. Im Bildraum
genügt die Projektionsmatrix der einzigen darstellenden Kamera. Um die Ka-
merakoordinaten in Slicemap-Koordinaten zu transformieren, müssen sie...
• zunächst mit der inversen View-Matrix der Darstellungskamera in Welt-
koordinaten gebracht werden,
• anschließend mit der View-Matrix der Voxelisierungskamera in die Vo-
xelisierungskamera-Koordinaten
• und dann mit der Projektionsmatrix der Voxelisierungskamera (und
Überführung in Fensterkoordinaten) in Slicemap-Texturkoordinaten
...transformiert werden (siehe Abbildung 18).
Die drei Matrizen sollten bereits im Vertex Shader multipliziert und das
Ergebnis als varying Variable an den Fragment Shader weitergereicht wer-
den.
27

Abbildung
18:
Die
T
ransformationssc
hritte
28

Es entsteht eine Texturkoordinate mit 3 Komponenten: Die ersten beiden
(s, t) werden dafür gebraucht, das entsprechende Texel (die Voxelspalte) aus
der Slicemap abzurufen. Nur ein spezielles Voxel innerhalb der 128 Voxel
dieses Texels soll daraufhin überprüft werden, ob es gefüllt ist, also ob sich
hier bei der Voxelisierung Geometrie befand. Mit der dritten Komponente
der Texturkoordinate wird ein Lookup in einer 1D-Textur gemacht, die der
in Abbildung 9 auf S. 17 dargestellten Bitmask entspricht. Eine bitweise
Verundung des entsprechenden Texels aus dieser Lookup-Textur mit dem
Texel aus der Slicemap liefert einen 128 Bit-Wert (aufgeteilt in einen 4-
Komponenten-Vektor mit je 32 Bits pro Komponente), in dem entweder alle
Bits 0 sind (leeres Voxel an der Stelle), oder aber in dem ein Bit gesetzt ist
(volles Voxel an der Stelle).
4.5
Bildraum vs. Voxelraum
Bildraum (einfachster Fall ohne Depth-Peeling und zusätzliche Kameras):
• keine komplizierten Transformationen: nur eine Kamera, nur ein einzi-
ger Raum
• kann auf alles angewendet werden, was in den Z-Buﬀer rasterisiert
werden kann; keine Einschränkungen der Meshes
• falsche Ergebnisse möglich wegen „nach hinten ragender vorderer Ob-
jekte“
• blickwinkelabhängig, hat keine Information über verdeckte Geometrie
und nicht-rasterisierte (außerhalb des Bildes beﬁndliche) Geometrie
Voxelraum:
• nicht blickwinkelabhängig
• kennt (näherungsweise) die gesamte Szenengeometrie, auch verdeckte
oder außerhalb des Sichtfelds der Darstellungskamera liegende Objekte
• Slicemap kann als diskretes Depth-Peeling angesehen werden, bei dem
die Anzahl der Schichten in z-Richtung vorgegeben ist
• fehleranfälliger aufgrund der verschiedenen Räume (Voxelisierungska-
mera, Darstellungskamera) und der Transformationen
• zusätzlicher Pass für die Voxelisierung und zusätzliche Textur (Slice-
map)
• vorgestellte Voxelisierungsmethode erfordert Meshes, die watertight
sind, und Shader Model 4.0 wegen der Integer-Texturen
29

Abbildung 19: Vergleich der Sichtbarkeitstests: Links: im Bildraum, rechts: im
Voxelraum. Die Bilder entstanden, indem ausgehend von einem
fest deﬁnierten Startpixel (rot markiert) ermittelt wurde, welche
anderen Pixel er im Bild sieht. Methode: Ray Marching, je 50
Schritte (mit Jittering) entlang eines Strahls.
Beide Verfahren:
• keine weiteren auf der CPU zu haltenden und zu pﬂegenden Daten-
strukturen
• keine Vorverarbeitung
• geeignet für dynamische Szenen
30

5
Implementierung
5.1
Überblick
In dieser Studienarbeit wurden folgende Verfahren umgesetzt:
• Ambient Occlusion mit Ray Marching im Bildraum und Voxelraum
• Indirektes Licht (erste Indirektion) im Bildraum einsammeln
(Sichtbarkeitsbestimmung dabei entsprechend des jeweiligen Ambient-
Occlusion-Verfahrens)
• Sichtbarkeitstests im Bildraum und Voxelraum („Was sieht ein Pixel?“)
Abbildung 20: Screenshot der Anwendung, in der die genannten Verfahren be-
trachtet werden können. Die Verfahren hängen von vielen manuell
zu setzenden Parametern ab, sodass ebenso viele Steuerelemente
für das Justieren der Werte benötigt werden.
Die in Abbildung 20 gezeigte Anwendung entstand in der Entwicklungs-
umgebung Visual Studio 2008 mit C++, OpenGL (Open Graphics Library)
31

und GLSL (OpenGL Shading Language). Das Laden von 3D-Modellen er-
möglicht der Wavefront-OBJ-Loader GLM von Nate Robins3. Die Benutzer-
oberﬂäche wurde mit der Bibliothek Qt4 (Version 4.5.1) realisiert.
Die wichtigsten Schritte, die bei jedem Zeichenaufruf abgearbeitet wer-
den, sind in Abbildung 21 dargestellt. Die Wahlmöglichkeiten des Benutzers,
sich nur bestimmte Texturen statt des ﬁnalen Bildes anzeigen zu lassen, sind
der Übersicht halber nicht abgebildet. Außerdem kann die voxelisierte Szene
in Form vieler Quader dargestellt werden, was insbesondere zum Debuggen
nützlich war.
Die Voxelisierung wird nur durchgeführt, wenn anschließende Schritte die
voxelisierte Szene (Slicemap) als Eingabe benötigen. Abschnitt 3 (S. 14 ﬀ.)
beschreibt die Erzeugung der Slicemap samt Implementierungsdetails, sodass
dieser Schritt hier nicht weiter erläutert wird.
Bei der Implementierung der Verfahren wurde besonders darauf geachtet,
die Algorithmen und deren Eingabewerte für Bild- und Voxelraum so ähnlich
wie nur möglich zu halten, um faire Vergleiche ziehen zu können.
Alle wesentlichen Schritte (Voxelisierung, G-Buﬀer-Erstellung, Ambient
Occlusion und indirektes Licht, Blur und Kombination der erzeugten Textu-
ren) sind als Shader implementiert.
5.2
G-Buﬀer erzeugen
In der Szene (Cornell-Box mit 3D-Modell(en)) gibt es eine Punktlichtquelle
und zwei gerichtete Lichtquellen, die die Grundhelligkeit der direkten Be-
leuchtung erhöhen. Optional kann Shadow Mapping eingeschaltet werden,
was einen zusätzlichen Render-Pass aus Sicht der Punktlichtquelle erfordert.
Für das Rendern der Szene wird ein Framebuﬀer-Objekt (FBO) mit meh-
reren Render Targets genutzt. Für die an das FBO gehängten Texturen (color
attachments) gelten bestimmte Regeln in Bezug darauf, wie oder ob inter-
ne Texturformate miteinander kombiniert werden dürfen. In der hier vorge-
stellten Implementierung wurden vier Render Targets mit jeweils 3 Kanälen
(RGB) und dem internen Format GL_RGB32F_ARB verwendet. Diese vier Tex-
turen bilden den G-Buﬀer. Eine Änderung des G-Buﬀer-Layouts zieht viele
Änderungen in anderen Programmteilen nach sich. Dennoch musste eine sol-
che in der letzten Implementierungsphase durchgeführt werden, denn der
zunächst angedachte einzelne Kanal für die Speicherung der Beleuchtungs-
stärke reichte für farbige Lichtquellen nicht aus.
Die ﬁnale Zusammensetzung des G-Buﬀers sieht wie folgt aus: je eine
Textur für die BRDF (fr,d= Reﬂexionsgrad/π), für die direkte Beleuchtung
(Ldir = fr,d · Edir), für Normalen in Kamerakoordinaten und für Positionen
in Kamerakoordinaten.
3enthalten im Tutors source code package: http://www.xmission.com/~nate/
tutors.html
4http://qt.nokia.com/
32

Abbildung 21: Rendering-Ablauf: Skizze der jeweiligen Schritte pro Frame.
33

Ausgehend von einer Szene mit rein diﬀusen Materialen wird für die
direkte/lokale Beleuchtung das Lambert-Beleuchtungsmodell eingesetzt. Die
Lichtquellen sind mit ihrer Lichtstärke I (Einheit: Candela) deﬁniert. Eine
100-Watt-Glühlampe erzeugt beispielsweise ca. 1000 Lumen, was für eine
Punktlichtquelle 1000lm ≈ 80cd sind.
4πsr
Die photometrische Formel für die Beleuchtungsstärke ist E = I·cos θ , wo-
d2
bei d der Abstand zu der Lichtquelle und θ der Winkel zwischen Oberﬂächen-
normale und dem Vektor in Richtung Lichtquelle ist. Gerichtete Lichtquellen
haben keine solche Abschwächung. Als Alternative zu den gerichteten Licht-
quellen wurde der Lookup in einer stark geblurrten diﬀusen Environment
Map implementiert.
5.3
Ambient Occlusion und indirektes Licht
5.3.1
Sampling
Um zu ermitteln, wie stark die Hemisphäre eines Punktes verdeckt ist, wird
Monte-Carlo-Integration eingesetzt, deren Grundlage die Erzeugung von
Samples mit einer bestimmten Dichte ist.
Die theoretischen Grundlagen wurden in Abschnitt 2.3.4 (S. 8 f.) erläu-
tert. Es wurde bereits darauf hingewiesen, dass die Wahl der Dichtefunktion,
mit der die Samples generiert werden, beeinﬂusst, wie schnell und gut sich
der geschätzte Wert der tatsächlichen Lösung annähert. „Schnell“ heißt, dass
möglichst wenig Samples benutzt werden müssen.
Die Basis für die Erzeugung von Samples bilden im Allgemeinen (0,1)-
verteilte Zufallszahlen. Diese sind im Intervall [0, 1] so verteilt, dass jeder
Wert mit gleicher Wahrscheinlichkeit angenommen werden kann. Hier spielt
die Güte der erzeugten Zufallszahlen eine wichtige Rolle. Statt echter oder
Pseudo-Zufallszahlen, wie der C++-Zufallszahlengenerator sie liefert, kön-
nen auch deterministisch erzeugte Low Discrepancy Sequenzen eingesetzt
werden. Jene Diskrepanz ist ein mathematisch deﬁniertes Maß für die Quali-
tät einer Sequenz – je niedriger die Diskrepanz, desto besser sind die Zahlen
verteilt.
Für die implementierten Ambient-Occlusion-Verfahren wurde die Low
Discrepancy Hammersley-Sequenz verwendet, da die Anzahl der Samples
vorab bekannt ist und sie eine bessere Diskrepanz als die Halton-Sequenz
aufweist. Später wurde zu Vergleichzwecken auch die Halton-Sequenz einge-
baut. Es zeigte sich, dass die Hammersley-Sequenz tatsächlich die bessere
Wahl ist (siehe Abbildung 22).
Das i-te n-dimensionale Element von insgesamt N Elementen der Hammer-
sley-Sequenz ist deﬁniert als Xi = ( i , Φ
N
2(i), Φ3(i), Φ5(i), ..., Φb(i)). Die Funk-
tion Φb(i) heißt radikal inverse Funktion mit i ∈ N und Basis b. Als Basen
sind Primzahlen zugelassen. Die Zahlen i liegen normalerweise im Dezimal-
system vor. Die radikal inverse Funktion konvertiert i zunächst ins Zahlen-
34

Abbildung 22: Konstruktion der Samples mit ... links: Hammersley-Sequenz, Mit-
te: Halton-Sequenz, rechts: C++-Pseudo-Zufallszahlen. (Verfah-
ren: Voxel-Space AO, Ray Marching)
system mit Basis b, spiegelt diese Zahl am Komma und konvertiert die ge-
spiegelte Zahl wieder ins Dezimalsystem. Das Ergebnis ist eine Zahl zwischen
0 und 1.
Ausgehend von einer zweidimensionalen Hammersley-Sequenz wurden
uniformes und cosinusgewichtetes Sampling der Hemisphäre umgesetzt (sie-
he Abbildung 23).
Abbildung 23: Links: Cosinusgewichtetes Sampling. Rechts: Uniformes Sampling
(ohne Cosinus-Term)
Dem Shader wird die Sequenz statt der fertigen Samples als uniform-
Variable übergeben, da die Werte der Sequenz pro Pixel modiﬁziert werden.
Das Vorgehen hierfür heißt Cranley-Patterson-Rotation [PH04, S. 348]:
Xi = (Xi + ξi) mod 1
ξi ist eine Zufallszahl zwischen 0 und 1, die pro Pixel aus einer kleinen
gekachelten Random-Textur gelesen wird. Würde man die Samples vorab be-
35

rechnen und als uniform-Variable an den Shader reichen, wäre das Sampling-
Muster für jeden Punkt gleich. Abbildung 24 zeigt den dabei auftretenden
Eﬀekt.
Abbildung 24: Ohne Rotation (links) treten die mit den Pfeilen markierten Ar-
tefakte auf, mit Rotation (rechts) wandeln sich diese zu Rau-
schen. (Verfahren: Voxel-Space AO, Ray Marching, Sampling mit
Hammersley-Sequenz)
Nach [PH04, S. 650 f., 656 f.] sind die Kugelkoordinaten bzw. kartesischen
Koordinaten der Sampling-Richtungen wie folgt zu berechnen:
Uniformes Sampling mit konstanter Dichte
Kugelkoordinaten:
θ =
cos−1 ξ1
φ =
2πξ2
Kartesische Koordinaten:
x =
cos(2πξ2)
1 − ξ21
y =
sin(2πξ2)
1 − ξ21
z =
ξ1
Cosinusgewichtetes Sampling mit Dichte proportional zu cos(θ)
Das cosinusgewichtete Sampling der Hemisphäre erzeugt erst uniform
verteilte Punkte (x,y) in einem Einheitskreis und hebt diese dann senk-
recht in die dritte Dimension auf die Oberﬂäche der Hemisphäre.
Kartesische Koordinaten:
x =
cos(2πξ2)
ξ1
y =
sin(2πξ2)
ξ1
z =
1 − x2 − y2
36

Eine Herleitung ﬁndet sich in der genannten Quelle. Die so erzeugten
kartesischen Koordinaten (x, y, z) entsprechen Einheitsvektoren. Sie sind um
eine Hemisphäre mit Normale (0,0,1) orientiert und müssen daher noch der
tatsächlichen Normalen entsprechend ausgerichtet werden.
Listing 3: Erzeugung der Richtungssamples: Auszug aus Ambient Occlusion GLSL
Fragment Shader
1
# v e r s i o n 120
2
# d e f i n e PI 3 . 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5
3
4
u n i f o r m s a m p l e r 2 D r a n d o m T e x ;
5
u n i f o r m v e c 2 s a m p l i n g S e q u e n c e [ 1 2 8 ] ; // 2 D Low D i s c r . S e q u e n c e
6
u n i f o r m int n u m R a y s ;
7
u n i f o r m b o o l u s e C o s W e i g h t ;
8
9
v o i d m a i n ()
10
{
11
[ . . . ]
12
// TBN B a s i s
13
// get n o r m a l N , c o m p u t e t a n g e n t Tan and b i t a n g e n t B i T a n
14
15
// get r a n d o m n u m b e r s [0 ,1]
16
v e c 3 r a n d = t e x t u r e 2 D ( r a n d o m T e x , mod ( g l _ F r a g C o o r d . st , 6 4 . 0 ) ←
/ 6 4 . 0 ) . rgb ;
17
18
// d i s t r i b u t e r a y s o v e r h e m i s p h e r e
19
for ( int i = 0; i < n u m R a y s ; i ++)
20
{
21
// Cranley - P a t t e r s o n R o t a t i o n
22
f l o a t u1 = f r a c t ( s a m p l i n g S e q u e n c e [ i ]. x + r a n d . x ) ;
23
f l o a t u2 = f r a c t ( s a m p l i n g S e q u e n c e [ i ]. y + r a n d . y ) ;
24
f l o a t r ;
25
if ( u s e C o s W e i g h t )
26
// c o s i n e w e i g h t e d s a m p l i n g
27
r = s q r t ( u1 ) ;
28
e l s e
29
// u n i f o r m s a m p l i n g
30
r = s q r t ( 1 . 0 f - u1 * u1 ) ;
31
f l o a t phi = 2 * PI * u2 ;
32
// c a r t e s i a n c o o r d i n a t e s
33
f l o a t x = cos ( phi ) * r ;
34
f l o a t y = sin ( phi ) * r ;
35
f l o a t z = s q r t ( max (0.0 ,1.0 - x * x - y * y ) ) ;
36
37
// t r a n s f o r m s a m p l i n g d i r e c t i o n to c a m e r a s p a c e
38
v e c 3 ray = x * Tan + y * B i T a n + z * N ;
39
40
// m a r c h ray [ . . . ]
41
}
42
}
37

Die Methode zur Ausrichtung der Richtungen
mit Hilfe einer Tangent-Bitangent-Normal Basis
stammt von NVIDIA5, siehe Listing 4. Ergänzt wur-
de die Berechnung durch die Zeilen 4 und 5, um
den Bug zu beheben, dass bei Normalen mit Rich-
tung (0,0,1) oder (0,0,-1) die Bitangente durch das
Kreuzprodukt zu (0,0,0) degeneriert und infolge-
dessen ebenso die Tangente (falsches Ergebnis siehe
rechts: Die Rückwand der Cornell-Box wird nicht
korrekt dargestellt). Die initiale „beliebige“ Tangente darf nicht mit der Nor-
malen übereinstimmen.
Listing 4: Berechnung der TBN Basis
1
v e c 3 N = t e x t u r e 2 D ( n o r m a l T e x , g l _ T e x C o o r d [ 0 ] . st ) . xyz ;
2
// a r b i t r a r y v e c t o r Tan not c o i n c i d i n g w i t h the n o r m a l
3
v e c 3 Tan = v e c 3 ( 0 . 0 , 0 . 0 , 1 . 0 ) ;
4
if ( N . x = = 0 . 0 && N . y = = 0 . 0 )
5
Tan = v e c 3 ( 0 . 0 , 1 . 0 , 0 . 0 ) ;
6
v e c 3 B i T a n = n o r m a l i z e ( c r o s s ( N , Tan ) ) ; // b i t a n g e n t
7
Tan = c r o s s ( BiTan , N ) ; // t a n g e n t
Jede Richtung wird mit einer benutzerdeﬁnierten Schrittzahl und inner-
halb eines ebenfalls benutzerdeﬁnierten Radius stückweise auf Schnittpunkte
mit Occludern abgetastet.
5.3.2
Gewichtung der Samples
Beim Ray Marching wird der erste Punkt, der sich innerhalb von Geometrie
beﬁndet, als Schnittpunkt angenommen. Deshalb können die einzelnen Sicht-
barkeitsergebnisse jeweils entsprechend des Abstandes zum ersten Schnitt-
punkt gewichtet werden (vgl. Abschnitt 2.4 Obscurances, S. 12). Abbildung
25 zeigt die Ergebnisse verschiedener Distanzabbildungsfunktionen. Auf der
y-Achse ist das Gewicht eines Samples abgetragen.
Dass der grundsätzliche Verlauf der Funktionen aus Abbildung 25 zu je-
nem in Abbildung 6 (S. 13) gespiegelt ist, liegt an der konkreten Berechnung
des Verdeckungswertes. Im Bild stehen dunkle Farb- oder Grauwerte für „ver-
deckt“. Bei den in dieser Studienarbeit implementierten Verfahren werden
nur die verdeckten Samples gewichtet und aufaddiert. Es ergeben sich hohe
Werte (größere Helligkeit) für verdeckte Bereiche, sodass der akkumulierte
Wert am Ende invertiert werden muss.
5NVIDIA Direct3D SDK 10.5 Sample Screen Space Ambient Occlusion (gemeint ist da-
mit Horizon-Based Ambient Occlusion) http://developer.download.nvidia.com/
SDK/10.5/direct3d/samples.html
38

Abbildung 25: Von links nach rechts: keine Abschwächung, lineare Abschwä-
chung, quadratische Abschwächung. (Verfahren: Voxel-Space AO,
Ray Marching)
5.3.3
Screen-Space AO und Screen-Space GI
Die Implementierung von Screen-Space AO und GI (kurz SSAO und SSGI)
ist getreu ihren Namen auf den Bildraum beschränkt. Es ﬁndet kein Depth-
Peeling statt und es gibt nur eine Kamera. Die Methode zur Sichtbarkeitser-
mittlung ist das auf S. 24 geschilderte Ray Marching. Bei Screen-Space AO
werden die Sichtbarkeitsergebnisse im Falle eines gefundenen Schnittpunktes
mit einer der genannten Gewichtungsfunktionen gewichtet, aufaddiert und
diese Summe durch die Anzahl der verschossenen Strahlen geteilt. Das Er-
gebnis muss schließlich invertiert werden, um zu erreichen, dass verdeckte
Bereiche im Bild dunkel erscheinen.
Der Fragment Shader für Screen-Space AO wird für jeden Pixel beim
Zeichnen eines bildschirmfüllenden Rechtecks aufgerufen. Er benötigt als
Eingaben: die Textur mit den Kamerakoordinaten, die Textur mit den Nor-
malen, eine kleine Zufallstextur, die Projektionsmatrix der Kamera, die zum
Zeitpunkt der G-Buﬀer-Erzeugung gesetzt war, eine 2D-Low-Discrepancy-
Sequenz und zahlreiche benutzerdeﬁnierte Parameter (z. B. Strahlanzahl,
Schrittanzahl, Kontrast).
Das Ergebnis schreibt er in eine an ein FBO geknüpfte Graustufen-
Textur vom Typ GL_LUMINANCE32F_ARB. Die Textur hat die Auﬂösung des
Viewports, der während des Zeichnens des bildschirmfüllenden Rechtecks ge-
setzt ist. Der Aufwand von Screen-Space-Verfahren hängt vor allem von der
Auﬂösung ab; die Geschwindigkeit beim Rendern kleinerer Auﬂösungen er-
höht sich entsprechend. Daher kann die Ambient-Occlusion-Textur in voller,
halber oder viertel Auﬂösung (volle Auﬂösung = Auﬂösung der G-Buﬀer-
39

Texturen) erstellt werden. Mit „halber Auﬂösung“ ist gemeint, dass sowohl
Breite als auch Höhe halbiert werden. Eigentlich handelt es sich um eine
Viertelung der Pixelanzahl und somit im besten Fall um eine Vervierfachung
der Geschwindigkeit. Für das Hochskalieren der Textur auf volle Auﬂösung
wird ein geometrie-sensitiver Blur genutzt, mehr dazu in Abschnitt 5.4 auf
S. 43.
Listing 5 zeigt, wie ein Strahl schrittweise durch Tiefenvergleiche auf
Schnittpunkte getestet wird. Es ist die 3D-Samples-Methode, die in Ab-
schnitt 4.3 auf S. 25 beschrieben wird. Mit j+rand.z in Zeile 13 wird die
Schrittweite pro Pixel „gejittert“.
Listing 5: SSAO: Schritte entlang eines 3D-Strahls in Kamerakoordinaten
1
f l o a t ao = 0 . 0 ; // i n i t ao for a c c u m u l a t i o n
2
for ( int i =1; i <= n u m R a y s ; i ++)
3
{
4
// c o n t r u c t i - th ray
5
6
b o o l hit = f a l s e ;
7
f l o a t h i t D i s t = 0 . 0 ;
8
// s t e p s a l o n g ray
9
for ( f l o a t j = 1 . 0 ; j <= n u m S t e p s ; j ++)
10
{
11
if (! hit )
12
{
13
v e c 3 s a m p l e P o s = P + ( j + r a n d . z ) / n u m S t e p s * R * ray ;
14
v e c 3 r e a l P o s = g e t E y e P o s i t i o n ( s a m p l e P o s ) ;
15
16
// c o m p a r e d e p t h s : hit ?
17
if ( r e a l P o s . z - eps > s a m p l e P o s . z )
18
{
19
f l o a t d = d i s t a n c e ( P , r e a l P o s ) ;
20
if ( d < R ) // s a m p l e i n s i d e r a d i u s ?
21
{
22
hit = t r u e ;
23
h i t D i s t = d ;
24
}
25
}
26
}
27
}
28
if ( hit )
29
{
30
f l o a t a t t e n u a t i o n ;
31
// c o m p u t e a t t e n u a t i o n
32
ao += a t t e n u a t i o n ;
33
}
34
}
35
f i n a l A O = 1.0 - c o n t r a s t * ao / f l o a t ( n u m R a y s ) ;
Die zentrale Funktion zur Projektion eines 3D-Samples in Texturkoordinaten
für den Lookup in der Kamerakoordinaten-Textur ist wie folgt deﬁniert:
40

Listing 6: SSAO: Projektion eines 3D-Samples
1
v e c 3 g e t E y e P o s i t i o n ( in v e c 3 p )
2
{
3
v e c 4 c l i p C o o r d = p r o j M a t r i x * v e c 4 ( p , 1 . 0 ) ;
4
v e c 3 n D e v i c e C o o r d = c l i p C o o r d . xyz / c l i p C o o r d . w ;
5
v e c 2 l o o k u p C o o r d = ( n D e v i c e C o o r d . xy + 1 . 0 ) / 2 . 0 ;
6
r e t u r n t e x t u r e 2 D ( e y e P o s T e x , l o o k u p C o o r d ) . xyz ;
7
}
Zu beachten ist hierbei, die Projektionsmatrix zu verwenden, die zum Zeit-
punkt der G-Buﬀer-Erzeugung gesetzt war, anstelle der Built-In Matrix
gl_ProjectionMatrix. Denn letztere ist für das Zeichnen des bildschirm-
füllenden Rechtecks gesetzt.
Der Screen-Space-GI-Shader schreibt in eine RGBA-Textur (32-bit ﬂoa-
ting point) – die ersten drei Kanäle enthalten das indirekte Licht, der Alpha-
Kanal den Ambient-Occlusion-Term. Zusätzlich zu den eben genannten Ein-
gaben benötigt er noch die Textur mit den Leuchtdichten der direkten Be-
leuchtung, um das indirekte Licht einzusammeln. Gesucht ist die Beleuch-
tungsstärke
N
1
E =
Lω cos θ
L(X
e
e dω ≈ π
i).
Ω
N i=1
Die rechte Seite der Gleichung ist der Monte-Carlo-Schätzer für die Be-
leuchtungsstärke der indirekten Beleuchtung bei cosinusgewichtetem Samp-
ling. Lω bzw. L(X
e
i) ist die Leuchtdichte der direkten Beleuchtung an dem
ersten mit Ray Marching gefundenen Schnittpunkt entlang einer Richtung
ωe bzw. Xi. Sie wird der Textur an der durch Projektion des Schnittpunkts
ermittelten Koordinate entnommen und parallel zu dem Ambient-Occlusion-
Term akkumuliert. Somit hat der SSGI Shader einen Texturzugriﬀ mehr pro
Strahl, für den ein Schnittpunkt gefunden wurde, und nur wenige Operatio-
nen mehr.
5.3.4
Voxel-Space AO und Hybrid-GI
Die Autoren von „Hybrid Ambient Occlusion“ [RBA09] nennen ihr voxelba-
siertes Ambient-Occlusion-Verfahren hybrid, da im Voxelraum die Sichtbar-
keit bestimmt wird, die AO-Textur aber mit geringerer Auﬂösung erstellt
und mit einem Joint Bilateral Upsampling Filter [KCLU07] im Bildraum
hochskaliert wird.
Im Folgenden wird trotzdem die Bezeichnung Voxel-Space AO verwendet,
da die Sichtbarkeitsbestimmung der zentrale Punkt von Ambient Occlusion
ist.
Im Falle der globalen Beleuchtung handelt es sich allerdings tatsächlich
um eine Mischform aus Voxelraum und Bildraum, sodass diese im Folgenden
41

Hybrid-GI genannt wird. Das Einsammeln des indirekten Lichts basiert auf
der Slicemap und der Textur mit den Leuchtdichten der direkten Beleuch-
tung. Die Sichtbarkeit wird mit Hilfe der voxelisierten Szene bestimmt, die
Information über die Leuchtdichte an einem Punkt allerdings aus der Textur
gelesen, sodass hier nur die rasterisierte Farbe verfügbar ist. Die Voxel selbst
enthalten nur die binäre Information voll/leer, aber keine weiteren Attribute
wie Farbe oder Leuchtdichte an der Stelle. Würde den Voxeln mehr als nur
1 Bit zur Verfügung gestellt, könnten diese auch mehr Informationen tragen.
Die Auﬂösung in z-Richtung würde sich aber stark verringern; mehr Slice-
maps wären nötig und der Vorteil der ursprünglich kompakten Speicherung
wäre nicht mehr vorhanden.
Die voxelbasierten Shader benötigen mehr Eingaben als jene, die im
Bildraum arbeiten: zusätzlich noch
• die Slicemap,
• eine 1D-Lookup-Textur für das Auslesen eines Voxels aus der Slicemap
• und 3 Matrizen für die Transformation von Kamerakoordinaten in
Slicemap-Texturkoordinaten: die inverse View-Matrix der Darstellungs-
kamera, die View-Matrix der Voxelisierungskamera und die Projek-
tionsmatrix der Voxelisierungskamera.
Jene 3 Matrizen werden bereits im Vertex Shader miteinander multi-
pliziert und das Ergebnis wird an den Fragment Shader weitergereicht. Der
Hybrid-GI-Shader benötigt zudem die Projektionsmatrix der Darstellungska-
mera, um die Texturkoordinate für den Lookup der Leuchtdichte berechnen
zu können.
Die wesentliche Änderung zum Screen-Space-Shader besteht darin, dass
der Tiefenvergleich (Listing 5, Zeile 14-17) durch den Funktionsaufruf
isFilledVoxel(samplePos) ersetzt wird. Die Funktion ist wie folgt deﬁniert:
Listing 7: Voxel-Space: Liegt ein gefülltes Voxel an einer bestimmten Position vor?
1
b o o l i s F i l l e d V o x e l ( in v e c 3 p ) // p in eye - s p a c e
2
{
3
p . z += 0 . 0 2 5 ; // s h i f t t o w a r d s c a m e r a ( r e m o v e s a r t i f a c t s )
4
v e c 4 c l i p C o o r d = t r a n s f o r m M a t r i x * v e c 4 ( p , 1 . 0 ) ;
5
v e c 3 l o o k u p C o o r d = ( c l i p C o o r d . xyz + 1 . 0 ) / 2 . 0 ;
6
7
u v e c 4 val = t e x t u r e 2 D L o d ( s l i c e m a p , l o o k u p C o o r d . xy ,0) ;
8
u v e c 4 m a s k = t e x t u r e 1 D ( l o o k u p M a s k , l o o k u p C o o r d . z ) ;
9
r e t u r n ( any ( n o t E q u a l ( u v e c 4 (0) , val & m a s k ) ) ) ;
10
}
42

Abbildung 26: Geometrie-sensitiver Blur: Links die AO-Textur mit halber Auf-
lösung (256x256), rechts die zugleich hochskalierte und weichge-
zeichnete Textur (512x512). Maskenbreite: 21 Pixel
5.4
Blur
Abhängig von der Kombination der Parameter Strahlanzahl, Schritte ent-
lang eines Strahls und vor allem Radiusgröße ist das Ergebnis mehr oder
weniger verrauscht. Das Rauschen tritt bei der Voxelraum-Variante etwas
stärker auf. Eine wahrscheinliche Ursache ist, dass die Oberﬂäche der Sze-
nenrepräsentation durch die Voxelisierung „klötzchenartig“ (eckig) ist statt
„glatt“ wie im Bildraum, obwohl auch dieser diskretisiert ist.
Abhilfe schaﬀt ein geometrie-sensitiver, kantenerhaltender Weichzeichner
(Blur). Dieser erhält zusätzlich zu der verrauschten Textur als Eingabe auch
die Normalen- und Kamerakoordinaten-Textur. So lässt sich erreichen, dass
nicht über Kanten, Objektgrenzen oder starke Sprünge in den Normalen
hinweg verwischt wird. Das Rauschen wird unterdrückt, aber auch Feinheiten
gehen verloren. Letzteres stellt im Allgemeinen kein großes Problem dar, da
Ambient Occlusion generell wenig Details erfasst.
Reinbothe et al. [RBA09] erweitern das von Kopf et al. vorgestellte Joint
Bilateral Upsampling [KCLU07]. Ein bilateraler Filter ist ein nicht-linearer
Filter, bei dem zwei spezielle Funktionen die Bildwerte innerhalb der Maske
abhängig von ihrer Lage (domain) und Helligkeit (range) gewichten. Reinbo-
the et al. deﬁnieren nun eine Reihe von Gewichtungsfunktionen, die Norma-
len, Kamerakoordinaten, Pixelpositionen und Grauwerte als Eingabe erhal-
ten. Eine zweite, leicht modiﬁzierte Version wurde erstellt, um auch RGBA-
Texturen weichzeichnen zu können.
Obwohl der Filter nicht separierbar ist, wird er trotzdem näherungswei-
se in zwei Passes auf die verrauschte AO-/GI-Textur angewendet, um die
Geschwindigkeit zu erhöhen. Im ersten Pass wird in x-Richtung mit einer
43

m × 1 -Maske geﬁltert, im zweiten Pass in y-Richtung mit einer 1 × m-Maske
und mit der Ergebnis-Textur des ersten Passes als Eingabe. m ist die benut-
zerdeﬁnierte Maskengröße in Pixeln.
Die Anwendung des Blurs ist insbesondere dann notwendig, wenn die
AO-/GI-Textur nicht voll aufgelöst ist (siehe Abbildung 26). Aber auch voll
aufgelöste Texturen können von einer Rauschunterdrückung proﬁtieren.
5.5
Finale Kombination
Am Ende müssen die während des Renderings erzeugten Komponenten zu-
sammengesetzt und auf einen für den Bildschirm darstellbaren Bereich ab-
gebildet werden. Dafür kommt der Tonemapper von Drago et al. [DMAC03]
1
zum Einsatz. Der letzte Schritt ist eine Gamma-Korrektur (R, G, B, A) γ mit
einem angenommenen Gamma-Wert γ = 2.2.
Kombiniert werden müssen:
• Leuchtdichte der direkten Beleuchtung (Ldir)
• Leuchtdichte eines ambienten Umgebungslichtes (Lamb)
• diﬀuse BRDF (fr,d)
• Ambient-Occlusion-Term (AO)
• Beleuchtungsstärke der indirekten Beleuchtung (Eind),
damit ist gegeben: Lind = fr,d · Eind
Akenine-Möller et al. schlagen vor, in rein diﬀusen Umgebungen die di-
rekte Beleuchtung mit einem ambienten Licht und dem AO-Term wie folgt
zu kombinieren [AMHH08, S. 376]:
Lout = fr,d · AO · πLamb + Ldir
πLamb ist die ambiente Beleuchtungsstärke.
Durch Experimentieren wurde schließlich folgende Formel zur Kombina-
tion aller genannten Faktoren gefunden:
Lout = fr,d · (AO · πLamb + k · Eind) + Ldir · AO
Der benutzerdeﬁnierte Parameter k skaliert das indirekte Licht. Würde
der Ambient-Occlusion-Term nur das ambiente Licht verdunkeln, müsste die-
ses sehr hell sein, damit ein Eﬀekt sichtbar wird. Daher wird der AO-Term
zusätzlich auf die direkte Beleuchtung angewendet. Da Ambient Occlusion
kein physikalisch korrektes Konzept ist und alle Berechnungen nur nähe-
rungsweise ausgeführt werden, wurde mehr Wert auf ein optisch ansprechen-
des Ergebnis gelegt. Dieses ist nur durch Nutzerinteraktion (passende Wahl
der Parameter) zu erreichen. Ein Beispielergebnis ist in Abbildung 27 zu
sehen.
44

Abbildung 27: Finale Kombination: Beispiel eines Endergebnisses (die Streifen
auf dem Drachen stammen von einer Textur)
6
Ergebnisse
6.1
Qualität
Im Folgenden werden Unterschiede und Besonderheiten der Bildraum- und
Voxelraum-Verfahren in Bezug auf die Bildqualität betrachtet. Beide Vari-
anten liefern bei richtiger Wahl der Parameter überzeugende Ergebnisse.
Im Bildraum entstehen Artefakte durch verdeckte Objekte und am Bild-
rand. Besonders auﬀällig sind springende Schatten (popping shadows) bei
bewegten Bildern: Schatten können sprungartig verschwinden oder auftau-
chen. Bei statischen Bildern sind sie weniger auﬀällig. Abbildung 28 (Mitte)
zeigt einen derartigen Eﬀekt. Beim Bewegen des Bunnys oder der Kamera
würde sich der Fehler an der Wand hinter dem Bunny mitbewegen. Auch der
Kontaktschatten zwischen Bunny und Boden wäre nicht stabil. Die Sprün-
ge sind jedoch nicht abgehackt, sondern eher weich und daher, je nachdem,
wie ausgeprägt sie sind, tolerierbar. Ob Artefakte mehr oder weniger stark
auﬀallen, ist natürlich auch von der Wahrnehmung des Betrachters abhängig.
Das voxelbasierte Ambient Occlusion dagegen bleibt aus jeder Blick-
45

Abbildung 28: Links und Mitte: Screen-Space AO, rechts Voxel-Space AO. Iden-
tische Parameterwahl bei beiden Verfahren. Abschwächung der
Samples: keine. Das Bild links entstand ohne Radiuscheck („Be-
ﬁndet sich ein Sample innerhalb des Suchradius?“). Beim Bild in
der Mitte war dieser Radiuscheck aktiviert. Es ist klar ersichtlich,
dass der Radiuscheck im Bildraum unabdingbar ist. Im Voxelraum
(Bild rechts) ist ein solcher Radiuscheck nicht nötig. Auftretende
Artefakte im Bildraum sind mit Pfeilen gekennzeichnet: fehlerhaf-
te AO-Berechnung an der Wand durch das verdeckende Bunny
und am Bildrand (fehlende Verschattung).
richtung und bei Objektbewegungen stabil, da die Sichtbarkeitsbestimmung
nicht von der Kamerablickrichtung oder den für die Kamera sichtbaren Ob-
jekten abhängig ist.
Für SSGI und Hybrid-GI gilt: Indirektes Licht kann nur von im Bild sicht-
baren Flächen reﬂektiert werden. Ein Beispiel zeigt Abbildung 29. Interessant
ist der Unterschied zwischen SSGI und Hybrid-GI bei diesem Grenzfall. SS-
GI ignoriert weitestgehend das kleine Stück rote Wand als Quelle indirekten
Lichtes. Der Grund ist, dass die Wand im Bildraum nicht als stark verde-
ckendes Objekt erkannt wurde. Bei Hybrid-GI ist dies anders, da die Wand
im Voxelraum als Occluder erkannt wird. Der Auftreﬀpunkt wird zurück in
den Bildraum projiziert und an der entsprechenden Stelle kann die Farbe
ausgelesen werden. Beﬁndet sich die Wand allerdings außerhalb des Bildes,
liegt auch der projizierte Punkt außerhalb des Bildes, sodass hier nur die
geclampte Randfarbe gelesen werden kann.
Die Wahl der Parameter trägt entscheidend dazu bei, wie gut die Qualität
des ﬁnalen Bildes ist und wie stark der Ambient-Occlusion- oder GI-Eﬀekt
sichtbar wird. Insbesondere bei den Parametern zur Steuerung der Anzahl
der Samples (Strahlen, Schritte) und Auﬂösungsgröße sind Qualität und Per-
formance gegeneinander abzuwägen. Verfahren im Voxelraum sind rausch-
anfälliger als im Bildraum und benötigen daher tendenziell mehr Samples.
Abbildung 30 zeigt die Ergebnisse verschiedener Strahl-/Schrittanzahlen.
Sobald die Framerate in der Anwendung unter 6 fps fällt, wird während
einer Benutzerinteraktion (Bewegen eines Objektes, der Kamera oder der
Punktlichtquelle) die Auﬂösung der AO-/GI-Textur auf ein Viertel reduziert.
46

Abbildung 29: Grenzfallbetrachtung: Oben SSGI, unten Hybrid-GI. Links ist die
rote Wand noch knapp im Bild zu sehen und wirft daher indirektes
rotes Licht auf die hintere Wand und den Drachen. Der Eﬀekt auf
dem Drachen ist nur bei Hybrid-GI deutlich zu erkennen. Warum
SSGI hier den Color Bleeding-Eﬀekt kaum zeigt, wird auf S. 46
erläutert. Rechts ist die rote Wand aus dem Bild verschwunden,
sodass sie kein indirektes rotes Licht mehr reﬂektieren kann.
Nach Beendigung der Interaktion wird sie wieder auf die vorherige gewählte
Auﬂösung gesetzt.
Im Allgemeinen ist ein großer Radius insbesondere bei GI erforderlich, um
gute Ergebnisse zu erreichen (vgl. Abbildung 32). Kleine Radien sind für das
indirekte Licht nicht sinnvoll, denn auch in der Realität ist zu beobachten,
dass farbige Objekte auf weiter entfernte abstrahlen.
Zu beachten ist: Je größer der Radius ist, desto verrauschter wird das
Ergebnis, wenn nicht die Samples entsprechend vervielfacht werden, um den
47

größeren Raum abdecken zu können. Das Rausch-Problem ist wie erwähnt
bei den voxelbasierten Verfahren viel größer. Abbildung 31 zeigt Ambient
Occlusion mit verschiedenen Radien.
Abbildung 30: Wahl der Strahl- und Schrittanzahl (Verfahren: Voxel-Space AO,
in jedem Bild: Radius = 3.0, Slicemap-Auﬂösung: 1282, Bildauf-
lösung: 5122)
Abbildung 31: Radiusgröße (AO). Zur Orientierung: Die Cornell-Box hat die
Breite 5. (Verfahren: Voxel-Space AO, in jedem Bild: 20 Strah-
len, 20 Schritte, Slicemap-Auﬂösung: 1282, Bildauﬂösung: 5122)
Ein typisches Artefakt von SSGI wird exemplarisch in Abbildung 33 ge-
zeigt. Abhängig von der Radiusgröße erscheinen leuchtende Flecken.
In den Bildern sind pixelige Kanten sichtbar. Anti-Aliasing ist bei De-
ferred Shading nicht trivial. Die erste angedachte naive Lösung, einfach ein
FBO mit Multisampling zu benutzen, erwies sich als falsch, da anti-aliased
Normalen und Positionen keine Bedeutung haben und zu gravierenden Dar-
stellungsfehlern führen. Es gibt verschiedene Ansätze, Anti-Aliasing bei De-
ferred Shading zu realisieren, sie wurden im Rahmen dieser Studienarbeit
jedoch nicht weiter betrachtet.
Insgesamt lässt sich sagen, dass mit beiden GI-Varianten optisch sehr
ansprechende Ergebnisse möglich sind. Beispiele zeigen die Abbildungen 27,
34 - 37 und Abbildung 1 in der Einführung.
Das indirekte Licht in den in Abbildung 34 gezeigten Bildern wurde ver-
stärkt, um den Color-Bleeding-Eﬀekt hervorzuheben. Bei solch statischen
48

Abbildung 32: Große Radien (in Relation zur Szenengröße) sind für GI sinnvoll.
(Hier: Hybrid-GI)
Bildern sieht SSGI den Hybrid-GI Ergebnissen meistens sehr ähnlich, daher
wird hier nur die Hybrid-GI Variante gezeigt. Der Vorteil von Hybrid-GI, die
bessere Konstanz bei Objekt- oder Kamerabewegungen, kommt hier nicht
zur Geltung.
Abbildung 36 vergleicht SSGI mit Hybrid-GI in einer Szene, deren Objekt-
Wand-Konstellation der Grenzfallbetrachtung aus Abbildung 29 entspricht.
Somit ist bei dem mit SSGI erzeugten Bild (Mitte) auf dem Schaf kein Color
Bleeding zu sehen. Bei einem anderen Betrachtungswinkel (rechts) erscheint
auch bei SSGI das Color Bleeding. Jedoch ist bei beiden SSGI-Bildern auf
dem Bunny kaum orangefarbenes Licht auszumachen.
Abbildung 33: SSGI: Leuchtende Flecken. Mögliche Ursache: Fehlerhafte Ver-
schattung und zu viel indirektes Licht an den Stellen
49

Abbildung 34: Links: Direkte Beleuchtung mit Shadow Mapping.
Rechts: Hybrid-GI. FPS siehe Tabelle 2.
50

Abbildung 35: Die Szenen aus Abbildung 34 nur mit Voxel-Space AO
Abbildung 36: Vergleich Hybrid-GI / SSGI. In der Mitte fehlt das Color Bleeding
auf dem Schaf. Dieses wird erst sichtbar, wenn die pinkfarbene
Wand ein beträchtliches Stück weiter ins Bild gewandert ist.
Abbildung 37: Links: Direkte Beleuchtung ohne Shadow Mapping, eine Punkt-
lichtquelle. Rechts: SSAO Ray Marching
51

6.2
Performance
Ray Marching Methoden liefern qualitativ hochwertige Ergebnisse, haben
jedoch auch einen hohen Aufwand, der abhängt von der Anzahl der Strahlen
und der Schritte entlang eines Strahls. Entsprechend viele Texturzugriﬀe sind
nötig (Anzahl der Zugriﬀe = Strahlanzahl×Schrittanzahl, z. B. 32×16 = 512
(!) bei 32 Strahlen und 16 Schritten). Die Zugriﬀe sind aufgrund der Art,
wie die Samples erzeugt werden, zufällig von Strahl zu Strahl und liegen
je nach Radiusgröße weit auseinander. Somit ist die Wahrscheinlichkeit für
Textur-Cache-Misses extrem hoch.
Die übliche Methode, um den Aufwand zu verringern, ist das Rendern
der AO-/GI-Textur in geringerer Auﬂösung mit anschließendem Blurring.
Mit dem vorgestellten Blur sind die Ergebnisbilder zwar nicht mehr ver-
rauscht, haben aber trotz Geometrie-Sensitivität einen sehr weichen und
teils detailärmeren Eindruck (siehe Abbildung 38). Die Verwendung einer
GI-Textur mit halber Auﬂösung und Blur brachte in den Tests mindestens
eine Verdopplung bis Verdreifachung der Framerate (vgl. Tabelle 2).
Abbildung 38: Links: Buddha mit voll aufgelöster GI-Textur, rechts mit halber
Auﬂösung und Blur
Dynamisches Branching, insbesondere ein frühzeitiges bedingtes Verlas-
sen einer Schleife mit einem break, ist auf der GPU immer noch teuer. In
Listing 5 (S. 40) könnte die for-Schleife – sobald ein Schnittpunkt gefun-
den wurde – nach Zeile 13 mit einem break verlassen werden. Während
der Implementierung stellte sich heraus, dass dadurch die Performance des
Fragment Shaders um bis zu 20 % gesenkt wird. Anstelle eines bedingten
Verlassens der Schleife werden daher am Anfang der Schleife nur die folgen-
den Berechnungen abgefangen, falls schon ein Schnittpunkt gefunden wurde.
Dem Ray Marching gegenüber stehen SSAO-Varianten wie jene von Cry-
tek, die wesentlich weniger Samples einsetzen (meist weniger als 32). Sie sind
52

nicht strahlbasiert, sondern verteilen nur einzelne Punkte zufällig im Raum.
Deshalb erzielen sie meist ungenauere Ergebnisse bei jedoch höherer Perfor-
mance. Testweise wurde ein Punkte-Sampling im Bildraum implementiert,
bei dem eine gewisse Anzahl von Punkten zufällig (auf Grundlage einer 3D-
Hammersley-Sequenz) in der Hemisphäre eines betrachteten Oberﬂächen-
punktes verteilt werden. Die Ergebnisse sind in Abbildung 39 zu sehen. Die
Messungen der Frameraten sind in Tabelle 1 aufgeführt.
Abbildung 39: Vergleich Ray Marching (je 12 Strahlen, 10 Schritte) und einzel-
ne Samples (32 Punkte in Hemisphäre). Radius = 1,5. Slicemap-
Auﬂösung bei Voxelisierung: 1282. Das Sampling einzelner Punkte
liefert im Voxelraum stark verrauschte Bilder. Im Bildraum kön-
nen beide Sampling-Methoden ohne ein derartiges Problem einge-
setzt werden; im Voxelraum ist nur Ray Marching empfehlenswert.
53

Die Performance-Messungen wurden auf zwei Systemen durchgeführt:
System 1
System 2
NVIDIA GeForce 8600 GTS (256 MB),
NVIDIA GeForce GTX 260 (896 MB),
Intel Core 2 Duo 6420 (2x2,13 GHz),
AMD Phenom II X4 940 (4x3,00 GHz),
2 GB RAM
4 GB RAM
Tabelle 1: fps: Ray Marching vs. Sampling Points (Abbildung 39)
Sampling Points
Ray Marching
SSAO
24.2
79.9
9.6
35.7
VoxelAO
26.5
82.2
13.8
46.0
Voxel-Space AO ist etwas schneller als SSAO, da der Lookup in der 1282-
Slicemap (4 Kanäle à 32 Bit) schneller ist als in der 5122-Kamerakoordinaten-
Textur (3 Kanäle à 32 Bit). Es wurde nicht untersucht, wie Qualität und
Performance bei einer ebenso kleinen Kamerakoordinaten-Textur wären.
Tabelle 2: fps: Szenen aus Abbildung 34
Para-
Frames per Second (fps)
Szene
meter
direkte Bel.
AO
GI
1.9
7.9
1.8
7.4
V
Buddha
full
32/32
1.5
6.3
1.1
5.9
S
(200 000
55.3
146.0
4.0
5.3
18.7
V
half +
Dreiecke)
3.5
16.2
S
Blur 12
Sheep+
3.9
16.4
3.6
15.4
V
full
Bunny
24/20
3.1
12.9
2.2
12.3
S
77.6
209.9
(200 000
3.5
9.3
33.0
V
half +
Dreiecke)
6.5
29.2
S
Blur 10
3.0
11.8
2.7
11.0
V
Dragons
full
32/20
2.4
10.0
1.7
9.4
S
(287 000
43.0
106.8
3.5
6.9
23.7
V
half +
Dreiecke)
5.1
22.0
S
Blur 12
Zu Tabelle 2: V = Voxel-Space, S = Screen-Space, full/half = voll/halb
aufgelöste AO-/GI-Textur, Blur 12 = Blur aktiviert mit Blurradius 12 Pi-
xel. Die Performance beeinﬂussende Parameter sind Strahlen/Schritte, Ra-
dius (von oben nach unten in der Parameterspalte eingetragen), die AO-/GI-
Textur-Auﬂösung und bei aktiviertem Blur der Blurradius (siehe Spalte ganz
rechts). Alle Bilder haben eine Auﬂösung von 512×512. Die Slicemap hat im-
mer eine Auﬂösung von 1282. (Diese Auﬂösung ist ebenfalls ein Performance
beeinﬂussender Parameter.)
54

6.3
Erweiterungsmöglichkeiten
Mit einem geschickteren G-Buﬀer-Layout lässt sich Texturspeicher sparen.
Die Normalen und die Positionen könnten in einer einzelnen Textur zusam-
mengeführt werden: 2 Kanäle für die Normale, 1 Kanal für die Tiefe (Positio-
nen müssen rekonstruiert werden, siehe Abschnitt 4.3 auf S. 23). Dafür würde
ausgenutzt, dass die Normalen mit Länge 1 vorliegen und die dritte Kom-
ponente somit aus den ersten beiden bestimmbar ist. Das Vorzeichen der
dritten Komponente kann als Vorzeichen des Tiefenwerts gespeichert wer-
den, sofern alle Tiefenwerte dasselbe Vorzeichen besitzen und erkennbar ist,
ob es umgedreht wurde. Falls sich durch die G-Buﬀer-Änderung keine nen-
nenswerte Performance-Steigerung erzielen lässt, wären die Gründe dafür zu
suchen.
Das eindeutige Bottleneck ist das Sampling, also die zahlreichen Textur-
zugriﬀe. NVIDIAs Horizon-Based AO erreicht durch ein geschickteres Samp-
ling ähnliche Ergebnisse wie Ray Marching im Bildraum und ist dabei we-
sentlich schneller. Es wäre interessant zu untersuchen, inwieweit sich dieses
Sampling im Voxelraum durchführen lässt. Ebenfalls wäre die Übertragung
von Screen-Space Directional Occlusion auf den Voxelraum interessant. Im
folgenden Abschnitt wird eine Idee für einen schnelleren bzw. genaueren
Strahlschnitttest im Voxelraum erläutert.
Die Samples werden erst auf der GPU ausgehend von einer Low-Dis-
crepancy-Sequenz und einer Zufallszahl erzeugt. Eﬃzienter wäre es, bereits
fertig berechnete Samples zu übergeben und diese zufällig zu modifzieren.
Während der Implementierung wurde derartiges versucht, jedoch dominier-
te starkes Rauschen das Ergebnis, sodass keine zufriedenstellende Lösung
gefunden wurde.
Des Weiteren könnten die Bent Normals für die Beleuchtung herangezo-
gen werden - entweder für die direkte Beleuchtung oder für die indirekte mit
einem Lookup in diﬀusen Environment Maps.
Das implementierte Shadow Mapping ist verbesserungswürdig. Mit dem
derzeit verwendeten Model-Loader können keine komplexen Szenen vernünf-
tig geladen werden. Bisher sind nur quadratische Auﬂösungen möglich.
Als letzter Punkt wäre zu nennen: Anti-Aliasing wurde in dieser Studi-
enarbeit nicht umgesetzt, wäre aber ein wünschenswertes Feature.
6.4
Ausblick: Strahlschnitttest im Voxelraum
In den vorherigen Abschnitten ist deutlich geworden, dass sich im Voxel-
raum gute und vor allem konstante Ergebnisse erzielen lassen. Dafür ist
allerdings ein geeignetes Vorgehen für den Schnitt von Strahlen mit der Vo-
xelszene erforderlich. Bei Ambient Occlusion ergibt beispielsweise das spär-
liche Sampling einzelner Punkte im Halbraum oder in der Hemisphäre keine
guten Ergebnisse. Der Grund ist, dass diese Art des Samplings nur einen
55

zufälligen Punkt entlang eines Strahls testet und daraufhin für die gesamte
Richtung entscheidet, ob sie verdeckt ist. Ray Marching testet mehrere Vo-
xel entlang eines Strahls. Optimal wäre es, alle Voxel entlang des Strahls zu
testen. Je nach Strahllänge und Slicemap-Auﬂösung wäre dieses Vorgehen
bei einfachem Ray Marching sehr langsam.
Während der Studienarbeit wurde daher die Idee entwickelt, die in Ab-
schnitt 3.4 (S. 19 ﬀ.) beschriebenen Slicemap-Mipmaps zu nutzen, um einen
Strahl mit der Voxelszene zu schneiden. Die Visualisierung der Mipmaps (Ab-
bildung 14 auf S. 21) zeigt, dass die vollen Voxel der höheren Mipmapstufen
anzeigen, dass sich auf niedrigerer Ebene innerhalb dieses Bereichs mindes-
tens ein volles Voxel (also letztendlich Geometrie) beﬁndet. Leere Voxel auf
höheren Mipmapstufen wiederum bedeuteten, dass sich in dem gesamten
Bereich auf allen niedrigeren Ebenen keine vollen Voxel und somit keine
Geometrie beﬁndet. In diesen leeren Bereichen wird garantiert kein Schnitt-
punkt gefunden, sodass sie beim Schnitttest übersprungen werden können.
Bereiche, in denen sich mindestens ein volles Voxel beﬁndet, müssen dagegen
genauer untersucht werden.
Die Mipmaps ähneln einem Quadtree, da sie durch schrittweise Redu-
zierung der x- und y-Auﬂösung, nicht jedoch der z-Auﬂösung, entstanden.
Die Suche nach einem Schnittpunkt eines Strahls mit den Voxeln wird somit
zu einer Suche im Baum. Ein Knoten auf Mipmapstufe n ist ein Texel der
Slicemap-Mipmap dieses Levels. Er hat 4 Kinder auf Stufe n-1.
Wichtig ist für die Betrachtung, sich ein Texel (Voxelspalte) als Quader
vorzustellen (wie in Abbildung 8 auf S. 15). Diese Quader sind Axis-Aligned-
Bounding-Boxes (AABBs) im Voxelisierungskamera-Koordinatensystem. Die
Position und Abmessungen eines Quaders sind durch das Voxelisierungs-
kamera-Frustum, die Texelkoordinaten, die Slicemap-Auflösung und das ak-
tuelle Mipmap-Level gegeben.
Der grobe Ablauf des Algorithmus ist wie folgt: Ein AABB-Schnitttest
eines Strahls mit einem Quader liefert entweder keinen Schnitt oder den
Eintritts- und/oder Austrittspunkt. Bei keinem Schnitt werden die Geschwis-
terknoten untersucht. Bei einem Schnitt wird das Strahlstück als Voxelspal-
te konstruiert, und zwar mit vollen Voxeln zwischen den z-Werten des Ein-
und Austrittspunkts. Die Verundung des Strahlstücks mit dem Texel des
geschnittenen Quaders ergibt, ob der Strahl auf diesem Level volle Voxel
geschnitten hat. Falls ja, werden die 4 Kindknoten untersucht, sofern nicht
schon der niedrigste Mipmap-Level erreicht wurde. In diesem Fall wäre die
Suche mit dem Ergebnis „Schnitt gefunden“ beendet. Die Details, wie und
unter welchen Bedingungen im Baum auf- oder abgestiegen wird, werden
hier nicht erläutert.
Die Erwartung ist, dass die Berechnung genauer und unter Einbeziehung
dieser Genauigkeit schneller als das herkömmliche Ray Marching ist.
56

6.5
Fazit
In der Studienarbeit wurde untersucht, wie Sichtbarkeitstests im Kontext ei-
nes Deferred Shadings durchgeführt werden können. Sichtbarkeitstests arbei-
ten rein geometrisch, ihre Grundlage bildet die Szenenrepräsentation. Zwei
Arten, die Geometrie näherungsweise zu repräsentieren – (1) Bildraum und
(2) Voxelraum – wurden genauer betrachtet und im Rahmen von Ambient
Occlusion für die Sichtbarkeitsbestimmung eingesetzt. Darauf aufbauend lie-
ßen sich globale Beleuchtungseﬀekte im Bildraum realisieren.
Die Ergebnisse beider implementierter Verfahren sind visuell überzeu-
gend. Das voxelbasierte Verfahren kennt näherungsweise die gesamte Szene,
sodass die Sichtbarkeitstests blickwinkelunabhängig sind. Es liefert daher vor
allem in dynamischen Szenen und bei Kameraschwenks stabile Ergebnisse.
Dem gegenüber stehen potentiell springende Schatten im Bildraum. Die In-
tegration indirekten Lichts beruht wiederum nur auf Bildraum-Information,
sodass die gezeigten Color-Bleeding-Eﬀekte sowohl für das voxel- als auch
das bildraumbasierte GI-Verfahren von den im Bild zu sehenden Flächen
abhängt. Hybrid-GI schneidet bei den betrachteten Grenzfällen besser ab.
Die Verfahren sind gegeneinander abzuwägen in Bezug auf Genauigkeit
und Flexibilität. Voxel-Space AO ist genauer, erfordert aber spezielle Meshes.
Reine Bildraum-Verfahren können auf alles angewendet werden, was in den
Bildraum rasterisiert wurde.
SSAO wird bereits in aktuellen Computerspielen eingesetzt (Crysis, Burn-
out Paradise) und ist für das kommende StarCraft 2 fest eingeplant. Es
scheint nur eine Frage der Zeit zu sein, bis sich auch Screen-Space-Verfahren
für globale Belechtungseﬀekte wie Color Bleeding in künftigen Spielegenera-
tionen als Standard etablieren.
57

Literatur
[AMHH08] Akenine-Möller, Thomas ; Haines, Eric ; Hoffman, Naty:
Real-Time Rendering. 3. A K Peters, Ltd., 2008
[BS09]
Kapitel 6.2 Image-Space Horizon-Based Ambient Occlusion.
In: Bavoil, Louis ; Sainz, Miguel: Shader X7: Advanced Ren-
dering Techniques. Course Technology, 2009, S. 425–444
[BSD08]
Bavoil, Louis ; Sainz, Miguel ; Dimitrov, Rouslan: Image-
space horizon-based ambient occlusion.
In: SIGGRAPH
’08: ACM SIGGRAPH 2008 talks, ACM, 2008. –
DOI:
http://doi.acm.org/10.1145/1401032.1401061 (letzter Zugriﬀ
am 10.08.2009)
[Bun05]
Kapitel 14 Dynamic Ambient Occlusion and Indirect Lighting.
In: Bunnell, Michael: GPU Gems 2: Programming Techniques
for High-Performance Graphics and General-Purpose Computa-
tion (Gpu Gems). Addison-Wesley Professional, 2005, 223-233. –
Online unter http://download.nvidia.com/developer/GPU_Gems_
2/GPU_Gems2_ch14.pdf (letzter Zugriﬀ am 04.06.2009)
[DMAC03] Drago, Frederic ; Myszkowski, Karol ; Annen, Thomas ;
Chiba, Norishige:
Adaptive Logarithmic Mapping For Dis-
playing High Contrast Scenes.
In: Brunet, Pere (Hrsg.) ;
Fellner, Dieter W. (Hrsg.): The European Association for
Computer Graphics 24th Annual Conference: EUROGRAPHICS
2003 Bd. 22(3).
Granada, Spain : Blackwell, 2003 (Compu-
ter Graphics Forum 3), S. 419–426. –
Online unter http:
//www.mpi-inf.mpg.de/resources/tmo/logmap/logmap.pdf (letz-
ter Zugriﬀ am 17.09.2009)
[ED06]
Eisemann, Elmar ; Décoret, Xavier: Fast Scene Voxelization
and Applications. In: ACM SIGGRAPH Symposium on Inter-
active 3D Graphics and Games, ACM SIGGRAPH, 2006, 71-78.
– Online unter http://artis.imag.fr/Publications/2006/ED06
(letzter Zugriﬀ am 10.08.2009)
[ED08]
Eisemann, Elmar ; Décoret, Xavier: Single-pass GPU So-
lid Voxelization and Applications. In: GI ’08: Proceedings of
Graphics Interface 2008 Bd. 322, Canadian Information Pro-
cessing Society, 2008 (ACM International Conference Procee-
ding Series), 73-80. –
Online unter http://artis.imag.fr/
Publications/2008/ED08a (letzter Zugriﬀ am 10.08.2009)
58

[Kaj09]
Kapitel 6.1 Screen-Space Ambient Occlusion. In: Kajalin, Vla-
dimir: Shader X7: Advanced Rendering Techniques. Course
Technology, 2009 (ShaderX), S. 413–424
[KCLU07] Kopf, Johannes ; Cohen, Michael ; Lischinski, Dani ; Uyt-
tendaele, Matt:
Joint Bilateral Upsampling.
In: ACM
Transactions on Graphics (Proceedings of SIGGRAPH 2007
26 (2007), Nr. 3. –
Online unter http://johanneskopf.de/
publications/jbu/paper/FinalPaper_0185.pdf (letzter Zugriﬀ
am 17.09.2009)
[Kne07]
Knecht, Martin:
State of the Art Report on Ambient Oc-
clusion. Technical University of Vienna, 2007. – Online un-
ter http://www.cg.tuwien.ac.at/research/publications/2007/
knecht-2007-ao/knecht-2007-ao-paper.pdf (letzter Zugriﬀ am
06.05.2009)
[Lan02]
Landis, Hayden: Production-Ready Global Illumination. ACM
SIGGRAPH Course Notes, Course 16 (RenderMan in Pro-
duction), Juli 2002. – Online unter http://www.debevec.org/
HDRI2004/landis-S2002-course16-prodreadyGI.pdf (letzter Zu-
griﬀ am 24.8.2009)
[LB99]
Langer, Michael S. ; Bülthoff, Heinrich H.:
Perception
of shape from shading on a cloudy day / Max-Planck-Institut
für biologische Kybernetik.
Tübingen, Deutschland, Oktober
1999 (73). – Forschungsbericht. – Online unter http://www.
kyb.mpg.de/publications/pdfs/pdf1539.pdf (letzter Zugriﬀ am
04.09.2009)
[Mit07]
Mittring, Martin: Finding next gen: CryEngine 2. In: SIG-
GRAPH ’07: ACM SIGGRAPH 2007 courses, ACM, 2007, 97–
121. – Online unter http://ati.amd.com/developer/SIGGRAPH07/
Chapter8-Mittring-Finding_NextGen_CryEngine2.pdf
(letzter
Zugriﬀ am 06.05.2009)
[Mén07]
Méndez Feliu, Àlex: Fast Photorealistic Techniques to Simula-
te Global Illumination in Videogames and Virtual Environments,
Universitat Politècnica de Catalunya, Diss., April 2007. – Online
unter http://ima.udg.edu/~amendez/thesis/thesis.pdf (letzter
Zugriﬀ am 04.09.2009)
[PH04]
Pharr, Matt ; Humphreys, Greg: Physically Based Rende-
ring: From Theory to Implementation. San Francisco, CA, USA
: Morgan Kaufmann Publishers Inc., 2004
59

[RBA09]
Reinbothe,
Christoph
;
Boubekeur,
Tamy
;
Alexa,
Marc:
Hybrid Ambient Occlusion.
In: EUROGRAPHICS
2009 Areas Papers (2009). –
Online unter http://perso.
telecom-paristech.fr/~boubek/papers/HAO/HAO.pdf (letzter Zu-
griﬀ am 06.05.2009)
[RGS09]
Ritschel, Tobias ; Grosch, Thorsten ; Seidel, Hans-Peter:
Approximating Dynamic Global Illumination in Image Space. In:
I3D ’09: Proceedings of the 2009 symposium on Interactive 3D
graphics and games, ACM, 2009, 75–82. – Online unter http://
www.mpi-inf.mpg.de/~ritschel/Papers/SSDO.pdf (letzter Zugriﬀ
am 06.05.2009)
[ZIK98]
Zhukov, Sergej ; Inoes, Andrej ; Kronin, Grigorij: An Am-
bient Light Illumination Model. In: Drettakis, George (Hrsg.) ;
Max, Nelson (Hrsg.): Rendering Techniques ’98, Springer-Verlag
Wien New York, 1998 (Eurographics), S. 45–56
60

Document Outline

Einf�hrung
Beleuchtung
- Lokale Beleuchtungsmodelle
- Globale Beleuchtungsmodelle
- Ambient Occlusion
  - Definition
  - Berechnung
  - Bent Normal
  - Monte-Carlo-Integration
  - Existierende Verfahren
- Obscurances
Voxelisierung mit der GPU
- Einf�hrung
- Oberfl�chenvoxelisierung
  - Die Voraussetzungen
  - Der Ablauf
- K�rpervoxelisierung
- Erstellung von Slicemap-Mipmaps
Sichtbarkeit
- Problemstellung
- Sichtbarkeitstest im Objektraum (Referenzl�sung)
- Sichtbarkeitstest im Bildraum (Screen-Space)
- Sichtbarkeitstest im Voxelraum (Voxel-Space)
- Bildraum vs. Voxelraum
Implementierung
- �berblick
- G-Buffer erzeugen
- Ambient Occlusion und indirektes Licht
  - Sampling
  - Gewichtung der Samples
  - Screen-Space AO und Screen-Space GI
  - Voxel-Space AO und Hybrid-GI
- Blur
- Finale Kombination
Ergebnisse
- Qualit�t
- Performance
- Erweiterungsm�glichkeiten
- Ausblick: Strahlschnitttest im Voxelraum
- Fazit
Literaturverzeichnis