Raytracing
Ein Raytracer färbt eine Probe, indem er einer Linie folgt. Die Linie beginnt an der Kamera, an einer Lampe oder an einem früheren Treffer und läuft in eine Richtung, bis der Algorithmus aufhört. Die erste Frage ist geometrisch. Welche Fläche liegt auf dieser Linie am nächsten? Arthur Appel hat 1968 bei IBM mit diesem Test feste Körper schattiert und die Gebiete im Schatten markiert. Das Beleuchtungsmodell von Turner Whitted, 1980, ging weiter. Vom Treffer aus konnte es einen Reflexionsstrahl schicken, einen Brechungsstrahl und einen Schattenstrahl zu jeder Lampe. Dreidimensionale Computergrafik führt die Linie weiter bis zu Kajiyas Rendergleichung von 1986 und zum Path Tracing, das Whitteds festes Strahlenbäumchen durch Zufallsstichproben ersetzt. Was diese Stichproben kosten und welches Rauschen sie lassen, steht in Licht, Material und das gerechnete Bild.
Die Suche frisst die Zeit. Liegen in einer Szene mehr Dreiecke, als man einzeln prüfen will, verbringt ein Test jedes Dreiecks gegen jeden Strahl die meiste Zeit mit Fehltreffern, die eine Schachtel hätte verwerfen können. Eine Beschleunigungsstruktur, sehr oft eine Hüllkörperhierarchie, packt die Primitive in geschachtelte Schachteln. Der Strahl geht die Schachteln ab, die er wirklich trifft. Kameramodell, Material und die Wahl des nächsten Strahls wechseln mit dem Algorithmus. Der Gang durch die Schachteln bleibt gemeinsam.
Steven G. Parker, James Bigler, Andreas Dietrich, Heiko Friedrich, Jared Hoberock, David Luebke, David McAllister, Morgan McGuire, Keith Morley, Austin Robison und Martin Stich haben beschrieben, wie man diesen Gang teilt, in OptiX: a general purpose ray tracing engine, ACM Transactions on Graphics, Band 29 (2010), 13 Seiten, DOI 10.1145/1778765.1778803. McGuire war am Williams College und bei NVIDIA. Die übrigen Autoren waren bei NVIDIA. Die Fassung von 2010 lief auf den Quadro-, GeForce- und Tesla-GPUs der Firma, über CUDA. Ältere interaktive Tracer, darunter OpenRT, Manta, Razor und Arauna, waren um einen Renderer oder um eine Maschine herum gebaut. Arbeiten, die Raytracing schon auf eine GPU gebracht hatten, jagten Geschwindigkeit. OptiX jagte ein Programmiermodell.
Die Engine weiß nicht, was eine Lampe ist. Schatten und Reflexionsgrad fehlen ihr ebenfalls. Beides gehört dem Programm, das sie aufruft. OptiX gibt eine Handvoll kleiner Programme, jedes für einen einzelnen Strahl geschrieben, und einen Compiler zur Laufzeit, der sie zu einem Kernel zusammenfügt. Die Rekursion schreibt weiterhin der Programmierer, so wie ein Whitted-Shader rekursiv ist. Bündeln, Umsortieren und der Bau der Beschleunigungsstruktur bleiben in der Engine. Ein Closest-Hit-Programm verteilt keine Arbeit auf der GPU.
Die Programme
Sieben Programmarten behandeln jeweils einen Strahl. Ein Hüllkörper-Programm steht daneben und rechnet an der Geometrie, nicht am Strahl, damit die Beschleunigungsstruktur eine Schachtel zum Einsetzen hat. Der Aufsatz zählt dieses Programm extra. Die Tabelle hält den ganzen Satz.
| Programm | Wann es läuft |
|---|---|
| Strahlerzeugung | Eingang. Oft eine Kopie je Pixel. |
| Schnitt | Während des Gangs. Berührt dieses Primitiv den Strahl, und wo? |
| Hüllkörper | Beim Bau der Struktur. Eine Schachtel, die das Primitiv sicher enthält. |
| Closest Hit | Einmal, am nächsten Treffer. Der Oberflächenshader. |
| Any Hit | Bei jedem gemeldeten Treffer, in beliebiger Reihenfolge. Darf den Strahl beenden oder den Treffer übergehen. |
| Miss | Der Strahl hat die Szene verlassen. Eine Hintergrundfarbe oder eine Umgebungskarte. |
| Exception | Der Strahl ist gescheitert, oder eigener Code hat geworfen. |
| Selector Visit | An einem Selector-Knoten. Wählt, in welches Kind der Strahl geht. |
Die Strahlerzeugung ist der Eingang eines Laufs. Ein Aufruf startet viele Kopien. Bei der gewöhnlichen Kamera baut jede Kopie einen Strahl für ein Pixel, verfolgt ihn und speichert eine Farbe. Dieselbe Programmform kann Photonen streuen, Licht vorberechnen oder Strahlanfragen annehmen, die ein OpenGL-Durchgang schon abgelegt hat. Der Schnitt ist die geometrische Prüfung. Ein Dreieck, eine Kugel, ein Zylinder, oder etwas ganz ohne Netz. Abbildung 1 des Aufsatzes enthält eine prozedurale Julia-Menge. Die Schachtel eines prozeduralen Primitivs ist manchmal nur eine Schätzung. Die Schätzung muss das Primitiv enthalten. Eine zu weite Schachtel verlängert den Gang. Das Bild bleibt dasselbe.
Closest Hit läuft ein einziges Mal, sobald der nächste Schnitt feststeht. Das ist der Oberflächenshader. Er darf schattieren, er darf weitere Strahlen losschicken, und er schreibt das Ergebnis in die Nutzlast des Strahls. Any Hit läuft auf dem Weg dorthin, einmal je Schnitt, den der Gang meldet, und die Meldungen dürfen in beliebiger Reihenfolge kommen. Von dort kann der Strahl sofort enden. So verhält sich ein Schattenstrahl, der ein Hindernis gefunden hat. Der Treffer kann auch übergangen werden. So stanzt eine Alpha-Textur ein Loch, ohne die Suche neu zu beginnen. Miss läuft, wenn innerhalb des Intervalls nichts getroffen wurde. Dort liegt eine flache Hintergrundfarbe oder eine Umgebungskarte. Exception läuft, wenn ein Strahl scheitert: der Rekursionsstapel ist über den Speicher des Threads hinausgewachsen, oder ein Pufferindex lag außerhalb. Eigener Code kann eine Ausnahme werfen. Selector Visit läuft an einem groben Knoten und wählt ein Kind. Detailstufen sind der schlichte Gebrauch. Ein ferner Strahl bekommt das grobe Modell.
Die Nutzlast ist ein Datensatz, den man selbst definiert und an den Strahl hängt. Schattierung und Schattenabschwächung reisen darin. Eine feste Lichtstruktur, in die man schreiben würde, gibt es nicht. In der ersten Abbildung des Aufsatzes stehen Path Tracing, die Julia-Menge, Photon Mapping, Sichtlinien- und Kollisionsprüfungen in großem Maßstab, Whitted-Schattierung bewegter Geometrie und Ambient Occlusion. Die Zusammenfassung nennt noch Kollisionserkennung, Anfragen für künstliche Intelligenz und wissenschaftliche Rechnungen wie Schallausbreitung. Ein Strahl ist in diesem Entwurf eine Anfrage. Das Bild ist eine Sorte Antwort.
Der Szenengraph
Die Geometrie liegt in einem Kontext, als gerichteter Graph. Ein Gruppenknoten hat Kinder und eine Beschleunigungsstruktur. Er kann der obere Stock eines zweistufigen Gangs sein. So verschiebt man starre Körper, ohne den ganzen Baum neu zu bauen. Eine Geometriegruppe ist ein Blatt. Sie hält Primitive und Materialien und hat eine eigene Beschleunigungsstruktur. Ein Transform-Knoten hat ein Kind und eine Matrix mit 4 mal 3 Einträgen, genug für eine affine Abbildung. Ein Selector-Knoten hat Kinder und ein Visit-Programm. Jeder Knoten darf die Wurzel sein, also können Kamerastrahl und Schattenstrahl in verschiedenen Graphen beginnen. Knoten dürfen mehrere Eltern haben. Das ist Instancing: ein Netz an vielen Orten, ein Material für Formen, deren Schnitttests sich unterscheiden.
Eine Geometrieinstanz ist die Verbindung. Sie bindet ein Geometrieobjekt an einen Satz Materialien. Schnitt- und Hüllkörperprogramme hängen an der Geometrie. Closest-Hit- und Any-Hit-Programme hängen am Material. Die Trennung ist Absicht. Ein Dreiecksformat, das ein Rasterisierer schon benutzt, kann in diesem Format bleiben, weil das Schnittprogramm es dort liest, wo es liegt. Eine Kopie in ein tracer-eigenes Netz ist nicht mehr der Preis für den Eintritt.
Die Reflexionsformel war 2010 schon alt. Offen blieb eine programmierbare Suche auf einer parallelen Maschine, die ein neues Verfahren nicht jedes Mal neu schreiben musste. Als Computerbilder alltäglich wurden, rechnete man ein Bild per Raytracing, während es noch auf dem Schirm stand.