Генерация псевдослучайных чисел в шейдерах

В довольно большом числе различных графических алгоритмов возникает необходимость в использовании генератора псевдослучайных чисел (RNG, random number generator). К сожалению в GL|SL нет встроенного подобного генератора, поэтому его приходится реализовывать самому. И довольно часто встречается вариант, использующий для этого функции sin и cos с высокой частотой.

Подобные варианты не так и просты и, что самое важное, используют в работе трансцендентные функции. Эти функции в GPU реализуются в специальных ядрах (SFU в терминологии NVidia), который сильно меньше чем обычных вычислительных ядер.

Одним из вариантов генерации псевдослучайных числе является линейно-конгруэнтный генератор (LCG). Он берет на вход некоторое стартовое число (seed) и просто умножает его на достаточно большое число. Полученное значение возвращается как псевдослучайное число и используется в качестве стартового значения для генерации следующего псевдослучайного числа.

uint lcg ( inout uint state ) 
{
    uint result   = state * 747796405u;

    state = result;

    return result;
}

Этот метод дает очень хорошее случайное распределение для старших битов, но вот с младшими битами все гораздо хуже - они обычно следуют довольно простому и заметному шаблону. Можно несколько улучшить распределение младших битов добавив к умножению еще и сложение.

uint lcg ( inout uint state ) 
{
    uint result   = state * 747796405u + 2891336453u;

    state = result;

    return result;
}

Тем не менее проблема с младшими битами все равно остается и в работе, ссылка на которую приводится в конце, предлагается довольно простой способ улучшения распределения младших битов - мы смешиваем их со старшими битами при помощи побитового XOR, как показано ниже.

uint lcg_xs_24 ( inout uint state ) 
{
    uint result        = state * 747796405u + 2891336453u;
    uint hashed_result = result ^ (result >> 14);

    state = hashed_result;

    return hashed_result >> 8;
}

В результате получается генератор псевдослучайных чисел, который очень прост, использует стандартные арифметические и побитовые операции и обладает хорошими статистическими свойствами. Кроме того, показано, что он фактически дает просто перестановку всех 32-битовых целых чисел. Но на практике чаще всего нам нужны не целые случайные числа, а случайные числа с плавающей точкой из диапазона [0,1).

У стандартных 32-битовых чисел с плавающей точкой (float) есть один знаковый бит, 8 бит экспоненты и 23 бита мантиссы. Наибольшее целое число, которое можно точно представить в виде float это \( 2^{24} \), т.е. 16,777,216. Поэтому есть взять старшие 24 бита из целого псевдослучайного числа и поделить их на \( 2^{24} \), то мы получим псевдослучайное число с плавающей точкой из диапазона [0,1).

float random ( inout uint state )
{
    const float invMaxInt = 1.0 / 16777216.0;

    uint result = lcg_xs_24 ( state );
    
    return float ( result ) * invMaxInt;
}

Давайте теперь проверим получившийся генератор в деле. Для этого мы в качестве стартового числа для каждого фрагмента будем брать порядковый номер фрагмента в окне при помощи следующей функции:

uint    getSeed ()
{
    return uint ( gl_FragCoord.x ) + uint ( gl_FragCoord.y ) * uint ( width );
}

На следующем рисунке приводится получающееся при этом изображение. Обратите внимание, что со случайностью здесь все очень плохо - есть хорошо видимый паттерн.

Рис 1. Первое случайное значение

Теперь давайте изобразим не первое получаемое число, а второе. Видно что сейчас все в порядке и мы имеем хорошие псевдослучайные числа.

Рис 2. Второе случайное значение

В статье предлагается чуть другой способ получения стартового числа - мы делаем несколько итераций генератора, используя при этом другие коэффициенты.

uint genSeed ()
{
    uint seed = uint ( gl_FragCoord.x ) + uint ( gl_FragCoord.y ) * uint ( width );

        // several iterations can be run to further decorrelate threads
    for ( int i = 0; i < 3; i ++ )
    {
        seed = seed * 2654435761u + 1692572869u;
        seed = seed ^ (seed >> 18);
    }

    return seed;
}

Рис. 3. Более сложная схема расчета стартового значения

Building a Fast, SIMD/GPU-friendly Random Number Generator For Fun And Profit