La roulette russe est-elle vraiment la réponse?

21

J'ai vu que dans certaines implémentations de Path Tracing, une approche appelée Russian Roulette est utilisée pour éliminer certains des chemins et partager leur contribution entre les autres chemins.

Je comprends que plutôt que de suivre un chemin jusqu'à ce qu'il tombe en dessous d'une certaine valeur seuil de contribution, puis de l'abandonner, un seuil différent est utilisé et les chemins dont la contribution est inférieure à ce seuil ne se terminent qu'avec une faible probabilité. Les autres trajets voient leur contribution augmentée d'un montant correspondant au partage de l'énergie perdue du trajet terminé. Il n'est pas clair pour moi s'il s'agit de corriger un biais introduit par la technique, ou si toute la technique est elle-même nécessaire pour éviter le biais.

La roulette russe donne-t-elle un résultat impartial?
La roulette russe est-elle nécessaire pour un résultat impartial?

Autrement dit, est-ce que l'utilisation d'un seuil minuscule et la fin d'un chemin au moment où il descend en dessous de ce seuil donneraient un résultat plus biaisé ou moins biaisé?

Étant donné un nombre arbitrairement élevé d'échantillons, les deux approches convergeraient-elles vers une image résultante non biaisée?

Je cherche à comprendre la raison sous-jacente de l'utilisation de l'approche de la roulette russe. Y a-t-il une différence significative de vitesse ou de qualité?

Je comprends que l'énergie est redistribuée entre les autres rayons afin de conserver l'énergie totale. Cependant, cette redistribution ne pourrait-elle pas encore être effectuée si le rayon était interrompu en tombant en dessous d'un seuil fixe, plutôt que d'avoir une durée de vie déterminée au hasard après avoir atteint ce seuil?

Inversement, si l'énergie qui serait perdue en terminant un rayon sans redistribuer son énergie est finalement perdue de toute façon (comme les rayons auxquels elle est redistribuée sont également finalement arrêtés), comment cela améliore-t-il la situation?

monte-carlo pathtracing trichoplax
la source

26

Afin de comprendre la roulette russe, regardons un traceur de chemin vers l'arrière très basique:

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);
}

C'EST À DIRE. nous rebondissons autour de la scène, accumulant des atténuations de couleur et de lumière au fur et à mesure. Pour être complètement mathématiquement impartiaux, les rebonds doivent aller à l'infini. Mais ce n'est pas réaliste et, comme vous l'avez noté, pas visuellement nécessaire; pour la plupart des scènes, après un certain nombre de rebonds, disons 10, le montant de la contribution à la couleur finale est très très minime.

Ainsi, afin d'économiser les ressources informatiques, de nombreux traceurs de chemin ont une limite stricte au nombre de rebonds. Cela ajoute du parti pris.

Cela dit, il est difficile de choisir quelle devrait être cette limite. Certaines scènes ont fière allure après 2 rebonds; d'autres (disons avec transmission ou SSS) peuvent prendre jusqu'à 10 ou 20.

Si nous choisissons trop bas, l'image sera visiblement biaisée. Mais si nous choisissons trop haut, nous perdons de l'énergie et du temps de calcul.

Une façon de résoudre ce problème, comme vous l'avez noté, est de terminer le chemin après avoir atteint un certain seuil d'atténuation. Cela ajoute également des biais.

Le serrage après un seuil fonctionnera , mais encore une fois, comment choisissons-nous le seuil? Si nous choisissons trop grand, l'image sera visiblement biaisée, trop petite et nous gaspillons des ressources.

La roulette russe tente de résoudre ces problèmes de manière impartiale. Tout d'abord, voici le 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);
}

La roulette russe termine aléatoirement un chemin avec une probabilité inversement égale au débit. Ainsi, les chemins à faible débit qui ne contribueront pas beaucoup à la scène sont plus susceptibles d'être interrompus.

Si nous nous arrêtons là, nous sommes toujours biaisés. Nous «perdons» l'énergie du chemin que nous terminons au hasard. Pour le rendre non biaisé, nous augmentons l'énergie des chemins non terminés par leur probabilité d'être terminée. Ceci, en plus d'être aléatoire, rend la roulette russe impartiale.

Pour répondre à vos dernières questions:

La roulette russe donne-t-elle un résultat impartial?
- Oui
La roulette russe est-elle nécessaire pour un résultat impartial?
- Cela dépend de ce que vous entendez par impartial. Si vous voulez dire mathématiquement, alors oui. Cependant, si vous voulez dire visuellement, alors non. Il vous suffit de choisir très soigneusement la profondeur de trajectoire maximale et le seuil de coupure. Cela peut être très fastidieux car il peut changer d'une scène à l'autre.
Pouvez-vous utiliser une probabilité fixe (coupure), puis redistribuer l'énergie «perdue». Est-ce impartial?
- Si vous utilisez une probabilité fixe, vous ajoutez un biais. En redistribuant l'énergie «perdue», vous réduisez le biais, mais il est toujours biaisé mathématiquement. Pour être totalement impartial, il doit être aléatoire.
Si l'énergie qui serait perdue en terminant un rayon sans redistribuer son énergie est finalement perdue de toute façon (comme les rayons auxquels elle est redistribuée sont également finalement arrêtés), comment cela améliore-t-il la situation?
- La roulette russe arrête seulement le rebond. Il ne supprime pas complètement l'échantillon. De plus, l'énergie «perdue» est comptabilisée dans les rebonds jusqu'à la terminaison. Donc, la seule façon pour que l'énergie soit «finalement perdue de toute façon» serait d'avoir une pièce complètement noire.

En fin de compte, la roulette russe est un algorithme très simple qui utilise une très petite quantité de ressources informatiques supplémentaires. En échange, il peut économiser une grande quantité de ressources de calcul. Par conséquent, je ne vois pas vraiment de raison de ne pas l'utiliser.

RichieSams
la source

Honnêtement, je n'en suis pas complètement sûr to be completely unbiased it must be random. Je pense que vous pouvez toujours obtenir des résultats mathématiques corrects en utilisant le poids fractionné des échantillons, plutôt que le passage / baisse binaire que la roulette russe impose, c'est juste que la roulette convergera plus rapidement car elle opère un échantillonnage d'importance parfaite.

v.oddou

9

La technique de la roulette russe elle-même est un moyen de terminer les chemins sans introduire de biais systémique. Le principe est assez simple: si à un sommet particulier vous avez 10% de chances de remplacer arbitrairement l'énergie par 0, et si vous le faites un nombre infini de fois, vous verrez 10% d'énergie en moins. L'augmentation d'énergie compense simplement cela. Si vous n'avez pas compensé l'énergie perdue en raison de la terminaison du chemin, la roulette russe serait biaisée, mais toute la technique est une méthode utile pour éviter les biais.

Si j'étais un adversaire cherchant à prouver que la technique des "terminaisons de chemins dont la contribution est inférieure à une petite valeur fixe" est biaisée, je construirais une scène avec des lumières si faibles que les chemins contributifs sont toujours inférieurs à cette valeur. Peut-être que je simule un appareil photo à faible luminosité.

Mais bien sûr, vous pouvez toujours exposer la valeur fixe en tant que paramètre modifiable à l'utilisateur, afin qu'il puisse la réduire encore plus si sa scène se trouve être en basse lumière. Ignorons donc cet exemple pendant une minute.

Que se passe-t-il si je considère un objet qui est éclairé par un grand nombre de chemins à très basse énergie qui sont collectés par un réflecteur parabolique ? Les chemins à faible énergie ne rebondissent pas nécessairement sans discernement d'une manière que vous pouvez complètement négliger. De même, le raisonnement s'applique, par exemple, pour couper des chemins après un nombre fixe de rebonds: vous pouvez construire une scène avec un chemin qui rebondit sur une série de 20 miroirs avant de toucher un objet.

Une autre façon de voir les choses: si vous définissez la contribution d'un chemin à 0 après qu'il tombe en dessous d'un epsilon fixe, comment corrigez-vous cette perte d'énergie? Vous ne réduisez pas simplement l'énergie totale d'une fraction. Vous ne savez rien sur la quantité d'énergie que vous négligez, car vous coupez à un certain seuil de contribution avant de connaître l'autre facteur: l'énergie incidente.

John Calsbeek
la source

8

Juste pour développer certaines des autres réponses, la preuve que la roulette russe ne donne pas un résultat biaisé est très simple.

Supposons que vous ayez une variable aléatoire $F$ qui est la somme de plusieurs termes:

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

$F = F_1 + \cdots + F_N$

Remplacez chaque terme par:

F_{je}^{'} = {\begin{cases} \frac{1}{p_{je}} F_{je} & avec probabilité p_{je} \\ 0 & autrement \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.$

Alors:

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

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

Notez que peu importe les probabilités que vous choisissez $p_i$ . La valeur attendue des termes, et donc la valeur attendue de $F$ , est le même.

Pseudonyme
la source

La roulette russe est-elle vraiment la réponse?

Réponses: