Der Algorithmus

Ray Tracing kann man als rekursiven Algorithmus z.B. wie folgt implementieren. Dabei wird vereinfachend nur von Intensität gesprochen.

RayTrace
begin
for all EyeRays do
Intensity $=$ Trace(EyeRay,0);
od
end

Die Prozedur RayTrace berechnet für alle Kamerastrahlen die Intensitäten. Dabei wird je Strahl die folgende Funktion Trace aufgerufen. Die Berechnung der eigentlichen Intensitäten ist in der Funktion LightModel versteckt.

Trace(Ray,RecDepth)
begin
Intensity$=$Nothing;
if NextHitPoint found then
for all ShadowRays at NextHitPoint do
Intensity$+=$LightModel(NextHitPoint,ShadowRay);
od
if RecDepth$<$MaxDepth then
Intensity$+=$Trace(ReflectedRay,RecDepth+1);
Intensity$+=$Trace(TransmittedRay,RecDepth+1);
fi
Intensity$+=$LightModel(NextHitPoint,AmbientLight);
else Intensity$=$BackGround
fi
return Intensity;
end

Beim Berechnen der ShadowRays muss man beachten, dass bei transparenten Objekten auch durch das Material beleuchtet werden kann, d.h. man muss den Winkel zwischen ShadowRay und Normalenvektor in die Betrachtung einbeziehen.

Ray Tracing ist ein Abtastvorgang mit den damit verbundenen Problemen. Eines dieser Probleme liegt im Aliasing (Treppeneffekte). Ein Vorschlag ist distributed Ray Tracing, d.h. eine geringfügige, zufällige Störung der Strahlen abweichend von ihrem idealen, strahlenoptischen Verlauf und ein Abtasten mit mehr als einem Strahl pro Pixel.

Die Beschleunigungsverfahren greifen an allen Faktoren der oben vorgestellten Formel, d.h. einerseits an der Anzahl der zu verfolgenden Strahlen, andererseits aber auch bei jedem einzelnen Strahl an dessen Berechnungsaufwand, insbesondere dem Auffinden des nächstgelegenen Schnittpunktes. Zudem können parallele Verfahren beim Ray Tracing leicht eingesetzt werden.

Also:

• Hardwareunterstützung
  • Einsatz von Parallelrechnern
  • Spezielle Programmierung der Prozessoren (z.B. nutzen von SSE und MMX)
  • Ausnutzen der Speicherhierarchien
  • Ausnutzen von Graphikhardware
• Softwareunterstützung
  • weniger Strahlen verfolgen
    • adaptives Abtasten und Interpolieren
    • adaptive Strahlaufspaltung je nach erwartetem Einfluss auf Bild
    • Ausnutzen von Softwarecaches (z.B. Lichtcache)
• Strahlen schneller verfolgen
  • optimierte Schnittpunktberechnung
    • umgebende Volumen
    • effiziente Algorithmen
  • Reduktion der Schnittpunktberechnungen durch Raumunterteilung
    • uniforme Raster
    • multilevel Raster
    • Octrees
    • BSP-Bäume
    • kd-Bäume
    • höher dimensionale Unterteilung
    • andere Unterteilungen
• Ausnutzen von Kohärenz

Beschleunigungsverfahren durch Strahlreduzierung

Die Anzahl der Strahlen kann durch Verringerung der Rekursionstiefe, spezielle Behandlung der ShadowRays, sowie Undersampling-Techniken reduziert werden.

