Raytracing

Das grundlegende Verfahren  

Das grundlegende Verfahren ist wie schon gesagt recht einfach zu erklären. Es kehrt dabei gewissermaßen die Vorgänge der Bildentstehung im menschlichen Auge (oder auch einer Kamera) um. Anstatt das Lichtstrahlen auf Gegenstände fallen, reflektiert werden, ihre Farbe ändern und schließlich ins Auge fallen, führt man diesen Prozess rückwärts durch.

Man legt einen Augpunkt fest und sendet aus diesem sog. Sehstrahlen durch einen virtuellen Bildschirm in die Szene aus. In der einfachsten Variante prüft man nun einfach, welche Gegenstände der Sehstrahl in seinem weiteren Verlauf in der Szene trifft. Die Farbe, die der virtuelle Bildschirm an der entsprechenden Stelle annimmt ist somit einfach die Farbe am ersten Schnittpunkt des Strahles. Man nennt dieses Verfahren Strahlverfolgung oder Raytracing .

Das Prinzip soll noch einmal durch folgende Abbildung verdeutlicht werden:

Das Faszinierende: Schon dieses noch sehr naive Verfahren genügt, um ein korrektes perspektivisches Abbild der 3D-Szene zu erhalten, ohne dass man sich um irgendeine wüste Matrizentransformation oder perspektivische Projektion, wie es in sog. Rasterizer-Systemen wie DirectX der Fall wäre, hätte kümmern müssen. Betrachten wir einmal eine Demo-Szene, wie sie mit der bisherigen Technik gerendert (engl. hier: berechnen) aussehen würde:

Tatsächlich ist Raytracing auch überhaupt keine neue Technik. Schon Maler der Frührenaissance machten sich vor über 500 Jahren bereits vergleichbare Techniken zu Nutze, indem sie von ihrem Auge aus Fäden durch einen Schirm zum abzubildenden Objekt zogen und so dreidimensionale Konturen korrekt abbilden konnten, wohlgemerkt bevor die perspektivische Zeichnung erfunden wurde. Im Gegenteil, die Perspektive (von lat. perspicere hindurchsehen) hat in eben solchen Techniken ihren Ursprung!

Mehr Realismus - Licht und Schatten  

Mit dem bisherigen Ansatz des Raytracings können wir unsere Szenen in perspektivisch korrekt projizierte, bunte Flächen auf dem Bildschirm verwandeln. Sonderlich realistisch sieht das allerdings noch nicht aus, die plastische Wirkung fehlt. Klar: Es fehlen Licht und Schatten!

Glücklicherweise lassen sich beide wunderbar einfach in das Raytracing-Konzept integrieren. Die Überlegung ist dabei folgende: Ein Körper ist im Licht, wenn Lichtstrahlen von einer Lichtquelle zu ihm gelangen können und nicht durch einen anderen Gegenstand blockiert werden (Schattenwurf). Wie üblich durchlaufen wir den natürlichen Vorgang beim Raytracing rückwärts, was uns zu folgendem Verfahren führt:

Um die Farbe am Schnittpunkt des Sehstrahls mit dem Gegenstand zu berechnen, schieße zu jeder Lichtquelleder Szene einen Licht-/Schattenstrahl . Trifft dieser auf seinem Weg dorthin auf einen Gegenstand, so verdeckt dieser ja die Lichtquelle, ihr Licht kann also die zurückgegebene Farbe nicht beeinflussen (Schatten). Andernfalls verrechne Gegenstands- und Lichtfarbe und addiere das zur Ergebnisfarbe hinzu.

Auch dieser Schritt wird mit einer Skizze verdeutlicht:

Nun bleibt nur noch eines zu klären: Betrachten wir eine von vorne beleuchtete Kugel, so sie vorne auch am hellsten, während die Helligkeit zu den Seiten hin abnimmt. Mit Schattenwurf ist dieses Phänomen nicht zu erklären, wohl aber mit dem Winkel des Lichteinfalls:

Die Farbe des Lichts wirkt sich umso stärker aus, je senkrechter es auf den Körper fällt.

Da die Licht/Schattenberechnung ebenfalls auf dem Aussenden von Strahlen beruht, werden wir kaum Aufwand haben, das Ganze mit vorhandenen Mitteln auszudrücken. Der resultierende Effekt ist allerdings gewaltig - Unsere Demoszene sieht nun so aus:

Rekursives Raytracing - Reflexionen  

Reflexionen an spiegelnden Oberflächen (Christbaumkugeln) sind das Thema schlechthin, das Raytracing berühmt macht. Sonst eine sehr komplizierte Berechnung ist es nämlich ein Klacks, diese mit Strahlverfolgung zu simulieren.

Trifft der Sehstrahl auf ein reflektierendes Objekt, berechne in welche Richtung der Strahl reflektiert wird (Reflexionsgesetz). Berechne die reguläre Farbe am Schnittpunkt und führe dann Raytracing mit dem reflektierten Strahl als neuem Sehstrahl durch. Verrechne beide Farben.

Diese Technik, bei der sich Raytracing ggf. selbst mit neuen Strahlen aufruft, nennt sich rekursives Raytracing. Der damit erreichte Grad an Realismus kann sich absolut sehen lassen:

Bis zu dieser Stelle haben wir mit Perspektive, Verdeckungsberechnung, Licht, Schattenwurf und Reflexion eine ordentiche Palette an Fähigkeiten für unsere Engine erlernt, die es nun zu implementieren gilt.

Die Implementierung  

Nun, da der Rundgang durch die theoretischen Grundlagen des Raytracings mathematikarm und programmiersprachenunabhängig absolviert wurde, geht es an die Implementierung. Diese wird in diesem Tutorial in F# erfolgen. Wer an Implementierungen in anderen Sprachen interessiert ist, findet neben den allgemein gehaltenen Informationen und Gleichungen am Ende des Artikels auch Beispiele in anderen Sprachen.

Strahlen und Vektoren  

Computergrafik ist normal extrem voll von höherer Mathematik. Beim Raytracing kann man zwar glücklichwerweise vieles auf einfacherem Niveau beschreiben, aber um einen "Grundbegriff" kommt man nicht herum: Den Vektor

Da wir uns im Dreidimensionalen aufhalten, meine ich im weiteren mit Vektor den dreidimensionalen Vektor, auch wenn es diese in jeder anderen Dimension ebenfalls gibt.

Einen Vektor kann man sich grob als die Koordinaten eines Punktes im Raum vorstellen, sprich x, y und z-Koordinate. Genauer gesagt ist er eine Verschiebung im Raum, ein Pfeil, wobei man mit der Schreibweise

meint, dass dieser Pfeil eine Einheit nach rechts, vier nach oben und drei nach vorne zeigt. Mit Vektoren kann fast genau so gerechnet werden wie mit Zahlen, man kann sie addieren (Pfeile hintereinander hängen), voneinander abziehen, mit einer Zahl multiplizieren und den eingeschlossenen Winkel bestimmen.

Strahlen , die beim Raytracing natürlich eine zentrale Rolle spielen, lassen sich durch zwei Vektoren p und u0 beschreiben. Für einen Strahl S schreibt man allgemein:

Dieser Strahl beginnt "an der Pfeilspitze von p" und breitet sich die Richtung von u0 aus. Die Zahl t gibt dabei an, wie weit man vom Ausgangspunkt in diese Richtung geht. Daraus ergibt sich auch, dass t größer als 0 sein muss, da der Strahl ja sich ja sonst in seine Gegenrichtung, also hinter den Anfangspunkt ausbreiteten würde (Strahlen sind Halbgeraden). Der Richtungsvektor u0 hat dabei stehts die Länge 1, was viele Berechnungen vereinfacht.

Ein konkretes Beispiel für einen Strahl:

Dieser Strahl beginnt am Punkt (1|1|1) und breitet sich je 0,6 Einheiten nach rechts, 0,8 nach vorne aus. Setzt man in diese Gleichung den Wert t = 5 ein, so landet man auf dem Punkt (4|1|5).

Vektoren und Strahlen werden wir überall in unserem Programm benötigen, daher werden wir auch entsprechende Datentypen dafür schreiben, die alle benötigten arithmetischen Operatoren unterstützen.

Für Interessierte verweise ich sonst an dieser Stelle auf diese Einführung zur Vektorrechnung.

Schnittstellenberechnung  

Für Strahlen haben wir nun eine mathematische Definition. Doch wie sieht das mit den Objekten unserer Szene aus und wie kommen wir an die Schnittkoordinaten unseres Sehstrahls?

Glücklicherweise ist das Vorgehen hier nicht viel anders als beim Strahl selbst. Für alle grundlegenden Objekte können wir vektorielle Gleichungen finden, die alle enthaltenen Punkte erfüllen müssen. Zum Berechnen der Schnittstellen werden Strahl und Objekt einfach gleichgesetzt. Zwar sind die Vektorgleichungen von Kugeln, Ebenen und Dreiecken nicht vorrangig Thema dieses Tutorials (sondern eher der Mathematik-Oberstufe), ein kurzes Beispiel für derartige Berechnungen führe ich allerdings trotzdem auf.

Eine zu rendernde Ebene wird beschrieben durch einen Punkt auf dieser Ebene sowie einen sog. Normalenvektor, der auf dieser senkrecht steht. Nehmen wir z.B. eine Ebene, die sich nach oben und nach hinten in den Raum ausbreitet (x2,3-Ebene) und um 7 Einheiten nach rechts verschoben ist:

In diese Gleichung setzen wir nun einfach den Term des Beispielstrahls aus vorigem Kapitel ein bestimmten den Parameter t.

Umgeformt ergibt sich

In einem Abstand von 10 Einheiten vom Ausgangspunkt trifft also unser Sehstrahl im Punkt (7|0|9) auf die Ebene.

Die Beschreibung von Szenen  

Nun aber zur eigentlichen Implementierung. Es gilt zunächst festzulegen, wie eine zu rendernde Szene eigentlich beschrieben wird.

Kein Problem: Wir benötigen

1. Eine Menge von abzubildenden Gegenständen im Raum
2. Eine virtuelle Kamera
3. Eine Hintergrundfarbe
4. Eine Menge von Lichtern mit ihrer Position und Farbe.

Unsere Datenstruktur für Szenen kann daher so definiert werden:

type Scene = {
  Objects    : ISceneObject list;
  Lights     : Light list;
  Camera     : Camera;
  Background : Color
}       

Listing 1: Ein Szenentyp

Wir erkennen die verwendeten Typen Light, Camera, Color und ISceneObject. Viel verwunderliches beinhalten die drei ersten nicht und ihr Zweck sollte klar sein. Wo es wieder interessant wird, ist die Repräsentation der Szenenobjekte, hier beschrieben durch die Schnittstelle ISceneObject.

Welche Funktionalitäten muss ein Objekt unterstützen, um "geraytraced" werden zu können?

Zunächst muss man seinen Schnittpunkt mit einem Strahl berechnen können. Als Ergebnis bekommen wir den Parameter t aus der Strahlgleichung, aus dem wir den Schnittpunkt berechnen können. Wenn mehrere Schnittpunkte auftreten, ist immer nur der kleinste positive t-Wert interessant, da dieser den ersten Schnittpunkt angibt, auf den der Strahl in seinem Verlauf trifft (alle anderen wären daher nicht sichtbar).

Zweitens brauchen wir das Lot an einem Körper, das auf diesem immer rechtwinklig steht, um Reflexion und Lichtintensität zu berechnen. Dieses Lot nennen wir Normalenvektor .

Drittens hat jedes Objekt eine Oberfläche mit einer bestimmten Materialbeschaffenheit. Zum Material gehört z.B. die Farbe an jeder Stelle, die Glanzfarbe, ob und wie stark der Körper reflektiert und wie "rau" seine Oberfläche ist.

Das führt zu folgenden Definitionen:

type Surface = {
    Diffuse    : Vector3 -> Color;
    Specular   : Vector3 -> Color;
    Roughness  : Vector3 -> float;
    Reflection : Vector3 -> float
}

type ISceneObject = 
    abstract IntersectRay : Ray -> float
    abstract Surface      : Surface
    abstract Normal       : Vector3 -> Vector3 

Listing 2: Weitere Definitionen

Die Schreibweise a -> b symbolisiert dabei Funktionen vom Typ a nach b.

Diese Schnittstelle wird dann von verschiedenen Primitiven, das sind grundlegende geometrische Formen wie Kugeln, Ebenen, Dreiecke, implementiert.

Die Kamera  

Die Kamera ist die Struktur, die beschreibt, von wo und wie wir unsere Szenen abbilden. Genauer gesagt definiert die Kamera den Augpunkt und die Lage des virtuellen Bildschirms, durch den wir unsere Sehstrahlen schießen. Das führt uns zu folgenden Komponenten:

1. Der Augpunkt
2. Der Ansichtspunkt, auf den die Kamera gerichtet ist. Er ist das Zentrum des virtuellen Bildschirms
3. Die Ausdehnung des virtuellen Bildschirms

Mittels Vektorrechnung kann man nun jedes Pixel auf dem Zielbild auf den virtuellen Bildschirm der Kamera projizieren, wodurch man den entsprechenden Sehstrahl für dieses Pixel aufstellen kann.

Code  

Nun soll's aber endlich Code geben. Natürlich werde ich hier nicht den kompletten Code aufführen, allerdings greife ich ein paar interessante Stellen heraus. Gut erkennbar ist die deklarative, bis weilen pseudocode-artige Natur von F#, die bei diesem hochgradig funktionalen Problem perfekt zur Geltung kommt.

Folgender Code berechnet den ersten Schnittpunkt, auf den ein gegebener Strahl in der aktuellen Szene trifft.

(* Ersten Strahl-Schnittpunkt berechnen *)
let firstIntersection ray =
   let intersections = seq { for obj in scene.Objects do 
                                 let t = obj.IntersectRay ray
                                 if t >= 0.0 then yield (t, obj) }
                                  
   if intersections |> Seq.isEmpty
       then None
       else Some(intersections |> Seq.minBy fst)

Listing 3: Schnittpunktberechnung

Die wesentliche Berechnung ist dann nur, die Schnittpunkte zu bestimmen und die Farben der Lichtquellen zu addieren.

(* Erzeugte Farben aller Lichtquellen aufsummieren *)
let lightSum = 
    scene.Lights |> Seq.sumBy (fun light ->
         
         (* Strahl zur aktuellen Lichtquelle nach Schatten werfenden Hindernissen absuchen *)
         let lightRay = Ray.FromPoints(light.Position, pos)
                  
         match firstIntersection lightRay with
         | Shaded -> Color.Zero
         | Illuminated -> 
             (* Farben berechnen ... *)
    )   

Listing 4: Farben und Lichter

Für den letztlichen Raytracer benötigen wir nun lediglich die Rekursion.

(* Komplette Strahlverfolgung eines Sehstrahls von der Kamera zum Bildschirmpunkt (x, y) *)
member this.Raytrace(x, y) =
    let ray = Ray.FromPoints(scene.Camera.CameraPos, voxel(x, y))
    
    (* Rekursives Strahlverfolgen (Strahl, Verbleibende Rekursionstiefe) *)
    let rec raytraceRec ray depth =
        match firstIntersection ray with
        | None         -> scene.Background
        | Some(t, obj) -> 
            let pos = ray.At t
            let surface = obj.Surface
            let norm = obj.Normal pos
            
            (* Reflektierten Strahl vorberechnen (Reflexionsgesetz) *)
            let d = ray.Direction 
            let reflectedDir = (d - (2.0 * norm .* d) * norm).Unit
            
            (* Erzeugte Farben aller Lichtquellen aufsummieren *)
            let lightSum = ...
            
            (* Wenn eine reflektierende Oberfläche getroffen wurde, rekursiv den reflektierten Strahl weiterverfolgen *)
            if surface.Reflection pos <= 0.0 || depth <= 0
                then lightSum + new Color(0.5, 0.5, 0.5)
                else 
                    let reflectedRay = new Ray(pos + 0.0001 * reflectedDir, reflectedDir)
                    lightSum + surface.Reflection pos * raytraceRec reflectedRay (depth - 1) 
                                            
    raytraceRec ray recursiveDepth

Listing 5: Rekursion

Ausblick und Fazit  

Das war's - Ein kompletter Raytracer mitsamt Kugel- und Ebenenprimitiven, Rekursion und Lichtquellen passt in gerade einmal 10KB F#-Quellcode.

Aber natürlich kratzt auch diese Implementierung nicht annährend am Rand des Möglichen. Gerade das macht den Raytracing zu einer unglaublich interessanten Technologie. Das grundlegende Programm ist sehr klein, gut nachzuvollziehen und trotzdem schon sehr detailgetreu. Daher eignet es sich sehr gut, mit neuen Programmiersprachen zu experimentieren. Nebenbei eignet es sich sehr gut zur Ausführung auf Mehrkernprozessoren, da die einzelnen Strahlen einander nicht bedingen und daher parallel berechenbar sind.

Wer aber möchte, kann das Verfahren immer weiter verfeinern. Als naheliegendste Erweiterung wäre beispielsweise denkbar, die Reflexionen der Lichtstrahlen weiterzuverfolgen. Aber auch Nebeleffekte, Lichtbrechungen und transparente Oberflächen sind ins Raytracing-Konzept ohne weiteres integrierbar. Die Liste von möglichen Erweiterungen ist je nach Kenntnisstand schier endlos. Für weichere Kanten kann man mehrere zufällige Strahlen pro Pixel verschießen (diffuses Raytracing), Baumstrukturen können den Raum in kleinere Portionen hacken und die Geschwindigkeit der Kollisionserkennung enorm steigern - bis hin zur Berechnung von globalen Beleuchtungsverhältnissen und Quanteneffekten ist alles recht, um noch mehr Realismus zu erzielen. Das Resultat, das solche Tools erzeugen können, ist gewaltig (aber die Algorithmen auch entsprechend komplex):

Ein Beispiel für einen derart professionellen Raytracer ist das Programm PovRay, das sogar über eine eigene Sprache zur Beschreibung und Generation von Szenen verfügt.

Das obligatorische Beispielprogramm in diesem Tutorial kann da natürlich nicht mithalten. Eine C#-Benutzeroberfläche und ein eigenes Szenenformat hat es aber trotzdem spendiert bekommen - Voilà:

Downloads und Links  

Download

Demoprojekt [230.035 Bytes]

(Benötigt .NET-Framework 4.0 und F#)

Links zum Thema

1. LukeH's Raytracer in C#3.0 - Eine C#-Implementierung, auf der Teile des Codes im Beispielprojekt sowie die gerenderte Demoszene basieren
2. Linq raytracer - Ähnliche Implementierung, die aus einem einzigen Linq-Ausdruck besteht

Abbildungsverzeichnis

1. http://upload.wikimedia.org/wikipedia/commons/6/69/358durer.jpg
2. http://upload.wikimedia.org/wikipedia/commons/8/83/Ray_trace_diagram.svg
3. http://en.wikipedia.org/wiki/File:Glasses_800_edit.png

Ihre Meinung  

Falls Sie Fragen zu diesem Tutorial haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.