Shadow Volumes und Shadow Mapping mit OpenGL/GLSL

Bachelorarbeit von Andy Reimann

Einleitung:

Um die Realität in der Computergrafik so gut wie möglich nach zustellen, sind realistisch anmutende Schatten unerlässlich. Je realistischer die Szenen werden, desto weniger Fehldarstellungen kann man sich erlauben. Schatten geben dem Betrachter in einer virtuellen Umgebung eine genauere Vorstellung von der Objekt Objekt Beziehung und unterstützen den räumlichen Eindruck. Im Rahmen dieser Bachelorarbeit werden die zwei bekanntesten Herangehensweisen Shadow Mapping und Shadow Volumes diskutiert und implementiert. Die Vor und Nachteile dieser werden intensiv erläutert. Des weiteren werden Möglichkeiten aufgezeigt, welche die genannten Techniken visuell verbessern und beschleunigen können. Von der Vielzahl an Erweiterungen von Shadow Mapping werden die Techniken Perspective Shadow Mapping, Light Space Perspective Shadow Mapping, Cascaded Shadow Mapping und Dual Paraboloid Shadow Mapping genauer erläutert. Zu den Shadow Volumes werden die beiden Verfahren Z Pass und Z Fail genau erklärt und implementiert. Des weiteren wird der Algorithmus anhand eines Minimalbeispiels erläutert und auf Probleme eingegangen.

Inhaltsverzeichnis:

Textprobe:

Kapitel 3.2.1, Zeitgeschichtliche Entwicklung:

Das erste Konzept für Shadow Volumes wurde im Jahre 1977 von Frank Crow vorgestellt. Nur ein Jahr später folgte das erste Konzept für Shadow Mapping von Lance Williams. Schon damals hat zum einen Lance Williams auf die Problematik des perspektivischen Aliasing und zum anderen Frank Crow auf die hohe Komplexität des Shadow Volume Algorithmus und die zusätzlich zu speichernden Daten hingewiesen. Crow sagte, dass alle Herangehensweisen, die das Polygonmodell der Objekte als Grundlage nehmen auch immer additionale Daten für die ebenfalls polygonalen Shadow Volumes in Anspruch nehmen. Im Jahre 1987 folgte vom William T. Reeves, David H. Salesin und Robert L. Cook ein Konzept zur Erstellung von Softshadows um dem Aliasing-Effekt von Tiefentexturen entgegenzuwirken (Percentage Closer Filtering). Bis heute wird diese Verbesserungsmöglichkeit in fast allen Shadow Mapping Verfahren verwendet, da es Fehldarstellungen, die auf Aliasing zurückzuführen sind sehr gut minimieren kann. 1991 folgte die erste Implementierung von Shadow Volumes durch Tim Heidmann. Er zeigte, wie man den Stencilbuffer dazu verwenden kann, die Schattenvolumen effizient zu rendern. 2002 reichten William Bilodeau und Michael Songy ein Patent ein, welches eine robuste Technik beschreibt, Schattenvolumen zu rendern. Diese wurde bereits 1998 von den Patentträgern entwickelt. In den folgenden Jahren bis heute wurden insbesondere für den Shadow Mapping Algorithmus viele Erweiterungen entwickelt.

Bereits sehr früh im Jahre 1998 wurde vom Wolfgang Heidrich und Hans-Peter Seidel eine Technik vorgeschlagen, mit der es möglich ist die komplette Umgebung einer Punktlichtquelle in nur zwei Texturen aufzunehmen. Sie verwendet 2 Paraboloide mit geeigneter Transformation um alle umliegenden Punkte in den paraboloiden Raum zu transformieren. In dem Artikel wurde die Technik zwar nicht im Hinblick auf Shadow Mapping beschrieben, sie lässt sich jedoch fast unverändert übernehmen.

Im Jahre 2000 entwickelten Tom Lokovic und Eric Veach eine Technik namens Deep Shadow Maps (DSM). Dabei wird nicht ein Tiefenwert pro Pixel gespeichert, sondern eine teilweise Sichtbarkeit für mehrere Tiefen, was zur Unterstützung von teilweise transparenten Objekten führt. Als im Jahre 2001 mit Adaptive Shadow Maps (ASM) eine neue Technik entwickelt wurde, existierte eine weitere Möglichkeit Aliasing-Effekten entgegenzuwirken. ASM versucht Pixelgrößenunterschiede zwischen Pixeln im Kamerakoordinatensystem und im Koordinatensystem des Lichtes zu erkennen. Dies wird erreicht, indem die Sicht der Lichtquelle nicht wie bisher in einer Textur gespeichert wird, sondern als hierarchische Grid-Struktur unter Verwendung eines Quad-Trees. Somit kann Auflösung dort allokiert werden wo sie auch benötigt wird.

Im selben Jahr folgte dann von Tae-Yong Kim und Ulrich Neumann die Opacity Shadow Maps (OSM). Anstatt Tiefenwerte zu speichern, werden bei OSM Alphawerte gespeichert. Um diese Alphawerte zu gewinnen werden mehrere Slices durch die Objekte gelegt und für jeden Slice ein Wert in die Opacity Shadow Map gespeichert. Bei dieser Technik werden ebenfalls teilweise transparente Objekte wie Wolken oder Nebel unterstützt. 2002 folgte eine weitere Shadow Mapping Technik, die das Problem des Aliasing-Effektes versucht zu minimieren. Unter dem Namen Perspective Shadow Maps (PSM), vorgestellt von Marc Stamminger und George Drettakis, ist die Technik bekannt. Entgegen der traditionellen Herangehensweise der Erstellung der Tiefentextur im Weltkoordinatensystem, versucht die PSM Technik die Aliasing-Effekte zu minimieren, indem sie die Tiefentextur in Normalisierten Gerätekoordinaten, also nach der perspektivischen Transformation speichert. Dies führt jedoch dazu, dass die Qualität der Schatten sehr von der Lichtposition im Kamerakoordinatensystem abhängt.

2003 folgte eine komplett neue Art Schatten zu erzeugen. Pradeep Sen, Mike Cammarano und Pat Hanrahan versuchten mit der Technik Shadow Silhouette Maps die Vorteile von Shadow Mapping und Shadow Volumes zu kombinieren, indem sie eine neue Silhouette Map einführten, die die Kanten der Geometrien pro Pixel speichern. Zusammen mit einer Shadow Map lassen sich nun gerade die Ergebnisse an den Kanten deutlich verbessern. Die Technik Trapezoidal Shadow Maps (TSM) folgte im Jahre 2004 von Tobias Martin und Tiow Seng Tan. Sie versucht das Problem der zu geringen Auflösung der Tiefentextur zu minimieren, indem das Kamerafrustum aus Sicht der Lichtquelle mit einem Trapez approximiert wird, um es anschließend in eine Shadow Map zu überführen. Das Ziel hierbei ist, dass die Shadow Map zu jedem Zeitpunkt sehr gut ausgenutzt wird. Des weiteren werden durch diese Anpassung die Artefakte, die entstehen wenn sich die Kamera bewegt minimiert. Ebenfalls im Jahre 2004 folgte die Technik Light Space Perspective Shadow Maps (LSPSM) von Michael Wimmer, Daniel Scherzer und Werner Purgathofer. Sie verwendet eine spezielle perspektivische Transformation, die es erlaubt alle Lichter als Directional Lights zu betrachten. Dies führt dazu, dass alle Vorteile von PSM bestehen bleiben ohne dessen Problemen weiter zu unterliegen. Probleme von PSM sind zum Beispiel verschwundene Objekte, die keinen Schatten mehr werfen, da sie außerhalb des sichtbaren Kamerafrustums liegen, z.B. hinter der Kamera.

