Die Bedeutung der frühen Strahlbeendigung und der Durchquerung von vorne nach hinten bei der Strahlverfolgung

7

Ich bin neu in der Computergrafik. In diesen Tagen habe ich versucht zu verstehen, wie Raytracing mithilfe einer Beschleunigungsdatenstruktur funktioniert. Ich bin mehrmals auf den Begriff "Early Ray Termination" gestoßen, habe ihn auch mehrmals über das Internet angesehen, konnte aber keine zufriedenstellende Erklärung dafür finden. Was bedeutet es, einen Strahl vorzeitig zu beenden und warum müssen wir das tun?
Außerdem ist mir aufgefallen, dass der Begriff "Front-to-Back-Traversal" fast jedes Mal erwähnt wird, wenn von "Early Ray Termination" die Rede ist. Wie funktioniert konkret die Durchquerung von vorne nach hinten (zum Beispiel bei einem kd-Baum)?

user2651062
quelle

Antworten:

5

Front-to-Back-Traversal ist die Idee, dass wir beim Durchlaufen eines Strahls durch die Beschleunigungsstruktur Knoten untersuchen möchten, die sich vor, dh näher an der Kamera, vor anderen Knoten befinden. Wenn Sie nur den ersten Schnittpunkt mit einer Oberfläche wünschen (wie beim Raytracing üblich), müssen Sie keine Knoten dahinter durchqueren, wenn Sie einen Schnittpunkt im vorderen Knoten erhalten. Als mögliche Kreuzung würde es später sein als die, die Sie bereits gefunden haben. Das spart Zeit.

In einem kd-Baum haben Sie beispielsweise an jedem Knoten eine Aufteilungsebene, die den Raum in zwei untergeordnete Knoten unterteilt. Sie würden zuerst zu dem Kind hinabsteigen, das näher an der Kamera liegt, und nur wenn dort keine Kreuzungen gefunden werden, steigen Sie zu dem anderen Kind hinab.

Early Ray Termination scheint ein Begriff zu sein, der im Zusammenhang mit der Volumenwiedergabe verwendet wird. Wenn Sie einen Strahl durch ein Medium bewegen, das Licht abschwächt, wie Nebel, Rauch, trübe Flüssigkeiten usw., besteht ab einer bestimmten Entfernung keine Möglichkeit mehr, dass der Strahl mehr Einfluss auf das Bild hat. Wenn Sie dichten Nebel mit einer Sichtweite von 10 Metern haben, kann ein Objekt in 11 Metern Entfernung nicht gesehen werden.

Sie können den Abstand vorberechnen, bei dem die Dämpfung etwa 99% erreicht (sie erreicht nie ganz 100%, nähert sich ihr jedoch exponentiell an). Es gibt keinen Grund, den Strahl gegen weiter entfernte Objekte zu schneiden. Wenn Sie also die Beschleunigungsstruktur verwenden, können Sie einfach alle Knoten außerhalb dieser Entfernung verwerfen. Tatsächlich wird der Strahl zu einem Liniensegment, das mit einer festen Länge abgeschlossen ist. Wenn es innerhalb dieser Länge nichts trifft, macht es keinen Sinn, weiter zu prüfen. (Ein weiterer Fall, in dem Strahlen mit begrenzter Länge nützlich sind, sind Schattenstrahlen. Sie möchten sie nur bis zur ursprünglichen Lichtquelle zurückverfolgen. Darüber hinausgehende Schnittpunkte sind für den Schatten irrelevant.)

Nathan Reed
quelle
Danke @NathanReed. 1 weitere Frage. Angenommen, ich möchte zuerst die Baumbreite durchqueren, ich bin auf Stufe 0 (dh an der Wurzel des Baums habe ich den Baum noch nicht geteilt, ich habe einen Begrenzungsrahmen mit allen Grundelementen der Szene). Ich teile den Begrenzungsrahmen entlang einer Achse so, dass der linke untergeordnete Knoten derjenige ist, der näher an der Kamera liegt. Dann finde ich, dass ein bestimmter Strahl R den linken Knoten schneidet. R sollte in Bezug auf den richtigen untergeordneten Knoten und alle seine zukünftigen untergeordneten Knoten vorzeitig beendet werden. Aber ich muss immer noch den Schnittpunkt von R mit den zukünftigen untergeordneten Knoten dieses linken Knotens testen, oder?
user2651062
1
@ user2651062 Normalerweise hätten Sie den gesamten Baum erstellt, bevor Sie ihn durchlaufen. Ihr Kommentar lässt es so klingen, als würden Sie versuchen, gleichzeitig zu bauen und zu durchqueren? Oder was meinst du mit "zukünftigen untergeordneten Knoten"? In jedem Fall müssen Sie alle untergeordneten Knoten durchlaufen, die den Strahl oder das Segment schneiden. Wenn es das linke Kind schneidet, steigen Sie in das linke Kind ab und wiederholen den Vorgang für seine Kinder. Möglicherweise müssen Sie in beide untergeordneten Elemente absteigen, wenn beide den Strahl / das Segment schneiden.
Nathan Reed