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.