Качественная целочисленная шумовая функция / Общее / Форум / Программирование игр / GameDev.ru

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

Более фрмально: ищется функция \(\mathrm{uint32} \mapsto \mathrm{uint32}\), для которой последовательность \(f(0),\, f(1), f(2), f(3), f(4), \dots\) выглядит как белый шум.

Основные цели: генерация текстур и звука, ну и всякая мелочёвка.
Требования: сносные статистические характеристики, отсутствие затайленности, скорость, компактность, лёгкость обобщения на n-мерную (\(\mathrm{uint32}^n \mapsto \mathrm{uint32}\)).

Кандидаты:
1. Переделать функцию из libnoise:

double IntegerNoise (int n)
{
  n = (n >> 13) ^ n;
  int nn = (n * (n * n * 60493 + 19990303) + 1376312589) & 0x7fffffff;
  return 1.0 - ((double)nn / 1073741824.0);
}

Даже отвлекаясь от int вместо uint32_t и знакового целочисленного переполнения, ведущего к undefined bevavior, всё равно не очень вдохновляюще. Вроде смутно вспоминается, что видел к ней какие-то претензии.

2. n-й член последовательности какого-либо генератора случайных чисел (LCG, PCG). O(log(n)) не радует, хочется константного времени.

3. Применить однократно шаг, например, LCG ко входу (return A*x+B;). Отстой, как легко видеть.

4. Применить несколькократный шаг, например, LCG ко входу. Тоже отстой.

5. Взять какой-нибудь CRC-подобный хеш. Вроде тоже не особо здраво.

6. PrecomputedArray[x%size]. Его надо ещё отдельно предпросчитывать; и тайлится.

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

Причём я особо не приглядывался, и если готовых ответов в интернете не находится, то можно функции поисследовать прямо в этой теме.

Текущий лидер:

uint32_t noise_uint32(uint32_t n)
{
    uint64_t state=n;
    state=state*state;
    state=state*6364136223846793005ULL+1442695040888963407ULL;
    uint32_t xorshifted=uint32_t(((state>>18u)^state)>>27u);
    uint32_t rot=uint32_t(state>>59u);
    return (xorshifted>>rot)|(xorshifted<<((-rot)&31));
}

Zab
Постоялец

#1
23:53, 1 июля 2016

см. Кнут Искусство программирования том 2.

kvakvs
Постоялец

#2
0:57, 2 июля 2016

xorshift? Реализуется очень просто, существуют множество вореций реализации.
https://en.wikipedia.org/wiki/Xorshift
Это псевдослучайный генератор с состоянием в виде одного целого числа. Содержимое его скачет по всему диапазону, не 1, 2, 3....

Если надо рандом где на входе идут последовательные числа 1...N, погляди на всякие алгоритмы хеширования, начиная с MD5 и вперёд к звёздам. Вообще определение хэш-функции - это такая функция, в которой при минимальном изменении входных данных получается максимальный эффект на все биты результата. Ну то есть нечто шумоподобное.

ArchiDevil
Постоялец

#3
1:44, 2 июля 2016

http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine
https://ru.wikipedia.org/wiki/Вихрь_Мерсенна

Не благодари.

}:+()___ [Smile]
Постоялец

#4
3:33, 2 июля 2016

FordPerfect
> 5. Взять какой-нибудь CRC-подобный хеш. Вроде тоже не особо здраво.
Я пробовал, получилась фигня.

Попробуй к индексу применить одну итерацию PCG, у него функция перемешивания вывода неплохая.

FordPerfect
Постоялец

#5
12:12, 2 июля 2016

Zab
А подробнее можно пальцем ткнуть?
При беглом осмотре - там сплошняком stateful rng.
Что с ними делать? Очевидных идей 2: n-й член последовательности (мой п. 2) - не радует O(log(n)) времени работы (~20 умножений на одно несчастное значение?!); и применение трансформации (мои пп. 3,4) к аргументу функции - не радует отстойным качеством для большинства rng.

kvakvs
См. комментарии выше о stateful rng. Сама по себе трансформация xorshift - не вдохновляет.
Комментарий о "какой-нибудь хеш-функции" весьма расплывчат. Интересно, какую именно. CRC похоже что отстой же (вон }:+()___ [Smile], вроде, пробовал), а MD5 - довольно тяжеловесная. А так - да, хеш.

ArchiDevil
К Mersenne Twister несколько дополнительных претензий, кроме озвученных выше.

}:+()___ [Smile]
>Попробуй к индексу применить одну итерацию PCG, у него функция перемешивания вывода неплохая.
Сама по себе итерация PCG - это чистый LCG, перемешивание используется только для вывода.
Ты подразумеваешь что-то вроде

uint32_t IntNoisePCG(uint32_t n)
{
    uint64_t state=n;
    state=state*6364136223846793005ULL+1442695040888963407ULL;
    uint32_t xorshifted=uint32_t(((state>>18u)^state)>>27u);
    uint32_t rot=uint32_t(state>>59u);
    return (xorshifted>>rot)|(xorshifted<<((-rot)&31));
}

?
Можно взглянуть.

FordPerfect
Постоялец

#6
12:51, 2 июля 2016

Сделал тут такой незатейливый тест:

+ Показать

− Скрыть

// This software is in the public domain. Where that dedication is not
// recognized, you are granted a perpetual, irrevocable license to copy
// and modify this file as you see fit. 

#include <cstdio>
#include <cstdint>

// IntegerNoise from libnoise.
// WARNING: contains undefined behavior.
uint32_t f1(uint32_t n)
{
  int32_t m=int32_t(n);
  m = (m >> 13) ^ m;
  int32_t nn = (m * (m * m * 60493 + 19990303) + 1376312589) & 0x7fffffff;
  return uint32_t(nn);
}

// Modified IntegerNoise from libnoise.
uint32_t f2(uint32_t n)
{
  n = (n >> 13) ^ n;
  uint32_t nn = (n * (n * n * 60493 + 19990303) + 1376312589);
  return nn;
}

// 1 iteration of LCG (from Borland rng).
uint32_t f3(uint32_t n)
{
  n=n*1103515245+12345;
  return n;
}

// 5 iterations of LCG (from Borland rng).
uint32_t f4(uint32_t n)
{
  for(uint32_t i=0;i<5;++i)
    n=n*1103515245+12345;
  return n;
}

// 1 iteration of xorshift128.
uint32_t f5(uint32_t n)
{
  uint32_t x = n, y = 0, z = 0, w = 0;

    uint32_t t = x;
    t ^= t << 11;
    t ^= t >> 8;
    x = y; y = z; z = w;
    w ^= w >> 19;
    w ^= t;
    return w;
}

// 5 iterations of xorshift128.
uint32_t f6(uint32_t n)
{
  uint32_t x = n, y = 0, z = 0, w = 0;

  for(uint32_t i=0;i<5;++i)
  {
    uint32_t t = x;
    t ^= t << 11;
    t ^= t >> 8;
    x = y; y = z; z = w;
    w ^= w >> 19;
    w ^= t;
  }
    return w;
}

// 1 iteration of PCG (default values of multiplier & increment),
// followed by PCG scrambling.
uint32_t f7(uint32_t n)
{
    uint64_t state=n;
    state=state*6364136223846793005ULL+1442695040888963407ULL;
    uint32_t xorshifted=uint32_t(((state>>18u)^state)>>27u);
    uint32_t rot=uint32_t(state>>59u);
    return (xorshifted>>rot)|(xorshifted<<((-rot)&31));
}

int main()
{
  const uint32_t w=128;

  uint32_t (*f)(uint32_t)=f7;

  FILE *image=fopen("image.pgm","wb");
  fprintf(image,"P5 %d %d\n255 ",int(4*w),int(w));
  for(uint32_t y=0;y<w;++y)
    for(uint32_t x=0;x<4*w;++x)
      fprintf(image,"%c",int(f(y*w+(x%w))>>((x/w)*8)));
  fclose(image);
  return 0;
}

Тест заполняет текстуру 128x128 значениями NoiseUint32(128*y+x). Точнее, 4 текстуры - младшие 8 бит, биты 8..15, биты 16..24, старшие 8 бит.

Резултаты:

+ libnoise

+ libnoise, модификация с использованием uint32_t

Видим, что версия }:+()___ [Smile] (если я его правильно понял) на глаз выглядит лучше всего, но сдаётся мне, там всё-равно диагональные полосы видны.

kvakvs
Постоялец

#7
13:10, 2 июля 2016

xorshift это стейтфул генератор, ты ему подавал 1,2,3... на вход, это неверно :) Надо подавать результат предыдущего вызова и следующий будет случайнее чем сейчас. Ну потому что это не функция шума, а именно псевдослучайный генератор.

А по хэшам это по виду именно то, что тебе надо. Гуглируй список алгоритмов хэщей. Вон либнойс взял и пользуйся :)

Zab
Постоялец

#8
15:54, 2 июля 2016

FordPerfect
> А подробнее можно пальцем ткнуть?
Подробно там и есть. Половина тома посвящена генераторам, больше 200 страниц. Все не просто и наивные генераторы как правило очень плохие. Из того, что ты не знаешь какие будут значения, вовсе не значит что они случайные. А если они и признаны случайными для одного применения, будут не случайными для другого. У разных потребителей разные требования к качеству.

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

FordPerfect
Постоялец

#9
16:11, 2 июля 2016

Накодил вот такое:

uint32_t f8(uint32_t n)
{
    uint64_t state=n;
    state=state*state;
    state=state*6364136223846793005ULL+1442695040888963407ULL;
    uint32_t xorshifted=uint32_t(((state>>18u)^state)>>27u);
    uint32_t rot=uint32_t(state>>59u);
    return (xorshifted>>rot)|(xorshifted<<((-rot)&31));
}

На глаз вроде выглядит нормально.
Его бы на каких-нибудь специальных тестах прогнать.
У кого-то есть под рукой рабочий TestU01?

Имбирная Ведьмочка
Постоялец

#10
18:21, 2 июля 2016

FordPerfect
> + libnoise, модификация с использованием uint32_t
Рекомендую вместо одного генератора на 32 бита взять 4 таких, каждый со своим семенем, и собирать верхние 8 бит. У линейных, как правило, чем правее цифра, тем меньше период (что и видно на текстурах).
FordPerfect
> У кого-то есть под рукой рабочий TestU01?
Кстати, зачем тебе нужен этот шум? В зависимости от назначения там свои требования будут. Если это текстура, то там достаточно, чтобы выглядело ровно, а с тонкостями можно и не заморачиваться.

FordPerfect
> Основные цели: генерация текстур и звука
А, ну вот.
У текстуры главное, чтобы приятно глазу было. Для звука хорошим критерием будет автокоррелляция - чем равномернее распределение по частотам, тем шум ближе к белому.
Теоретически, можно пойти от обратного - заполнить комплексный вектор одинаковыми амплитудами и средней случайности фазами, а затем сделать обратное FFT, правда, скорость будет не очень, да и диапазон у результата не гарантируется.

И 32 бита для обоих случаев - это оверкилл. Для звука очень хорошего качества достаточно 24 бит, а для HDR-текстуры - 16 бит/канал. Разные каналы в любом случае придётся генерировать раздельно, разве что если какой-нибудь убер-хеш не задействован.

FordPerfect
Постоялец

#11
19:25, 2 июля 2016

На всякий случай:

Классический stateful rng здесь не ищется.
Потому что задача "нужен stateful rng для gamedev"- что её решать, можно взять PCG и не париться.

Но stateful rng - последовательный, что не всегда удобно. Иногда хочется чистой функции "индекс - значение" (ну например заполняем мы текстуру самплингом value noise, причём, например, координаты замеров не эквидистантны: tex(u,v)=SampleNoise(sin(u),cos(v))).

И хочется найти шумовую функцию, которая решает эту задачу примерно так же хорошо, как PCG - задачу "нужен stateful rng для gamedev".
Чтобы
>дальше копипастить из этой темы, не заморачиваясь переизобретением по каждому поводу

Ну и хочется качественное решение - общее, быстрое.

Ограничения на ровном месте не вдохновляют.
Задачу по возможности хочется возложить не на пользователя, а на составителя функции UintNoise.
Условно говоря: если пользователю нужно помнить, что нужно говорить rnd()>>24, а не rnd()&255, то ваша rnd() - отстой. Особенно - если можно без потерь сделать обще.

Хочется этой теме найти достаточно хорошую функцию. И дальше пользоваться.

Mr F
Постоялец

#12
19:59, 2 июля 2016

https://www.shadertoy.com/view/MsV3z3 оч дешёвый и вроде паттернов никаких не раглядел

}:+()___ [Smile]
Постоялец

#13
21:12, 2 июля 2016

FordPerfect
> Видим, что версия }:+()___ [Smile] (если я его правильно понял) на глаз выглядит лучше всего, но сдаётся мне, там всё-равно диагональные полосы видны.
Да, я именно это имел в виду. Попробуй заменить итерацию LCG в начале на полином по типу libnoise, должно стать лучше.

susageP
Постоялец

#14
2:36, 3 июля 2016

FordPerfect

Мне как то требовалось такое.
Нужно было генерить случайные числа(вектора, цвета, матрицы) для 1D,2D,3D,4D карт причем от позиции, а не последовательно. Не хранить все карты в памяти а от позиции восстановить.
В итоги получилась хэш.
Причем подбирал так что:
1) на изменение 1бита вероятность изменение любого бита на выходе 0.5
2) корреляция между измененным битом на входе и битами на выходе ->0
3) корреляция между выходными битами при изменение 1бита на входе->0

Использует SSE на выходе 128 бит. трактовать можно как 16 char, или 4 uint32, 4 int32 ...

Если есть желание пощупать могу выложить код.