Method AliasTable

Source/Falcor/Utils/Sampling/AliasTable.cpp:48–139

This builds an alias table via the O(N) algorithm from Vose 1991, "A linear algorithm for generating random numbers with a given distribution," IEEE Transactions on Software Engineering 17(9), 972-975. Basic idea: creating each alias table entry combines one overweighted sample and one underweighted sample into one alias table entry plus a residual sample (the overweighted sample minus some of i

// have 2 valid entries to combine.  By definition, in these corner cases, all remaining unhandled samples
// actually have the average weight (within numerical precision limits)
AliasTable::AliasTable(ref<Device> pDevice, std::vector<float> weights, std::mt19937& rng) : mCount((uint32_t)weights.size())
{
    // Use >= since we reserve 0xFFFFFFFFu as an invalid flag marker during construction.
    if (weights.size() >= std::numeric_limits<uint32_t>::max())
        FALCOR_THROW("Too many entries for alias table.");

    std::uniform_int_distribution<uint32_t> rngDist;

    mpWeights =
        pDevice->createStructuredBuffer(sizeof(float), mCount, ResourceBindFlags::ShaderResource, MemoryType::DeviceLocal, weights.data());

    // Our working set / intermediate buffers (underweight & overweight); initialize to "invalid"
    std::vector<uint32_t> lowIdx(mCount, 0xFFFFFFFFu);
    std::vector<uint32_t> highIdx(mCount, 0xFFFFFFFFu);

    // Sum element weights, use double to minimize precision issues
    mWeightSum = 0.0;
    for (float f : weights)
        mWeightSum += f;

    // Find the average weight
    float avgWeight = float(mWeightSum / double(mCount));

    // Initialize working set. Inset inputs into our lists of above-average or below-average weight elements.
    int lowCount = 0;
    int highCount = 0;
    for (uint32_t i = 0; i < mCount; ++i)
    {
        if (weights[i] < avgWeight)
            lowIdx[lowCount++] = i;
        else
            highIdx[highCount++] = i;
    }

    // Create alias table entries by merging above- and below-average samples
    std::vector<AliasTable::Item> items(mCount);
    for (uint32_t i = 0; i < mCount; ++i)
    {
        // Usual case:  We have an above-average and below-average sample we can combine into one alias table entry
        if ((lowIdx[i] != 0xFFFFFFFFu) && (highIdx[i] != 0xFFFFFFFFu))
        {
            // Create an alias table tuple:
            items[i] = {weights[lowIdx[i]] / avgWeight, highIdx[i], lowIdx[i], 0};

            // We've removed some weight from element highIdx[i]; update it's weight, then re-enter it
            // on the end of either the above-average or below-average lists.
            float updatedWeight = (weights[lowIdx[i]] + weights[highIdx[i]]) - avgWeight;
            weights[highIdx[i]] = updatedWeight;
            if (updatedWeight < avgWeight)
                lowIdx[lowCount++] = highIdx[i];
            else
                highIdx[highCount++] = highIdx[i];
        }

        // The next two cases can only occur towards the end of table creation, because either:
        //    (a) all the remaining possible alias table entries have weight *exactly* equal to avgWeight,
        //        which means these alias table entries only have one input item that is selected
        //        with 100% probability