www.codeworx.org/grafik/artikel/Schatten


Ausarbeitung zum Thema Schatten

Autor: Sebastian Schäfer, grasmo@grasmo.de, 17.03.2003
Johann Wolfgang Goethe Universität Frankfurt am Main,
FB. 15 Informatik, Professur für Graphische Datenverarbeitung
Proseminar „Computer Graphics and 3D Games“, WS 2002
Betreuer: Tobias Breiner, Wolfgang Baier
Aufbereitung: Hans-Jakob Schwer, webmaster@codeworx.org, 10.09.2003


Inhaltsverzeichnis
1 Grundsätzliche Schattengedanken
2 Einfache Schattenalgorithmen
2.1 Prerendered Shadows
2.2 Planar Shadows
2.3 Soft Planar Shadows
3 Komplexe Schattenalgorithmen
3.1 Stencil Volume Shadows
3.1.1 Das Schattenvolumen
3.1.2 Abdunkeln des Volumens
Zwischeneinschub: Der Stencilbuffer
3.2 Shadow Mapping
3.2.1 Erzeugen der Shadow-Map
3.2.2 Vergleichen der Tiefenwerte
3.2.3 Dual-Textur Shadow Mapping
4 Zusammenfassung & Ausblick
4.1 Zusammenfassung
4.2 Ausblick
4.2.1 ShadowMapping
4.2.2 Stencil Volume Shadows
4.2.3 Shadow Volume Shader
4.2.4 Photon Mapping
Literaturverzeichnis

1 Grundsätzliche Schattengedanken
Schatten ist paradoxerweise ein Lichtphänomen, weil es ohne Licht keinen Schatten geben kann.
Schatten entsteht daher auf ganz natürliche Weise dort, wo etwas nicht beleuchtet ist. Die ganze
Welt ist von vorneherein unbeleuchtet und in Dunkelheit getaucht. Erst durch eine oder mehrere
Lichtquellen und einem angestrahlten Objekt wird aus der unbeleuchteten Fläche das, was wir
Schatten nennen: „Ein dunkler Raum hinter einem beleuchteten, undurchsichtigen Körper“ [Bro83].

Man unterscheidet zwei verschiedene Arten von Schatten:
• Kernschatten (engl. umbra)
Kernschatten sind komplett unbeleuchtete Flächen. Sie entstehen z.B. dann, wenn es nur eine
Lichtquelle gibt. Der Bereich hinter dem beleuchteten Objekt ist dann immer komplett
unbeleuchtet.

• Schlagschatten oder Halbschatten (engl. penumbra)
Schlagschatten sind im Gegensatz zu Kernschatten teilweise ausgeleuchtete Flächen. Handelt es
sich bei einer Lichtquelle nicht um eine punktförmige Lichtquelle, oder wird ein Objekt von
mehr als einer Lichtquelle beleuchtet, so entstehen Schlagschatten, die nur von einer oder einem
Teil der Lichtquelle beleuchtet werden.

Da sich Licht im normalen Raum geradlinig ausbreitet, kann man Schattenverläufe in gegebenen
Szenen auf dem Papierriss relativ leicht konstruktiv bestimmen (Abb. 1). Dazu braucht man
zusätzlich zu einem Blatt Papier und einem Stift nur noch ein Lineal. Man verbindet jede
Lichtquelle bzw. die Enden jeder Lichtquelle mit den Kanten des schattenwerfenden Objektes.
Diesen Lichtstrahl verlängert man solange, bis er auf die Wand trifft. Jetzt kann man recht einfach
erkennen, von wie vielen Lichtern eine Fläche auf der Wand ausgeleuchtet wird. Dieses Verfahren
lernt man allgemein im Schulunterricht bei der Behandlung von Sonnen- und Mondfinsternis
kennen.



Abb.1: Skizze der Schattenverlauf einer Mondfinsternis


In der Realität trifft man selten auf reine Kernschatten (Abb. 2). Dies hat zwei verschiedene Gründe.
Zum Einen gibt es so gut wie keine punktförmigen Lichtquellen in der realen Welt. Zum anderen
reflektieren Oberflächen auch einen Teil des Lichts, der den Schattenbereich noch zu einem
gewissen Teil ausleuchtet. Dieses Phänomen nimmt mit zunehmender Entfernung von
schattenwerfendem Objekt und der schattierten Wand zu, da mehr Licht auf die Unterseite des
Objektes einfallen kann.


Abb.2: Skizze der Schattenverlauf einer Mondfinsternis


Schatten sind für das menschliche Auge sehr wichtig. Sie erleichtern uns, die räumliche Anordnung
einer Szene zu begreifen. Außerdem entstehen in der Natur Schatten und der Mensch ist es daher
gewohnt, Schatten zu sehen. Sobald die Schatten fehlen, wirkt die betrachtete Szene unnatürlich
und komisch. Irgendetwas stimmt einfach nicht. Dies lässt sich auch an einfachen

__
Abb. 3 und 4: Einfache Szene mit und ohne Schatten


Schattenalgorithmen nachweisen, mit denen sich der Realitätsgrad einer Szene steigern lässt

2 Einfache Schattenalgorithmen

2.1 Prerendered Shadows

Der einfachste Schattenalgorithmus ist der „prerendered Shadows-“Algorithmus. Der Schatten wird
mit einem externem Programm berechnet (z.B. ein 3D-Renderprogramm, wie Maya oder
Cinema4D) und im Programm selbst als eine Textur verwendet. Der Schatten ist somit statisch – er
verändert sich nicht. Oftmals besteht der Schatten aus einem einfachen Kreis, der von außen nach
innen dunkler wird. Dieser Schatten entsteht in ähnlicher Weise immer dann, wenn sich die
Lichtquelle weiter entfernt über oder vor einem Objekt befindet.
Der Vorteil dieses Algorithmuses ist, dass er sehr wenig Rechenzeit erfordert: Der Schatten muss
nicht berechnet, sondern nur angezeigt werden. Deswegen wurde er schon sehr früh erdacht und bis
vor kurzer Zeit noch in Spielen verwendet. Mittlerweile wird er in aktuellen Spielen jedoch nicht
mehr angewandt, da die verfügbare Rechenkapazität die Verwendung von anderen Algorithmen
erlaubt. Der „prerendered Shadows“-Algorithmus kam z.B. in folgenden Spielen zur Anwendung:

• Rayman, erschienen für Dreamcast im Jahr 2000
• Sonic Adventure(Abb. 5), erschienen für Dreamcast im Jahr 1998



Abb. 5: Segas Sonic Adventure, Dreamcast


Im Spiel selbst wird der Schatten meistens per Texturprojektion oder als zusätzliche Textur in die
Szene projiziert. Dies geschieht entweder in einem zweiten Rendervorgang, in dem die Textur
projiziert wird, oder – sofern die Grafikhardware dies unterstützt – per Multitexturing schon im
ersten Rendervorgang. Auch wenn diese Methode gewisse Vorteile, wie hohe Geschwindigkeit und einfache
Implementierung hat, überwiegt dennoch der große Nachteil, dass der Schatten nicht dynamisch ist.
Hervorzuheben ist aber, dass Kern- und Schlagschatten je nach vorgerendertem Schatten erzeugt
werden können.

2.2 Planar Shadows

Die einfachsten dynamischen Schatten werden mit dem „Planar Shadows“-Algorithmus erzeugt.
Um ihn verstehen zu können, muss man auch wissen, wie ein 3D-Punkt der virtuellen Welt zu ein
2D-Punkt auf den Bildschirm transformiert wird: Er wird mit der Projektionsmatrix multipliziert
und anschließend innerhalb der „Viewport Transformation“ einem 2D-Punkt zugewiesen. Die
Projektionsmatrix legt die verwendete (orthogonale oder perspektivische) Projektion und deren
Parameter fest. Beim „Planar Shadows“-Algorithmus werden mit Hilfe einer
Schattenprojektionsmatrix die schattenwerfenden Objekte auf eine zweidimensionale Ebene
innerhalb der virtuellen 3D-Welt geworfen und mit der Schattenfarbe gerendert. Danach muss die
Matrixmultiplikation wieder rückgängig gemacht und die Objekte mit der normalen
Projektionsmatrix gerendert werden.
Um die Schattenprojektionsmatrix zu bestimmen, muss die Ebenengleichung der Ebene und die
Position des Lichtes bekannt sein:



Die Ebengleichung errechnet man üblicherweise aus 3 Vektoren, die die Ebene aufspannen.
Die mit diesem Verfahren erzeugten Schatten sind zwar dynamisch, werden jedoch immer auf eine
Ebene projiziert. Sobald man den Schatten auf einer nicht planaren Oberfläche erzeugen will, gibt
es zwei Möglichkeiten: Entweder setzt man die Oberfläche aus mehreren planaren Flächen
zusammen oder man muss sich für einen anderen Algorithmus entscheiden. Eine wichtige Rolle
spielt dabei der Unterschied zwischen einer Ebene und einer Fläche:

• Ebene
Eine Ebene teilt einen Raum in zwei Halbräume auf. Sie besitzt eine unendlich große Fläche, die
von unendlicher Ausdehnung ist.

• Fläche
Eine Fläche ist eine Teilmenge einer Ebene. Sie hat eine genau bestimmbare Ausdehnung.

Der geschilderte „Planar Shadows“-Algorithmus kann Schatten auf Ebenen erzeugen. In den
seltensten Fällen will man jedoch einen Schatten auf einer ganzen Ebene haben. Es kann zu
sogenannten „Clipping“-Fehlern kommen: Der Schatten auf dem Boden ragt über den Boden hinaus
in die Wand hinein (Abb. 7).
Dieses Problem behebt man typischerweise unter Ausnutzung eines Puffers [Kil99], der in
modernen Grafikkarten in der Hardware vorhanden ist: der Stencilbuffer. Der Stencilbuffer ist ein
Puffer (wie etwa der Tiefenspeicher), in dem zusätzliche Informationen gespeichert werden können.
Er hat üblicherweise eine Kapazität von 8 Bit und kann wie das Maskierungswerkzeug einer
Bildbearbeitung benutzt werden. So kann man den Stencilbuffer nutzen, um z.B. nur in einem
vorher markierten Bereich zu rendern. In der Praxis markiert man die Fläche, auf die der Schatten
geworfen werden soll, im Stencilbuffer und rendert den Schatten auf die Fläche (Abb. 8).


__
Abb. 7 und 8: Szene fehlerhaften und korrekten planaren Schatten


Ein Problem, mit dem man häufig konfrontiert werden kann, ist die sogenannte „Rückprojektion“
des Schattens [AMH02]. Beim Rendern von planaren Schatten wird immer ein Schatten erzeugt.
Auch wenn sich das schattenwerfende Objekt nicht zwischen dem Licht und der Fläche befindet, so
kommt es fälschlicherweise zu einem Schatten, dem sogenannten Anti-Schatten (Abb. 9).


Abb. 9: Rückprojektion auf der Decke


Der Anti-Schatten entsteht, da das Objekt durch die Lichtquelle hindurch auf die Fläche projiziert
wird. Dieses Problem kann man nur durch Überprüfung der Position von Licht und Objekt im Vergleich zur Fläche lösen.
Der große Vorteil von planaren Schatten ist deren Rendergeschwindigkeit. Lediglich das
schattenwerfende Objekt muss zweimal gezeichnet werden. Entscheidet man sich für „gestencilte“
planare Schatten, muss zusätzlich die Fläche noch in den Stencilbuffer gerendert werden. Allerdings
kann beim ersten Rendervorgang von Objekt und Fläche die Beleuchtung sowie die Texturierung
abgeschaltet werden, um Zeit zu sparen. Hinzu kommt, dass der Schatten für jeden Frame neu
berechnet werden muss, auch wenn sich weder Objekt noch Licht verändern. In einem solchen Fall
kann man den Schatten in eine Textur rendern, die dann zusätzlich auf die Fläche gelegt wird.
Nachteil ist auch, dass der erzeugte Schatten ein Kernschatten ist. Aber auch für dieses Problem gibt
es eine Lösung.

2.3 Soft Planar Shadows

Der „Soft Planar Shadows“-Algorithmus ist eine Erweiterung des „Planar Shadows“-Algorithmus.
Der Schatten wird für jede Lichtquelle mit einem „Alpha-Wert“, d.h. halbtransparent, gerendert.
Dort, wo sich mehrere halbtransparente Schatten überlagern, wie dies im Kernbereich des Schattens
der Fall sein wird, entstehen dunklere Schatten. Möchte man mit einer einzelnen Lichtquelle
Schlagschatten erzeugen, so rendert man mehrere Schatten, deren Lichtquelle minimal von der
originalen Lichtposition abweichen. Praktikabel ist zum Beispiel, die Lichtquellen sphärisch um die
originale Lichtposition anzuordnen. Die Qualität des Schlagschattens wie auch die
Berechnungsdauer nimmt mit der Anzahl der verwendeten Lichtquellen zu (Abb.10 – Abb. 12).

