Ist russisches Roulette wirklich die Antwort?

21

Ich habe gesehen, dass in einigen Implementierungen der Pfadverfolgung ein Ansatz namens Russisches Roulette verwendet wird, um einige der Pfade auszusondern und ihren Beitrag unter den anderen Pfaden zu teilen.

Ich verstehe, dass anstatt einem Pfad zu folgen, bis er unter einen bestimmten Beitragsschwellenwert fällt, und ihn dann aufzugeben, ein anderer Schwellenwert verwendet wird und Pfade, deren Beitrag unter diesem Schwellenwert liegt, nur mit einer geringen Wahrscheinlichkeit beendet werden. Der Beitrag der anderen Pfade erhöht sich um einen Betrag, der der Aufteilung der verlorenen Energie aus dem abgeschlossenen Pfad entspricht. Mir ist nicht klar, ob dies eine durch die Technik eingeführte Verzerrung korrigieren soll oder ob die gesamte Technik selbst notwendig ist, um Verzerrungen zu vermeiden.

Gibt das russische Roulette ein unbefangenes Ergebnis?
Ist russisches Roulette für ein unvoreingenommenes Ergebnis notwendig ?

Das heißt, würde die Verwendung eines winzigen Schwellenwerts und die Beendigung eines Pfads in dem Moment, in dem dieser Schwellenwert unterschritten wird, zu einem stärker oder weniger stark voreingenommenen Ergebnis führen?

Konvergieren beide Ansätze bei einer willkürlich großen Anzahl von Stichproben zu einem unverfälschten Ergebnisbild?

Ich möchte den Grund für die Verwendung des russischen Roulette-Ansatzes verstehen. Gibt es einen signifikanten Unterschied in Geschwindigkeit oder Qualität?

Ich verstehe, dass die Energie unter anderen Strahlen umverteilt wird, um die Gesamtenergie zu erhalten. Könnte diese Umverteilung jedoch nicht noch durchgeführt werden, wenn der Strahl beim Unterschreiten eines festgelegten Schwellenwerts abgebrochen würde, anstatt nach Erreichen dieses Schwellenwerts eine zufällig festgelegte Lebensdauer zu haben?

Umgekehrt, wenn die Energie, die durch das Beenden eines Strahls verloren gehen würde, ohne seine Energie neu zu verteilen, schließlich ohnehin verloren geht (da die Strahlen, auf die es neu verteilt wird, schließlich auch beendet werden), wie verbessert sich die Situation?

monte-carlo pathtracing Trichoplax
quelle

26

Um das russische Roulette zu verstehen, schauen wir uns einen sehr einfachen Rückwärtspfad-Tracer an:

void RenderPixel(uint x, uint y, UniformSampler *sampler) {
    Ray ray = m_scene->Camera.CalculateRayFromPixel(x, y, sampler);

    float3 color(0.0f);
    float3 throughput(1.0f);

    // Bounce the ray around the scene
    for (uint bounces = 0; bounces < 10; ++bounces) {
        m_scene->Intersect(ray);

        // The ray missed. Return the background color
        if (ray.geomID == RTC_INVALID_GEOMETRY_ID) {
            color += throughput * float3(0.846f, 0.933f, 0.949f);
            break;
        }

        // We hit an object

        // Fetch the material
        Material *material = m_scene->GetMaterial(ray.geomID);
        // The object might be emissive. If so, it will have a corresponding light
        // Otherwise, GetLight will return nullptr
        Light *light = m_scene->GetLight(ray.geomID);

        // If we hit a light, add the emmisive light
        if (light != nullptr) {
            color += throughput * light->Le();
        }

        float3 normal = normalize(ray.Ng);
        float3 wo = normalize(-ray.dir);
        float3 surfacePos = ray.org + ray.dir * ray.tfar;

        // Get the new ray direction
        // Choose the direction based on the material
        float3 wi = material->Sample(wo, normal, sampler);
        float pdf = material->Pdf(wi, normal);

        // Accumulate the brdf attenuation
        throughput = throughput * material->Eval(wi, wo, normal) / pdf;


        // Shoot a new ray

        // Set the origin at the intersection point
        ray.org = surfacePos;

        // Reset the other ray properties
        ray.dir = wi;
        ray.tnear = 0.001f;
        ray.tfar = embree::inf;
        ray.geomID = RTC_INVALID_GEOMETRY_ID;
        ray.primID = RTC_INVALID_GEOMETRY_ID;
        ray.instID = RTC_INVALID_GEOMETRY_ID;
        ray.mask = 0xFFFFFFFF;
        ray.time = 0.0f;
    }

    m_scene->Camera.FrameBuffer.SplatPixel(x, y, color);
}

IE. Wir hüpfen durch die Szene und akkumulieren dabei Farbe und Lichtschwächung. Um vollständig mathematisch unbefangen zu sein, sollten Bounces ins Unendliche gehen. Aber das ist unrealistisch und, wie Sie bemerkt haben, visuell nicht notwendig. Bei den meisten Szenen ist der Beitrag zur endgültigen Farbe nach einer bestimmten Anzahl von Sprüngen, z. B. 10, sehr, sehr gering.

Um Rechenressourcen zu sparen, ist die Anzahl der Bounces bei vielen Pfadverfolgern stark begrenzt. Dies fügt Voreingenommenheit hinzu.

Das heißt, es ist schwer zu entscheiden, was dieses harte Limit sein soll. Einige Szenen sehen nach zwei Bounces großartig aus. andere (etwa mit Übertragung oder SSS) können bis zu 10 oder 20 dauern.

Wenn wir zu niedrig wählen, wird das Bild sichtbar verzerrt. Wenn wir jedoch zu hoch wählen, verschwenden wir Rechenleistung und Zeit.

Eine Möglichkeit, dies zu lösen, besteht darin, den Pfad zu beenden, nachdem wir eine Dämpfungsschwelle erreicht haben. Dies fügt auch Voreingenommenheit hinzu.

Das Klemmen nach einer Schwelle wird funktionieren , aber wie wählen wir die Schwelle aus? Wenn wir zu groß wählen, wird das Bild sichtbar verzerrt, zu klein und es werden Ressourcen verschwendet.

Russian Roulette versucht, diese Probleme unvoreingenommen zu lösen. Hier ist zunächst der Code:

void RenderPixel(uint x, uint y, UniformSampler *sampler) {
    Ray ray = m_scene->Camera.CalculateRayFromPixel(x, y, sampler);

    float3 color(0.0f);
    float3 throughput(1.0f);

    // Bounce the ray around the scene
    for (uint bounces = 0; bounces < 10; ++bounces) {
        m_scene->Intersect(ray);

        // The ray missed. Return the background color
        if (ray.geomID == RTC_INVALID_GEOMETRY_ID) {
            color += throughput * float3(0.846f, 0.933f, 0.949f);
            break;
        }

        // We hit an object

        // Fetch the material
        Material *material = m_scene->GetMaterial(ray.geomID);
        // The object might be emissive. If so, it will have a corresponding light
        // Otherwise, GetLight will return nullptr
        Light *light = m_scene->GetLight(ray.geomID);

        // If we hit a light, add the emmisive light
        if (light != nullptr) {
            color += throughput * light->Le();
        }

        float3 normal = normalize(ray.Ng);
        float3 wo = normalize(-ray.dir);
        float3 surfacePos = ray.org + ray.dir * ray.tfar;

        // Get the new ray direction
        // Choose the direction based on the material
        float3 wi = material->Sample(wo, normal, sampler);
        float pdf = material->Pdf(wi, normal);

        // Accumulate the brdf attenuation
        throughput = throughput * material->Eval(wi, wo, normal) / pdf;


        // Russian Roulette
        // Randomly terminate a path with a probability inversely equal to the throughput
        float p = std::max(throughput.x, std::max(throughput.y, throughput.z));
        if (sampler->NextFloat() > p) {
            break;
        }

        // Add the energy we 'lose' by randomly terminating paths
        throughput *= 1 / p;


        // Shoot a new ray

        // Set the origin at the intersection point
        ray.org = surfacePos;

        // Reset the other ray properties
        ray.dir = wi;
        ray.tnear = 0.001f;
        ray.tfar = embree::inf;
        ray.geomID = RTC_INVALID_GEOMETRY_ID;
        ray.primID = RTC_INVALID_GEOMETRY_ID;
        ray.instID = RTC_INVALID_GEOMETRY_ID;
        ray.mask = 0xFFFFFFFF;
        ray.time = 0.0f;
    }

    m_scene->Camera.FrameBuffer.SplatPixel(x, y, color);
}

