Raytracing

Eine Grafikkarte fragt für jedes Dreieck, welche Pixel es abdeckt. Ein Raytracer dreht das um und fragt für jedes Pixel, was man sieht, wenn man von der Kamera aus genau dort hindurchschaut. Mit Kugeln und einer Ebene passt das in ein paar Dutzend Zeilen. Ich wollte außerdem wissen, was Schatten und Spiegelungen davon kosten, also lassen sie sich in der Demo einzeln abschalten.

Die Maus bewegt das Licht. Es hängt drei Einheiten über dem Boden, genau über dem Punkt, auf den du zeigst. Unten wechselst du zwischen 80x45, 160x90 und 320x180 Pixeln (das Bild wird immer auf 640x360 aufgezogen) und schaltest Schatten und Reflexionen ein und aus. Rechts zählt die Demo jeden einzelnen Strahl mit.

Ein Strahl pro Pixel

Die Kamera sitzt an einem Punkt, jedes Pixel bekommt eine Richtung. Die Mitte des Pixels wird auf -1 bis 1 umgerechnet und mit Sichtfeld und Seitenverhältnis skaliert, die z-Komponente ist immer 1:

const float sx = (2.0F * u - 1.0F) * aspect * cam.tanHalfFov;
const float sy = (1.0F - 2.0F * v) * cam.tanHalfFov - cam.shift;
return {cam.pos, normalize(Vec3{sx, sy, 1.0F})};

shift schiebt nur den Horizont im Bild nach oben, ohne die Kamera zu kippen. Mit dem Strahl wird jedes Objekt gefragt, ob und wo es getroffen wird. Der kleinste positive Abstand t gewinnt. Einen Z-Buffer braucht man dafür nicht.

Die Kugel ist eine quadratische Gleichung

Ein Punkt auf dem Strahl ist origin + t * dir. Er liegt auf der Kugel, wenn sein Abstand zum Mittelpunkt dem Radius entspricht. Einsetzen ergibt eine quadratische Gleichung in t:

const Vec3 oc = ray.origin - s.center;
const float a = dot(ray.dir, ray.dir);
const float halfB = dot(oc, ray.dir);
const float c = dot(oc, oc) - s.radius * s.radius;
const float disc = halfB * halfB - a * c;
if (disc < 0.0F) return false;

Ist die Diskriminante negativ, geht der Strahl vorbei. Sonst gibt es zwei Lösungen, die nähere gewinnt. Liegt der Startpunkt in der Kugel, ist die nähere negativ und die ferne der Weg hinaus. Die Tests rechnen das von Hand nach: Strahl aus dem Mittelpunkt trifft bei t gleich Radius, ein Strahl bei y = 1,001 an einer Kugel mit Radius 1 geht vorbei, bei y = 1 streift er genau (Diskriminante 0). Der Boden ist einfacher: t = (Höhe - origin.y) / dir.y, und läuft der Strahl parallel zum Boden, gibt es keinen Treffer.

Normale und Licht

Am Treffpunkt ist die Normale (Punkt - Mittelpunkt) / Radius. Wie hell der Punkt wird, sagt das Skalarprodukt aus Normale und Richtung zum Licht: 1, wenn die Fläche genau zum Licht schaut, 0 bei quer, darunter negativ und auf 0 geklemmt. Dazu kommt ein fester Anteil von 0,2, damit die Rückseite nicht schwarz wird:

const float facing = std::max(0.0F, dot(normal, toLight));
Vec3 color = albedo * (kAmbient + (1.0F - kAmbient) * facing * lit);

lit ist 1 oder 0 und kommt vom Schattenstrahl.

Schatten

Ein Punkt liegt im Schatten, wenn zwischen ihm und dem Licht etwas steht. Also geht ein zweiter Strahl vom Treffpunkt zum Licht. Trifft er eine Kugel, bevor er das Licht erreicht, ist lit gleich 0. Der Abstand zum Licht ist die Obergrenze für t, eine Kugel hinter dem Licht wirft also keinen Schatten (auch das steht im Test). Schaut die Fläche vom Licht weg, spart sich die Demo den Strahl, weil dort ohnehin nur das Umgebungslicht übrig bleibt.

Shadow Acne

Der Schattenstrahl startet auf einer Oberfläche. Durch Rundungsfehler liegt sein Startpunkt gern ein Hauch darunter, sagen wir 0,0001. Das Erste, was der Strahl findet, ist dann die Oberfläche selbst bei t knapp über 0. Der Punkt verschattet sich selbst, und auf der Kugel liegt ein Muster aus Punkten und Streifen. Abhilfe ist ein kleiner Versatz entlang der Normalen:

const Vec3 origin = point + normal * bias;   // bias = 0.001

Der Test baut genau das nach: ein Punkt auf der Spitze einer Einheitskugel, 0,0001 unter der Oberfläche, das Licht darüber. Ohne Versatz meldet occluded fälschlich einen Blocker, mit 0,001 nicht. Ein echter Blocker zwischen Punkt und Licht wird mit Versatz weiterhin gefunden. In dieser Szene fällt der Versatz nicht auf.

Spiegelung

Bei der Spiegelkugel wird die Richtung an der Normalen gespiegelt, d - n * 2 * dot(d, n), und der neue Strahl wird wie ein Kamerastrahl weiterverfolgt, also rekursiv:

if (opt.reflections && reflectivity > 0.0F && depth < opt.maxDepth) {
    const Ray bounce{point + normal * kShadowBias, normalize(reflect(ray.dir, normal))};
    color = lerp(color, trace(scene, bounce, depth + 1, opt, rays), reflectivity);
}

Die Kugel spiegelt zu 85 Prozent, der Boden zu 20, der Rest ist die eigene Farbe. Bei höchstens 3 Bounces ist Schluss, sonst würden sich zwei Spiegel gegenüber nie beruhigen. Der Test stellt genau das auf: zwei Spiegelkugeln einander gegenüber, ein Strahl dazwischen, und gezählt werden 4 Strahlen. Der Versatz gegen Acne steckt hier auch drin.

Was es kostet

Bei 320x180 sind das 57.600 Pixel. Ohne Schatten und Spiegelung ist es genau ein Strahl pro Pixel, also 57.600. Mit Schatten sind es rund 93.000, mit Spiegelung rund 100.000, weil Boden und Spiegelkugel einen Strahl mehr schicken, und mit beidem rund 143.000, also 2,5 pro Pixel. Die Auflösung wirkt quadratisch: jede Stufe hat viermal so viele Pixel.

In Millisekunden waren es auf meinem Mac im Browser meist 2 bis 5 für ein Bild bei 320x180 mit allem an. Mein Rechner hatte nebenher zu tun, die Werte streuen also. Ohne Schatten und Spiegelung war es in meinen Messungen am schnellsten, mit allem an etwa das 1,6-fache.

Damit es auf langsameren Geräten nicht hängt, rendert die Demo pro Frame nur so viele Zeilen von oben, wie in 8 Millisekunden passen, und macht im nächsten Frame weiter. Die orange Linie im Bild zeigt, wo sie gerade ist, unter der Linie steht noch das alte Bild. Mit auf ein Fünfundzwanzigstel gedrosselter CPU (DevTools) braucht ein Bild rund 50 Millisekunden und wird über mehrere Frames gezeichnet. Auf einem echten Handy habe ich es nicht probiert.

Stolperfallen

Die Kachelfarbe des Bodens kommt aus floor(x) + floor(z). Mit einem bloßen Cast auf int wäre die Kachel um 0 doppelt so breit, weil -0,5 und 0,5 beide zu 0 werden. Deshalb prüft ein Test auch negative Koordinaten. Die Normale muss Länge 1 haben, sonst stimmt weder die Helligkeit noch die Spiegelung. Und der Boden darf nur treffen, wenn t positiv ist: ein Strahl nach oben schneidet die Ebene hinter der Kamera.

Den Code findest du im Repo unter raytracing. Alle Demos der Serie sammelt das Projekt Game Dev Snippets.