__ __

3 Komplexe Schattenalgorithmen

Im Kapitel „Komplexe Schattenalgorithmen“ möchte ich zwei Schattenalgorithmen vorstellen, die
Schatten nicht nur auf Ebenen werfen können. Beide Methoden erzeugen Schatten auf relativ
natürliche Art und Weise, jedoch in einer völlig unterschiedlichen Verfahrensweise:

• Stencil Volume Shadows erzeugen zu jedem Objekt ein Schattenvolumen, das innen nicht
beleuchtet wird.
• Shadow Mapping hingegen überprüft, ob jeder für die Kamera sichtbare Pixel vom Licht aus
sichtbar ist und entscheidet so, ob dieser Pixel beleuchtet werden soll.

Beide Algorithmen bestimmen einen Bereich, der nicht beleuchtet wird, im Gegensatz zu den
einfachen Schattenalgorithmen, die den zuerst voll beleuchteten Schattenbereich nachträglich
abdunkeln. Auch können beide Algorithmen im Gegensatz zu den einfachen Schattenalgorithmen
Selbstschattierungen erzeugen.

3.1 Stencil Volume Shadows

Der hier beschriebene Algorithmus basiert auf dem von Heidmann und stammt von Everitt und
Kilgard aus dem Jahre 2002 [EKN02]. Der zugrunde liegende „Shadow Volume“-Algorithmus geht
auf Crow zurück, der schon 1977 einen Schattenalgorithmus auf Basis von Schattenvolumen
formuliert hat. Obwohl der Algorithmus schon 25 Jahre alt ist, findet man erst in den letzten Jahren
einige Spiele oder Programme, die diesen Algorithmus benutzen. Dies liegt zum Einen daran, dass
die Erzeugung des Schattenvolumens sehr rechenaufwändig ist. Zum Anderen haben erst seit kurzer
Zeit Grafikkarten eine große Verbreitung gefunden, die 3D-Schnittstellen beschleunigen.
Es gab zwar auch mehrere Ansätze, den Algorithmus ohne Stencilbuffer umzusetzen, jedoch sind
diese eher ineffizient [EKN02]. Der erste Ansatz zu einem Schattenvolumenalgorithmus auf Basis
des Stencibuffers stammt von Heidmann aus dem Jahre 1991.

3.1.1 Das Schattenvolumen

Zunächst muss das Schattenvolumen bestimmt werden. Es besteht aus der von der Lichtquelle
erzeugten Silhouette des Lichtes, welche in die „Unendlichkeit“ verlängert wird. Wenn das Objekt
ein einfaches dem Licht zugewandtes Dreieck ist, so ist das Schattenvolumen ein Pyramidenstumpf,
der beim Dreieck beginnt und vom Licht weg verlängert wird.
Der Ansatz ist im Prinzip der Gleiche, wie wir ihn im ersten Kapitel in der „Pen & Paper“-Methode
kennen gelernt haben, nur wird er jetzt für drei Dimensionen eingesetzt. Allerdings sind die
wenigsten Objekte so simpel wie ein einfaches Dreieck. Bei komplexeren Objekten ist es ein klein
wenig aufwändiger, die Silhouette zu bestimmen. Vereinfachend ist, dass die Objekte immer als ein
Dreiecksnetz geladen werden, so dass sich der folgender Algorithmus anwenden lässt:
• Zu jedem Dreieck muss die Normale bestimmt werden (sofern dies noch nicht geschehen ist).
• Anschließend wird anhand der Normale n und der Lichtposition l überprüft, ob das Dreieck dem
Licht zugewandt ist:

d = nx * lx + ny * l y + nz l * z

Wenn d > 0, ist das Dreieck dem Licht zugewandt. Gilt jedoch d < 0, so ist es dem Licht
abgewandt. Sobald zwei benachbarte Dreiecke einen unterschiedlichen Wert für d haben, ist
deren gemeinsame Kante Bestandteil der Silhouettenliste.
Die einzelnen Silhouettenpunkte werden per Multiplikation in die „Unendlichkeit“ projiziert und
bilden so die Ummantelung des Schattenvolumens (Abb. 13).

__
Abb. 13: Drahtgittermodell der Ummantelung, Abb. 14: Schattenvolumen des Torus

Der Vorteil dieses Verfahrens ist, dass das Schattenvolumen so exakt wie möglich bestimmt wird
(Abb. 14). Von Nachteil ist der extrem hohe Rechenaufwand, da zu jedem einzelnen Dreieck die
Lichtausrichtung berechnet und mit der aller benachbarter Dreiecke verglichen werden muss. Da
sich bei jeder Veränderung (Rotation oder Translation) des Objektes oder des Lichtes das
Schattenvolumen ändert, wird der Algorithmus in bewegten Szenen auch sehr oft ausgeführt. Eine
Möglichkeit, hier Rechenzeit zu sparen, besteht darin, die Silhouette eines weniger detailierteren
Modells zu berechnen. Nicht nur eine optimierte Datenstruktur, sondern auch der eigentliche
Algorithmus kann einige Optimierungen enthalten und so helfen, Zeit zu sparen.

3.1.2 Abdunkeln des Volumens

Um eine Beleuchtung innerhalb des Schattenvolumens zu verhindern, wird der Stencilbuffer
benutzt. Die Verwendung des Stencilbuffers wurde oben anhand eines Spezialfalles beschrieben.
Hier soll nun eine allgemeinere Einführung folgen.

Zwischeneinschub: Der Stencilbuffer