Russisches Roulette beendet einen Pfad zufällig mit einer Wahrscheinlichkeit, die umgekehrt dem Durchsatz entspricht. Daher ist es wahrscheinlicher, dass Pfade mit geringem Durchsatz, die nicht viel zur Szene beitragen, beendet werden.

Wenn wir dort aufhören, sind wir immer noch voreingenommen. Wir verlieren die Energie des Weges, den wir zufällig beenden. Um es unparteiisch zu machen, erhöhen wir die Energie der nicht abgeschlossenen Pfade um ihre Abschlusswahrscheinlichkeit. Dies, zusammen mit dem Zufall, macht russisches Roulette unvoreingenommen.

So beantworten Sie Ihre letzten Fragen:

Gibt das russische Roulette ein unbefangenes Ergebnis?
- Ja
Ist russisches Roulette für ein unvoreingenommenes Ergebnis notwendig?
- Kommt darauf an, was du mit unvoreingenommen meinst. Wenn Sie mathematisch meinen, dann ja. Wenn Sie jedoch visuell meinen, dann nein. Sie müssen nur die maximale Pfadtiefe und die Grenzschwelle sehr sorgfältig auswählen. Dies kann sehr mühsam sein, da es sich von Szene zu Szene ändern kann.
Können Sie eine feste Wahrscheinlichkeit (Cut-Off) verwenden und dann die "verlorene" Energie neu verteilen? Ist das unvoreingenommen?
- Wenn Sie eine feste Wahrscheinlichkeit verwenden, fügen Sie eine Verzerrung hinzu. Indem Sie die "verlorene" Energie umverteilen, reduzieren Sie die Verzerrung, aber sie ist immer noch mathematisch verzerrt. Um völlig unvoreingenommen zu sein, muss es zufällig sein.
Wenn die Energie, die durch das Beenden eines Strahls verloren gehen würde, ohne seine Energie neu zu verteilen, irgendwann ohnehin verloren geht (da die Strahlen, auf die es neu verteilt wird, auch irgendwann beendet werden), wie verbessert dies die Situation?
- Russisches Roulette stoppt nur das Hüpfen. Die Probe wird nicht vollständig entfernt. Außerdem wird die "verlorene" Energie in den Bounces bis zur Beendigung berücksichtigt. Die einzige Möglichkeit, dass die Energie „irgendwann sowieso verloren geht“, wäre ein komplett schwarzer Raum.

Letztendlich ist Russisches Roulette ein sehr einfacher Algorithmus, der nur sehr wenig zusätzliche Rechenressourcen benötigt. Im Gegenzug kann eine große Menge an Rechenressourcen eingespart werden. Daher sehe ich keinen Grund, es nicht zu benutzen.

RichieSams
quelle

Ehrlich gesagt bin ich mir da nicht ganz sicher to be completely unbiased it must be random. Ich denke, Sie können immer noch mathematisch einwandfreie Ergebnisse erzielen, wenn Sie eine Teilgewichtung der Stichproben verwenden, anstatt den binären Durchgang / Abfall, den das russische Roulette auferlegt. Es ist nur so, dass das Roulette schneller konvergiert, weil es eine Stichprobe von perfekter Wichtigkeit ausführt.

v.oddou

9

