Bounding Volume Hierarchy
Die Geschwindigkeit beim Raytracing hängt im Wesentlichen von der Ermittlung des Schnittpunkts des Augstrahls mit der Geometrie ab.
Der triviale Ansatz testet für jeden(!) Strahl in jedem(!) Schritt die ganze(!) Geometrie. Da eine komplexe Geometrie z.B. beim Raymarching eine kleine Schrittweite benötigt, ist der Aufwand höher als linear zur Anzahl der Geometrieelemente.
Zur Beschleunigung wird daher entweder die Szene (Geometry Subdivision) oder der Raum (Space Subdivision) unterteilt.
Bekannte Raumunterteilungen sind Rektilineare Gitter, Octrees, kd-Bäume, Binary Space Partition Trees.
Geometrieunterteilungen basiert i.d.R. auf Bounding Volume Hierachys (BVH). Die gesamte Geometrie wird dabei in begrenzende Volumina eingebaut, die ihrerseits wieder in einer Hierarchie zusammen gefasst werden.
CC BY-SA 3.0 Wikimedia User:Schreiberx
Am beliebtesten sind als Grundstruktur Axis-Aligned Bounding Boxes (AABB). Diese sind schnell zu erstellen (Minimum und Maximum der Vertices einer Geometrie komponentenweise ermitteln), brauchen nicht viel Speicher, und können z.T. auch vorberechnet werden.
Von neuerer Grafikhardware wird über DirectX12 und Vulkan Raytracing unterstützt (NVidia 2060 aufwärts, ATI Radeon RX6800 aufwärts, PS5, XBox Series X). In OpenGL sind keine Erweiterungen für Raytracing vorgesehen.
Dabei werden v.a. die Ermittlung des Schnittpunkts sowie die Erstellung der Beschleunigungsstrukturen mit speziellen Einheiten unterstützt. Prinzipiell ist die Implementierung opak (d.h. ein Hersteller kann sich frei entscheiden), praktisch nutzen derzeit alle BVHs mit AABBs. Dreiecke werden in Hardware unterstützt, aber es kann beliebige implizite Geometrie programmiert werden.
Prinzipiell ist Raytracing auch mit älterer Hardware implementierbar, aber sehr viel langsamer (bis zu 2 Größenordnungen). Und man muss die Beschleunigungsstrukturen selber erstellen und im Shader auswerten.
Empfehlenswert: Raytracing Gems, ein frei verfügbares (CC BY-NC-ND 4.0) Buch der “Gems” Reihe über Raytracing inkl. Nutzung in DirectX.