Der Stencilbuffer ist ein Teil des Framebuffers. Auf ihn kann man in OpenGL seit der Version 1.0
aus dem Jahr 1991 und in DirectX seit der Version 6.0 aus dem Jahr 1998 [EKN02] zugreifen.
Bevor aus den gerasterten Fragmenten auf dem Bildschirm sichtbare Pixel werden, können sie
einige der folgenden Tests durchlaufen: Tiefenvergleich, Alphatest, Stenciltest, Blending, .... Der
Stencilbuffer speichert für jeden Pixel einen gewöhnlicherweise 8bit großen Wert. Während man
Objekte rendert, kann der im Stencilbuffer gespeicherte Wert erhöht, erniedrigt, invertiert,
überschrieben, zurückgestellt oder beibehalten werden. Dabei kann man unterschiedliche
Operationen den unterschiedlichen Ergebnissen einer Tiefenwertvergleichsfunktion zuordnen. So
kann z.B. der Stencilwert nur dann verändert werden, wenn das gerenderte Objekt sichtbar ist, d.h.,
wenn der Z-Wert des neuen Objektes kleiner als der im Tiefenpuffer vorhandene Wert ist.
Anschließend kann anhand einer Vergleichsfunktion nur dort gerendert werden, wo im Stencilbuffer
ein bestimmter Wert gespeichert ist. Die Vergleichsfunktion überprüft die Werte anhand einer
Maske, so dass man sowohl absolute Werte als auch nur einzelne Bits vergleichen kann [WNDS99].
Mit Hilfe des Stencilbuffers kann recht einfach bestimmt werden, welche Bereiche des
Framebuffers innerhalb und welche außerhalb eines oder mehrerer Schatten sind:
Der ursprüngliche Algorithmus von Heidmann sah vor, dass die Vorderseite des Schattenvolumens
den Stencilbufferwert erhöht (Abb. 15) und die Rückseite ihn erniedrigt (Abb. 16). Der Wert im
Stencilbuffer gibt so die Anzahl der Schattenvolumen an, innerhalb derer sich ein Pixel befindet.
Folglich darf eine Beleuchtung nur dort erfolgen, wo im Stencilbuffer der Wert 0 steht (Abb. 17).


____
Abbildung 15: Vorderseite des Schattenvolumens
Abbildung 17: Komplettes Schattenvolumen
Abbildung 16: Rückseite des Schattenvolumens

Allerdings ist diese Vorgehensweise nicht unproblematisch. So ist das Schattenvolumen nicht
komplett abgeschlossen, es wird nur die Ummantelung, nicht aber die Ober- und Unterseite in den
Stencilbuffer gerendert. Die Oberseite des Volumens wird abgeschlossen, indem die dem Licht
zugewandten Dreiecke an ihrem normalen Platz gerendert werden; die dem Licht abgewan
Dreiecke werden wie Silhouettenkanten in die Unendlichkeit projiziert. Die in die Unendlichkeit
verlängerten Dreiecke müssen immer gerendert werden, so dass aus jedem Blickwinkel der Kamera
heraus das Schattenvolumen abgeschlossen wird. Um dies zu erreichen, muss die Projektionsmatrix
entsprechend angepasst werden. In ihr wird nämlich der Abstand zur entfernten Clippingebene
angegeben. Dieser Abstand muss jetzt maximal, also unendlich, werden. Die normale
Projektionsmatrix, welche in OpenGL mit dem Befehl glFrustum erzeugt wird, sieht wie folgt
aus [EKN02]:


left : linke Clippingplane
right : rechte Clippingplane
top: obere Clippingplane
bottom: untere Clippingplane
near: nahe Clippingplane
far : entfernte Clippingplane

Nach Blinn kann man die Matrix umformen, so dass die entfernte Clippingplane nicht mehr
verwendet wird:

Der Algorithmus sieht damit so aus:
• Falls nötig, müssen die Silhouettenkanten neu bestimmt werden.
• Die Szene wird komplett mit Hintergrundbeleuchtung gerendert. Alle diffusen Lichter oder Spots
werden deaktiviert.
• Der komplette Stencilbuffer wird auf 0 gesetzt.
• Nur das Schreiben in den Stencilbuffer wird zugelassen, alle anderen Puffer werden deaktiviert.
• Die von der Kamera aus sichtbare Vorderseite des Schattenvolumens wird gezeichnet und erhöht
den Wert im Stencilbuffer dann, wenn der Tiefenvergleich positiv ist (also das Volumen sichtbar
ist).
• Die Rückseite des Schattenvolumens wird gezeichnet. Wenn der Tiefenvergleich positiv ausfällt,
wird der Wert im Stencilbuffer erniedrigt.
• Die Hintergrundbeleuchtung wird jetzt ausgeschaltet, die anderen Lichter werden aktiviert.
• Der Tiefenvergleich bleibt deaktiviert, das Schreiben in den Farbpuffer wird aktiviert und
zusätzlich wird Blending eingeschaltet. Dadurch wird die helle Beleuchtung der Szene
hinzugefügt.
• Der Stenciltest wird so konfiguriert, dass gerenderte Daten nur bei einem Stencilwert von 0 in
den Farbpuffer geschrieben werden.
• Jetzt wird die komplette Szene ein zweites Mal gerendert.

Wie man leicht sehen kann, ist der gesamte Algorithmus sehr komplex. Die Berechnung der
Silhouettenkanten kostet je nach Komplexität des Objektes unterschiedlich viel Rechenzeit, die der
Hauptprozessor leisten muss. Sowohl die Szene als auch das Schattenvolumen muss zusätzlich
zweimal gerendert werden, so dass der Algorithmus viel Rechenaufwand benötigt. Dafür erzeugt er
realistische Kernschatten, die überall – auch auf dem Objekt selbst – Schatten erzeugen (Abb. 18).


Abbildung 18: Stencil Volume Schatten des Torus

3.2 Shadow Mapping

Mit dem „Shadow Mapping“-Algorithmus wird zwar ein ganz anderer Ansatz verfolgt, aber man
kommt zu dem gleichen Ergebnis.
Jeder von der Kamera aus sichtbaren Pixel wird überprüft, ob er vom Licht aus sichtbar ist. Ist dies
nicht der Fall, weil er durch ein dem Licht näheren Objekt verdeckt wird, so muss sich der Pixel im
Schatten befinden. Um festzustellen, ob ein Pixel sichtbar ist, wird eine sogenannte Shadow-Map
benutzt.
Zuerst wird eine Shadow-Map erzeugt, deren gespeicherten Tiefenwerte dann im zweiten Schritt
mit den realen Tiefenwerten verglichen werden. So kann über die Schattierung oder
Nichtschattierung entschieden werden.
Der hier beschriebene Algorithmus wurde von Kilgard 2000 auf der Game Developer Conference
2000 vorgestellt [Kil00].

3.2.1 Erzeugen der Shadow-Map

Die Shadow-Map ist eine Textur, in der die vom Licht aus gerenderte Ansicht gespeichert wird.
Allerdings wird nicht das sichtbare Bild gespeichert, sondern die Z-Werte, also die Tiefenwerte des
Bildes. Manchmal wird sie auch Depth-Map aufgrund der gespeicherten Werte genannt. Zur
Darstellung der Shadow-Map werden die Tiefenwerte in RGB-Werte umgewandelt, so dass das
Ergebnis eine Graustufenbild ist (Abb. 19).


Abb. 19: Graustufendarstellung der Shadow-Map

Um die Shadow-Map zu erhalten, muss zunächst die Kamera auf die Position des Lichtes
verschoben werden. Anschließend wird eine Projektionsmatrix erstellt, die den vom Licht
beleuchteten Bereich mit der Kamera „einfängt“.
Da es sich dabei um eine perspektivische Projektion handelt, kann die Matrix P aus dem Kapitel
3.1.2 verwendet werden. Hier gilt es, die Parameter für die nahe und die entfernte Clippingplane
geschickt zu wählen. Man muss beachten, dass der Tiefenspeicher der Shadow-Map begrenzt ist.
Üblicherweise kann man die Z-Werte mit einer Genauigkeit von 16 Bit speichern, jedoch ist der
Wert von der Hardware abhängig. Dennoch müssen die beiden Clippingplanes der Szene individuell
angepasst werden. Liegen sie zu weit auseinander, so wird der Schatten inakkurat. Ist der Abstand
der beiden Clippingplanes zu nah an der Szene, so schneiden diese die Szene: Der Bereich
außerhalb der Clippingplanes erzeugt keinen Schatten, da er ignoriert wird.
Weiter ist die Auflösung der Shadow-Map von Bedeutung. Von ihr hängt die Qualität des Schattens
maßgeblich ab. Um dies zu verdeutlichen werden hier einige Screenshots mit unterschiedlich
aufgelösten Shadow-Maps dargestellt. Zum Vergleich sind Shadow-Maps mit einer Auflösung von

64x64 Pixel (Abb. 20), 256x256 Pixel (Abb. 21) und 512x512 Pixel (Abb. 22)

____

verwendet worden:
Die maximale Auflösung hängt von der Grafikkarte ab. Jedoch steigt die zu übertragende Datenzahl
mit der Größe der Shadow-Map und der zweite Teil des Algorithmuses dauert entsprechend länger.
Um die Erstellung der Shadow-Map zu beschleunigen, können nicht benötigt Renderfeatures
abgeschaltet werden, wie etwa Texturierung oder Beleuchtung, da aus oben geschilderten Gründen
nur die Z-Werte von Interesse sind.

3.2.2 Vergleichen der Tiefenwerte

Jetzt muss jeder von der Kamera aus sichtbare Pixel überprüft werden, ob er auch vom Licht aus
sichtbar ist. Dazu wird seine Position innerhalb der Shadow-Map ermittelt. Mit Hilfe der X/Y
Koordinaten kann der in der Shadow-Map gespeicherte Tiefenwert ausgelesen werden (==> A).
Anschließend wird der Abstand des sichtbaren Pixels zum Licht berechnet (==> B).

__


Der Vergleich von A und B führt zu zwei möglichen Ergebnissen:

1. A < B
Der in der Shadow-Map gespeicherte Tiefenwert ist kleiner als der Abstand des von der Kamera
aus sichtbaren Pixels. Somit befindet sich ein Objekt zwischen dem Licht und dem Pixel: Der
Pixel muss im Schatten liegen (Abbildung 23).
2. A = B
Beide Abstände stimmen in etwa überein: Der vom Licht aus sichtbare Pixel wird auch vom
Licht aus gesehen und muss somit beleuchtet werden (Abbildung 24).

Schwierig ist es allerdings, zu einem für die Kamera sichtbaren Pixel die X/Y-Koordinaten aus der
Sicht des Lichtes herauszufinden, um den Tiefenwert in der Shadow-Map nachzuschauen.
Grafikkarten ab der Nvidia GeForce-Generation unterstützen die sogenannte Texturprojektion, mit
der eine Textur einfach in den virtuellen Raum hineinprojiziert werden kann [Kil00]. Die dafür
notwendigen Texturkoordinaten werden automatisch innerhalb der Hardware erzeugt. Die
Texturprojektion lässt sich in etwa mit einem sehr flexiblen Videoprojektor vergleichen, mit dem
man das Bild beliebig in den Raum werfen kann.
So kann auch die Shadow-Map in die Szene hineinprojiziert werden. Zusätzlich können die durch
Texturprojektion erzeugten Texturkoordinaten benutzt werden, um den Tiefenwertvergleich
durchzuführen. Hinzukommt, dass dieser Vergleich von bestimmten Grafikkarten unterstützt wird.
Unter OpenGL gibt es dazu zwei Erweiterungen:

• SGIX_depth_texture
Wenn die Erweiterung SGIX_depth_texture unterstützt wird, so bietet die Grafikkarte die
Möglichkeit an, die Shadow-Map mit einer sehr hohen Genauigkeit zu erzeugen. Außerdem ist
der Kopiervorgang der Tiefenwerte in die Shadow-Map beschleunigt.

• SGIX_shadow
Mit der Erweiterung SGIX_shadow wird ein neuer Textur-Filtermodus „Shadow comparison“
hinzugefügt, mit dem der direkte Vergleich durchführt werden kann.

Leider ist die Hardware nicht besonders verbreitet, die diese beiden Erweiterungen anbietet.

3.2.3 Dual-Textur Shadow Mapping

Jedoch gibt es einen alternativen Ansatz, der von Heidrich 1999 entwickelt wurde. Er funktioniert
auf aller zur Zeit erhältlicher Grafikhardware, die nicht nur Texturprojektion, sondern auch
Multitexturierung unterstützt.
Multitexturierung bedeutet, dass pro gerendertem Dreieck mehr als eine Textur aufgebracht werden
kann. Zusätzlich kann man auch genau bestimmen, auf welche Weise die Texturen miteinander
kombiniert werden.
Der hier erläuterte Ansatz benutzt zwei Texturen:

1. Die Shadow-Map, die wie oben erläutert erzeugt wird

