Bilderspiele: Ray Tracing - Verfolgungsjagd mit dem Computer
In den letzten Folgen haben Sie einige Techniken kennengelernt, die benutzt werden, um schattierte Bilder darzustellen. Immerhin, weiche Farbverläufe und Schlaglichteffekte sind möglich. Man kann diese Verfahren mit erheblichem Aufwand auch noch weiter verbessern, so daß Schatten und Transparenz möglich werden. In dieser Folge soll aber nun ein schon vom Konzept her völlig anderes Prinzip der Berechnung realistischer Bilder vorgestellt werden, das zwar einen erheblich höheren Grundaufwand erfordert als die ‘traditionellen' Verfahren, dafür aber all die schönen Spezialeffekte gleich in einem Aufwasch miterledigt. Dazu sind Ray-Tracing-Programme auch noch relativ leicht zu implementieren. Vorhang auf.
Das Ray Tracing-Verfahren wurde ursprünglich als Hidden-Surface-Verfahren entwickelt. In dieser Form tut ein Ray-Tracing-Programm also nichts anderes als die in der letzten Folge vorgestellten Verfahren, wie der z-Buffer oder der Maleralgorithmus. Allerdings ist ein Ray-Tracing-Programm als reiner Hidden-Surface-Prozessor extrem ineffizient.
Schon sehr schnell stellte sich aber heraus, daß das Verfahren viel mehr Möglichkeiten bietet. Heute sind Ray Tracing-Systeme das Standardwerkzeug in der High-End-Computergrafik. Kein Verfahren erlaubt es, so gute Bilder zu berechnen. Einziger Nachteil ist der hohe Rechenaufwand. Aber auch da versucht man, mit immer neuen Verbesserungen Abhilfe zu schaffen.
Die Grundidee ist einfach. Der Betrachter einer beliebigen Szene sieht Licht, das von irgendwelchen Lichtquellen (Lampen. Sonnen, Feuer, Kerzen usw.) ausgesandt und von den Gegenständen, aus denen die Szene besteht, in Richtung des Betrachters reflektiert wird. Über die einfache Modellierung des Verhaltens von Licht haben Sie ja bereits in der letzten Folge dieser Serie einiges erfahren. Auch bei einem Ray Tracer gilt: Je besser das Lichtmodell, desto besser die Ergebnisse. Ray Tracer erlauben übrigens den Einsatz erheblich besserer Lichtmodelle als die ‘traditionellen’ Verfahren.
Um festzustellen, was der Betrachter sieht, verfolgt man einfach jeden Lichtstrahl von seinem Entstehungsort an und beobachtet, wo er hinstrahlt, wohin er reflektiert wird usw...
Oder nein, vielleicht ist das keine allzugute Idee, denn von den Lichtstrahlen, die eine Lichtquelle aussendet, erreicht nur ein verschwindend kleiner Teil den Betrachter. Außerdem sendet so eine Lichtquelle unendlich viele Lichtstrahlen aus, was zu einer etwas unpraktisch langen Rechenzeit führen könnte. So geht es also nicht. Aber umgekehrt... Wenn man einfach vom Auge des Betrachters aus alle Lichtstrahlen in die Szene verfolgt, hat man schon mal entschieden weniger zu tun. Aber immer noch unendlich viel. Man muß sich also noch etwas einfallen lassen, das die Anzahl der zu verfolgenden Strahlen begrenzt. Dazu fällt uns sofort der Bildschirm ein. Schließlich müssen wir das Bild sowieso auf einem endlichen Raster aus z.B. 640*400 Punkten darstellen. Also verfolgen wir nur diejenigen Strahlen, die vom Betrachterstandpunkt. (Wir nehmen selbstverständlich einen punktförmigen Betrachter an.) aus durch ein Pixel des Bildschirms auf die Szene fallen. Um die Rechnerei zu vereinfachen, nehmen wir einfach mal an, der Bildschirm läge auf der xy-Ebene. In Bild 1 sehen Sie, wie das aussieht. Jeder Strahl muß sich irgendwie mathematisch beschreiben lassen, ohne Steckbrief können wir ihn schlecht verfolgen. Zwei Punkte des Strahls sind uns bekannt, die Koordinaten des Pixels, dessen Strahl wir gerade verfolgen und die Koordinaten des Blickpunktes. Daraus läßt sich glücklicherweise eine Geradengleichung konstruieren, und zwar derjenigen Geraden, die durch das Pixel und den Blickpunkt geht.
Es gilt:
x = x1 + (x2 - x1)*t
y = y1 + (y2 - y1)*t
z = z1 + (z2 - z1)*t
wobei x,y,z ein beliebiger Punkt auf dem Strahl ist, x1,y1,z1 der Blickpunkt und x2,y2,z2 das entsprechende Bildschirmpixel. Da wir die xy-Ebene für den Bildschirm gewählt haben, ist z2 gleich 0. Wenn t=0 ist, erhält man als Ergebnis der Gleichung den Blickpunkt, wenn t=1 ist, ergibt sich das Pixel. Daraus kann man entnehmen, daß t>l wird, wenn wir den Strahl weiter in die Szene verfolgen. Warum tun wir das überhaupt? Nun, wir wollen wissen, welches Objekt vom Blickpunkt, wenn er sozusagen entlang des Strahls durch das Pixel schaut, sichtbar ist. Dieses Pixel müssen wir dann nämlich entsprechend dem gefundenen Objekt verändern. Finden wir ein blaues Objekt, muß dieses Pixel blau werden, ist es rot, wird das Pixel eben auch rot. Um festzustellen, auf welches Objekt der Strahl trifft, berechnen wir einfach Schnittpunkte zwischen dem Strahl und allen Objekten der Szene. Wenn der Strahl kein Objekt trifft, verläßt er die Szene und das Pixel erhält die Farbe des Hintergrundes (z.B. des blauen Himmels über dem Kornfeld). Trifft er nur ein Objekt, ist alles klar. Gibt es aber Schnittpunkte mit mehreren Objekten, müssen wir wissen, welcher Schnittpunkt dem Beobachter am nächsten liegt, denn dieses Objekt verdeckt dann alle anderen. Das ist einfach. Am Pixel ist der Wert für t gleich 1. am Blickpunkt 0. Wenn sich jetzt für die Schnittpunkte Werte für t zwischen 2 und 7 ergeben, liegt der Punkt mit dem kleinsten Wert für t dem Bildschirm (und damit auch dem Beobachter) am nächsten.
Ein Strahl durch den Blickpunkt und eines der Pixel der Bildebene wird auf Schnittpunkte nit den Objekten der Szene untersucht. Bei Mehreren Schnittpunkten wird der der Bildebene an nächsten liegende Schnittpunkt weiterverwendet.
Wenn alle Schnittpunkte aller Strahlen (ein Strahl durch jedes Pixel) mit jeweils jedem Objekt berechnet worden sind, ist der Algorithmus am Ende (Ihre Geduld wahrscheinlich auch). Für jedes Pixel wurde jetzt festgestellt, welches Objekt von dort aus sichtbar ist. Dies ist die einfachste Aufgabe des Ray Tracing-Verfahrens, nämlich die Auffindung aller sichtbaren Objektteile.
Vielleicht ist Ihnen aufgefallen, daß dies im Prinzip eine Digitalisierung der dreidimensionalen Welt ist. Eigentlich treffen unendlich viele Strahlen den Beobachter, Sie wählen jedoch nur eine endliche Anzahl davon aus. Nichts anderes geschieht beim Digitalisieren von Musik, z.B. für die CD-Produktion; das kontinuierliche Musiksignal wird in einzelne Abtastwerte zerlegt. Wie für Musik ist auch hier das Abtasttheorem von Shannon gültig, nach dem sich immer dann Verzerrungen ergeben, wenn die Abtastrate niedriger als das Doppelte der höchsten im abzutastenden Signal vorkommenden Frequenz ist. Was man bei Musik hören kann, sieht man auch auf dem Bildschirm: leider sind diese Verzerrungen, die sich bei Rasterbildschirmen als häßliche Treppchen in schrägen Konturen zeigen, nur mit aufwendigen, Anti-Aliasing genannten Verfahren zu mildern. Anti-Aliasing ist eines der kompliziertesten Gebiete der digitalen Signalverarbeitung, deshalb habe ich diesen Punkt in dieser Serie auch fein säuberlich ausgespart. Es ist gar nicht so einfach, ein Anti-Aliasing-Verfahren zu implementieren, das akzeptable Ergebnisse bei vernünftigem Aufwand ergibt. Noch etwas anderes. Wie berechnet man Schnittpunkte eines Strahles mit einem Objekt ?
Ganz einfach, man benötigt dafür nur eine mathematische Beschreibung des Objektes. Eine Kugel ist mathematisch sehr einfach zu beschreiben, das Männchen bei der Juggler-Demo, die wohl jeder Amiga-Besitzer kennt oder sein eigen nennt (ha, das reimt sich !), ist z.B. aus Kugeln zusammengesetzt. Es ist auch möglich, frei geformte Oberflächen mathematisch zu beschreiben, aber dann steigt die ohnehin schon lange Rechenzeit eines Ray Tracers stark an, weil Schnittpunkte mit solch komplexen Objekten sehr schwer zu bestimmen sind. 640*400 Pixel sind insgesamt 256.000 Pixel. Wenn eine Szene aus zehn Objekten, was wahrlich nicht viel ist, besteht, müssen 256.000 Strahlen mit jeweils 10 Objekten geschnitten werden. Das macht 2.560.000 Schnittpunktberechnungen. Und das sind nur die Schnittpunkte, die für die Hidden Surface-Berechnung gebraucht werden. Alle Effekte, die realistische Bilder erzeugen, haben wir ja noch gar nicht erwähnt.
In Bild 2 sehen Sie die Berechnung des Schnittpunktes eines Strahles mit einer Kugel. Mit Zylindern ist es auch nicht viel schwieriger. Die Grundidee bleibt immer die gleiche; man setzt die Gleichung des Strahles in die des Objektes ein und schaut nach, ob etwas Sinnvolles herauskommt. Wenn nicht, gibt es keinen Schnittpunkt.
Special Effects...
Bisher haben wir einfach aufgehört, wenn wir ein erstes Objekt gefunden hatten. So geht das aber nicht. Das Licht kommt ja nicht von diesem Objekt, sondern von irgendeiner Lichtquelle und ist nur von diesem Objekt reflektiert worden. Die geometrische Optik liefert alle Gesetze, die man zur Berechnung der Lichtbrechung auf einer Oberfläche braucht. Was wir tun müssen, ist festzustellen, unter welchem.Winkel ein Lichtstrahl die Oberfläche erreicht. Damit kann man dann auch feststellen, aus welcher Richtung er die Oberfläche wieder verläßt. Wir tun dies natürlich andersherum.
Wir wissen ja, wie der Lichtstrahl gekommen sein müßte und verfolgen also den Weg des Lichtstrahls über alle Ecken und Kanten, bis er die Szene verläßt oder auf eine Lichtquelle trifft. Damit wissen wir, welche Intensität er gehabt hat, als er losgesendet wurde. Wenn er von der Lampe kommt, hat er die Intensität der Lampe, kommt er aus dem Hintergrund, die der Umgebungshelligkeit. Bei jeder Reflektion wird diese Intensität gemindert, wobei die Stärke der Minderung von den Oberflächeneigenschaften des reflektierenden Objektes abhängt. Ein Spiegel mindert wenig, eine matte Oberfläche stark.
Wenn man transparente Oberflächen zuläßt, taucht ein weiteres Problem auf. An einer transparenten Oberfläche wird ein Strahl nicht nur gespiegelt, sondern auch gebrochen (Bild 3). Auch hierbei gelten wieder die Gesetze der geometrischen Optik. Der erste Schnittpunkt ist im allgemeinen also nicht das Ende der Strahlverfolgung. Im Gegenteil, hier spaltet der ursprüngliche Strahl sich in einen Baum von reflektierten und gebrochenen Strahlen auf, die alle verfolgt werden müssen, bis sie die Szene verlassen.
Die Gesautintensitat ergibt sich als Summe der Umgebungshelligkeit (Faktor Ka * Intensität Ial, der diffusen Reflektion aller Lichtquellen CKd * Sunne aus Lichtintensität nal Lichtwinkel aller Langen) sowie den von Seiten des reflektierten und gebrochenen Strahles zurückkommenden Intensitäten (Faktor Krr bzw. Krg und Intensität Irg bzw. Irr!. Der Brechungswinkel ergibt sich aus den Verhältnis der Materialkonstanten u1 und u2.
Für eine genaue Erklärung fehlt es hier leider an Raun, wir müssen Sie an die entsprechende Literatur verweisen.
Erst dann, wenn die Ausgangspunkte aller Strahlen, die aus dem Ursprungsstrahl entstanden sind, berechnet wurden, kann damit begonnen werden, die tatsächlichen Helligkeitsverhältnisse am ersten Schnittpunkt zu berechnen. Die Helligkeit an dieser Stelle ist nämlich die Summe aller auf den Punkt auftreffenden Teilhelligkeiten. An jeder Brechungsoder Reflektionsstelle müssen, vom Ursprungsort ausgehend, die Veränderungen, die die Objekte je nach Materialeigenschaften dem Lichtstrahl angetan haben, berechnet werden. Die Summe all dieser Teilintensitäten ergibt die endgültige Helligkeit des Pixels.
Die Berechnung der Schnittpunkt-Intensitäten wird mit Beleuchtungsmodellen wie denen, die Sie bereits in der letzten Folge kennengelernt haben, durchgeführt. Wie bereits oben erwähnt, gibt es aber erheblich raffiniertere Simulationen des Lichtverhaltens. Sogar die Reflektion von diffusem Licht zwischen verschiedenen Objekten und die diffuse Streuung an Nebel, Staub oder Rauch kann mit einem komplexen Modell und einer dazugehörigen Abwandlung des Ray Tracing-Verfahrens (sogenannte Radiosity-Methode, entwickelt an der Comell-Universität) berechnet werden. Ergebnis sind ganz besonders subtile Licht- und Schatteneffekte. In diesem Fall liegt der besondere Gewinn im Detail.
An den Schnittpunkten der beiden Strahlen R1 und R2 entstehen jeweils 2 Schattenfühler. Nur der S2 steht in direkter Verbindung zu einer Lichtquelle; Die anderen Fühler stoßen auf Hindernisse. Also trägt die Lichtquelle, auf die der Fühler zeigt nicht oder vernindert zur Beleuchtung des Schnittpunktes bei.
Bei einem Ray Tracer genügt es nicht, das Lichtmodell für jede Grundfarbe einzeln zu berechnen. Im allgemeinen müssen sogar für jede Grundfarbe eigene Brechungen und eigene Strahlbäume berechnet werden - nicht jedes Material reflektiert und bricht das Licht in der gleichen Richtung, ein Glasprisma beispielsweise bricht jeden Lichtanteil unterschiedlich, Ergebnis ist ein Farbspektrum. Aus Gründen der Rechenzeit verzichtet man allerdings meistens auf derartige Feinheiten.
Jetzt fehlen nur noch die Schatten, die über unseren Häuptern schweben... Sie stellen aber überhaupt kein Problem dar. An jedem Schnittpunkt konstruiert man außer den gebrochenen und reflektierten Strahlen sogenannte ‘Shadow Feeler’, Schattenfühler. Das sind Strahlen, die vom Schnittpunkt aus in Richtung auf jede vorhandene Lichtquelle zeigen. Diese Strahlen müssen jetzt wiederum mit jedem Objekt geschnitten werden. Liegt kein Objekt zwischen Schnittpunkt und Lichtquelle, ist der Schnittpunkt von dieser Lichtquelle voll beleuchtet. Liegt ein nichttransparentes Objekt dazwischen, liegt der Schnittpunkt, auf diese Lichtquelle bezogen, im Schatten. Ist das Objekt dazwischen transparent, entsteht ein Halbschatten, die Wirkung der Lichtquelle auf den Schnittpunkt muß gemindert werden (Bild 4).
Sie sehen, die Anzahl der Schnittpunktberechnungen hat sich inzwischen vervielfacht. Für jede Reflektion und jede Brechung müssen wieder Schnittpunkte der entstehenden Strahlen, für jeden Schnittpunkt vor Anwendung des Lichtmodells Schattenfühler für jede Lichtquelle berechnet und auch diese mit edem Objekt geschnitten werden. Bei Szenen mit vielen Objekten kann das leicht zu 100 (oder auch erheblich mehr) Schnittpunktberechnungen pro Pixel führen. Und die sind bei komplexen Objekten auch erheblich komplizierter als bei Kugeln. Kein Wunder also, daß man auch nach Einsatz aller Beschleunigungstechniken immer noch davon ausgeht, das 800-1000 MFlop für die Real-Time-Berechnung von Ray Tracing-Bildern benötigt werden. Selbst die schnellsten heute verfügbaren Computer benötigen mindestens 10 Minuten für ein Bild, an dem ein ST oder Amiga Jahre zu rechnen hätte.
Dennoch, der Aufwand lohnt sich. Keine andere Technik kann so realitätsnahe Computerbilder erzeugen wie eben Ray Tracing. Und bei wirklich komplexen Szenen ist es auch um die Effizienz der anderen Techniken, die von Objekten und nicht vom Bildschirm ausgehen, nicht mehr so gut bestellt.
Schließlich fällt, wenn man die Fachliteratur verfolgt, auf, daß viele Möglichkeiten oder Feinheiten, die im Labor implementiert sind, in kommerziellen Systemen vernachlässigt sind. Bald werden also noch viel leistungsfähigere Grafiksysteme zur Verfügung stehen.
Es sei noch erwähnt, daß es natürlich auch möglich ist, einen Ray Tracer für Objektbeschreibungen aus Polygonen, wie sie in den Verfahren der letzten Folgen aufgezeigt wurden, zu verwenden. Die Berechnung von Schnittpunkten mit Polygonen ist sogar besonders einfach, dabei ist aber zu beachten, daß selbst einfache Objekte im allgemeinen aus sehr vielen Polygonen zusammengesetzt sind, so daß sehr viele Berechnungen nötig werden. Wenn Sie also solche Objekte verwenden wollen, werden Optimierungsverfahren, wie sie im nächsten Abschnitt beschrieben werden, noch viel wichtiger, als für ‘einfache’ Objektstrukturen wie zum Beispiel mathematische Beschreibungen.
Es gibt im Falle der Verwendung von Polygonen noch etwas zu beachten: Wie Sie bereits aus der letzten Folge wissen, haben Polygone nur eine einzige Oberflächennormale. Und mit den üblichen Lichtmodellen erhalten diese Polygone auch mit einem Ray Tracer immer nur eine einzige Schattierungsintensität. Wie langweilig. Um also eine vernünftige Schattierung zu erreichen, muß, wie beim Phong-Schattierungsverfahren, für jedes Pixel eine Normale interpoliert werden. Die Normale wird auch für die Berechnung der Lichtbrechung und Reflektion benötigt. Polygone erfordern also besondere Rücksicht.
Natürlich haben sie auch ihre Vorteile. Wenn Sie Polygonbeschreibungen verwenden, können Sie ein System konstruieren, das Animationen in Real Time mit Drahtmodellen, schnelle Skizzen mit Gouraud- oder Phongshading und schließlich die endgültige Produktion der Bilder mit einem Ray Tracer ermöglicht. Und das alles mit einer einzigen Objektbeschreibung. Praktisch, nicht?
Verbesserungen
Das Wort ‘Beschleunigungstechniken’ im vorigen Absatz hat Sie hoffentlich neugierig gemacht. Es wurden, gerade in neuester Zeit, einige Algorithmen entwickelt, die Ray Tracing erheblich effizienter machen, und vor allem den fatalen Effekt, daß die Rechenzeit mit steigender Objektanzahl exponential ansteigt (Warum wohl?) auf mindestens lineare Verhältnisse mildem.
Eine Analyse von Ray-Tracing-Programmen hat ergeben, daß das Verfahren über 95% seiner aktiven Rechenzeit mit Schnittpunktberechnungen verbringt. Nahezu alle Optimierungen beschäftigen sich daher mit zwei Fragen: 1. Wie kann man die Schnittpunktberechnungen beschleunigen? und 2. Wie kann man die Zahl der Schnittpunktberechnungen reduzieren?
Ein Baum aus Strahlen wird von oben nach unten aufgebaut. An jeden Knoten werden die neuen Verzweigungen berechnet. Nenn alle Strahlen die Szene verlassen, wird der Baum in umgekehrter Reihenfolge durchgearbeitet; an jeden Knoten wird das Beleuchtungsnodell berechnet, wobei in das Ergebnis die Nerte der bereits berechneten Strahlen eingehen CSiehe Bild 4: Die Summanden Krglrg und Krrlrr). Das Endergebnis an Knoten 1 ist der Nert, der den Pixel, durch das der Strahl führt, zugeordnet wird.
Eine Beschleunigung der Schnittpunktberechnungen ist nur in den seltensten Fällen durch verbesserte mathematische Verfahren möglich. Zum Beispiel wurden die Verfahren für die Schnittpunktberechnung mit parametrischen, freiformbaren Oberflächen in den letzten Jahren stark verbessert. Dennoch liegt das Hauptgewicht bei allen Verbesserungen auf einer Verringerung der Anzahl der Berechnungen.
Eine erste Maßnahme ist es, die Umrisse der darzustellenden Objekte auf konventionelle Weise rechnerisch auf die Bildebene zu projizieren. Dann müssen nur noch die Strahlen verfolgt werden, die innerhalb der Umrisse liegen. Bei sehr komplizierten oder sehr vollen Szenen nützt das leider praktisch nichts.
Sehr gebräuchlich ist die Zusammenfassung mehrerer beieinander liegender Objekte in einer Hierarchie. Beispiel: Objekte sind ein Tisch und eine daraufstehende Obstschale mit Äpfeln. Jetzt kann man diese ganze Gruppe mit einem Volumen umschließen, einer Kugel oder Box etwa. Ein Strahl, der dieses Volumen nicht schneidet, kann auch unmöglich eines der Objekte im Inneren schneiden. Die Obstschale wird ebenfalls samt Inhalt in ein Testvolumen gepackt. Wenn nun ein Strahl die Box der gesamten Szene schneidet, kann man wiederum die Box um die Obstschale testen. Auch hier gilt: Wenn der Strahl die Box nicht trifft, kann er auch keines der Objekte im Innern treffen. Dieses Verfahren nutzt Zusammenhänge innerhalb des Bildes aus und kann dann einige Erleichterung schaffen. Problematisch ist unter Umständen die Auswahl eines vernünftigen Umhüllungsvolumens: es muß einfach zu berechnen sein (am besten eine Kugel), aber auch möglichst gut passen, sonst nützt es nicht viel.
Besonders die Polygonrepräsentierung, bei der ja jedes Objekt aus vielen Einzelpolygonen besteht, für die jeweils ein Schnittpunkt berechnet werden muß, gewinnt viel durch dieses ‘Bounding Box’-Verfahren.
Es gibt ein weiteres Verfahren, das erstmals in einem Artikel vom letzten Jahr (’87) beschrieben wurde. Es nutzt den Umstand aus, daß entsprechend dem Verhalten natürlicher Objekte jedes Pixel den umliegenden Pixeln verhältnismäßig ähnlich ist. Beispiel: Wenn Sie eine Fläche bearbeiten, werden alle Pixel, außer den am Rand liegenden, nur leichte Änderungen gegenüber den umliegenden Pixeln aufweisen. Die Gemeinsamkeiten zwischen den Bildteilen eines Objektes lassen uns dieses Objekt erst als solches erkennen. Diese Eigenschaft kann man zu einer Vorsortierung aller möglichen Strahlen nutzen, womit sich ein annähernd konstantes Verhalten des Algorithmus erreichen läßt. Einer der bestechenden Vorteile des einfachen Ray Tracers, seine simple Implementierung, geht damit aber verloren.
Eine ganze Reihe von Verbesserungen basieren auf einem anderen Prinzip. Hier wird der an sich kontinuierliche, ‘analoge’ Raum in einzelne Raumzellen zerlegt, ähnlich wie ein Rasterbildschirm die Fläche des Bildschirms durch ein Raster aus Pixeln darstellt. Hier gibt es zwei Ansätze:
Der meines Erachtens interessanteste ist ganz neu und basiert auf einer Zerlegung des Raums in gleichmäßig große Raumzellen, exakt den Pixeln des Bildschirms entsprechend. Zum Verfolgen eines Strahles wird jetzt auch keine mathematische Berechnung verwendet, sondern ein Verfahren, das eine dreidimensionale Erweiterung eines Algorithmus’ zum Linienziehen im Zweidimensionalen darstellt. Dieses Verfahren hat den Vorteil, daß ausschließlich Integer-Arithmetik - nicht eine einzige Division ist nötig - verwendet werden kann. Der Strahl wird einfach als Linie im 3D-Raum in die Raumzellen hineingezogen. Wenn er auf eine nicht leere Zelle stößt, ist dies automatisch der Schnittpunkt mit dem nächsten Objekt, der Strahl pflanzt sich ja vom Bildschirm aus beginnend in seiner Richtung fort. Damit spart man sich langwierige Schnittpunktberechnungen mit Objekten, die am Ende den Strahl gar nicht berühren. Die Geschwindigkeitsgewinne des Verfahrens sind enorm: Bilder, die auf traditionelle Weise auf einer VAX vorsichtig geschätzt 40 Tage Rechenzeit benötigt hätten, waren nach dem neuen Algorithmus in zweieinhalb Stunden fertig. Man muß allerdings zwei Schritte beachten: In Experimenten hat sich gezeigt, daß man die Zahl der Raumzellen sorgfältig wählen muß. Zwischen 404040 und 505050 Zellen haben sich als optimal erwiesen. Für jede Raumzelle muß, bevor der eigentliche Tracer seine Arbeit aufnimmt, eine Liste angelegt werden, in der steht, welche Objekte in der Zelle enthalten sind. Wenn der Tracer dann später eine Zelle erreicht, muß er nur kontrollieren, ob die Zelle leer ist. Wenn ja, darf er weiter machen, andernfalls muß er Schnittpunkte nur mit den in der Liste eingetragenen Objekten berechnen.Effizient ist dieser Algorithmus natürlich nur bei komplexen Szenen. Der Grundaufwand ist so hoch, daß bei Szenen mit sehr wenigen Objekten ein traditioneller Ray Tracer vergleichbare Effizienz aufweist (Warum wohl???). Der andere Ansatz zerlegt den Raum in eine Hierarchie von verschieden großen Zellen. Leere Raumgebiete werden zu großen, leeren Zellen, andere Gebiete werden solange unterteilt, bis die Zellen klein genug sind, um eine einfache Beschreibung des Objektteiles zu ermöglichen. Die Strahlverfolgung kann auch in dieser Variante mit einem 3D-Linienalgorithmus erfolgen, es geht aber auch anders. Die Resultate dieses Verfahrens sind nicht ganz so günstig, wie die des vorigen und zudem von der Kohärenz der Szene abhängig. Auch für bestimmte, hochkomplexe Objekttypen wie frei formbare Oberflächen oder fraktale Landschaften gibt es Verfahren, die die bei diesen Objektformen extrem aufwendigen Schnittpunktberechnungen stark beschleunigen.
Eine letzte Gruppe von Verbesserungen befaßt sich mit der Bildqualität. Auch mit Ray Tracing in seiner Grundform ist es nicht möglich, das gesamte physikalische Verhalten von Licht zu simulieren. Neuere Ergänzungen setzen sich zum Ziel, auch die Lichtbeugung an einem Spalt oder die Diffusion in nebelartigen Atmosphären berechnen zu können. Aber dies geht weit über diesen Artikel hinaus. Bei all diesen Veränderungen und Verbesserungen sieht man den ursprünglich so einfach zu implementierenden Algorithmus mit Tränen in den Augen zu einem hochkomplexen Monstrum werden...
Implementierungshinweise
Mit ein paar Hinweisen zur Implementierung soll dieser Teil seinen Abschluß finden.
Es bietet sich förmlich an, den Algorithmus so aufzubauen, das Strahlen auf einen Stack abgelegt werden. Vor dem Aufruf der eigentlichen Tracer-Routine berechnet ein init-Teil den Ausgangsray für ein bestimmtes Pixel, schiebt ihn auf einen Stack und ruft dann den Tracer auf. Dieser holt einen Strahl vom Stack und berechnet Schnittpunkte. Wenn er den nächsten gefunden hat, berechnet er die entstehenden Strahlen und speichert auch diese auf dem Stack. Dann beginnt er von vorne und wiederholt diesen Vorgang solange, bis alle entstehenden Strahlen ins Leere gelangen.
Jetzt geht es umgekehrt: Der Reihe nach werden die Strahlen vom Stack geholt und für ihre Schnittpunkte, die natürlich in der Datenstruktur ‘Ray’ gespeichert sein müssen, wird das Beleuchtungsmodell angewendet. Das Beleuchtungsmodell sollte die Schattenfühler berechnen und damit sein Ergebnis beeinflussen, das zur Helligkeit des jeweiligen Pixels addiert wird.
Wenn der Stack leer ist, ist man wieder am Ausgangspunkt angelangt und kann das Pixel auf die berechnete Helligkeit setzen.
Sie sehen also, daß es überhaupt nicht schwierig ist, einen primitiven Ray Tracer zu implementieren. Allerdings rechtfertigt die Bildqualität eines ST die dafür notwendige Rechenzeit meines Erachtens nicht so ganz. Ein Gouraud-Shading-Algorithmus mit Transparenz, Schatten und Texturemapping ergibt ähnliche Ergebnisse in weit kürzerer Zeit. Aber wer Lust hat, sollte sich doch einmal an eines der Beschleunigungsverfahren machen...
Großes Finale
Meine Damen und Herren, dies ist nun das Ende dieser Grafikserie. Falls Sie irgendwelche Fragen oder besonderen Wünsche zu diesem Thema haben, schreiben Sie uns. Wir werden uns dann bemühen, in einer Fortsetzung diesen Vorschlägen entgegenzukommen. Ich hoffe. Sie haben einen kleinen Einblick in das weite Feld der Computergrafik gewonnen. Zum Schluß möchte ich Ihnen noch ein neues Buch vorstellen, das gerade im Springer Verlag erschienen ist. Es ist wohl die vollständigste Zusammenstellung von Algorithmen für die komplizierteren Probleme der Computergrafik, die bisher erschienen ist. Es beinhaltet von grafischen Datenstrukturen bis zur Simulation natürlicher Phänomene wie Wasser, Feuer oder Wolken, von Lichtmodellen über Methoden zur Berechnung von Schatten und Transparenzeffekten über Beschleunigungstechniken für Ray Tracer einfach alles. Wenn Sie Interesse an Computergrafik haben, müssen Sie dieses Buch einfach lesen. Es ist gut illustriert und erklärt, ein extrem vollständiges Verzeichnis von Originalliteratur rundet das Werk ab. Insgesamt fast 400 Seiten voll mit geballtem Wissen. Ach so, den Titel und die Verfasser habe ich fast vergessen:
Image Synthesis - Theory and Practice von den in der Szene sehr bekannten kanadischen Professoren Nadia Magnenat-Thalman und Daniel Thalmann.
Herausgeber ist der ebenfalls nicht unbekannte Tosiyasu L. Kunii. Erschienen ist das Buch in der Springer-Serie ‘Computer Science Workbench’. Leider ist es nicht ganz billig, 148.- DM kostet es, aber wert ist es dieses Geld auf alle Fälle.
So, mit diesem Tip für Fans verabschiede ich mich endgültig von Ihnen. Tschüß,
Christian Schormann