docVariance Shadow Maps
download 
Denúncia Transcrição
Variance Shadow Maps
Variance Shadow Maps Oliver Knörzer∗ Fakultät für Informatik, Universität Ulm 21. November 2006 2006] vorgestellt werden. Zum besseren Verständnis soll davor der grundsätzliche Algorithmus für Shadow Maps vorgestellt werden, sowie auf einige andere auf diesem aufbauende Ansätze eingegangen werden, um die Vorteile der Variance Shadow Maps gegenüber diesen beurteilen zu können. 2 Abbildung 1: VARIANCE S HADOW M APS : Der erste Screenshot zeigt die Szene bei Anwendung des grundlegenden Shadow-MapVerfahrens, der zweite bei Anwendung von Percentage Closer Filtering in Verbindung mit bilinearem Filtering und der dritte bei Anwendung von Variance Shadow Maps in Verbindung mit Mipmapping und 16-fachem anisotropen Filtering CR Categories: K.7.m [Computer Graphics]: Three-Dimensional Graphics and Realism—Color, shading, shadowing, and texture Schatten in der Computergraphik Ein Körper wirft einen Schatten, wenn er von mindestens einer Lichtquelle angestrahlt wird. Alles, was aus Sicht der Lichtquelle hinter einem Körper liegt, wird von den ausgestrahlten Lichtstrahlen nicht getroffen und liegt damit im Schatten des Körpers. An den Rändern entsteht dabei je nach Art der Lichtquelle und evtl. anderer vorhandener Lichtquellen ein Bereich, der zumindest teilweise von den Lichtstrahlen getroffen wird, die sogenannte Penumbrae. Als wie stark der geworfene Schatten wahrgenommen wird, ist von verschiedenen Parametern abhängig: Sowohl von der Helligkeit der Lichtquelle und der Anzahl und Helligkeit anderer vorhandener Lichtquellen (sowie der Grundhelligkeit der Szene), als auch von der Transparenz des beleuchteten Körpers. Die Darstellung des Schattens, den ein teilweise transparenter Körper wie eine Plastikflasche oder ein volumetrischer Körper wie eine Wolke wirft, stellt ein großes Problem der Computergraphik dar, das vom grundlegenden Shadow-Map-Algorithmus nicht gelöst wird, weshalb später z. B. der Deep-Shadow-Map-Algorithmus entwickelt wurde. Keywords: variance shadow maps, shadow maps 1 Einleitung Shadow Maps [Williams 1978] sind die heute am weitesten verbreitete Methode um in Computerspielen einen möglichst realistisch aussehenden Schattenwurf von dreidimensionalen Objekten in Echtzeit zu simulieren. Varianten, die auf Kosten eines höheren Zeit- und Speicherplatzaufwands eine bessere Bildqualität liefern, kommen jedoch auch bei der Erstellung von Animationsfilmen zum Einsatz, z. B. die Deep Shadow Maps [Lokovic and Veach 2000] in Pixars “RenderMan” [Pix 2006]. In dieser Seminararbeit für das Seminar “Computergraphik” im Wintersemester 2006/2007 an der Universität Ulm soll das von William Donnelly und Andrew Lauritzen neu entwickelte Verfahren für Variance Shadow Maps [Donnelly and Lauritzen 2006] [Lauritzen ∗ e-mail: [email protected] Abbildung 2: S CREENSHOT AUS “S LY R ACCOON ”: Kein realistischer Schattenwurf, die Taschenlampe des Wächters leuchtet durch die Säule rechts hindurch Schatten sind vielfältige Informationsträger, die nicht nur für das realistischere und damit schönere Aussehen der Szene sorgen, sondern dem Betrachter auch genauere Anhaltspunkte über das Aussehen des Objekts und die räumliche Anordnung der Objekte zueinander geben. In Actionspielen können Schatten dem Spieler sogar wertvolle Informationen über die Lichtquelle und das beleuchtete Objekt liefern, z. B. könnte der Spieler so ein Monster frühzeitig entdecken, das hinter einer Ecke steht, dessen Schatten aber frühzeitig auf dem Boden zu sehen ist. In Spielen wie “Thief” und “Splinter Cell” ist es dagegen sogar ein wesentlicher Spielinhalt, sich mit der eigenen Spielfigur im Schatten zu verstecken. Gerade Spiele mit derartigen Schleicheinlagen profitieren besonders von verbesserten Schattenalgorithmen, da der Schattenwurf von Objekten hier nicht nur einer schöneren Optik dient, sondern Teil der Spielmechanik ist. Obwohl viele neue Spiele für den PC oder die neue Generation von Videokonsolen Shadow Maps oder ähnliche Techniken zur Generierung von Schatten unterstützen, finden sich gerade auf der PlayStation 2 aufgrund deren begrenzter Rechenkapazität immer noch Spiele, bei denen dies nicht der Fall ist, wie am abgebildeten Screenshot aus “Sly Raccoon” zu sehen ist (gilt auch für die beiden Nachfolger “Sly 2: Band of Thieves” und “Sly 3: Honor Among Thieves”). 3 Shadow Maps Die Grundidee der Shadow Maps wurde erstmals 1978 von Lance Williams in seinem Artikel “Casting Curved Shadows on Curved Surfaces” vorgestellt. Der Algorithmus basiert auf dem Einsatz eines zusätzlichen Z-Buffers pro Lichtquelle, was nach sich zieht, dass die Zeit- und Speicherkomplexität des Algorithmus linear in der Anzahl der Lichtquellen bzw. der Anzahl an Polygonen in der zu beleuchtenden Szene ansteigt. Je nach gewählter Auflösung der Shadow Map kann mit einem Aufwand pro zusätzlicher Lichtquelle gerechnet werden, der ungefähr dem Aufwand des Hidden Surface Removals durch den Z-Buffer-Test am Ende des Rendering-Vorgangs entspricht. Dazu kommt ein gewisser Zusatzaufwand für die notwendigen Transformationsvorgänge der Bildkoordinaten. Grundsätzlich kann der Shadow-Map-Algorithmus also ohne weitere Zusatzinformationen über die geometrische Anordnung der Objekte für beliebig aufgebaute Szenen eingesetzt werden. Shadow Map an der Stelle der transformierten x p - und y p Koordinaten gespeicherten zs -Wert verglichen. Ist der z p -Wert des Punktes größer, so muss ein anderes Objekt zwischen ihm und der Lichtquelle liegen und er liegt somit in dessen Schatten. Aufgrund der mangelnden Genauigkeit von Gleitkommazahlen, wobei durch die notwendigen Transformationsschritte weitere Rundungsfehler auftreten können, ist jedoch kein Vergleich auf exakte Gleichheit möglich. Das bedeutet, dass der Punkt beleuchtet wird, wenn z p ≈ zs oder z p < zs gilt, wobei letzteres Vergleichsergebnis ebenfalls nur aufgrund von Rechenungenauigkeiten auftreten kann, da sich der betrachtete Punkt ansonsten näher an der Lichtquelle befinden müsste als der der Lichtquelle am nächsten liegende Punkt, was einen offensichtlichen Widerspruch darstellt. In Verbindung mit dem niemals unendlich genauen Sampling kann dies zu Self-Shadowing führen, bei dem ein Punkt auf der beleuchteten Oberfläche eines Objekts einen Schatten auf einen direkt benachbarten Punkt wirft. Um dieses Problem zu umgehen wurden zwei verschiedene Ansätze gefunden: Abbildung 3: S ELF -S HADOWING : Ein durch unterschiedliche Abtastpunkte ausgelöstes Self-Shadowing kann durch einen genügend großen Offset bei der Konstruktion der Shadow Map verhindert werden Der Algorithmus arbeitet so, dass für jeden auf dem Bildschirm sichtbaren Pixel, gegeben durch die Projektion der Szene auf die Eye View Image Plane, also den Frame Buffer, für die gegebene Lichtquelle überprüft wird, ob der durch diesen Pixel repräsentierte Punkt im Raum auch von der Lichtquelle aus gesehen sichtbar ist. Genau genommen müsste aber nicht ein einzelner Punkt sondern der gesamte Oberflächenteil des Objekts oder der Objekte, die durch das Pixel repräsentiert werden, betrachtet werden, was durch Sampling-Methoden (deutsch: Abtastung) wie in [Cook 1986] beschrieben jedoch nur näherungsweise erfolgen kann, z. B. mit Hilfe von Jittered Sampling. Ist der von diesem Pixel repräsentierte Punkt auf der Oberfläche eines Objekts sichtbar, so wird er von der Lichtquelle beleuchtet, andernfalls liegt er im Schatten eines anderen Objekts und die Helligkeit des Pixels wird infolgedessen nicht erhöht. Um dies zu testen, sind die folgenden zwei Schritte notwendig: • Aufgrund des Aufwands zu bestimmen, welche Teile eines Objekts aus Sicht einer Lichtquelle zur Vorder- und welche zur Rückseite gehören, wird der zweite Ansatz jedoch meistens bevorzugt. Hierbei wird zu jedem in der Shadow Map gespeicherten Wert ein Offset (auch: Tiefenversatz) addiert, so als ob das Objekt ein kleines Stück weiter von der Lichtquelle entfernt wäre als es tatsächlich ist. Das Schaubild aus [Everitt et al. o.J.] verdeutlicht das Prinzip. 1. Genauso wie beim Z-Buffer-basierten Hidden-SurfaceRemoval-Verfahren wird die Szene aus Sicht der Lichtquelle konstruiert. Die Funktionsweise des Z-Buffer-Verfahrens wird im Anhang näher erläutert. Die am Schluss vollständig vorliegende Depth Map der Szene wird dabei als Shadow Map bezeichnet. Sie enthält die z-Werte aller Oberflächenpunkte der Objekte, die von der Lichtquelle aus gesehen sichtbar sind und damit später im Licht liegen. Es ist zu beachten, dass die Auflösung der Shadow Map anders als die Depth Map aus Sicht des Betrachters nicht an die Bildschirmauflösung gebunden ist, sondern frei festgelegt werden kann. Um auf die hardwareseitige Unterstützung der weiteren Verarbeitung von Texture Maps (als solche kann eine Shadow Map interpretiert werden) zurückgreifen zu können, sollte dabei aber stets eine quadratische Auflösung gewählt werden, deren Kantenlänge in Pixeln einer Zweierpotenz entspricht, also z. B. 1.024 * 1.024 Pixel. 2. Anschließend wird die Szene aus Sicht der Kamera konstruiert. Für jeden Pixel wird dabei für den korrespondierenden Punkt auf der Oberfläche eines Objekts getestet, ob er im Schatten liegt oder nicht. Dazu muss der Punkt vom Kamerakoordinatensystem über das Weltkoordinatensystem ins Koordinatensystem der Lichtquelle transformiert werden. Sein transformierter z p -Wert wird anschließend gegen den in der Das bei weitem größte Problem von Shadow Maps stellen jedoch Aliasing-Effekte an den Schattenrändern dar. Diese machen sich derart bemerkbar, dass der Übergang von schattiger zu beleuchteter Fläche nicht in einer geraden Linie erfolgt, sondern in Treppenstufen. Beim Shadow-Map-Verfahren ist dies ein noch wesentlich schwerwiegenderes Problem als beim Zeichnen normaler Linien, auf die kein Anti-Aliasing angewendet wurde. Denn während • Eine Möglichkeit besteht darin, bei der Erstellung der Shadow Map nur die Rückseiten der Objekte zu berücksichtigen. So wird gewährleistet, dass die gespeicherten z-Tiefenwerte größer sind als die der Lichtquelle tatsächlich am nächsten liegenden Punkte auf der Vorderseite des jeweiligen Objekts. Gilt nun z p ≤ zs , so ist sicher, dass der zu z p gehörende Punkt im Licht liegen muss. bei diesen die Treppenstufen nur einen Pixel groß sind und damit nicht sehr störend auffallen, können die Treppenstufen bei Shadow Maps sehr viele Pixel umfassen, worunter der optische Eindruck stark leidet. Dies wird durch die begrenzte Auflösung von Shadow Maps hervorgerufen. Angenommen ein beleuchtetes Objekt liege sehr nahe an der Lichtquelle und es würden zwei Punkte am Rand des Objekts betrachtet, deren z-Tiefenwerte in der Shadow Map in zwei diagonal zueinander liegenden Pixel abgespeichert wurden, so würde der durch diese beiden in der Shadow Map repräsentierten Pixel gehende pyramidenförmige Sichtbereich durch die perspektivische Sicht immer weiter auffächern. Auf einer weit entfernten Fläche entständen statt einer diagonalen Linie somit zwei große Treppenstufen, die leicht mehr als zehn Pixel groß werden können. Durch die perspektivische Sicht werden also nahe gelegene Objekte in zu niedriger Auflösung in der Shadow Map gespeichert. Dieses Phänomen wird auch als Dueling Frusta bezeichnet. Einfach die Auflösung der Shadow Map zu erhöhen ist aufgrund des erhöhten Speicher- und vor allem Zeitaufwands nur in gewissen Grenzen möglich. Weil dies aber sehr einfach zu implementieren ist, wird eine derartige Option dem Spieler in vielen modernen Computerspielen als erweiterte Grafikoption angeboten. Eine alternative, in die gleiche Richtung gehende Möglichkeit wäre, für nahe und weiter entfernte liegende Objekte mehrere Shadow Maps unterschiedlicher Auflösung zu verwenden. Die abgebildeten Screenshots aus dem am 3. November 2006 veröffentlichten Rollenspiel “Neverwinter Nights 2” für den PC verdeutlichen das Problem, wobei die Verwendung von Shadow Maps in einer Auflösung von 4096 * 4096 Pixeln in Außengebieten selbst auf einem PC mit einem AMD Athlon64 X2 4200+ und einer NVIDIA Geforce 7600 GT XT unspielbar ruckelt. 4 4.1 Weitere Schattierungstechniken Shadow Volumes Wenn man von Ray-Tracing-Verfahren absieht, die zwar mathematisch sehr exakte Schatten berechnen können, dafür für Echtzeitanwendung derzeit aber noch nicht infrage kommen, sind als wichtigster alternativer Ansatz zur Generierung semi-realistischer Schatten vor allem Shadow Volumes [Hun 2002] zu nennen, die z. B. bei “Doom 3” zum Einsatz kamen. Als deren wichtigster Vor- Abbildung 4: S CREENSHOTS AUS N EVERWINTER N IGHTS 2: Die gleiche Szene mit einer Shadow-Map-Auflösung von stets 512 * 512 Pixeln für die drei Shadow-Map-Arten “Character”, “High Resolution Environment” und “Low Resolution Environment” (links) sowie mit 2.048 * 2.048 und zweimal 4.096 * 4.096 Pixeln (rechts); die Treppenstufenartefakte sind bei geringerer Auflösung deutlich zu erkennen teil ist zu nennen, dass Aliasing ein viel geringeres Problem als bei Shadow Maps darstellt. Wesentlicher Nachteil von Shadow Volumes dagegen ist, dass der Berechnungsaufwand mit zunehmender geometrischer Komplexität der Szene immer größer wird. Shadow Volumes sind zudem aufwendiger zu implementieren als Shadow Maps, die auf dem ohnehin eingesetzten Z-Buffer-Verfahren basieren. 4.2 Percentage Closer Filtering Das unter dem Namen Percentage Closer Filtering bekannte, von William T. Reeves et al. [Reeves et al. 1987] entwickelte Verfahren stellte einen ersten Schritt zur Vermeidung des oben beschriebenen Aliasing-Effekts dar. Zusätzlich ermöglicht das Verfahren die Darstellung der im Halbdunklen liegenden Penumbrae am Schattenrand. Weil die wesentlichen Vorteile von Variance Shadow Maps gerade im Vergleich mit Verfahren, die mit Percentage Closer Filtering vergleichbar sind, deutlich werden, soll das Verfahren hier näher erläutert werden: Wenn ein Pixel perspektivisch in die Szene projiziert wird, ergibt sich als Ergebnis eine Fläche, die viereckig ist, wenn sie im Innenbereich eines Polygons eines Objekts liegt. Wird angenommen, dass diese kleiner als die Auflösung der Shadow Map ist, entstehen wie auf Seite 396 in [Keller 2006] dargestellt Magnification-Aliases. Anders als für Texture Maps macht es für Shadow Maps aber keinen Sinn bilineares Filtering oder eine andere AntiAliasing-Technik anzuwenden. Der gefilterte z-Wert der Shadow Map würde mit dem z-Wert des gerenderten Objekts verglichen, was nicht nur zu einem wiederum binären Ergebnis führen würde, was weichgezeichnete Schattenränder unmöglich macht, sondern auch generell gar keinen Bezug mehr zur tatsächlichen räumlichen Anordnung der Objekte hätte. Im ersten unten abgebildeten Beispiel, bei dem ein einfacher 3 * 3 Mittelwert-Filter angewendet wird, würde sich ein gefilterter z-Wert von 22,9 ergeben, was mit Hinblick auf die beiden Objekte, die ca. 1 bzw. 50 Längeneinheiten von der Lichtquelle entfernt sind, keinen Sinn ergibt. Wie dagegen am zweiten Beispiel zu sehen ist, liegt die Lösung darin, die beiden Schritte zu vertauschen: Zuerst werden die neun z-Werte der über die Shadow Map gelegten Filtermaske mit dem z-Wert des Objekts verglichen (Sample Transformation) und erst danach wird der Mittelwert, hier 0,55, aus den neun nun binären Filterwerten gebildet. Dieser Mittelwert im Bereich von jeweils einschließlich 0 bis 1 gibt an, zu wie viel Prozent der Oberflächenpunkt von der Lichtquelle beleuchtet wird. Wenn wie im Schaubild dargestellt von einer 3 * 3 Pixel großen Filtermaske und einer einfachen Mittelwertbildung der neun Zellen ausgegangen wird, ergäbe sich ein Wert von 0 bzw. 1 für ganz im Schatten bzw. ganz im Licht liegenden Punkte, und Werte von 0,11, 0,22, 0,33, 0,44, 0,56 (richtig gerundet), 0,67, 0,78 und 0,89 für am Schattenrand liegende Punkte. Auf diese Weise erzeugte Schattenränder sind damit wie gewünscht weichgezeichnet. Abbildung 5: P ERCENTAGE C LOSER F ILTERING : Oben wird gezeigt, dass normales Filtering bei Shadow Maps nicht zum gewünschten Ergebnis führt; unten wird das korrekte Percentage Closer Filtering dargestellt Im Gegensatz dazu sind auch Minification-Aliases denkbar, bei dem die projizierte Fläche größer als die Auflösung der Shadow Map ist. Hier kann ähnlich wie oben angegeben vorgegangen werden, mit dem Unterschied dass sich der Filter für die Shadow Map aus der Größe der projizierten Fläche ergibt, siehe dazu auch die Schaubilder auf den Seiten 398 bis 400 in [Keller 2006]. 4.3 Erweiterte Shadow-Map-Verfahren Deep Shadow Maps lösen sowohl das Problem der korrekten Schattierung feiner Strukturen wie Haare oder Fell, als auch das teilweise transparenter Objekte wie Wolken. Das Verfahren basiert darauf, dass für jeden Pixel der Shadow Map die Werte einer Sichtbarkeitsfunktion in geeigneter Weise gespeichert werden, die angeben, wie viel Licht bis in die jeweilige Tiefe durchdringt. Aufgrund des großen Aufwands ist dieses Verfahren nur für NichtEchtzeitanwendungen wie Animationsfilme geeignet. Opacity Shadow Maps [Kim and Neumann 2001] verfolgen einen ähnlichen Ansatz. Der wesentliche Ansatz von Adaptive Shadow Maps [Fernando et al. 2001] hingegen ist es, auf eine hierarchisch aufgebaute Shadow Map zurückzugreifen. Diese zeichnet sich dadurch aus, dass ihre Auflösung an den Stellen, an denen Artefakte auftreten können und besonders gut sichtbar sind, also an Schattenrändern in der Nähe der Kamera, dynamisch erhöht wird. Um Speicherplatz einzusparen wird ihre Auflösung dafür an anderen Stellen reduziert. 5 Variance Shadow Maps Die von William Donnelly und Andrew Lauritzen entwickelten Variance Shadow Maps unterscheiden sich von gewöhnlichen Shadow Maps dadurch, dass nicht nur ein einziger z-Tiefenwert pro Pixel gespeichert wird, sondern auf eine Tiefenverteilung zurückgegriffen wird. Um eine derartige Tiefenverteilung für einen Pixel der Shadow Map mit möglichst geringem Speicheraufwand zu approximieren, werden der Mittelwert und der quadrierte Mittelwert als erster und zweiter Impuls der Verteilung gespeichert. In einem nächsten Schritt kann nun die Varianz über die verwendete Filterregion berechnet werden, mit deren Hilfe eine obere Schranke für den verdeckten und somit im Schatten liegenden Oberflächenteil bestimmt werden kann. Die derart bestimmte obere Schranke stellt eine gute Näherungslösung für den tatsächlichen Grad der Verdeckung dar. Während es beim normalen Shadow-Map-Verfahren nicht sinnvoll wäre, auf die generierte Shadow Map Anti-Aliasing-Operationen anzuwenden (siehe dazu das Kapitel über Percentage Closer Filtering), ist dies beim Variance-Shadow-Map-Verfahren grundsätzlich anders. Hier werden die beiden in der Shadow Map gespeicherten Tiefenwerte und quadrierten Tiefenwerte gefiltert. Um den FilterVorgang zu beschleunigen können zuvor Prefiltering-Techniken angewandt werden. Dazu können Summed Area Tables berechnet werden oder Mipmaps erzeugt werden. Um die Bildqualität bei flachem Blickwinkel oder unterschiedlicher Entfernung zu verbessern, können anschließend lineare Anti-Aliasing-Techniken wie bilineare, trilineare oder anisotrope Interpolation zum Einsatz kommen, deren Anwendung auf eine Texture Map je nach verwendeter Kommazahlendarstellung von der Grafikkarte ggf. direkt unterstützt wird. Auch Super-Sampling der Shadow Map, bei der die Interpolation durch das Herunterrechnen einer höher aufgelösten Texture Map auf die gewünschte Auflösung erreicht wird, ist möglich. Durch die zusätzliche Filterung, z. B. durch eine Gauss’sche Unschärfemaske, erhält man Schatten mit noch sanfteren Übergängen von Dunkel nach Hell an den Schattenrändern, wobei die Größe der Penumbrae von der Auflösung der Filtermaske abhängt. Anders als bei Percentage Closer Filtering ist dies in O(2n) = O(n) statt in O(n2 ) möglich, wobei n die Größe der Maske angibt, denn dies kann in zwei aufeinander abfolgenden Schritten erst horizontal und dann vertikal (bzw. umgekehrt) erfolgen (Separable Convolution), was bei Percentage Closer Filtering nicht möglich ist. Evtl. muss eine automatisch erfolgende GammaKorrektur der Shadow Map durch die Grafikkarte abgeschaltet werden. Wird nun ein Filter auf die Shadow Map angewandt, ergeben sich die Impulse M1 und M2 für die einfachen bzw. quadrierten Tiefenwerte mathematisch wie folgt: Z ∞ M1 := E(z) = M2 := E(z2 ) = z ∗ p(z)dz (1) z2 ∗ p(z)dz (2) −∞ Z ∞ −∞ obere Schranke wird in der “Ungleichung von Chebychev” angegeben: Sei z ein zufällig bestimmter Wert einer Verteilung mit dem Mittelwert µ und der Varianz σ 2 . Dann gilt für jeden Wert t > µ: P(z ≥ t) ≤ pmax (t) ≡ Abbildung 6: M IPMAPPING : Mipmapping der Variance Shadow Map kann den Treppenstufeneffekt an den Schattenrändern deutlich reduzieren Zur Mittelwertbildung wird also das Integral der Tiefenwerte unter Berücksichtigung des (unendlich großen) Filterbereichs gebildet, wobei p(zi, j ) den durch die Filtermaske bestimmten Anteil angibt, den der im Pixel (i, j) gespeicherte z-Tiefenwert für das Ergebnis im betrachteten Pixel (x, y) hat. In der Praxis kann die Filtermaske natürlich nicht unendlich groß sein, was sich schon aus der endlichen Größe der Shadow Map ergibt. Zu große Filtermasken würden außerdem die Schattenränder zu stark weichzeichnen. Um dies zu verdeutlichen soll das im Kapitel über Percentage Closer Filtering vorgestellte Beispiel aufgegriffen werden, wo ein Ausschnitt aus einer Shadow Map mit folgenden Tiefenwerten gegeben war: |50,2 |50,1 | 1,3 50,0 1,2 1,4 50,0| 1,1| 1,2| Die ebenfalls in der erweiterten Shadow Map gespeicherten quadrierten Tiefenwerte ergeben sich damit zu 1 : |2520,0 |2510,0 | 1,7 2500,0 1,4 2,0 2500,0| 1,2| 1,4| σ2 σ 2 + (t − µ)2 (5) Weiter gilt, dass wenn t ≤ µ gilt, pmax (t) = 1 ist. Die Wahrscheinlichkeit P(z ≥ t) gibt den Prozentanteil der von der Filtermaske abgedeckten Pixel der Shadow Map an, deren z-Wert größer ist als der zu vergleichende z-Wert des vom Betrachter aus sichtbaren Punkts auf der Oberfläche eines Objekts. Würde man auf das obige Beispiel keinen Gauss-Filter sondern für die ganze Berechnung eine einfache Mittelwertbildung der neun Zellen vornehmen, so würde sich für einen zu testenden Punkt mit dem z-Wert 49,8 damit ergeben: P(z ≥ 49, 8) ≤ pmax (49, 8) = ... = 0, 45. Damit würde der Punkt mit einer Intensität von 1 − 0, 45 = 0, 55 beleuchtet, was sich offensichtlich genau mit dem Ergebnis deckt, wenn Percentage Closer Filtering angewendet worden wäre. Trotzdem stellt pmax (t) nur eine obere Schranke dar, es ist also nicht möglich, den korrekten Wert für P(z ≥ t) zu berechnen. Wie am obigen Beispiel zu sehen, stellt diese obere Schranke aber oftmals eine sehr gute Näherungslösung dar, was an einem weiteren Beispiel noch weiter verdeutlicht werden soll: Gegeben sei ein Objekt, dessen zur Lichtquelle zeigende Vorderseite einen Abstand zu dieser von genau d1 habe. Wenn von einer Punktlichtquelle ausgegangen wird, muss die Vorderseite also eine (leichte) konkave, kreisförmige Krümmung aufweisen. Diese Erkenntnis ist für die weitere Rechnung aber unerheblich. Gegeben sei des weiteren eine hinter dem Objekt liegende, ebenfalls konkav kreisförmig gekrümmte Wand, die einen Abstand zur Lichtquelle von d2 aufweise. Sei außerdem ein fester Filter gegeben, der auf den zu einem in der Nähe des Randes liegenden Punktes auf der Oberfläche des Objekts korrespondierenden Bereich der Shadow Map angewendet wird, wobei p der Prozentanteil des Filterbereichs sei, für den gilt, dass der getestete z-Wert im Schatten liegt. Wendet man auf die mittlere Zelle nun einen 3 * 3 Pixel großen Gauss-Filter mit den Werten Um das schon mehrmals verwendete Beispiel wieder aufzugreifen, würde die Shadow Map unter diesen Voraussetzungen jetzt so aussehen: |1 1/16 * |2 |1 |50 |50 | 1 2 4 2 1| 2| 1| an, so ergeben sich für die mittlere Zelle die Impulswerte M1 = 15.055,1 2 E(z2,2 ) = 312,4 = 940, 9. 16 = 19, 5 und M2 = E(z2,2 ) = 16 50 1 1 50| 1| 1| p wäre in diesem Fall für einen z-Wert von 49,8 wie gehabt 0,45. Allgemein ergibt sich: Der Mittelwert µ für z2,2 und die Varianz σ 2 ergeben sich zu 2 : µ := E(z) = M1 (3) σ 2 := E(z2 ) − E(z)2 = M2 − M1 2 (4) Die Varianz ist ein Maß für die Variabilität bzw. Dispersion einer Verteilung. Mit ihr ist es unter anderem möglich, eine obere Schranke dafür anzugeben, mit welcher Wahrscheinlichkeit ein gemessener Wert z größer oder gleich wie ein gegebener Wert t ist. Eine = pd2 + (1 − p)d1 2 E(z ) = pd2 2 + (1 − p)d1 2 σ2 = pd2 2 + (1 − p)d1 2 − (pd2 + (1 − p)d1 )2 = pd2 2 − 2pd1 d2 + pd1 2 − p2 d2 2 + 2p2 d1 d2 − p2 d1 2 = (p − p2 )(d2 − d1 )2 µ = E(z) Und pmax lässt sich wie in der Ungleichung von Chebyshev angegeben bestimmen zu: 1 Alle berechneten Ergebnisse wurden der Übersichtlichkeit halber auf eine Nachkommastelle gerundet 2 Die Varianz σ 2 einer empirischen Verteilung mit dem arithmetischen Mittelwert xm ist allgemein wie folgt definiert: σ2 := ∑ni=1 (xi −xm )2 n pmax (d2 ) = σ2 σ2 = σ 2 + (d2 − µ)2 σ 2 + (µ − d2 )2 = = = = (p − p2 )(d (p − p2 )(d2 − d1 )2 2 2 2 − d1 ) + (pd2 + (1 − p)d1 − d2 ) (p − p2 )(d2 − d1 )2 2 2 2 2 − d1 ) + (1 − p) (d2 − d1 ) (p − p2 )(d p − p2 1− p p In diesem Spezialfall der Ungleichung von Chebyshev gilt also Gleichheit und der Wert von pmax (d2 ) stimmt genau mit dem Wert überein, der sich bei Anwendung von Percentage Closer Filtering ergeben hätte. Wenn man nun aber bedenkt, dass es in realen Szenen sehr häufig der Fall ist, dass ein einzelnes Objekt einen Schatten auf ein anderes einzelnes Objekt wirft und sich die z-Werte der Punkte auf der Oberfläche eines Objekts in direkt benachbarten Pixeln so gut wie nicht unterscheiden, wird deutlich, dass es bei bei oberen Schranke pmax in vielen Fällen um eine sehr gute Näherung für den tatsächlichen Wert p handelt. Abbildung 7: Performance: Performance in Frames pro Sekunde von Variance Shadow Maps im Vergleich zu Percentage Closer Filtering bei fester Bildschirmauflösung von 1024 * 768 Pixeln und variabler Shadow-Map-Größe Wenn kein eigener Filter wie der obige Gauss-Filter zum Einsatz kommen soll und statt dessen auf die auf der Grafikkarte zu Verfügung stehenden Interpolationstechniken zurückgegriffen werden soll, werden M1 und M2 dabei direkt von der Grafikkarte berechnet. 5.1 Vorteile Der größte Vorteil der Variance Shadow Maps besteht darin, dass auf die von der Grafikkarte angebotenen Operationen zum Filtern der Shadow Map zurückgegriffen werden kann. So unterstützen z. B. alle GeForce-6- und Geforce-7-Grafikkarten von NVIDIA Mipmapping und anisotropes Filtering von 16 Bit Floating-PointTexture-Maps. Außerdem ist der Einsatz eines eigenen Weichzeichenfilters bis zu einer Größe von 15 * 15 Pixeln vorstellbar, während bei Percentage Closer Filtering die Filtergröße in der Praxis auf maximal 5 * 5 Pixel beschränkt ist. Die abgebildeten Performance-Statistiken zeigen deutlich den Geschwindigkeitsvorteil von Variance Shadow Maps im Vergleich zu Percentage Closer Filtering auf einer GeForce-6800-GTGrafikkarte. “Bil. PCF 3x3” bedeutet dabei, dass eine 3 * 3 Pixel große Gauss-Filtermaske auf eine zuvor bilinear gefilterte Shadow Map angewendet wurde. Auf die Variance Shadow Map wurde Mipmapping, trilineares und 16-faches anisotropes Filtering angewendet, im zweiten Versuch dazu ein zusätzlicher 3 * 3 Pixel großer Gauss-Filter. Dabei fällt auf, dass Percentage Closer Filtering fast nicht über die Auflösung der Shadow Map skaliert. Es wird deutlich, dass Variance Shadow Maps insbesondere beim Einsatz einer eigenen Filtermaske deutlich schneller sind. Aber auch sonst sind sie in etwa gleich schnell wie Percentage Closer Filtering, und das bei wesentlich verbesserter Bildqualität durch die angewendeten Filter-Techniken (siehe dazu die Screenshots auf Seite 1). Ein weiterer Vorteil beim Einsatz von Variance Shadow Maps ist, dass sie zusammen mit komplementären Techniken wie Adaptive Shadow Maps oder Perspective Shadow Maps [Stamminger and Drettakis 2002] eingesetzt werden können um die Bildqualität noch weiter zu verbessern. Auch das Problem des Self-Shadowing von Objekten wird durch den Einsatz von Variance Shadow Maps stark reduziert, da Flächen im Zweifelsfall eher heller beleuchtet werden, was jedoch auch das unten beschriebene Problem der Lichthöfe nach sich zieht. Trotzdem kann es nötig sein, bei der Erstellung der Shadow Map einen geringen Offset für die z-Tiefenwerte zu verwenden. Abbildung 8: Performance: Performance in Frames pro Sekunde von Variance Shadow Maps im Vergleich zu Percentage Closer Filtering bei fester Shadow-Map-Größe von 512 * 512 Pixeln und variabler Bildschirmauflösung 5.2 5.2.1 Probleme Lichthöfe Das größte Problem, das beim Einsatz von Variance Shadow Maps auftritt, ist das Entstehen von Lichthöfen (engl. Light Bleeding). Wie am abgebildeten Screenshot 3 zu sehen ist, sind darunter Bereiche zu verstehen, die vollständig im Schatten eines Objekts liegen sollten, aber trotzdem heller dargestellt werden. Es gibt eine ganze Reihe von Situationen, die das Entstehen von Lichthöfen begünstigen, weshalb derartige Artefakte relativ häufig auftreten. Lichthöfe treten dann verstärkt auf, wenn die Tiefenkomplexität der Szene hoch ist, d. h. wenn die Szene aus vielen sich aus Sicht der Lichtquelle überlappenden Objekten in unterschiedlicher Entfernung besteht, so dass sich ein großer Wert für die Varianz ergibt. Wenn sich zwei oder mehr Objekte aus Sicht der Lichtquelle überlappen, ist die durch die Ungleichung von Chebyshev gegebene Näherungslösung weniger gut. An den Überlappungsstellen können dann Lichthöfe entstehen. Die Überlappung von Objekten 3 Screenshot von Zaknafein aus dem Thread “Shadow-Mapping Directional Lights” im TV3D-Forum unter http://www.truevision3d.com/ phpBB2/viewtopic.php?t=13817 ten Fläche besonders groß sei, sei der Einsatz einer globalen, gerichteten Lichtquelle (engl. directional light) oder weiterer Punktlichtquellen zu empfehlen. • Außerdem solle eine Punktlichtquelle nicht zu hell sein. • Weil die Lichthöfe vor allem auffallen würden, wenn sie sich bewegten, solle es vermieden werden, die jeweiligen Lichtquellen zu bewegen. Weil der Designer bei der Gestaltung der Levels in seiner Gestaltungsfreiheit einschränkt wird und sich bewegende Lichtquellen evtl. gar nicht vermeiden lassen, z. B. wenn eine Spielfigur eine Taschenlampe als Lichtquelle bei sich trägt, stellen diese Vorschläge aber nur im Fall massiver Probleme mit Lichthöfen eine Option dar. Abbildung 9: L ICHTH ÖFE : Das Problem der Lichthöfe an der Schnittstelle zwischen Objekten, hier Teekanne und Deckel, sind bei dieser (vermutlich nicht optimalen) Implementierung besonders gut zu erkennen stellt aber auch für viele andere Schattendarstellungstechniken ein Problem dar. Verstärkt wird dieses Problem durch die mangelnde Präzision des verwendeten 16-Bit-Kommazahlenformats. Die Größe der Lichthöfe hängt ferner von der Größe der verwendeten Filtermaske ab. Sie sind maximal so groß wie es diese nach der Projektion aus dem Lichtkoordinatensystem ins Kamerakoordinatensystem ist. Eine einfache Lösung bei verstärktem Auftreten von Lichthöfen wäre es daher, die Größe der verwendeten Filtermaske zu reduzieren, wobei dann aber wieder mit verstärkten Aliasing-Effekten an den Schattenrändern zu rechnen ist. Wenn statt mit einem eigenen (Gauss-)Filter nur mit trilinearem oder anisotropem Filtering gearbeitet wird, sind die Lichthöfe daher nicht größer als ein projiziertes Pixel der Shadow Map. Der Rückgriff auf zusätzliche Informationen, wie das Minimum oder Maximum einer Tiefenverteilung könnte außerdem helfen, kritische Stellen zu erkennen und geeignete Gegenmaßnahmen zu ergreifen, die fälschlicherweise beleuchteten Pixel also zu schattieren. Hierfür ist jedoch noch kein Verfahren bekannt, welches ein möglichst gutes Ergebnis bei möglichst geringem zusätzlichen Aufwand liefert. 4 Andrew Lauritzen denkt, dass das Problem dadurch gelöst werden könnte, wenn in die Berechnungen auch die dritte und vierte Potenz der z-Tiefenwerte eingehen würden, eine zusätzliche für jedes weitere überlappende Objekt. Zwar würde dies einen höheren Zeit- und Speicheraufwand nach sich ziehen, die eigentliche Schwierigkeit dieses Ansatzes besteht aber darin, dass bis dato keine mehrdimensionale Version für beliebige n der Ungleichung von Chebyshev bekannt ist. Hier besteht also weiterer Forschungsbedarf. Er schlägt daher vor, schon bei der Konstruktion einer Szene die folgenden, auch beim Einsatz anderer Schattierungstechniken zu beachtenden Ratschläge zu befolgen um die oben genannten Hauptfehlerquellen zu umgehen: Wenn der Abstand zwischen dem Schatten werfenden Objekt und einem direkt dahinter liegenden Objekt sehr gering ist, z. B. dem Boden, ist es außerdem möglich, dass der Schatten schwach statt stark dargestellt wird. Dieses Problem tritt auf, wenn bei Verwendung eines nicht genügend präzisen Kommazahlenformats ein geringer Offset eingestellt wird, um numerische Instabilitäten zu vermeiden, die unter anderem Self-Shadowing hervorrufen könnten. In schwächerem Ausmaß tritt das Problem auch auf, wenn der von der Lichtquelle ausgehende Sichtbereich horizontal zum Boden verläuft, was in diesem Fall an der größeren Varianz innerhalb der Filterregion liegt. 5.2.2 Numerische Instabilität Die Berechnung von E(z2 ) − E(z)2 ist numerisch instabil, wenn die verwendete Zahlendarstellung nicht genug viele Stellen aufweist, gerade wenn die Varianz gering ist und somit E(z2 ) ≈ E(z)2 gilt. Die Verwendung eines möglichst präzisen Zahlenformats ist für Variance Shadow Maps daher von entscheidender Bedeutung. 8-Bit-Zahlenformate sind völlig ungeeignet und selbst bei 16-BitKommazahlenformaten können noch Probleme wie Lichthöfen auftreten, gerade wenn die zur Verfügung stehende Präzision nicht gut ausgenutzt wird. • Da Lichthöfe vor allem dann störend auffielen, wenn der Kontrast zwischen der im Schatten liegenden und der beleuchte- Um die Interpolationstechniken wie Mipmapping und anisotropes Filtering der GeForce-6- und Geforce-7-Grafikkarten von NVIDIA nutzen zu können, sollte dabei auf 16-Bit Floating-Point-Zahlen zurückgegriffen werden. Um deren mögliche Präzision maximal ausnutzen zu können, ist es außerdem empfehlenswert, alle Punkte des Lichtkoordinatensystems maßstabsgetreu in den Bereich [1,0 1,0] zu transformieren, wodurch nicht nur die höhere Präzision von Floating-Point-Zahlen um den Nullpunkt ausgenutzt wird, sondern durch das Vorzeichen ein weiteres Bit an Präzision gewonnen wird. Es wird empfohlen, dabei nicht auf die von OpenGL angebotene Post-Projection in den Bereich [-1, 1] zurückzugreifen, weil in diesem Fall der größte Teil der Präzision für den Bereich nahe der Lichtquelle verwendet wird, so dass bei weiter entfernten Gegenständen sichtbare Artefakte auftreten können. Noch mehr Präzision lässt sich gewinnen, wenn unter Verwendung der obersten, einen Pixel großen Mipmap-Textur des letzten Frames der Mittelwert und der quadrierte Mittelwert der zuletzt verwendeten Shadow Map bestimmt wird, um den Wertebereich der neuen Shadow Map damit so zu skalieren, dass der neue Mittelwert 0 ergibt und die neue Varianz 1 (unter der vereinfachten Annahme, dass die alte und neue Shadow Map identisch sind). 4 Mangels anderer Quellen geht diese und einige andere Anmerkungen auf Beiträge im Thread “Variance Shadow Maps” des GameDev.NetForums unter http://www.gamedev.net/community/forums/topic. asp?topic_id=374989 zurück, vor allem auf Beiträge der beiden Entwickler des Verfahrens, die dort unter den Pseudonymen AndyTX für Andrew Lauritzen und Pragma für William Donnelly auftreten Im Gegensatz dazu muss für Radeon-Grafikkarten des Herstellers ATI auf 16-Bit Fixed-Point-Zahlen zurückgegriffen werden, was aufgrund deren höherer Präzision durch die fehlende Exponentendarstellung vorteilhafter ist. Auf ATI-Grafikkarten fehlt dagegen die hardwareseitige Unterstützung von Mipmapping, bilinearem und anisotropem Filtering. Während bilineares Filtering einfach per Shader emuliert werden kann, ist dies für die anderen beiden Techniken deutlich aufwendiger und kommt für Echtzeitanwendungen derzeit nicht infrage. Bei der Implementierung ist außerdem darauf zu achten, dass 16-Bit-Festkommazahlen von NVIDIAGrafikkarten fälschlicherweise als 8-Bit-Festkommazahlen interpretiert werden, was sich in massiven Artefakten bemerkbar macht. Es ist damit zu rechnen, dass kommende Grafikkartengenerationen, wie heute schon die in der Spielekonsole XBox 360 eingesetzte Grafikkarte, 32-Bit-Floating-Point-Zahlen nativ unterstützen werden, was sich positiv auf den Einsatz von Variance Shadow Maps auswirken würde. Sollen trotzdem 32-Bit-Floating-Point-Zahlen verwendet werden, muss im schlechtesten Fall mit einer um 30 % bis 40 % geringeren Framerate gerechnet werden, was für die meisten Szenen, bei denen nur geringe Artefakte auftreten, nicht gerechtfertigt erscheint. 6 Fazit und Ausblick Insgesamt ist das Variance-Shadow-Maps-Verfahren als sehr vielversprechendes Verfahren zur Vermeidung von Aliasing-Effekten anzusehen und überzeugt im Vergleich zu Percentage Closer Filtering sowohl was die resultierende Bildqualität als auch die benötigte Rechenzeit angeht. Auch die beschriebenen Probleme mit Lichthöfen sollten nicht überbewertet werden, da auch andere Schattierungstechniken bei komplex aufgebauten Szenen häufig sichtbare Artefakte produzieren. Trotzdem besteht hier noch weiterer Forschungsbedarf, welcher der vorgeschlagenen Lösungsansätze die Vorteile der Variance Shadow Maps, die vor allem in der Geschwindigkeit des Verfahrens liegen, bestmöglich erhalten. Nicht gelöst werden durch Variance Shadow Maps jedoch die Probleme, die transparente Objekte oder Haar bzw. Fell verursachen, weswegen Variance Shadow Maps keine Alternative zu den hierfür z. B. verwendeten Deep Shadow Maps darstellen. Bis zu einem breiten Einsatz in der Praxis dürfte ebenfalls noch einige Zeit vergehen, da es sich um ein neues Konzept handelt, für das bis auf den zitierten Artikel und den begleitenden Vortrag noch keine weitere Literatur existiert. Es ist auch vorstellbar, dass sich Variance Shadow Maps sinnvoll mit anderen Shadow-Map-Techniken kombinieren lassen um die Bildqualität weiter zu erhöhen und das Problem der Lichthöfe zu minimieren. Wie erwähnt, unterstützt z. B. die Grafikkarte der XBox 360 schon heute 32-Bit Floating-Point-Zahlen, was von Andrew Lauritzen als sehr wichtig für den zukünftigen Einsatz von Variance Shadow Maps angesehen wird. Auch John Carmack, der Geschäftsführer und leitende Programmierer von id Software, kündigte mit Hinblick auf die Limitierungen der in der Doom-3-Engine eingesetzten Shadow Volumes an, einen Blick auf Variance Shadow Maps werfen zu wollen. Sollten in der neuesten Engine von id Software Variance Shadow Maps Verwendung finden, dürfte das zum Durchbruch der Technik beitragen. 7 7.1 Anhang Der Z-Buffer-Algorithmus Um die Arbeitsweise des Shadow-Map-Algorithmus genau verstehen zu können, ist es hilfreich zu wissen, wie der zugrunde liegende Z-Buffer-Algorithmus funktioniert. Dieser soll daher hier vorgestellt werden: Das erstmals von E. Catmull in “A Subdivision Algorithm for Computer Display of Curved Surfaces” [Catmull 1974] vorgestellte ZBuffer-Verfahren wird in [Slater et al. 1992] näher erläutert. Es handelt sich dabei um ein Verfahren, um diejenigen, aus planaren Polygonen aufgebauten, Objekte einer Szene zu bestimmen, die gerade sichtbar sind und auf dem Bildschirm dargestellt werden sollen. Das Verfahren wird daher auch als Hidden Surface Removal bezeichnet. Es ist außerdem ein Image Space-Verfahren, was bedeutet, dass es erst nach der Projektion aus dem originalen Weltkoordinatensystem in das Kamerakoordinatensystem zum Einsatz kommt. Beim namensgebenden Z-Buffer, manchmal auch als Depth Buffer oder Depth Map bezeichnet, handelt es sich um ein zweidimensionales Array mit der Größe der Bildschirmauflösung, in dem die z-Tiefenwerte jedes Pixels als Gleitkommazahlen gespeichert werden. Der Algorithmus läuft wie folgt ab: In einem ersten Schritt wird die sogenannte Edge Table (ET) der Szene aufgebaut. Die Edge Table besteht aus genau yn vielen Einträgen, wobei n die Anzahl der Pixel in y-Richtung (vertikal von unten nach oben) ist, die auf dem Bildschirm dargestellt werden sollen. Die Einträge der ersten Ebene der Edge Table sind wiederum Listen. Es werden nun die Kanten aller Polygone der Szene, die nach dem Clipping-Vorgang noch für die Darstellung infrage kommen, sequentiell durchlaufen. Der minimale y-Wert einer der beiden Eckpunkte legt fest, in welches Array-Element der Edge Table die Kante einsortiert wird. Für die Kante von (x1 , y1 ) nach (x2 , y2 ) gelte y1 < y2 , damit wird die Liste an der Stelle ET[y1 ] um einen Eintrag erweitert. Dieser Eintrag ist ein Quadrupel aus (y2 , x1 , dx/dy, ptr), wobei ptr ein Zeiger auf das zur Kante gehörende Polygon ist. Ist dies für alle Polygone erfolgt, enthalten die Einträge ET[i] der ersten Ebene der Edge Table somit alle derart repräsentierten Kanten, deren niedrigerer der beiden y-Werte den Wert i hat. Anschließend wird für das Polygon der aktuellen Kante für jeden yWert zwischen einschließlich y1 und y2 außerdem die Ausdehnungen in x-Richtung betrachtet. Jede der Scanlines schneidet eine gerade Anzahl an Kanten des aktuellen Polygons 5 . Im Falle von konvexen Polygonen werden immer genau zwei Kanten geschnitten, so dass eine anschließende Sortierung nach x-Werten unnötig ist. Diese “aktiven” Kanten werden in eine Active Edge Table (AET) eingetragen. Der Active Edge Table werden anschließend weitere Kanten hinzugefügt, wenn für die Scanline an der Position y die Kanten der Edge Table an der Stelle E[y] betrachtet werden. Im Gegensatz dazu werden vollständig betrachtete Kanten aus der Active Edge Table wieder entfernt, was an den y2 -Werten zu erkennen ist. Die verbleibenden Kanten werden aktualisiert, indem ihr x1 -Wert um dx/dy erhöht wird. Für jede Position (x, y) jeder Scanline wird nun der z-Wert ausgerechnet und dieser wird mit dem korrespondierenden z-Wert des Z-Buffers verglichen. Ist der z-Wert niedriger, d. h. die Position ist näher am Betrachter als die vorher gespeicherte, so wird der Pixel entsprechend der im zugehörigen aktuellen Polygon abgelegten Farbinformation eingefärbt und der alte im z-Buffer stehende z-Wert durch den eben berechneten z-Wert der Position (x, y) ersetzt. Literatur C ATMULL , E. 1974. A Subdivision Algorithm for Computer Display of Curved Surfaces. PhD thesis, University of Utah. 5 abgesehen von Spezialfällen wie einer horizontal verlaufenden Kante oder dem oberen und unteren Eckpunkt für die geeignet vorgegangen werden muss C OOK , R. L. 1986. Stochastic sampling in computer graphics. In ACM Transactions on Graphics (TOG), ACM Press / ACM SIGGRAPH, New York, vol. 5, ACM, 51–72. D ONNELLY, W., AND L AURITZEN , A. 2006. Variance shadow maps. In Proceedings of the 2006 symposium on Interactive 3D graphics and games, ACM Press / ACM SIGGRAPH, New York, ACM, 161–165. E VERITT, C., R EGE , A., AND C EBENOYAN , C. o.J. Hardware Shadow Mapping. NVIDIA Corporation. http://developer.nvidia.com/object/hwshadowmap paper.html. F ERNANDO , R., F ERNANDEZ , S., BALA , K., AND G REENBERG , D. P. 2001. Adaptive shadow maps. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, ACM Press / ACM SIGGRAPH, New York, ACM, 387–390. H UN Y EN K WOON. 2002. The Theory of Stencil Shadow Volumes. http://www.gamedev.net/reference/articles/article1873.asp. K ELLER , A. 2006. Vorlesungsskript Computergraphik Sommersemester 2006. http://medien.informatik.uni-ulm.de/lehre/XYZ. K IM , T.-Y., AND N EUMANN , U. 2001. Opacity shadow maps. In Proceedings of the 12th Eurographics Workshop on Rendering Techniques, Springer-Verlag, London, 177–182. L AURITZEN , A. 2006. Variance Shadow Maps (Slides). http://www.punkuser.net/vsm/. L OKOVIC , T., AND V EACH , E. 2000. Deep shadow maps. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques, ACM Press / ACM SIGGRAPH, New York, ACM, 385–392. P IXAR A NIMATION S TUDIOS. 2006. Pixar’s RenderMan: The Core Rendering Technology. https://renderman.pixar.com/products/tools/renderman.html. R EEVES , W. T., S ALESIN , D. H., AND C OOK , R. L. 1987. Rendering antialiased shadows with depth maps. In Proceedings of the 14th annual conference on Computer graphics and interactive techniques, ACM Press / ACM SIGGRAPH, New York, ACM, 283–291. S LATER , M., D RAKE , K., DAVISON , A., KORDAKIS , E., B IL LYARD , A., AND M IRANDA , E. 1992. A statistical comparison of two hidden surface techniques: the scan-line and z-buffer algorithms. In Computer Graphics Forum, Blackwell Publishing, Oxford, vol. 11, Eurographics Association, 131–138. S TAMMINGER , M., AND D RETTAKIS , G. 2002. Perspective shadow maps. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques, ACM Press / ACM SIGGRAPH, New York, ACM, 557–562. W ILLIAMS , L. 1978. Casting curved shadows on curved surfaces. In Proceedings of the 5th annual conference on Computer graphics and interactive techniques, ACM Press / ACM SIGGRAPH, New York, ACM, 270–274.
