sebadorn.de

Im Path Tracing verwendet man spezielle Datenstrukturen für die Geometrie, um diese schneller gegen die Strahlen testen zu können. Eine der üblichsten ist dabei die Bounding Volume Hierarchy (BVH) – ein Binärbaum, der die Szene immer weiter unterteilt. Einen solchen Baum würde man normalerweise rekursiv durchlaufen. Auf der GPU mit OpenCL steht jedoch keine Rekursion zur Verfügung.

Was man daher macht, ist, selbst einen kleinen Stack zu verwalten, in dem man sich den nächsten zu besuchenden Knoten merkt. Dieser Stack benötigt jedoch zusätzlichen privaten Speicher, welcher knapp bemessen ist, und dadurch die Anwendung ausbremst. Wünschens­wert ist daher ein Verfahren, das ohne Stack auskommt.

Aufbau und Ablauf

• Jeder Knoten hat entweder genau zwei oder keine Kindknoten.
• Jeder Knoten hat zudem ein Attribut nextNode.
  • Für den linken Kindknoten zeigt nextNode auf den rechten Geschwisterknoten.
  • Für den rechten Kindknoten zeigt nextNode auf den Elternknoten.

Vom Wurzelknoten aus wird immer zuerst dem linken Kindknoten gefolgt. Falls der Strahl die Bounding Box nicht trifft, es sich um einen Blatt­knoten handelt oder zuletzt ein rechter Knoten besucht wurde, dann wird als nächstes der Knoten besucht, auf den nextNode zeigt. Ist man wieder beim Wurzel­knoten angelangt, beendet der Algorithmus.

Nachteil: Knoten werden auf dem Weg nach oben erneut besucht. Ein unnötiger Schritt, der nur zusätzliche Zeit in Anspruch nimmt.

Optimierung

Die Optimierung ist denkbar einfach. Dafür muss jediglich der nextNode der rechten Knoten angepasst werden. Anstatt auf den Elternknoten, können rechte Kindknoten direkt auf den nächsten zu testenden Knoten zeigen.

Dafür setzt man zunächst nextNode immer weiter auf einen höheren Elternknoten, bis es sich bei diesem um einen linken Kindknoten handelt. Danach setzt man nextNode auf den rechten Geschwister­knoten. Auf diese Weise werden alle bereits besuchten Eltern­knoten über­sprungen. Existiert kein rechter Kindknoten, ist man beim Wurzel­knoten angelangt und zeigt auf diesen, was den Endpunkt markiert.

Den so erzeugten Baum kann man dann folgendermaßen abwandern:

int index = 0;

do {
	bvhNode node = scene->bvh[index];

	float tNear = 0.0f;
	float tFar = INFINITY;

	bool isNodeHit = (
		intersectBox( ray, node, &tNear, &tFar ) &&
		tFar > 0.00001f && ray->t > tNear
	);

	// In case of no hit: Go right or up.
	index = node.nextNode;

	if( !isNodeHit ) {
		continue;
	}

	// Not a leaf node, progress further down to the left.
	if( !isLeaf( node ) ) {
		index = node.leftChild;
	}
	// Node is leaf node.
	else {
		intersectFaces( scene, ray, node, tNear, tFar );
	}
} while( index > 0 );

Anmerkung: Links/rechts

Welcher der beiden Kindknoten als „linker“ und welcher als „rechter“ gesetzt wird, ist egal. Ich setze als linken Kindknoten denjenigen mit mehr Ober­fläche. Mehr Ober­fläche bedeutet, dass ihn potentiell mehr Strahlen treffen und man so eventuell ein früheres Ende erreicht. Tatsächlich hat diese Vorsortierung die Performance gering­fügig verbessert.

Resultat

Mein Algorithmus kommt wie gewünscht ohne Stack aus. Weiterer Speicher wird nur für eine Variable index, sowie ein neues Knoten-Attribut nextNode benötigt. Beim Abwandern des Baumes wird jeder Knoten höchstens ein einziges Mal besucht.

Zumindest in meiner Implemen­tierung [1] verbesserten sich die Render-Zeiten in allen meinen Test-Szenen. Dies kann aber auch an einer schlechten Implemen­tierung des Stack-basierten Algorithmus liegen, mit dem ver­glichen wurde. Ich habe beide Verfahren im Projekt belassen und versuche sie von Zeit zu Zeit weiter zu optimieren und erneut zu vergleichen.

---

[1] Vorbereitung der BVH-Datenstruktur und BVH traversal.