2. Die „Abstandstextur“ ist eine eindimensionale Textur, die einen linearen Verlauf von 0 bis 1
enthält. Sie dient dazu, den Abstand zwischen dem Licht und jedem sichtbaren Pixels
festzustellen.

Die Texturprojektion wird zuerst so eingerichtet, dass sie die Shadow-Map aus der Sicht des Lichtes
in die Szene hineinwirft (Abb. 25).

__
Abbildung 25: In die Szene projizierte Shadow-Map
Abbildung 26: In die Szene projizierte Abstandstextur


Die zweite Textur wird so projiziert, dass ihre Wert von 0 bis 1 entsprechend dem Abstand zum
Licht in die Szene geworfen werden (Die genauen Parameter können bei [Kil00] gefunden werden)
(Abb. 26). Wir haben jetzt zwei verschieden Texturwerte für jeden von der Kamera aus sichtbaren
Pixel: Tex0, der Wert aus der Shadow-Map und Tex1, der reale Abstand zum Licht. Beide Werte
werden in den Alphakanal der Textur geschrieben und haben einen Wert zwischen null und eins.

Wenn Tex0-Tex1 < 0, ist der Pixel schattiert. Leider gibt es diese subtraktive
Kombinationsmöglichkeit nicht und der Alphawert darf auch nicht negativ werden. Jedoch kann
man den Term entsprechend mathematisch umformen, so dass ein erlaubtes additives
Kombinationsverfahren benutzt wird:

Wenn Tex0 + (1 – Tex1) – 0.5 < 0.5, ist der Pixel schattiert.
Das genaue Verfahren wird von [Kil00] geschildert und wurde auch als Quellcode in C und
OpenGL veröffentlicht [Kil01].

Falls es trotz korrekten Algorithmuses zu fehl erhaften Schatten kommt, hilft es, Polygon Offset zu
aktivieren bzw. dessen Parameter zu verändern. Mit Hilfe von Polygon Offset wird zu den
Tiefenwerten eines Polygons ein bestimmter Offset-Wert hinzugefügt. Auch werden die
bestehenden Tiefenwerte „verbreitert“, d.h. die Sättigung der Werte kann erhöht oder vermindert
werden. So können Schattenartefakte umgangen werden. Die Artefakte entstehen zum Einen, indem
man die Objekte aus zwei verschiedenen Perspektiven (Lichtansicht und Kameraansicht) rendert,
wobei die gerasterten Ergebnisse nicht homogen sein müssen.
Auch ist es so, dass viele von der Kamera aus sichtbaren Pixel unter Umständen durch einen
einzigen Schattenpixel der Shadow-Map abgedeckt werden, während andererseits auch genau der
umgekehrte Fall möglich ist. Die Parameter für den Polygon Offset müssen aber für jeden Szene
individuell gewählt werden. Sind sie nicht optimal, kann es zu Artefakten kommen.
Der „Shadow Mapping“-Algorithmus besticht durch seinen logischen Ansatz und durch die
Tatsache, dass er nur pro Lichtquelle ausgeführt werden muss. Szenen mit komplexen Objekten
können deshalb viel schneller gerendert werden. Der Nachteil besteht darin, dass es viele Parameter
gibt, die man individuell anpassen muss. Auch sollte die Shadow-Map eine geeignete Größe haben,
so dass es nicht zur „hässlichen Blockbildung“ des Schattens kommt (Abb. 20 – 22).

4 Zusammenfassung & Ausblick

4.1 Zusammenfassung


Im Prinzip gilt für alle Algorithmen: Je besser das gewünschte Ergebnis sein soll, desto höher ist der
dafür notwendige Rechenaufwand. Dies gilt insbesondere für die beiden komplexen Algorithmen,
deren Qualität variabel bleibt.
Prerendered Shadows eignen sich auf alle Fälle immer dort, wo man es mit statischen Objekten und
Lichtern zu tun hat. Diese Situation ist sehr ähnlich zu den Light-Maps, da es genau genommen hier
modifizierte Light-Maps sind, die auch Schatten enthalten. Der Schatten, den statische Objekte
erzeugen, kann als Abdunklung in die Light-Map aufgenommen werden. Die Schatten entstehen
ohne Rechenzeitverlust und sind somit empfehlenswert, wenn immer die Vorraussetzungen
stimmen.
Planare Schatten sollten immer dann verwendet werden, wenn man auf einer ebenen Fläche
Schatten erzeugen möchte. Der Algorithmus erzeugt in solchen Situationen immer den richtigen
Schatten – vorausgesetzt man überprüft, dass es zu keiner Rückprojektion des Schattens kommt.
Hier ist besonders die Variante der Soft Planar Shadows interessant, da sie nicht allzu viel
zusätzliche Rechenzeit verlangt, weil lediglich das schattenwerfende Objekt mehrfach gerendert
wird. Allerdings gibt es hier keine Selbstschattierung, was im Vergleich zu den andern Algorithmen
schon ein deutlicher Nachteil sein kann.
Shadow Mapping überzeugt durch seinen relativ geringen Rechenaufwand, sofern man alle
Parameter richtig gewählt hat. Dass dies ein durchaus langwieriges Procedere sein kann, kann der
Autor aus eigener Erfahrung bestätigen. Ein Vorteil ist auf jeden Fall, dass die ShadowMaps vom
Licht abhängen, so dass die schattenwerfenden Objekte nur Renderleistung kosten – nicht aber
Rechenzeit wie dies bei den Stencil Volume Shadows der Fall ist.
Diese erzeugen zu jedem Objekt realistische Kernschatten, ohne dass es zur Bildung von Artefakten
kommt. Allerdings ist die Berechnung des Schattenvolumens sehr rechenaufwändig, was sich durch
Verwendung eines niedriger aufgelösten Modells umgehen lässt.
Die einzelnen Vor- und Nachteile sind noch einmal in folgender Tabelle hervorgehoben:
Dynamisch Schlagschatten Selbstschattierung Implementierung Speed


Anmerkung: Ich selbst benutze wann immer möglich planare Schatten. Als Alternative hat sich aus
meiner Ansicht der Stencil Volume Shadow Algorithmus bewährt. Weiter beschäftige ich mich zur
Zeit mit der Shader Programmierung unter DirectX, mit denen es eine Alternative gibt (siehe
Kapitel 4.2.3).
Bei der aktuellen Spieleentwicklung kann man erkennen, dass der Trend zur Benutzung von Stencil
Volume Shadows geht. Das Spiel Doom3 vom schon legendären Programmierer John Carmack
setzt voll auf Stencil Volume Shadows, da diese laut einer unveröffentlichten Email von John
Carmack weniger Probleme als Shadow Mapping bereiten [Car02].

4.2 Ausblick

4.2.1 Shadow Mapping

Grafikkarten, die kompatibel zu DirectX 8 sind (wie etwa der NVidia GeForce3 [NVI01] oder der
ATI Radeon 8500 Chip [ATI01]) , unterstützen den Shadow-Map Algorithmus. Sie bieten die
Möglichkeit, direkt in eine Textur statt in den Framebuffer zu rendern, wodurch die
Pixeltransferzeit eingespart werden kann. Dieses Feature ist auch für andere Grafikeffekte
interessant. Hinzu kommt, dass die erwähnten Chips auch ein erweitertes Texturformat bieten, so
dass die Genauigkeit des Tiefenwertespeichers erhöht ist. Dennoch findet der Algorithmus
möglicherweise aufgrund seiner schwierigen Anpassbarkeit nur wenig Akzeptanz [Car02].

4.2.2 Stencil Volume Shadows

DirectX 9.0 bietet die Möglichkeit des zweiseitigen Stencil Tests [MS03]. Dieser interessante
Ansatz setzt voraus, dass es zwei verschiedene Stencil Buffer für die Vorder- und Rückseite gibt.
Somit muss das Schattenvolumen nur einmal in den Stencilbuffer gerendert werden. Hierdurch
ergibt sich ein gewisser Zeitvorteil gegenüber dem geschilderten Algorithmus. Grafikchips, die den
DirectX 9 Standard unterstützen sind der NVidia GeForceFX und ATIs Radeon 9500/9700.
Besonders interessant ist diese Variante in Verbindung mit Shadern!

4.2.3 Shadow Volume Shader

Shader sind kleine Programme, die an die Grafikkarte gesendet werden und dort innerhalb der GPU
(Graphics Processing Unit) sehr schnell ablaufen. Es gibt zwei verschiedene Arten von Shadern:
Pixel- und Vertexshader. Erstere bestimmen die Einfärbung von Pixeln, letztere sind besonders für
die Erstellung von Schattenvolumen interessant, da sie auf die Vertexdaten zugreifen und diese
verändern können. So hat David Kirk im Jahre 2001 einen DirectX 8 Shader vorgestellt [Kir01], der
das Schattenvolumen erstellt. Somit entfällt die zeitaufwändige Erstellung des Schattenvolumens
innerhalb des Hauptprozessors. Nach Ansicht des Autors wird dies in der Zukunft die am häufigsten
verwendete Methode zur Erstellung von Schatten sein, sobald Grafikkarten, die Shader unterstützen
eine entsprechende Verbreitung gefunden haben. Solche Grafikkarten sind seit eineinhalb Jahren
erhältlich.
Es gibt jedoch auch einen völlig anderen Ansatz, 3D-Grafiken zu erzeugen, der nicht mit solchen
Problem zu kämpfen hat.

4.2.4 Photon Mapping

Photon Mapping ist eine Erweiterung für Raytracing-Renderer. Mit Photon Mapping können
verschiedene grafische Effekte, wie Caustics oder indirekte Beleuchtung, effizient erzielt werden.
Der Ansatz von Photon Mapping entspricht der tatsächlichen natürlichen Beleuchtung [Lee03]. Es
werden von einer Lichtquelle aus mehrere Photonen in zufällige Richtungen ausgesandt. Der Weg
dieser Photonen wird nachverfolgt. Kommt es zu einer Kollision mit einem Objekt, wird es an
dieser Stelle erhellt und das Photon mit entsprechend verminderter Energie reflektiert und weiter
verfolgt. Dies geschieht solange, bis das Photon keine Energie mehr hat. Das Ergebnis, also die
Beleuchtungspunkte, wird in einer „Photon-Map“ gespeichert. Diese wird in einem zweiten
Rendervorgang benutzt, um per Raytracing für die komplette Beleuchtung zu sorgen.
Die Ergebnisse eines mit Photon Mapping berechneten Bildes sind äußerst realistisch , wie dies die
Abbildung 27 verdeutlicht.



Ein Vorteil ist die hervorragende Qualität des Ergebnisses, die durch kein anderes bisher bekanntes
Verfahren erreicht wird. Dies liegt daran, dass der Algorithmus die natürliche Beleuchtung
immitiert und es so möglich geworden ist, auch indirekte Beleuchtungen zu erzeugen. Da die Szene
durch die Photonen beleuchtet wird, sind auch alle Schatten realistisch: Auf die entsprechenden
Stellen fallen keine Photonen. Nachteilig ist, dass der Algorithmus sehr zeitaufwändig ist, da man
selbst für einfache Szenen ca. 20.000 Photonen benötigt. Die Berechnung der Photonen erfolgt
ausschließlich im Hauptprozessor und wird bisher nicht direkt durch Hardware unterstützt.
Echtzeitrendering ist mit diesem Algorithmus daher leider nicht möglich.

Literaturverzeichnis

[AMH02] Akenine-Möller, Tomas/ Haines, Eric; „Real-time Rendering“, A. K. Peters, 2002
Beide Autoren nennen mehrere Schattenalgorithmen, die sie sehr ausführlich
vorstellen. Dabei gehen sie auch auf deren Vor- und Nachteile ein.
[ATI01] ATI Corp.(2001). Radeon Whitepaper (PDF-Datei, Stand 2001)
http://www.ati.com/technology/hardware/radeon/whitepaperradeon.pdf. (Zugriff
16.03.2003, 14:00 MEZ)
Das vom Hersteller ATI veröffentlichte Whitepaper beschreibt die Techniken, die der
Radeon Chipsatz unterstützt. Darin wird auch die „p-Buffer Rendering“
Unterstützung genannt, also die Möglichkeit nicht in den Framebuffer sondern in eine
Textur zu rendern.
[Bro83] Der große Brockhaus, Band 19, S. 149, F. A. Brockhaus, 1983
„Der große Brockhaus“ ist eine sehr bekannte Enzyklopädie in 24 Bänden, die sich
mit dem Begriff „Schatten“ sehr allgemein auseinandersetzt.
[Car02] Carmack, John (2002). unveröffentlichte E-Mail: „Warum Stencil Volume Shadows
statt Shadow-Maps in Doom 3 benutzt werden“ (WWW-Seite, Stand 13.08.2002)
http://doom3hq.net/. (Zugriff 16.03.2003, 14:01 MEZ)
John Carmack äußert sich über den „Shadow Mapping“-Algorithmus auf Nachfrage
per Email. Er sagt, dass man sehr große Shadow-Maps für eine akzeptable Qualität
braucht. Ausserdem haben sie mehr Nach- als Vorteile.
[EKN02] Everitt, Cass/ Kilgard, Mark (2002). „Practical and Robust Stencil Volume Shadows
for Hardware Accelerated Rendering“(PDF-Datei, Stand 12.03.2002)
http://developer.nvidia.com/docs/IO/2585/ATT/RealShadowsRealTime.pdf. (Zugriff
16.03.2003, 14:03 MEZ)
Die beiden Mitarbeiter von NVidia schildern zunächst die Geschichte des
Schattenvolumen-Algorithmus. Anschließend gehen sie detailiert auf die
Implementierung ein.
[Kil99] Kilgard, Mark (1999). „Creating Reflections and Shadows using Stencil Buffers“
(WWW-Seite, Stand 19.03.1999)
http://www.opengl.org/developers/code/features/StencilTalk/index.htm. (Zugriff
16.03.2003, 14:05 MEZ)
Der Autor beschreibt in dieser Präsentation viele Effekte, die der Stencilbuffer
ermöglicht, wie z.B Reflektionen, Schatten, Glühen, .... Zusätzlich zu den Techniken
nennt er auch Quellcodeauszüge für OpenGL und DirectX 6.
[Kil00] Kilgard, Mark (2000). „Shadow Mapping with Today's OpenGL Hardware“ (PDFDatei,
Stand 2003),
http://developer.nvidia.com/docs/IO/1379/ATT/GDC2K_ogl_Shadow-Map.pdf.
(Zugriff 16.03.2003, 14:10 MEZ)
Mark Kilgard erklärt alle Aspekte des „Shadow Mapping“-Algorithmus. Dabei geht
er auf die Implementierung in OpenGL ein und nennt auch Möglichkeiten für die
Hardwareunterstützung des Algorithmus.
[Kil01] Kilgard, Mark (2001). „OpenGL Shadow Mapping“ (ZIP-Datei, Stand 30.11.2001),
http://developer.nvidia.com/docs/IO/1254/ATT/shadowcast.zip. (Zugriff 16.03.2003,
14:17 MEZ)
Der gut dokumentierte Quellcode zum Demoprogramm ist äußerst interessant, da das
Programm auch die Hardwareoptimierungen, die z.B. eine GeForce 3 basierte
Grafikkarte bietet, unterstützt. Kilgard benutzt den „Dual-Texture Shadow Map“-
Algorithmus von Heidrich.
[Kir01] Kirk, David (2001). „Vertex Shader Shadow Volume“, (Zip-Datei, Stand
10.08.2001), http://developer.nvidia.com/docs/IO/1153/ATT/ShadowVolume.zip.
(Zugriff 16.03.2003, 14:15 MEZ)
David Kirk hat den Shadow Volume Shader auf der „Microsoft's Meltdown 2001“
Veranstaltung veröffentlicht. Zwar funktioniert der Shader noch nicht für animierte
Modelle, dafür ist der Quellcode gut dokumentiert.
[Lee03] Lee, Eugene (2003). „Tachyonic: Photon Mapping“, (WWW-Seite, Stand
04.03.2003), http://och.phpwebhosting.com/tachyonic.htm. (Zugriff 16.03.2003
15:02 MEZ)
Eugene Lee beschreibt auf seiner Homepage den „Photon Mapping“-Algorithmus,
den er auch implementiert hat, sehr ausführlich anhand vieler Bilder.
[MS02] Microsoft Corp. (2003), „Two-Sided Stencil“, (WWW-Seite, Stand 2003)
http://msdn.microsoft.com/library/enus/
directx9_c/directx/graphics/programmingguide/advancedtopics/TwoSidedStencil.a
sp. (Zugriff 16.03.2003, 15:30 MEZ)
In der technischen Dokumentation zu DirectX 9 schildert Microsoft, wie das
sogenannte „Two-Sided Stenciling“ den „Stencil Volume Shadow“-Algorithmus
beschleunigen kann.
[NVI01] NVidia Corp. (2001). „Shadow Buffer, Technical Brief“ (PDF-Datei, Stand 2003)
http://www.nvidia.com/docs/lo/1047/SUPP/Shadow_Buffer_100101.pdf. (Zugriff am
16.03.2003, 14:40 MEZ)
Der Grafikchiphersteller NVidida beschreibt in dem Dokument die Shadow Mapping
Technologie. Das Dokument nennt insbesondere die Vorzüge des GeForce3Ti, der
Shadow Mapping auf mehreren Ebenen unterstützt.
[Smy02] Smyk, Miloslaw (2002). „JaTrac -- open image synthesis framework: examples“,
(WWW-Seite, Stand 19.07.2002)
http://wfmh.org.pl/~thorgal/jatrac/examples.html. (Zugriff am 16.03.2003, 14:48
MEZ)
Auf der Homepage des Objekt-Orientierten OpenSource Renderers „JaTrac“ findet
man zur Zeit nur einige Bilderbeispiele. Diese überzeugen allerdings sehr in ihrer
Qualität.
[Son98] Sega Enterprise Ltd., Sonic Adventure, 1998
Sonic Adventure ist ein Spiel für die Sega Dreamcast. Es bestach zu seiner Zeit durch
die Schnelligkeit und die Qualität der Grafik.
[WNDS99] Woo, Mason (hrsg.)/ Neider, Jackie/ Davis, Tom/ Shreiner, Dave; „OpenGL
Programming Guide“, Third Edition, Reading: Addison Wesley, 1999
Das Buch „OpenGL Programming Guide“ gilt als das Standartwerk für das Thema
OpenGL. In der dritten Auflage wird OpenGL 1.2 sehr ausführlich und detailiert
beschrieben.
Abbildungen 1, 2, 6 sind Skizzen vom Verfasser.
Abbildungen 3, 4, 7-22, 25, 26 sind Screenshots von Programmen des Autors. Die Programme
werden inklusive Quellcode Ende März 2003 unter http://opengl.grasmo.de auf der Homepage des
Autors veröffentlicht.