EyeRays brauchen prinzipiell nicht verfolgt zu werden, da man auf einfachere Algorithmen (z.B. Scanline-Algorithmen) zurückgreifen kann. Ist für ein Pixel das zu sehende Objekt gefunden, kann der Schnittpunkt und Normalenvektor berechnet werden. Ohne Verspiegelung oder Transparenz endet auch dann bereits das `Tracen'.

Bemerkung: Man beachte allerdings, dass schnelle Verfahren--wie eben der Scanline-Algorithmus--nicht unbedingt mit allen Basisobjekten gut zurechtkommen. Eventuell ist es notwendig alle Basisobjekte in Polygone zu zerlegen, was jedoch dann die Ränder krummliniger Objekte wiederum verschlechtert. Hier muss man wohl auch einen Kompromiss zwischen Qualität und Geschwindigkeit machen.

Die Rekursionstiefe

entscheidet über die sichtbaren Mehrfachspiegelungen, d.h. will man hier eine gewisse Anzahl erreichen, muss auch eine gewisse Rekursionstiefe zugelassen werden. Es zeigt sich jedoch, dass je nach Materialeigenschaften die Intensität, die ein Strahl transportiert, abnimmt. Als ein weiteres Abbruchkriterium kann nun eine untere Schranke für diese Intensität eingfügt werden. Je nach Beleuchtungsmodell muss diese Schranke anders gewählt werden, allerdings kann man im einfachsten Modell das Produkt der materialabhängigen Abschwächungsfaktoren auf dem Pfad im Strahlbaum nehmen.

ShadowRay-Erzeugung:

Prinzipiell kann jede Lichtquelle einen Einfluss auf den darzustellenden Punkt haben, somit lässt sich im Allgemeinen nichts bezüglich der Anzahl der Strahlen erreichen, allerdings können besondere Eigenschaften der Lichtquelle ausgenutzt werden, so dass die Schnittpunktberechnung für einen ShadowRay stark vereinfacht wird.

• Begrenzt strahlende Lichtquellen erfordern keinen ShadowRay, wenn der NextHitPoint außerhalb der Reichweite der Lichtquelle liegt.
• Da es genügt ein Objekt zu finden, das bezüglich einer Lichtquelle Schatten wirft, kann man sich eine Liste (kleiner Cache) der zuletzt schattenwerfenden Objekten halten. Man testet zuerst die Elemente dieser Liste, bevor man einen eigentlichen ShadowRay aussendet. (Dies erfordert allerdings eine bestimmte Auswertungsreihenfolge der Schnittpunktberechnungen, so dass im gleichen Schatten liegende Punkte möglichst zeitlich nah ausgewertet werden.)
• Man erzeugt um eine Lichtquelle eine Schattenkarte (ShadowMap), in die die von dieser Lichtquelle beleuchteten Objekte eingetragen werden, da nur beleuchtete Objekte Schatten werfen können. Der Aufbau dieser Karte erfolgt durch eine Diskretisierung einer umgebenden Fläche (z.B. ein Würfel).

  Die Schattenkarte kann durch einen einfachen Vorberechnungsschnitt je Lichtquelle berechnet werden. Liegt nun das Objekt nicht in der Liste des zugehörigen Bereiches, so liegt es im Schatten. Im anderen Fall müssen die in der Liste vorkommenden Objekte als potentielle Schattenspender untersucht werden.

  Der Speicherplatz ist maximal
  

  $$O(\char93 \mbox{Diskretisierung}*\char93 \mbox{Lichtquellen}*\char93 \mbox{Objekte})$$
  
  
  allerdings ist dies in der Praxis oft wesentlich geringer, da nicht jede Lichtquelle jedes Objekt beleuchtet und wenn dann auch nur in einem kleinen Raumwinkel.

Anzahl der EyeRays:

Die Methode des Undersampling reduziert die Anzahl der ausgesendeten EyeRays. Dies führt jedoch dazu, dass nicht mehr alle Bildpunkte exakt berechnet werden.

In der einfachsten Version wird der Zwischenpunkt einfach durch Interpolation der Farbwerte der beiden Randpunkte berechnet. Als erste Verbesserung kann untersucht werden, ob beide Randpunkte mit dem EyeRay das selbe Objekt treffen. Die Interpolation wird nur dann vorgenommen, wenn dies der Fall ist, sonst wird der Bildpunkt normal berechnet. Als weitere Verbesserung kann der Mittelpunkt auf jeden Fall korrekt berechnet werden, allerdings erübrigt sich ein Tracen, falls die Strahlen der Randpunkte das gleiche Objekt treffen, man nimmt einfach an, es wird das gleiche Objekt getroffen. Die Interpolation findet also erst auf zweiter Rekursionsstufe statt. Statt das Verfahren nur in der Bildzeile anzuwenden, ist es auch möglich, dies über Zeilen hinweg durch versetzte Anordnung der Abtastpunkte zu implementieren.

Undersampling birgt eine erhöhte Gefahr des Aliasing. Oft werden Bilder mit Supersampling, d.h. einer höheren Auflösung, berechnet und anschließend auf die eigentliche Auflösung reduziert. Da durch die höhere Auflösung mehr Information vorhanden ist (höhere Abtastfrequenz), können Alias-Effekte reduziert werden. Man wendet also zweckmäßigerweise an Kanten oder anderen Übergängen Supersamling an und an einheitlichen Bildausschnitten Undersampling.