# Shadow Mapping

Shadow Mapping ist eine Methode der Computergrafik, um Schattenwurf darzustellen. Das Konzept wurde 1978 im Paper "casting curved shadows on curved surfaces" von Lance Williams vorgestellt. Shadow Maps werden sowohl für Offlinerendering als auch für Echtzeitanwendungen benutzt.
Beim Shadow Mapping werden Schatten generiert, indem getestet wird, ob ein Pixel von einer Lichtquelle aus sichtbar ist. Dabei wird zunächst die sogenannte Shadow Map erzeugt. Diese ist eine aus Sicht der Lichtquelle erzeugte Tiefenkarte. Diese enthält Informationen über den geringsten Abstand von Objekten einer Szene zur Lichtquelle (Z-Buffer). Durch den Vergleich des Abstandes des zu rendernden Objektes zur Lichtquelle und dem entsprechenden Punkt in der Shadow Map kann der Schattenwurf berechnet werden.

## Funktionsprinzip

Das Rendern einer Szene mit Schatten unter Zuhilfenahme von einer Shadow Map geschieht im Wesentlichen in zwei Schritten. Als erstes wird die Szene aus der Sicht des Lichts gerendert und für jedes sichtbare Objekt die Tiefeninformation gespeichert. Anschließend wird die Szene normal gerendert, wobei für jedes Pixel mit Hilfe der Shadow Map bestimmt wird, ob es für das Licht sichtbar ist. Falls dies nicht der Fall ist, wird das Pixel schattiert gerendert.
Diese Technik bietet weniger genaue Resultate als Schattenvolumen, ist aber im Allgemeinen schneller in der Berechnung. Zudem können Shadow Maps ohne Zuhilfenahme des Stencilbuffers realisiert werden und erlauben das Zeichnen von weichen Kanten.

## Algorithmus
### Zeichnen der Shadow Map

Als erstes wird die Tiefenkarte für jedes Licht erstellt. Für Punktlichtquellen sollte dazu eine perspektivische Projektion verwendet werden, während für gerichtete Lichtquellen mit parallelen Strahlen (wie zum Beispiel bei der Sonne) eine orthogonale Projektion geeignet ist. Dazu wird die Szene von der Position des Lichts aus gerendert und die Tiefeninformation gespeichert. Häufig wird die Tiefenkarte als Textur im Speicher der Grafikkarte gespeichert. Damit dieser Rendervorgang möglichst effizient abläuft, kann sowohl die Licht- als auch die Farbberechnung weggelassen bzw. abgeschaltet werden.
Jedes Mal, wenn sich die Position eines Lichts oder eines Objekts in der Szene ändert, müssen die Tiefenkarten neu berechnet werden.

### Schattieren der Szene

Als zweiter Schritt wird die Szene aus der Sicht der Kamera gerendert und die Shadow Map auf die einzelnen Pixel angewendet. Dieser Schritt besteht im Wesentlichen aus drei Operationen. Der Erste ist, die relativen Koordinaten eines Objekts im Vergleich zur Kamera auf die entsprechenden relativen Koordinaten vom Licht aus gesehen zu transformieren. Als Zweites werden die Koordinaten mit der Tiefenkarte verglichen und als Letztes wird das Objekt als beleuchtet oder schattiert gezeichnet.

## Uniform Shadow Mapping

Beim Zeichnen der eigentlichen Szene kann für jedes Pixel die Entfernung zur Lichtquelle mit der Entfernung verglichen werden, die für diese Stelle in der Tiefentextur steht. Falls die Entfernung des Pixels größer ist als die in der Textur gespeicherte Entfernung, liegt der Pixel im Schatten.
Bei globalen Lichtquellen wie der Sonne ist das Gebiet, über das sich die Tiefentextur erstreckt, sehr groß. Die räumliche Auflösung des Schattens ist demzufolge sehr gering. Die gleichförmige Verteilung des Texturraums über das betroffene Gebiet führt außerdem dazu, dass die vom Betrachter wahrgenommene Schattenauflösung in der Nähe sehr niedrig ist, während in der Entfernung eine unnötig hohe Auflösung erreicht wird.

## Perspective Shadow Mapping (PSM)

Perspective Shadow Mapping erweitert die Projektionsmatrix des Lichtes um eine perspektivische Komponente der Betrachterprojektion. Damit wird der vorher quadratische Ausdehnungsbereich der Schattentextur auf ein Trapez verformt, das seine schmale Seite beim Betrachter hat und damit dort sehr viel mehr Texel pro Maßeinheit bietet als in der Ferne. Die Methode arbeitet gut für Szenarien, in denen die Blickrichtung des Betrachters größtenteils senkrecht zur Lichtrichtung ist. Das Verfahren hat aber einige numerische Totstellen, in denen die Projektionsmatrix ungültige Werte annimmt oder den Schatten invertiert.

## Light Space Perspective Shadow Mapping (LiSPM)

Light Space Perspective Shadow Mapping (benutzt zum Beispiel in SpellForce 2) ist eine Erweiterung der PSM-Methode, die durch geänderte Formeln den Grad der perspektivischen Verzerrung der Lichtprojektion frei wählbar gestaltet. Bei einem senkrechten Blickwinkel zur Lichtrichtung entspricht diese Methode der PSM-Methode. Je paralleler Sichtrichtung und Lichtrichtung werden, desto geringer wird die perspektivische Verzerrung, bis die Methode bei Parallelität auf normales Uniform Shadow Mapping zurückfällt. Diese Methode verhindert die Totstellen von PSM, wobei das optische Ergebnis aber immer noch stark von der Blickrichtung abhängt.

## Cascaded Shadow Mapping (CSM)

Cascaded Shadow Mapping (benutzt zum Beispiel in 3DMark2005 und 3DMark2006) verhindert die ungleiche Verteilung der Schattentexel-Dichte durch Einsatz mehrerer geschachtelter Shadow Maps für verschiedene Entfernungen. Jede einzelne Shadow Map wird gleichförmig projiziert oder kann mit einer der obigen Varianten perspektivisch projiziert werden. Die Methode ist leicht zu implementieren und liefert flexibel einstellbare Schattenqualität für alle Entfernungen, benötigt aber ein Vielfaches der Rechenzeit und des Grafikkarten-Speichers anderer Methoden.

## Dual Paraboloid Shadow Mapping (DPSM)

Die traditionelle Technik des Shadow Mapping verwendet nur eine Tiefenkarte. Möchte man aber ein in mehrere Richtungen scheinendes Licht, z. B. ein Punktlicht realisieren, reicht die traditionelle Methode nicht mehr aus. So kam man im Laufe der Zeit auf Dual Paraboloid Shadow Mapping, eine Technik, bei der man den Raum um die Lichtquelle auf zwei Paraboloide, projiziert, die zwei Tiefenkarten entsprechen. Diese Methode ist annähernd so performant wie das traditionelle Shadow Mapping, hat aber auch Nachteile, die hauptsächlich mit der Verzerrung durch die Projektion auf das gewölbte Paraboloid zusammenhängen. Durch geeignete Gegenmaßnahmen lassen sich diese aber auf ein Minimum reduzieren.
Dual Paraboloid Mapping wurde zum ersten Mal 1998 in der Publikation "View-independent environment maps" von Wolfgang Heidrich und Hans-Peter Seidel beschrieben.

## Weitere Methoden

Es gibt weitere Möglichkeiten, Shadow Maps verbessert darzustellen, allerdings eignen sie sich nicht zur Berechnung in Echtzeit. Sie arbeiten durch Segmentierung der Szene und Zuordnung verschieden großer Schattentextur-Fragmente zu diesen Segmenten nach verschiedenen Qualitätskriterien. Es gibt auch Echtzeit-Varianten, aber die Aufteilung der Szene in Echtzeit ist problematisch und führt zu sichtbaren Sprüngen in der Schattenqualität im Bild.