Mit Subdivided Shadow Maps (SSM) wird seit 2005 eine Technik, entwickelt und vorgestellt von On Lloyd, Sung-eui Yoon, David Tuft und Dinesh Manocha, beschrieben, die aus Sicht der Lichtquelle die Szene an den sichtbaren Flächen des Kamerfrustums unterteilt. Wenn man sich das Kamerafrustum als Geometrisches Objekt vorstellt, so kann man für jede Seitenfläche entscheiden, ob diese in Richtung des Lichtes zeigt oder nicht, was hier als Grundlage für die Unterteilungen verwendet wird. Diese Unterteilungen können bedingt von dem Algorithmus weiter unterteilt werden, wenn eine ungünstige Konstellation von Position des Lichtes und Kamerafrustum vorliegt.

Jede Unterteilung wird nun durch eine separate Shadow Map repräsentiert, was zu einer deutlich kleineren Fehler führt. Dieser Algorithmus kann als Vorreiter des in dieser Bachelorarbeit genau untersuchten und erst 2 Jahre später entwickelten Algorithmus Cascaded Shadow Maps verstanden werden, da er auch als Grundlage eine Unterteilung der Szene vornimmt und jede Unterteilung in eine separate Shadow Map aufnimmt um die Auflösung zu vergrößern. Lediglich die Art der Unterteilung unterscheidet sich bei den beiden Algorithmen.

2006 wurde ein weiterer Algorithmus unter dem Namen Variance Shadow Maps (VSM) von William Donnelly und Andrew Lauritzen vorgestellt. Entgegen dem nativen Algorithmus, der pro Pixel nur einen Tiefenwert speichert, speichert der VSM Algorithmus pro Pixel die mittlere Verteilung von Tiefenwerten sowie die quadrierte mittlere Verteilung. Dadurch können verschiedene hardwarebeschleunigte Filter wie beispielsweise trilineare Filterung auf die Shadow Map angewendet werden, was bei normalen Shadow Maps nicht funktioniert. Ebenfalls in diesem Jahr wurde von Markus Giegl und Michael Wimmer eine weitere Technik unter dem Namen Queried Virtual Shadow Maps bekannt, bei der die Auflösung einer einzigen Shadow Map durch Mehrfachverwendung virtuell vervielfacht wird. Eine Shadow Map wird in einem Multipass-Rendering System mehrfach komplett überschrieben und sofort direkt auf kleine Teile der Szene angewendet. In Verbindung mit Techniken wie Deferred Shadowing kann zudem der deutliche Mehraufwand durch ein Multipass Rendering eliminiert werden, indem die Szene in einem Deferred Renderpass mit all ihren Informationen über Beleuchtung, Normalen und Shading komplett zwischengespeichert wird und anschließend ohne weitere Geometrien rendern zu müssen jederzeit rekonstruiert werden kann.

Mit Cascaded Shadow Maps wurde 2007 ein komplett neuer Ansatz zur Verbesserung der Qualität von Rouslan Dimitrov vorgestellt. Erstmals gelingt es deutlich größere Szenen mit Schatten zu bereichern, wenn auch nur durch die Erhöhung der Anzahl der Renderpässe. Ziel ist es, mehrere Auflösungen und Bereiche einer Szene in mehreren gleich großen Texturen zu halten und für jedes Pixel zu entscheiden, welche dieser Texturen die besten Resultate liefert. Dies geschieht durch Aufsplittung des Kamerafrustums in mehrere Subfrustums. Jedes Subfrustum wird nun durch eine eigenständige Shadow Map repräsentiert.

2002 wurde des weiteren von Brandon Lloyd, Naga Govindaraju, Cory Quammen, Steve Molnar und Dinesh Manocha eine Technik namens Logarithmic Perspective Shadow Maps (LogPSM), die aus einer perspektivischen Projektion und einer logarithmischen Transformation besteht. Sie kann für jede Lichtart verwendet werden und produziert deutlich weniger Aliasing-Fehler als PSM. Sie erzielt zudem auch bessere Resultate als CSM, da diese Technik prinzipiell mit mehreren Shadow Maps eine diskrete Annäherung an die mit LogPSM erreichte Rasterisierung der Shadow Map produziert.