Die russische Roulette-Technik selbst ist eine Möglichkeit, Pfade zu beenden, ohne systemische Vorurteile einzuführen. Das Prinzip ist ziemlich einfach: Wenn Sie an einem bestimmten Scheitelpunkt eine 10% ige Chance haben, die Energie willkürlich durch 0 zu ersetzen, und wenn Sie dies unendlich oft tun, werden Sie 10% weniger Energie sehen. Der Energieschub gleicht das nur aus. Wenn Sie den Energieverlust aufgrund einer Pfadbeendigung nicht kompensieren würden, wäre das russische Roulette voreingenommen, aber die gesamte Technik ist eine nützliche Methode zur Vermeidung von Voreingenommenheit.

Wenn ich ein Gegner wäre, der nachweisen möchte, dass die Technik "Pfade beenden, deren Beitrag weniger als ein kleiner fester Wert ist" voreingenommen ist, würde ich eine Szene mit Lichtern konstruieren, die so dunkel sind, dass die beitragenden Pfade immer sind weniger als dieser Wert sind. Vielleicht simuliere ich eine Kamera mit schlechten Lichtverhältnissen.

Sie können den festen Wert jedoch jederzeit als einstellbaren Parameter für den Benutzer verfügbar machen, damit er ihn bei schlechten Lichtverhältnissen noch weiter ablegen kann. Lassen Sie uns dieses Beispiel für eine Minute ignorieren.

Was passiert, wenn ich ein Objekt betrachte, das von vielen sehr energiearmen Pfaden beleuchtet wird, die von einem Parabolreflektor gesammelt werden ? Niedrige Energiebahnen nicht notwendigerweise springen wahllos auf eine Weise umher, die Sie völlig vernachlässigen können. Ähnliches gilt beispielsweise für das Abschneiden von Pfaden nach einer festgelegten Anzahl von Bounces: Sie können eine Szene mit einem Pfad erstellen, der von einer Reihe von 20 Spiegeln abprallt, bevor Sie auf ein Objekt treffen.

Eine andere Sichtweise: Wenn Sie den Beitrag eines Pfades auf 0 setzen, nachdem er unter ein festes Epsilon gefallen ist, wie korrigieren Sie diesen Energieverlust? Sie reduzieren nicht einfach die Gesamtenergie um einen Bruchteil. Sie wissen nichts darüber, wie viel Energie Sie vernachlässigen, weil Sie an einer Beitragsschwelle abschneiden, bevor Sie den anderen Faktor kennen: die einfallende Energie.

John Calsbeek
quelle

8

Um nur einige der anderen Antworten zu erläutern, ist der Beweis, dass russisches Roulette kein falsches Ergebnis liefert, sehr einfach.

Angenommen, Sie haben eine Zufallsvariable $F$ Das ist die Summe mehrerer Begriffe:

F = F_{1} + \dots + F_{N}

$F = F_1 + \cdots + F_N$

Ersetzen Sie jeden Begriff durch:

F_{ich}^{'} = {\begin{cases} \frac{1}{p_{ich}} F_{ich} & mit wahrscheinlichkeit p_{ich} \\ 0 & Andernfalls \end{cases}

$F'_i = \left\{ \begin{array}{ll} \frac{1}{p_i} F_i & \hbox{with probability } p_i \\ 0 & \hbox{otherwise} \end{array} \right.$

Dann:

E [F_{ich}^{'}] = p_{ich} \times \frac{1}{p_{ich}} E [F_{ich}] + (1 - p_{ich}) \times 0 = E [F_{ich}]

$E[F'_i] = p_i \times \frac{1}{p_i}E[F_i] + (1-p_i) \times 0 = E[F_i]$

Beachten Sie, dass es keine Rolle spielt, für welche Wahrscheinlichkeiten Sie sich entscheiden $p_i$ . Der erwartete Wert der Terme und damit der erwartete Wert von $F$ , ist dasselbe.

Pseudonym
quelle

Ist russisches Roulette wirklich die Antwort?

Antworten: