Chapter 23 Figure 23-4 updateReservoir function

[jeremyong]

@acmarrs-nvidia Hey Adam! In Chapter 23, Figure 23-4, the code as listed looks like the following:

function updateReservoir(Reservoir result, Reservoir input)
    result.totalWeight+= input.weight;
    result.M++;
    if rand() < (input.weight/result.totalWeight) then
        result.sample = input.sample;
        result.sampleTargetPdf = input.sampleTargetPdf;
    return result;

function mergeReservoirs(Reservoir r1, Reservoir r2)
    Reservoir merged;
    updateReservoir(merged, r1);
    updateReservoir(merged, r2);
    merged.M = r1.M + r2.M;
    return merged;

As written, this code works but I believe updateReservoir has a bug in it, specifically related to the update of result.M (which denotes the sample count). I believe the correct update should be result.M += input.M;. Note that the listing as a whole works provided the user only uses mergeReservoirs because merged.M is overwritten with the correct result afterwards. A refactored code listing might look like:

function updateReservoir(Reservoir result, Reservoir input)
    result.totalWeight+= input.weight;
    result.M += input.M;
    if rand() < (input.weight/result.totalWeight) then
        result.sample = input.sample;
        result.sampleTargetPdf = input.sampleTargetPdf;
    return result;

function mergeReservoirs(Reservoir r1, Reservoir r2)
    Reservoir merged = r1;
    updateReservoir(merged, r2);
    return merged;

Note: the only distinction between mergeReservoirs and updateReservoir as implemented above is that the former leaves its arguments r1 and r2 unchanged, while updateReservoir mutates the first argument.

[acmarrs-nvidia]

Hi @jeremyong - thanks for your message! I've pointed the authors of Chapter 23 here so they can take a look at your question / bug report. They'll either respond here directly or I'll post for them once they've had a chance to review.

[chris-wyman]

@jeremyong Yes, the code as written should work, but you're correct that moving the summation of M values into updateReservoir may be clearer. (We have code doing it both ways internally, I think this variant derives from code that assumes updateReservoir is for adding a single light while mergeReservoir is to combine groups of lights from multiple reservoirs.)

To avoid some hard-to-explain and hard-to-debug problems, I suggest leaving mergeReservoirs() to have two calls to updateReservoir() rather than copying the reservoir, as in your revision. Though I don't think it should really matter in this code.

(The simplistic, TL;DR reason for this is reservoirs may have different representations when actively in use v.s. just loaded from memory. Intermediate reservoirs reused, say, between frames may compress some data to save space while the active, in-register variants probably store uncompressed data plus temporary additional components. Trying to merge one reservoir from each state is extremely easy to do and, speaking from experience, will cause very hard-to-debug problems. Forcing all updates to new or existing reservoirs to go through a single updateReservoir function means the only code that needs to correctly handle both forms of reservoir data is the code inside updateReservoir() that touches members of input. Any result reservoirs from updateReservoir are then guaranteed to be the in-register variant. This approach is used in RTXDI, though I agree it feels awkward.)

[jeremyong]

Thanks @chris-wyman, I wonder than if it might be better to have a struct like ReservoirSample with an implicit sample count of 1, and then just rely on overload resolution so that updateReservoir can do the appropriate thing depending on whether you're merging another reservoir or incorporating a single sample.