Ray Tracing

Question 1

Voxel

Accepted Answer

Die meiste Zeit beim Ray Tracing wird für die Schnittpunktberechnung benötigt. Grundidee ist also nur mit möglichen Kandidaten zu schneiden. Weitere Möglichkeiten zur Beschleunigung sind u.a.: - Effiziente Algorithmen für Schnittpunktberechnung und Vektoroperationen- Cache-Optimierung- Kohärenzausnutzung- Parallelisierung

Question 2

Uniform-Grid (Voxel)

Accepted Answer

Über die Welt wird ein uniformes Gitter von Würfeln gelegt (Voxel). Für jedes Voxel wird eine Kandidatenliste ersetllt, welche die Objekte innerhalb des Voxels referenziert. Vom Voxel des Strahlursprungs geht man in Strahlrichtung durch das Voxelgitter (3D-Bresenham) und testet die Kandidaten innerhalb. Dies geschieht so lange, bis mindestens ein Objekt geschnitten wird. Es werden immer alle Objekte in einem Voxel getestet und bei Schnitten der vorderste Schnittpunkt ermittelt. Die Voxelgröße ist benutzerdefiniert, in dynamischen Szenen müssen die Kandidatenlisten aktualisiert werden. Objekte werden u.U. mehrfach geschnitten. Diese können in einer Liste gespeichert werden. Das Protokollieren ist jedoch an sich wiederum aufwändig.

Question 3

Implementierung

Accepted Answer

Es wird die Ableitung einer abstrakten Klasse für die Datenstrukturen erstellt. Die Datenstruktur wird im Konstruktor aufgebaut und es wird eine Bounding-Box bestimmt. Das Objekt muss dann nur überprüft werden, wenn der Strahl die Bounding-Box durchdringt. Für die Traversierung werden zwei Hauptroutinen benötigt: Ermittlung des vordersten Schnittpunktes (muss sortieren) Schattenfühler (muss nicht sortieren)

Question 4

Traversierung

Accepted Answer

Ein Voxel kann durch zwei Punkte beschrieben werden. Geradenparameter wird als Vektor berechnet: Vektor t = (Vektor vmax - Vektor p) / vektor d mit der oberen Ecke des Voxels vmax , dem Startpunkt p und der Strahlrichtung d . Damitberechnet man zwei t-Parameter für den Schnitt des Strahls mit der x- und der y-AchseFür den Schnittpunkt des Strahls mit dem nächsten Voxel berechnen sich die Inkremente mit Delta t = Vektor s / vektor t . Der Vektor s beschreibt hier die Kantenlänge der Voxel.

Question 5

Octree

Accepted Answer

Da viele Voxel in der Szene oft keine Geometrie enthalten, lohnt es sich deren Größe nicht uniform zu gestalten. Eine Möglichekeit eine Szene mit unterschiedlich großen Voxeln zu generieren, ist es einen Octree zu erstellen. Dafür wird der Szenenwürfel in 8 Teilwürfel unterteilt. Dies wird rekursiv fortgesetzt, bis maximal Objekte in einem Voxel enthalten sind. Um die Schnittpunkte mit den enstprechenden Voxeln zu erhalten wird ebenfalls rekursiv von außen nach innen gearbeitet.

Question 6

Formel für Schnitt mit Bounding Box

Accepted Answer

Vektor t min = Vektor (b min - Vektor p ) / Vektor d (Analog Max) Die Szene wird verfehlt, wenn maxtmin < mintmax Ansonsten können die Schnitte mit dem Mittelgitter (also der nächsten Rekursionsstufe) berechnet werden über: (midtx , midty) = 1/2 (Vektor t minx, + tmaxx)

Question 7

Schnitt mit hierarchischen Strukturen

Accepted Answer

Option 1: Zuerst Transformationen entlang des Pfades akkumulieren und Objekt entsprechend in Weltkoordinaten umformen. Danach Schnitt des Strahls mit dem Objekt bestimmen. Option 2: Transformation des Strahls (Punkt und Richtung) in das lokale KS des Objekts (Inverse der akkumulierten Matrix). Der Schnitt mit dem transformierten Strahl liefer dann wie gehabt die baryzentrischen Koordinaten und Geradenparameter.

Question 8

Bounding Volumes

Accepted Answer

Komplexe geometrische Objekte werden durch einfache Geometrien angenähert. Der Raytracer schneidet immer zuerst mit der äußersten Bounding-Box, um zu entscheiden, ob er in der Hierarchie-Ebene nach unten geht. Gängige BB-Typen sind: Bounding Sphere (einfachen Schnittpunkttest, jedoch oft zu groß) Oriented Bounding-Box (bessere Approximation, komplexerer Test) Bounding-Slabs / k-DOPs (discretely oriented polytypes) Axis-Aligned Bounding-Box (einfache Berechnung)

Question 9

Schnittpunkttest

Accepted Answer

Tests werden zuerst mit dem Bounding-Volume durchgeführt. Existiert kein Schnittpunkt, dann können auch innere Objekte nicht getroffen werden. Andernfalls müssen die inneren Objekte überprüft werden. Durch Zusammenfassen der Bounding-Volumes entsteht eine Baumstruktur, in der die Szenenobjekte Blätter sind. Ein Schnittpunkttest entspricht dann der Traversierung der Hierarchie. Schlägt der Test fehl, kann der gesamte Teilbaum ignoriert werden.

Question 10

Hierarchie-Traversierung (Priority-Queue)

Accepted Answer

Um zusätzlich die Lageder Bounding-Volumes zu berücksichtigen kann eine Priority-Queue eingeführt werden. Diese sortiert nach der Entfernung des Schnittpunktes zum Startpunkt des Strahls. D.h. es wird immer zuerst das Bounding-Volume behandelt, das den geringsten Abstand zum Startpunkt hat. Wird ein Schnittpunkt gefunden, werden die Kinder des Bounding-Volumes in die Queue gegeben. Auch wenn ein Objektschnittpunkt gefunden wird, muss immer die gesamte aktuelle Queue abgearbeitet werden, da das gesuchte Objekt nicht unbedingt in der nächsten Bounding-Box sein muss. Für die PQ ist keine vollständige Ordnung notwendig, da in jedem Durchlauf nur das Element mit der kleinsten geschätzten Distanz benötigt wird. Eine Effiziente Umsetzung ist z.B. mit einem Heap möglich.

Question 11

Erzeugung von Bounding-Volume-Hierarchien

Accepted Answer

Von Hand Durch Modellierung (Szenengraph) Bottom-Up (rekursives Zusammenfassen) Top-Down (Sortieren der Objekte entlang einer Koordinatenachse, Heuristik nach Goldsmith/Salmon)

Question 12

Binary Space Partitioning (BSP)

Accepted Answer

Der Raum wird rekursiv in zwei Teilräume aufgeteilt (getrennt durch eine Ebene). Ein Binärbaum speichert die Räume als Knoten und Objekt(listen) als Blätter. Dies wird fortgeführt bis entweder die Anzahl der inneren Objekte unterhalb eines Schwellwerts liegt, oder eine maximale Baumtiefe erreicht wird.

Question 13

Polygon-Aligned BSP

Accepted Answer

Die Orientierung der Splitting-Plane wird hier durch ein Polygon festgelegt. Die Auwahl erfolgt z.B. durch das least-crossed-criterium, d.h. es wird die Ebene gewählt, welche die wenigsten Schnitte mit anderen Polygonen aufweist. Die Erzeugung eines effizienten PA-BSPs ist somit recht aufwändig und Polygone müssen ggf. entlang der Splitting-Plane aufgespalten werden.

Question 14

Axis-Aligned BSP

Accepted Answer

Die Orientierung der Splitting-Plane erfolgt hier ausschließlich parallel zu den Koordinatenachsen. Die Wahl der Ebene ist dabei immer entlang der längsten Kante. Sie wird entweder genau mittig positioniert oder so, dass die Objektanzahl in den beiden Teilräumen gleich groß ist. Die in zwei Teilräumen enthaltenen Objekte werden aufgespalten oder dupliziert. ! Werden auch oft als k-d Tree bezeichnet, da sie mehrdimensionale binäre Suchbäume sind.

Question 15

Traversierung

Accepted Answer

Der Sichtstrahl wird zuerst am Bounding-Volume der gesamten Szene geclippt. Daraus ergibt sich das Strahlintervall, in dem sich ein Schnittpunkt befinden kann. Für jeden Knoten (also Unterraum) wird der Schnitt mit der Splitting-Plane berechnet und mit dem Strahlintervall verglichen.

Question 16

Was ist Raytracing?

Accepted Answer

Das Bild wird durch verschiedene Strahlen abgetastet - Abtastung je Pixel des Bildschirms - → Dauer skaliert mit Größe des Bildschirms - Berechnung des vordersten Schnittpunkts mit der Szenengeometrie - → Dauer skaliert mit Größe der Szene

Question 17

Unterschied zu OpenGL

Accepted Answer

OpenGL: Render Dreieck → berechne getroffene Pixel - gute Parallelisierung - schnelle Hardware - aber nur aus einem Betrachterwinkel... - Raytracing: Render Pixel → berechne getroffene Geometrie - Parallelisierung je nach Beschleunigung schwierig - Viele Effekte möglich

Question 18

Was bringt Raytracing? Welche Effekte?

Accepted Answer

- Primärstrahl: vorderster Schnittpunkt mit Geometrie- → gesehener Punkt - Strahl an Normale reflektieren und erneut testen- → Reflektionen - Strahl leicht ablenken und weiter verfolgen- → Refraktionen - Strahl neu starten zu Lichtquelle- → Schatten

Question 19

Was bringt Raytracing? Welche Effekte? II

Accepted Answer

Viele Strahlen in Richtung flächiger Lichtquelle→ Weiche Schatten Viele Strahlen in Umgebung→ Ambient Occlusion Viele Strahlen in Umgebung und dann ins Licht→ Indirekte Beleuchtung (1. Indirektion) Effekte mehrfach kombinieren→ Path Tracing→ Korrekte Beleuchtung

Question 20

Was bringt Raytracing? Welche Effekte? III

Accepted Answer

Path Tracing ausgehend von Auge und Lichtquelle→ Bidirektionales Path Tracing → schneller - Ausgehend von Lichtquelle Strahlen verschießen und speichern→ Photon Mapping → korrekte schnelle Kaustiken - Durch Path Tracing Strahl zu Lichtquelle, Strahl dann abwandeln und weiter testen→ Metropolis Light Transport (MLT)

Question 21

Uniform Grid

Accepted Answer

Raytracing Beschleunigung Szene wird in Boxen (“Voxel”) eingeteilt - Während Strahltraversierung kein direkter Test mit Objekten der Szene, sondern erst mit Voxeln - Test nur mit Objekten, die in getroffenen Voxeln liegen

Question 22

Uniform Grid Vor und Nachteile

Accepted Answer

+ Gute Beschleunigung + Schnell aufzustellen - Hoher Speicherverbrauch... - Kein Level-of-Detail

Question 23

Hierarchische Datenstrukturen

Accepted Answer

Gewähren Verfeinerung dort, wo es benötigt wird Sparen Speicherplatz

Question 24

Octree

Accepted Answer

- Verfeinerung der Voxelstruktur nur dort, wo es benötigt wird - in kritischen Bereichen bessere Auflösung - bessere Speicherplatznutzung

Question 25

Andere Ansätze:

Accepted Answer

- Nicht 2*2*2 gleich große Kindknoten wie Octree - 2 Kindknoten mit dynamischer Trennschicht → KD-Tree - 2 Kindknoten an Bounding Boxen der enthaltenen Objekte orientiert→ Bounding Volume Hierarchie (BVH)

Question 26

KD-Tree

Accepted Answer

2 Kinder - Dynamische Splitting Plane - Aber wo Splitting Plane setzen? - Median aus Geometrie berechnen - → langsam wegen Sortierung - Kalkulieren mit SAH (Surface Area Heuristic) - → nicht unbedingt die beste...

Question 27

BVH

Accepted Answer

Statt Voxelgitter werden Bounding Volumes (BVs) verwendet, um Strahl nicht direkt mit gesamter Geometrie zu testen Erst einmal Schnittest mit einfacher Geometrie- Kugel oder Box oder ähnliches - Hilfsgeometrie muss das eigentliche Objekt komplett umspannen (Bounding Volume) - Wird Bounding Volume geschnitten, dann Test mit eigentlicher Geometrie - Bounding Volume so klein wie möglich

Question 28

Bounding Volumes, die mehrere Bounding Volumes umspannen

Accepted Answer

Bounding Volume Hierarchie - BV um gesamte Szene - Darin BVs um Teilszenen - Immer weitere Verschachtelung - Wird ein BV nicht mit einem Ray geschnitten, dann müssen auch die darin liegenden BV oder Geometrien nicht getestet werden

Question 29

Priority Queue:

Accepted Answer

Teste BVH von oben nach unten (top-down) - Für jedes getroffene BV: Sortiere alle Kinder in die Queue - Für jede getroffene Geometrie: Sortiere Geometrie in Queue - Nutze die Distanz für richtige Stelle in der Queue- Wird eine Geometrie aus der Queue genommen, dann beende Verfahren

CG (Fach) / Ray Tracing (Lektion)